1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

/**

* 暴力枚举法

* @param nums

* @param target

* @return

*/

public static int[] twoSum(int[] nums, int target) {

int lgn = nums.length;

for(int i = 0; i < lgn; i++){

for(int j = i + 1; j < lgn; j++){

if(nums[i] + nums[j] == target){

return new int[]{i, j};

}

}

}

return new int[0];

}

/**

* MAP 处理

* @param nums

* @param target

* @return

*/

public static int[] twoSum1(int[] nums, int target) {

Map
    
      map = new HashMap<>();
    

for (int i = 0; i < nums.length; i++) {

int complement = target - nums[i];

if (map.containsKey(complement)) {

return new int[] { complement, nums[i] };

}

map.put(nums[i], i);

}

return new int[0];

}

2. 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 0 -> 8原因：342 + 465 = 807

/**

* 链表相应位置依次相加，最后处理进位

* @param l1

* @param l2

* @return

*/

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode head = null;

ListNode curr = null;

while (l1 != null || l2 != null){

if(l1 != null && l2 != null){

ListNode node = new ListNode(l1.val + l2.val);

if(curr == null && head == null) head = node;

curr = initNode(curr, node);

}else{

curr = initNode(curr, new ListNode(l1 != null?l1.val:l2.val));

}

l1 = l1 != null?l1.next:null;

l2 = l2 != null?l2.next:null;

}

curr = head;

while (curr != null){

if(curr.val >= 10){

curr.val -= 10;

if(curr.next == null){

curr.next = new ListNode(1);

}else {

curr.next.val += 1;

}

}

curr = curr.next;

}

curr = null;

return head;

}

public ListNode initNode(ListNode curr, ListNode newNode){

if(curr != null){

curr.next = newNode;

}

curr = newNode;

return curr;

}

3. 寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]nums2 = [2]则中位数是 2.0

示例 2:

nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5

/**

* 使用两个排序数据组的归并过程

* 分别定义两个数组的遍历索引，每次对比提取相应数组的元素

* 不实际存储归并后的数据，

* 处理前半数元素即可

* @param nums1

* @param nums2

* @return

*/

public static double findMedianSortedArrays(int[] nums1, int[] nums2) {

int lgn1 = nums1.length;

int lgn2 = nums2.length;

int allLgn = lgn1 + lgn2;

int middleIndex = allLgn/2;

int middleLeft = 0,middleRight = 0;

int index1 = 0;

int index2 = 0;

int curr = 0;

for (int i = 0; i < middleIndex + 1; i++) {

if(index1 < lgn1 && index2 < lgn2) {

if (nums1[index1] > nums2[index2]) {

curr = nums2[index2];

index2++;

} else {

curr = nums1[index1];

index1++;

}

}else if(index1 < lgn1){

curr = nums1[index1];

index1++;

}else if(index2 < lgn2){

curr = nums2[index2];

index2++;

}

if(i == middleIndex - 1){

middleLeft = curr;

}

if(i == middleIndex){

middleRight = curr;

}

}

if(allLgn%2 == 0){

return (middleLeft + middleRight)/2.0;

}else {

return middleRight;

}

}

4. Z 字形变换

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

L   C   I   RE T O E S I I GE   D   H   N

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1:

输入: s = "LEETCODEISHIRING", numRows = 3输出: "LCIRETOESIIGEDHN"

示例 2:

输入: s = "LEETCODEISHIRING", numRows = 4输出: "LDREOEIIECIHNTSG"解释:L     D     RE   O E   I IE C   I H   NT     S     G

/**

* 定义目标行数个链表，如示例，每次中间间隔的 numRows - 2 个列表逐个填充一个值

* 便利给定的字符串，依次处理，直到末尾

* @param s

* @param numRows

* @return

*/

public static String convert(String s, int numRows) {

if(numRows == 1){

return s;

}

String result = "";

if(numRows == 2){

result = "";

for (int i = 0; i < s.length(); i = i + 2) {

result += s.charAt(i);

}

for (int i = 1; i < s.length(); i = i + 2) {

result += s.charAt(i);

}

return result;

}

int middleCount = numRows - 2;

List[] all = new LinkedList[numRows];

for (int i = 0; i < numRows; i++) {

all[i] = new LinkedList<>();

}

int sIndex = 0;

int step = 0;

while (sIndex < s.length()){

for (int i = 0; i < numRows; i++) {

if(sIndex == s.length()) break;

all[i].add(s.charAt(sIndex));

sIndex++;

}

for (int j = numRows - 2; j > 0 ; j--) {

if(sIndex == s.length()) break;

all[j].add(s.charAt(sIndex));

sIndex++;

}

step = step + middleCount;

}

for (int i = 0; i < numRows; i++) {

for (int j = 0; j < all[i].size(); j++) {

result += all[i].get(j);

}

}

return result;

}

5. 整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123输出: 321

示例 2:

输入: -123输出: -321

示例 3:

输入: 120输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2³¹,  2³¹ − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

/**

* 数据范围判断

* @param x

* @return

*/

public static int reverse(int x) {

double result = 0;

while (x != 0){

result = result * 10 + x%10;

if (result > Integer.MAX_VALUE) return 0;

if (result < Integer.MIN_VALUE) return 0;

x = x/10;

}

return (int) result;

}

6. 回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

 

/**

* 转化为字符串，一次便利，首末对称位置对比

* @param x

* @return

*/

public static boolean isPalindrome(int x) {

String s = String.valueOf(x);

int lgn = s.length();

for (int i = 0,j = lgn -1; i <= j; i++,j--){

if(s.charAt(i) == s.charAt(j)){

continue;

}else {

return false;

}

}

return true;

}

7. 盛最多水的容器

给定 n 个非负整数 a₁，a_2，...，a_n，每个数代表坐标中的一个点 (i, a_i) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, a_i) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

 

/**

* 枚举

* @param height

* @return

*/

public static int maxArea(int[] height) {

int area = 0, lgn = height.length;

if(lgn < 2) return 0;

for (int i = 0; i < lgn; i++) {

for (int i1 = i + 1; i1 < lgn; i1++) {

int tmpArea = (height[i]>height[i1]?height[i1]:height[i]) * (i1 - i);

if(tmpArea > area){

area = tmpArea;

}

}

}

return area;

}

/**

* 双指针

* @param height

* @return

*/

public static int maxArea2(int[] height) {

int area = 0, lgn = height.length;

if(lgn < 2) return 0;

for (int i = 0, j = lgn - 1; i < j; ) {

int tmpArea = (height[i]>height[j]?height[j]:height[i]) * Math.abs(j - i);

if(tmpArea > area){

area = tmpArea;

i++;//正方向前进一步，避免反方向遍历时，重复比较

}else {

j--;//反方向前进一步，避免正方向遍历时，重复比较

}

}

return area;

}

8. 整数转罗马数字

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值I             1V             5X             10L             50C             100D             500M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

 

public static String intToRoman(int num) {

if(num > 3999) return "";

if(num/1000 > 0){

return dealQianWei(num);

}else if(num/100 > 0){

return dealBaiWei(num);

}else if(num/10 > 0){

return dealShiWei(num);

}else {

return dealGeWei(num);

}

}

/**

* 千位

* @param num

* @return

*/

public static String dealQianWei(int num){

return countStr(num/1000, "M") + dealBaiWei(num%1000);

}

/**

* 百位

* @param num

* @return

*/

public static String dealBaiWei(int num){

int bc = num/100;

if(bc == 9) return "CM" + dealShiWei(num % 100);

if(bc == 4) return "CD" + dealShiWei(num % 100);

int fbc = num/500;

num = num%500;

return countStr(fbc, "D") + countStr(num/100, "C") + dealShiWei(num%100);

}

/**

* 十位

* @param num

* @return

*/

public static String dealShiWei(int num){

int tens = num/10;

if(tens == 9) return "XC" + dealGeWei(num % 10);

if(tens == 4) return "XL" + dealGeWei(num % 10);

int ftens = num/50;

num = num%50;

return countStr(ftens, "L") + countStr(num/10, "X") + dealGeWei(num%10);

}

/**

* 个位

* @param num

* @return

*/

public static String dealGeWei(int num){

if(num == 9) return "IX";

if(num == 4) return "IV";

if(num >= 5) return "V" + dealGeWei(num % 5);

return countStr(num, "I");

}

public static String countStr(int count, String num){

if(count == 0) return "";

String result = "";

for (int i = 0; i < count; i++) {

result += num;

}

return result;

}

9. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

注意：利用上面的两数值和

 

public static List
    
     
      > threeSum(int[] nums) {
     
    

if(nums == null || nums.length < 3) return new ArrayList();

Set
    
     
      > result = new HashSet<>();
     
    

List
    
      numList = new ArrayList();
    

for (int num : nums) {

numList.add(num);

}

for (Integer num : numList) {

List
    
      copy = new ArrayList();
    

copy.addAll(numList);

copy.remove(num);

List
    
      tmp = twoSum(copy, -num);
    

if(tmp.size()>0){

for (int[] ints : tmp) {

List
    
      list = new ArrayList(){
  {add(num);add(ints[0]);add(ints[1]);}};
    

Collections.sort(list);

result.add(list);

}

}

}

return new ArrayList(result);

}

public static List
    
      twoSum(List
     
       nums, int target) {
     
    

List
    
      result = new ArrayList();
    

Map
    
      map = new HashMap<>();
    

for (int i = 0; i < nums.size(); i++) {

int complement = target - nums.get(i);

if (map.containsKey(complement)) {

result.add(new int[] { complement, nums.get(i) });

}

map.put(nums.get(i), i);

}

return result;

}

10. 最接近的三数之和

给定一个包括 n 个整数的数组 nums和 一个目标值 target。找出 nums中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

public static int threeSumClosest(int[] nums, int target) {

int min = Integer.MAX_VALUE;

int ele1 = 0, ele2 = 0, ele3 = 0;

for (int i = 0; i < nums.length; i++) {

for (int i1 = 0; i1 < nums.length; i1++) {

if (i1 == i) continue;

for (int i2 = 0; i2 < nums.length; i2++) {

if (i2 == i1 || i2 == i) continue;

int sum = Math.abs(nums[i] + nums[i1] + nums[i2] - target);

if (sum < min) {

min = sum;

ele1 = nums[i];

ele2 = nums[i1];

ele3 = nums[i2];

}

}

}

}

return ele1 + ele2 + ele3;

}

11. 缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]输出: 3

示例 2:

输入: [3,4,-1,1]输出: 2

示例 3:

输入: [7,8,9,11,12]输出: 1

/**

* 数组操作

* @param nums

* @return

*/

public static int firstMissingPositive(int[] nums) {

int max = 0;

for (int i = 0; i < nums.length; i++) {

if(nums[i] < 0) continue;

if(nums[i] > max){

max = nums[i];

}

}

max = max == Integer.MAX_VALUE?max:max + 2;

for (int i = 1; i < max; i++) {

if(contains(nums, i)) continue;

return i;

}

return max + 1;

}

public static boolean contains(int[] nums, int ele){

for (int i = 0; i < nums.length; i++) {

if(nums[i] == ele) return true;

}

return false;

}

/**

* map操作

* @param nums

* @return

*/

public static int firstMissingPositive1(int[] nums) {

Map
    
      vs = new HashMap<>();
    

int max = 0;

for (int i = 0; i < nums.length; i++) {

if(nums[i] < 0) continue;

if(nums[i] > max){

max = nums[i];

}

vs.put(nums[i], i);

}

max = max == Integer.MAX_VALUE?max:max + 2;

for (int i = 1; i < max; i++) {

if(vs.get(i) != null) continue;

return i;

}

return max + 1;

}

12. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

 

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6

/**

* 分割

* @param height

* @return

*/

public static int trap(int[] height) {

//最大索引位置

int maxIndex = findMax(height);

int lsubMaxindex = maxIndex, rsubMaxIndex = maxIndex;

int area = 0;

//左边处理

while (lsubMaxindex > 0){

int tmpMax = lsubMaxindex;

lsubMaxindex = findMax(Arrays.copyOfRange(height, 0, tmpMax));

area += height[lsubMaxindex] * (tmpMax - lsubMaxindex - 1);

for (int i = lsubMaxindex + 1; i < tmpMax; i++) {

area -= height[i] * 1;

}

}

//右边处理

while (rsubMaxIndex < height.length - 1){

int tmpMax = rsubMaxIndex;

rsubMaxIndex = tmpMax + findMax(Arrays.copyOfRange(height, tmpMax + 1, height.length)) + 1;

area += height[rsubMaxIndex] * (rsubMaxIndex - tmpMax - 1);

for (int i = tmpMax + 1; i < rsubMaxIndex; i++) {

area -= height[i] * 1;

}

}

return area;

}

public static int findMax(int[] nums){

int max = 0, maxIndex = 0;

for (int i = 0; i < nums.length; i++) {

if(nums[i] > max){

max = nums[i];

maxIndex = i;

}

}

return maxIndex;

}

13. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3"输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"输出: "56088"

说明：

1. num1 和 num2 的长度小于110。
2. num1 和 num2 只包含数字 0-9。
3. num1 和 num2 均不以零开头，除非是数字 0 本身。
4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

 

public static String multiply(String num1, String num2) {

if(num1 == null || num2 == null || "".equals(num1) || "".equals(num2) || "0".equals(num1) || "0".equals(num2)) return String.valueOf(0);

int lgn1 = num1.length(), lgn2 = num2.length();

int[] result = new int[lgn1 + lgn2];

int resultIndex = result.length - 1;

for (int i = lgn1 - 1; i > -1 ; i--) {

int first = Integer.parseInt(String.valueOf(num1.charAt(i)));

int innerIndex = 0;

for (int j = lgn2 - 1; j > -1 ; j--) {

int second = Integer.parseInt(String.valueOf(num2.charAt(j)));

int plus = first * second;

result[resultIndex - innerIndex] += plus%10;

if(plus >= 10) {

result[resultIndex - innerIndex - 1] += plus / 10;

}

innerIndex++;

}

resultIndex--;

}

//处理进位

StringBuilder sb = new StringBuilder();

for (int i = result.length - 1; i >= 0; i--) {

if(result[i]>=10) {

result[i - 1] += result[i]/10;

result[i] %= 10;

}

}

//提取有效位

boolean start = false;

for (int i = 0; i < lgn1 + lgn2 ; i++) {

if(!start && result[i] != 0){

start = true;

}

if(start){

sb.append(result[i]);

}

}

return sb.toString();

}

14. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。   从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

 

/**

* 枚举遍历

* @param nums

* @return

*/

public static int jump(int[] nums) {

if(nums == null || nums.length == 1) return 0;

if(nums.length == 2) return 1;

int steps = Integer.MAX_VALUE/2;

int initStep = 1;

if(nums[0] >= nums.length - 1) return 1;

if(nums[0] == 0) return steps;

while (initStep <= nums[0]){

int subNeedStep = jump(Arrays.copyOfRange(nums, initStep, nums.length));

if(subNeedStep + 1 < steps){

steps = subNeedStep + 1;

}

initStep++;

}

return steps;

}

/**

* 每次选择 和下一跳（最大跳值）之和最远的=》递归处理

* @param nums

* @return

*/

public static int jump2(int[] nums) {

if(nums == null || nums.length == 1) return 0;

if(nums.length == 2) return 1;

int steps = Integer.MAX_VALUE/2;

int initStep = nums[0];

if(nums[0] >= nums.length - 1) return 1;

if(nums[0] == 0) return steps;

int maxSum = 0;

int fromStep = 1;

while (initStep > 0){

if(initStep + nums[initStep] > maxSum){

fromStep = initStep;

maxSum = initStep + nums[initStep];

}

initStep--;

}

steps = 1 + jump2(Arrays.copyOfRange(nums, fromStep, nums.length));

return steps;

}

15. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]输出:[  [1,2,3],  [1,3,2],  [2,1,3],  [2,3,1],  [3,1,2],  [3,2,1]]

/**

* 递归处理

* @param nums

* @return

*/

public static List
    
     
      > permute(int[] nums) {
     
    

List
    
     
      > result = new ArrayList();
     
    

if(nums.length == 1) {

result.add(new ArrayList(){
  {add(nums[0]);}});

return result;

}

for (int num : nums) {

int[] tmp = new int[nums.length - 1];

int index = 0;

for (int i = 0; i < nums.length; i++) {

if(num == nums[i]) continue;

tmp[index] = nums[i];

index++;

}

List
    
     
      > sub = permute(tmp);
     
    

sub.stream().forEach(item->item.add(num));

result.addAll(sub);

}

return result;

}

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]输出:[  [1,1,2],  [1,2,1],  [2,1,1]]

/**

* 递归处理

* Set 处理重复

* @param nums

* @return

*/

public static List
    
     
      > permuteUnique(int[] nums) {
     
    

List
    
     
      > result = new ArrayList();
     
    

if(nums.length == 1) {

result.add(new ArrayList(){
  {add(nums[0]);}});

return result;

}

for (int num : nums) {

int[] tmp = new int[nums.length - 1];

int index = 0;

for (int i = 0; i < nums.length; i++) {

if(num == nums[i] && index == i) continue;

tmp[index] = nums[i];

index++;

}

List
    
     
      > sub = permuteUnique(tmp);
     
    

sub.stream().forEach(item->item.add(num));

result.addAll(sub);

}

Set
    
     
      > sets = new HashSet();
     
    

result.stream().forEach(item->sets.add(item));

return new ArrayList(sets);

}

16. 旋转图像

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = [  [1,2,3],  [4,5,6],  [7,8,9]],原地旋转输入矩阵，使其变为:[  [7,4,1],  [8,5,2],  [9,6,3]]

public static void rotate(int[][] matrix) {

int step = matrix.length;

int[][] tmp = new int[step][step];

for (int i = 0; i < step; i++) {

for (int j = 0; j < step; j++) {

tmp[i][j] = matrix[step - j - 1][i];

}

}

for (int i = 0; i < step; i++) {

for (int j = 0; j < step; j++) {

matrix[i][j] = tmp[i][j];

}

}

}

17. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],输出:[  ["ate","eat","tea"],  ["nat","tan"],  ["bat"]]

说明：

• 所有输入均为小写字母。
• 不考虑答案输出的顺序。

 

public static List
    
     
      > groupAnagrams(String[] strs) {
     
    

List
    
     
      > result = new ArrayList();
     
    

if(strs == null ||strs.length == 0) return result;

if(strs.length == 1){

result.add(Arrays.asList(strs[0]));

return result;

}

Map
    
     > maps = new HashMap();
    

for (String str : strs) {

char[] arr = str.toCharArray();

Arrays.sort(arr);

String sorted = Arrays.toString(arr);

if(maps.get(sorted) != null){

maps.get(sorted).add(str);

}else {

maps.put(sorted, new ArrayList(){
  {
  add(str);}});

}

}

maps.remove(null);

return maps.values().stream().collect(Collectors.toList());

}

18. Pow(x, n)

实现 ，即计算 x 的 n 次幂函数。

示例 1:

输入: 2.00000, 10输出: 1024.00000

示例 2:

输入: 2.10000, 3输出: 9.26100

示例 3:

输入: 2.00000, -2输出: 0.25000解释: 2

^-2

= 1/2

²

= 1/4 = 0.25

说明:

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−2³¹, 2³¹ − 1] 。

 

/**

* 快速降幂 避免递归过深造成栈溢出

* @param x

* @param n

* @return

*/

public static double power(double x, int n) {

if(!(x > -100 && x < 100)) return 0;

if(!(n <= Integer.MAX_VALUE && n >= Integer.MIN_VALUE)) return 0;

if(x == 0) return 0;

if(x == 1) return 1;

if(n == 0) return 1;

if(n == 1) return x;

if(n == -1) return 1/x;

if(n > 1 || n < -1){

double nextValue = power(x, n / 2);

return (n % 2 == 0 ? 1 : (n > 0 ? x : 1/x)) * nextValue * nextValue;

}

return x;

}

19. 进制转换

进制转换 十进制 =》 62进制 这里所谓62进制是指采用0~9A~Za~z等62个字符进行编码（按ASCII顺序由小到大）。

public static String BASE = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

public static String transfer(int num) {

int scale = 62;

StringBuilder sb = new StringBuilder();

while (num > 0) {

//余数对照进制基本位 BASE 放到相应位置

sb.append(BASE.charAt(num % scale));

//除处理下一进位

num = num / scale;

}

sb.reverse();

return sb.toString();

}

20. 报数

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     12.     113.     214.     12115.     111221

1 被读作  "one 1"  ("一个一") , 即 11。

11 被读作 "two 1s" ("两个一"）, 即 21。

21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

 

public static String countAndSay(int n) {

if(n < 1 || n > 30) return "";

int start = 1;

String report = "1";

String result = "";

while (start < n ){

result = "";

for (int i = 0; i < report.length();) {

int c = i;

int count = 1;

while (c + 1 < report.length()){

if(report.charAt(c) != report.charAt(c + 1)){

break;

}

count++;

c++;

}

result += String.valueOf(count) + String.valueOf(report.charAt(i));

i = i + count;

}

report = result;

start++;

}

return report;

}

21. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"输出: "bab"注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"输出: "bb"

public static String longestPalindrome(String s) {

if(s == null || s.length() == 1 || s.length() == 0) return s;

if(s.length() == 2) return s.charAt(0) == s.charAt(1)?s:String.valueOf(s.charAt(0));

String maxP = "";

//中间索引

int middle = (s.length()-1)/2;

//字符串长度奇偶 判别

boolean dmiddle = s.length()%2 == 0 && s.charAt(middle) == s.charAt(middle + 1);

//遍历使用临时中间字符索引

int tmpMiddle = middle;

//紧邻元素接次判断

int initJudge = 1;

//每次判断中间最长回文字符

String tp = "";

//最开始 判断是否偶长度

boolean first = true;

//中间字符逐次左移判断

while (tmpMiddle > 0) {

initJudge = 1;

//左右指针

int lindex = tmpMiddle - 1, rindex = tmpMiddle + (first && dmiddle?2:1);

while (lindex > -1 && rindex < s.length()) {

if(initJudge == 1) {

//左边紧邻接次判断

if (s.charAt(lindex) == s.charAt(tmpMiddle)) {

lindex--;

initJudge++;

}

//右边紧邻接次判断

if (s.charAt(rindex) == s.charAt(tmpMiddle + (first && dmiddle?1:0))) {

rindex++;

initJudge++;

}

initJudge = initJudge>1?1:0;

first = false;

tp = s.substring(lindex + 1, rindex);

continue;

}

//对称位置判断

if (s.charAt(lindex) == s.charAt(rindex)) {

lindex--;

rindex++;

tp = s.substring(lindex + 1, rindex);

continue;

}

tp = s.substring(lindex + 1, rindex);

break;

}

if(tp.length() > maxP.length()){

maxP = tp;

}

tmpMiddle--;

}

tmpMiddle = middle;

tp = "";

first = false;

//中间字符逐次右移判断

while (tmpMiddle < s.length()) {

initJudge = 1;

//左右指针

int lindex = tmpMiddle - 1, rindex = tmpMiddle + (first && dmiddle?2:1);

while (lindex > -1 && rindex < s.length()) {

if(initJudge == 1) {

//左边紧邻接次判断

if (s.charAt(lindex) == s.charAt(tmpMiddle)) {

lindex--;

initJudge++;

}

//右边紧邻接次判断

if (s.charAt(rindex) == s.charAt(tmpMiddle + (first && dmiddle?1:0))) {

rindex++;

initJudge++;

}

initJudge = initJudge>1?1:0;

tp = s.substring(lindex + 1, rindex);

continue;

}

//对称位置判断

if (s.charAt(lindex) == s.charAt(rindex)) {

lindex--;

rindex++;

tp = s.substring(lindex + 1, rindex);

continue;

}

tp = s.substring(lindex + 1, rindex);

break;

}

if(tp.length() > maxP.length()){

maxP = tp;

}

tmpMiddle++;

}

return maxP;

}

22. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

输入："234"

输出：

[aeg, ceg, beh, aei, beg, aeh, cei, ceh, bei, bfg, afh, afg, cfh, bdg, bfi, adh, cfg, bfh, adg, afi, cdh, bdi, cdg, cfi, bdh, adi, cdi].

说明:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

public static Map
    
      maps = new HashMap(){
  {
    

put(2, "abc"); put(3, "def"); put(4, "ghi"); put(5, "jkl"); put(6, "mno"); put(7, "pqrs"); put(8, "tuv"); put(9, "wxyz");

}};

public static List
    
      letterCombinations(String digits) {
    

int size = digits.length();

if(digits == null || digits.length() == 0) return new ArrayList<>();

Set
    
      coms = new HashSet();
    

if(size == 1){

String ele = maps.get(Integer.parseInt(digits));

for (int i = 0; i < ele.length(); i++) {

coms.add(String.valueOf(ele.charAt(i)));

}

}else if(size == 2){

String left = maps.get(Integer.parseInt(String.valueOf(digits.charAt(0))));

String right = maps.get(Integer.parseInt(String.valueOf(digits.charAt(1))));

for (int k = 0; k < left.length(); k++) {

for (int l = 0; l < right.length(); l++) {

coms.add(String.valueOf(left.charAt(k) + String.valueOf(right.charAt(l))));

}

}

}else {

String left = maps.get(Integer.parseInt(String.valueOf(digits.charAt(0))));

List
    
      subs = letterCombinations(digits.substring(1, digits.length()));
    

subs.stream().forEach(item->{

for (int l = 0; l < left.length(); l++) {

coms.add(String.valueOf(left.charAt(l)) + item);

}

});

}

return new ArrayList<>(coms);

}

23. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

 

public static ListNode removeNthFromEnd(ListNode head, int n) {

ListNode first = head;

//subIndex 第n个元素的索引

int index = 0, subIndex = 0;

List
    
      list = new ArrayList();
    

while (first != null){

list.add(first);

if(index - subIndex > n){

subIndex++;

}

index++;

first = first.next;

}

if(list.size() < n) return null;

if(list.size() == 1) return null;

if(list.size() == n) return list.get(1);

//处理移除

list.get(subIndex).next = list.get(subIndex).next.next;

return list.get(0);

}

24. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

 

//括号映射

public static Map
    
      maps = new HashMap(){
  {
    

put("}", "{
   ");

put("]", "[");

put(")", "(");

put("{
   ", "}");

put("[", "]");

put("(", ")");

}};

public static boolean isValid(String s) {

if(s == null || s.length() == 1) return false;

if(s.length() == 0 ) return true;

int index = 1;

//当前字符

char focus = s.charAt(0);

//存储非相邻匹配的符号

List
    
      unmap = new LinkedList();
    

while (index < s.length())

//相邻对比

if(String.valueOf(s.charAt(index)).equals(maps.get(String.valueOf(focus)))){

//处理存储的非相邻匹配的符号匹配

int lIndex = unmap.size() - 1;

if(lIndex > 0) {

unmap.remove(lIndex);

}

while (lIndex > 0){

index++;

lIndex--;

//倒序遍历匹配

if(unmap.get(lIndex).equals(maps.get(String.valueOf(s.charAt(index))))){

//匹配上则删除list中元素

unmap.remove(lIndex);

continue;

}else {

//匹配不上则加入到list中

unmap.add(String.valueOf(s.charAt(index)));

index--;

break;

}

}

index++;

if(index >= s.length()) return true;

focus = s.charAt(index);

index++;

}else {

//相邻不匹配则加入到 list中以供后续使用

if(s.substring(index).contains(String.valueOf(maps.get(String.valueOf(focus)))) && (index + 1 < s.length()) &&s.substring(index + 1).contains(String.valueOf(maps.get(String.valueOf(s.charAt(index)))))){

//第一次非相邻的时候添加头一个元素

if(unmap.size() == 0) {

unmap.add(String.valueOf(focus));

}

unmap.add(String.valueOf(s.charAt(index)));

focus = s.charAt(index);

index++;

}else{

return false;

}

}

return false;

}

25. 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为：[  [-1,  0, 0, 1],  [-2, -1, 1, 2],  [-2,  0, 0, 2]]

/**

* 四数之和

* @param nums

* @param target

* @return

*/

public static List
    
     
      > fourSum(int[] nums, int target) {
     
    

Set
    
     
      > sets = new HashSet();
     
    

List
    
      numList = new ArrayList();
    

for (int num : nums) {

numList.add(num);

}

for (int i = 0; i < numList.size(); i++) {

List
    
      copy = new ArrayList();
    

copy.addAll(numList);

copy.remove(numList.get(i));

List
    
     
      > threes = threeSum(copy, target - numList.get(i));
     
    

final int finalI = i;

threes.forEach(item -> {

item.add(nums[finalI]);

Collections.sort(item);

sets.add(item);

});

}

return new ArrayList(sets);

}

/**

* 三数之和

* @param nums

* @param target

* @return

*/

public static List
    
     
      > threeSum(List
      
        nums, int target) {
      
     
    

if(nums == null || nums.size() < 3) return new ArrayList();

Set
    
     
      > result = new HashSet<>();
     
    

List
    
      numList = new ArrayList();
    

for (int num : nums) {

numList.add(num);

}

for (Integer num : numList) {

List
    
      copy = new ArrayList();
    

copy.addAll(numList);

copy.remove(num);

List
    
      tmp = twoSum(copy, target - num);
    

if(tmp.size()>0){

for (int[] ints : tmp) {

List
    
      list = new ArrayList(){
  {add(num);add(ints[0]);add(ints[1]);}};
    

Collections.sort(list);

result.add(list);

}

}

}

return new ArrayList(result);

}

/**

* 两数之和

* @param nums

* @param target

* @return

*/

public static List
    
      twoSum(List
     
       nums, int target) {
     
    

List
    
      result = new ArrayList();
    

Map
    
      map = new HashMap<>();
    

for (int i = 0; i < nums.size(); i++) {

int complement = target - nums.get(i);

if (map.containsKey(complement)) {

result.add(new int[] { complement, nums.get(i) });

}

map.put(nums.get(i), i);

}

return result;

}

26. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4输出：1->1->2->3->4->4

/**

* 合并两个有序链表

* @param l1

* @param l2

* @return

*/

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

if(l1 == null && l2 == null) return null;

List
    
      list1 = new ArrayList();
    

while (l1!= null){

list1.add(l1);

l1 = l1.next;

}

List
    
      list2 = new ArrayList();
    

while (l2!= null){

list2.add(l2);

l2 = l2.next;

}

List
    
      result = mergeArrays(list1, list2);
    

for (int i = 0; i < result.size() - 1; i++) {

result.get(i).next = result.get(i + 1);

}

return result.get(0);

}

public static List
    
      mergeArrays(List
     
       nums1, List
      
        nums2) {
      
     
    

List
    
      indexes = new LinkedList();
    

int lgn1 = nums1.size();

int lgn2 = nums2.size();

int allLgn = lgn1 + lgn2;

int index1 = 0;

int index2 = 0;

for (int i = 0; i < allLgn; i++) {

if(index1 < lgn1 && index2 < lgn2) {

if (nums1.get(index1).val > nums2.get(index2).val) {

indexes.add(nums2.get(index2));

index2++;

} else {

indexes.add(nums1.get(index1));

index1++;

}

}else if(index1 < lgn1){

indexes.add(nums1.get(index1));

index1++;

}else if(index2 < lgn2){

indexes.add(nums2.get(index2));

index2++;

}

}

return indexes;

}

27. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:[   1->4->5,   1->3->4,   2->6]输出: 1->1->2->3->4->4->5->6

/**

* 合并k个有序链表

* @param lists

* @return

*/

public static ListNode mergeKLists(ListNode[] lists) {

if(lists == null || lists.length == 0) return null;

if(lists.length == 1) return lists[0];

int middle = (lists.length + 1)/2;

ListNode left = mergeKLists(Arrays.copyOfRange(lists, 0, middle));

ListNode right = mergeKLists(Arrays.copyOfRange(lists, middle, lists.length));

List
    
      list1 = new ArrayList();
    

while (left!= null){

list1.add(left);

left = left.next;

}

List
    
      list2 = new ArrayList();
    

while (right!= null){

list2.add(right);

right = right.next;

}

List
    
      result = mergeArrays(list1, list2);
    

for (int i = 0; i < result.size() - 1; i++) {

result.get(i).next = result.get(i + 1);

}

return result.size() > 0?result.get(0):null;

}

public static List
    
      mergeArrays(List
     
       nums1, List
      
        nums2) {
      
     
    

List
    
      indexes = new LinkedList();
    

int lgn1 = nums1.size();

int lgn2 = nums2.size();

int allLgn = lgn1 + lgn2;

int index1 = 0;

int index2 = 0;

for (int i = 0; i < allLgn; i++) {

if(index1 < lgn1 && index2 < lgn2) {

if (nums1.get(index1).val > nums2.get(index2).val) {

indexes.add(nums2.get(index2));

index2++;

} else {

indexes.add(nums1.get(index1));

index1++;

}

}else if(index1 < lgn1){

indexes.add(nums1.get(index1));

index1++;

}else if(index2 < lgn2){

indexes.add(nums2.get(index2));

index2++;

}

}

return indexes;

}

28. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

 

public static ListNode swapPairs(ListNode head) {

if(head == null) return null;

ListNode first = head.next == null?head:head.next;

ListNode curr = head;

ListNode pre = null;

while (head != null){

if(head.next != null){

//保存需要交换位置的节点之后的节点

curr = head.next.next;

//将上一个节点和交换后的节点相连

if(pre != null){

pre.next = head.next;

}

//保存下一次需要交换位置节点的上一个节点

pre = head;

//交换节点

head.next.next = head;

//将交换位置后的第二个节点和后面的节点相连

head.next = curr;

}

//继续遍历

head = head.next;

}

return first;

}

 

29. k个一组翻转链表

给出一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么将最后剩余节点保持原有顺序。

示例 :

给定这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明 :

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

/**

* k个一组翻转链表

* @param head

* @param k

* @return

*/

public static ListNode reverseKGroup(ListNode head, int k) {

if(head == null) return null;

if(k == 1) return head;

if(head.next == null) return head;

List
    
      list = new LinkedList();
    

List
    
      listCopy = new LinkedList();
    

List
    
      tmpList = new LinkedList();
    

int index = 0;

while (head != null){

list.add(head);

head = head.next;

index++;

if(index%k == 0){

tmpList = list.subList(index - k, index);

Collections.reverse(tmpList);

listCopy.addAll(tmpList);

}

}

if(index%k != 0){

tmpList = list.subList(index > k?(index - index%k):0, index);

listCopy.addAll(tmpList);

}

for (int i = 0; i < listCopy.size() - 1; i++) {

listCopy.get(i).next = listCopy.get(i + 1);

}

listCopy.get(listCopy.size() - 1).next = null;

return listCopy.get(0);

}

 

30. 删除排序数组中的重复项

给定一个排序数组，你需要在删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。

 

public static int removeDuplicates(int[] nums) {

if(nums == null || nums.length == 0) return 0;

if(nums.length == 1) return 1;

int index = 0;

int lgn = nums.length;

while (index < lgn){

if(Arrays.binarySearch(nums, index + 1, lgn, nums[index]) > -1){

for (int i = index; i < lgn - 1 ; i++) {

nums[i] = nums[i + 1];

}

nums[lgn - 1] = Integer.MIN_VALUE;

lgn--;

}else {

index++;

}

}

return lgn;

}

31. 移除元素

给定一个数组 nums 和一个值 val，你需要移除所有数值等于 val 的元素，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

 

public static int removeElement(int[] nums, int val) {

if(nums == null || nums.length == 0) return 0;

int index = 0;

int lgn = nums.length;

while (index < lgn){

if(nums[index] == val){

for (int i = index; i < lgn - 1 ; i++) {

nums[i] = nums[i + 1];

}

nums[lgn - 1] = Integer.MIN_VALUE;

lgn--;

}else {

index++;

}

}

return lgn;

}

32. 实现strStr()

实现 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll"输出: 2

 

public static int strStr(String haystack, String needle) {

if(haystack == null || needle == null) return -1;

if(haystack.equals(needle) || "".equals(needle)) return 0;

int findex = 0;

int flgn = haystack.length(), slgn = needle.length();

while (findex + slgn <= flgn){

if(haystack.charAt(findex) == needle.charAt(0)) {

int sindex = 0;

for (; sindex < slgn; sindex++) {

if (needle.charAt(sindex) != haystack.charAt(findex + sindex)){

findex = findex + sindex - 1;

break;

}

}

if(sindex == slgn){

return findex;

}else {

findex = findex - sindex + 1;

findex++;

continue;

}

}else {

findex++;

}

}

return -1;

}

 

 

 

待续 。。。 。。。

 

项目地址：