高频题

三数之和

两数之和为基础

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

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

// 1 先将数组排序
  // 2 从后往前遍历最后一个数 找对应的二元组：二元组 + arr[i] = 0
  // 2.1 保证不重复
  // 2.2 找出前面部分满足条件的二元组
  // 2.3 遍历将arr[i]添加在后面
  public static List<List<Integer>> threeSum(int[] nums) {
      // 1
      Arrays.sort(nums);
      int N = nums.length;
      List<List<Integer>> ans = new ArrayList<>();
      // 2
      for (int i = N - 1; i > 1; i--) { // 三元组最后一个数，是arr[i]   之前....二元组 + arr[i]
          // 2.1
          if (i == N - 1 || nums[i] != nums[i + 1]) {
              // 2.2
              List<List<Integer>> nexts = twoSum(nums, i - 1, -nums[i]);
              // 2.3
              for (List<Integer> cur : nexts) {
                  cur.add(nums[i]);
                  ans.add(cur);
              }
          }
      }
      return ans;
  }

  // nums[0...end]这个范围上，有多少个不同二元组，相加==target，全返回
  // {-1,5}     K = 4
  // {1, 3}
  // 1 两个指针
  // 2 两数相加大于目标值就右缩;小于就左缩;等于就添加在结果集里面（先加左再加右）
  public static List<List<Integer>> twoSum(int[] nums, int end, int target) {
      int L = 0;
      int R = end;
      List<List<Integer>> ans = new ArrayList<>();
      while (L < R) {
          if (nums[L] + nums[R] > target) {
              R--;
          } else if (nums[L] + nums[R] < target) {
              L++;
          } else { // nums[L] + nums[R] == target
              if (L == 0 || nums[L - 1] != nums[L]) {
                  List<Integer> cur = new ArrayList<>();
                  cur.add(nums[L]);
                  cur.add(nums[R]);
                  ans.add(cur);
              }
              L++;
          }
      }
      return ans;
  }

两数之和

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

1 使用hashmap 结构 map.put(nums[i], i)

2 遍历一遍 如果查询到map里面有与解 就返回i和mapget的value

3 最后如果没有找到就返回new int[0]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i ++){
            if(map.containsKey(target - nums[i])){
                return new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }
}

搜索旋转排序数组（面试）

使用二分查找

整数数组nums按升序排列，数组中的值互不相同。

arr，原本是有序数组，旋转过，而且左部分长度不知道.(以某一个下标为轴旋转 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。)

题目需要在arr里面找到target

思路：

1. L = M = R 是最差的情况 不知道断点
2. L != M == R/ L == M != R/ L != M != R 只要三个数不全部一样就可以进行二分

public int search(int[] nums, int target) {
		int N = nums.length;
		int L = 0;
		int R = N - 1;
		while (L <= R) {
			int M = (L + R) / 2;
			if (nums[M] == target) {
				return M;
			}
			// nums[M] != target
			// 1 左 中 右 相等 -- 》不能二分
			if (nums[L] == nums[M] && nums[M] == nums[R]) {
				// 左中一直相等 L ++
				while (L != M && nums[L] == nums[M]) {
					L++;
				}
				// 1.1 左中直到重合都相等
				if (L == M) {
					L = M + 1;
					continue;// 回到循环开始重新来
				}
				// 1.2 或者是 到不相等地方 继续2

			}
			// 2 左中右不都相等 --> 代表可以二分
			if (nums[L] != nums[M]) { // 2.1 [L] != [M] ?= [R]
				if (nums[L] < nums[M]) {// 2.1.1 L < M 左边一定有序
					if (nums[L] <= target && target < nums[M]) {
						R = M - 1;
					} else {
						L = M + 1;
					}
				} else { // 2.1.2 L > M 左边一定有断点 右边有序
					if (nums[M] < target && target <= nums[R]) {
						L = M + 1;
					} else {
						R = M - 1;
					}
				}
			} else {// 2.2 [L] ?= [M] != [R]
				if (nums[M] < nums[R]) {// 2.2.1 M < R
					if (nums[M] < target && target <= nums[R]) {
						L = M + 1;
					} else {
						R = M - 1;
					}
				} else { // 2.1.2 M > R
					if (nums[L] <= target && target < nums[M]) {
						R = M - 1;
					} else {
						L = M + 1;
					}
				}
			}

		}
		return -1;
	}

合并两个有序数组

给你两个有序数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。进行合并。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = nums1.length;
       while(m > 0 && n > 0) { // 相等的时候先拷贝长数组的  尽可能让空间早释放
            if(nums1[m - 1] >= nums2[n -1]){
                nums1[--index] = nums1[--m];
            } else {
                nums1[--index] = nums2[--n];
            }
        }   
        while(n > 0) {// m都被填完 就把nums2剩下的n填进nums1
            nums1[--index] = nums2[--n];
        }
    }

螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

public List<Integer> spiralOrder(int[][] matrix) {
	List<Integer> order = new ArrayList<>();
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
		return order;
	}
	int left = 0;
	int top = 0;
	// 易错点一：注意right和bottom别写反了。
	int right = matrix[0].length - 1;
	int bottom = matrix.length - 1;
	while (left <= right && top <= bottom) {
		// 上层：从左到右，行不变，列变。
		for (int i = left; i <= right; i++) {
			order.add(matrix[top][i]);
		}
		// 右层：从上到下，行变，列不变。
		for (int i = top + 1; i <= bottom; i++) {
			order.add(matrix[i][right]);
		}
		// 易错点二：注意针对行列不相等时，下面两个循环要满足right > left && bottom > top条件 ⚠️
		if (right > left && bottom > top) {
			// 下层：从右向左，行不变，列变。
			for (int i = right - 1; i >= left; i--) {
				order.add(matrix[bottom][i]);
			}
			// 左层：从下到上，行变，列不变。
			// 易错点三：此处只需要 i>top, i不能=top
			for (int i = bottom - 1; i > top; i--) {
				order.add(matrix[i][left]);
			}
		}

		left++;
		top++;
		right--;
		bottom--;
	}
	return order;
}

字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

public String addStrings2(String num1, String num2) {
	int i = num1.length() - 1, j = num2.length() - 1, add = 0;
	StringBuffer ans = new StringBuffer();
	while (i >= 0 || j >= 0 || add != 0) {
		int x = i >= 0 ? num1.charAt(i) - '0' : 0;
		int y = j >= 0 ? num2.charAt(j) - '0' : 0;
		int result = x + y + add;
		ans.append(result % 10);
		add = result / 10;
		i--;
		j--;
	}
	// 计算完以后的答案需要翻转过来
	ans.reverse();
	return ans.toString();
}

二分查找

public int search(int[] nums, int target) {
        int L = 0;
        int R = nums.length - 1;
        while(L < R){ // ⚠️ 没有相等
            int mid = (L + R) >> 1;
            if(target < nums[mid]){
                R = mid - 1;
            } else if(target > nums[mid]){
                L = mid + 1;
            } else{
                return mid;
            } 
        }
        return (nums[L] == target) ? L : -1;
    }

在排序数组中找到元素第一个和最后一个位置

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 * @author chs
 *
 */
public class Fre_044_FindFirstAndLastPositionOfElementInSortedArray {
	// 借助二分 《找到数组中比它小的最右的数 (lessMostRight
	// 如果该位置右边!=target说明数组没有这个数
	// 如果是 那么左边界找到 右边界就是《找到比ta+1小的最右的数》 (lessMostRight
	public static int[] searchRange(int[] nums, int target) {
		if (nums == null || nums.length == 0) {
			return new int[] { -1, -1 };
		}
		int L = lessMostRight(nums, target) + 1;
		if (L == nums.length || nums[L] != target) {
			return new int[] { -1, -1 };
		}
		return new int[] { L, lessMostRight(nums, target + 1) };
	}

	// 利用二分 
	// 1 一个指针 M
	// 2 ans存放结果
	// 3 arr[M] 小于就去右边找 大于就去左边找
	public static int lessMostRight(int[] arr, int num) {
		int L = 0;
		int R = arr.length - 1;
		// 1
		int M = 0;
		// 2 
		int ans = -1;
		// 3
		while (L <= R) {
			M = L + ((R - L) >> 1);
			if (arr[M] < num) {
				ans = M;
				L = M + 1;
			} else {
				R = M - 1;
			}
		}
		return ans;
	}
}

字符串转化整数

注意有很多特殊情况

1.需要删除无用的前导空格

2.检查下一个字符为正还是负

3.只读一开始是数字的部分

4.超出范围的数字返回边界

1. 主函数myAtoi():
     1 除去空格和后面非数字的部分( 前后都要判空)【removeHeadZero()】
     2 判断该部分是否是有效数字【isValid()】
     3 转为负数形式（转回不会溢出，负数范围大些） posi(标志正负)
     4 res是最负的情况 (用了负数就只用可以装下，如果用整数转，最小就没法装)
2. removeHeadZero():
     1 是否有符号
     2 s标志第一个不是零的位置
     3 e标志数字部分后面的非数字部分的开头
     4 返回截取的带符号整数部分
3. isVaild():    判断带符号整数部分是否有效
     1 开头在remove部分没有判断，只要开头不是数字和符号都返回无效
     2 只有符号也无效
     3 夹杂着非数字字符也无效

public class Fre_072_StringToInteger {
  public int myAtoi(String s) {
        // 1 除去空格和后面不是数字的部分
        if(s == null || s.equals("")){// ⚠️
            return 0;
        }
        s = removeHeadZero(s.trim());
        if(s == null || s.equals("")){
            return 0;
        }

        // 2 判断这部分是不是有效数字
        char[] str = s.toCharArray();
        if(!isValid(str)){
            return 0;
        }

        // 3 转为负数形式 为了防止溢出 posi(标志正负) ⚠️不要搞反了
        boolean posi = str[0] == '-' ? false : true;
        // 后面会有*10的操作 需要先判断会不会溢出
        int minq = Integer.MIN_VALUE / 10;
        int minp = Integer.MIN_VALUE % 10;
        int res = 0;
        int cur = 0;
        for(int i = (str[0] == '-' || str[0] == '+') ? 1 : 0; i < str.length; i++){
            cur = '0' - str[i]; // 转为负数
            // 在乘十之前判断是否会溢出
            if(res < minq || (res == minq && cur < minp)){
                	return posi ? Integer.MAX_VALUE : Integer.MIN_VALUE; 
            }
            res = res * 10 + cur;

        }

        // 4 res是最负情况（也就是本来是最大的+1）
        if(posi && (res == Integer.MIN_VALUE)){
            return Integer.MAX_VALUE; // 返回边界
        }

        return posi ? -res : res;
    }

    public static String removeHeadZero(String s){
        // 1 是否有符号
        boolean r = (s.startsWith("+") || s.startsWith("-")); // ⚠️ 不能用charat

        // 2 标志第一个不是零的位置
        int start = r ? 1 : 0;
        for(; start< s.length(); start++){
            if(s.charAt(start) != '0'){
                break;
            }
        }

        // 3 找到数字部分后面的非数组部分开头 倒着遍历
        int e = -1;
        for(int i = s.length() - 1; i >= (r ? 1 : 0); i--){
            if(s.charAt(i) < '0'  || s.charAt(i) > '9') {
                e = i;
            }
        }

        // 4 返回截取的带符号的整数部分
        return (r ? String.valueOf(s.charAt(0)): "") + s.substring(start, e == -1 ? s.length() : e);
    }

    // 判断是否是有效的数字
    public static boolean isValid(char[] str) {
        // 1 如果开头不是数组
        if(str[0] != '-' && str[0] != '+' && (str[0] < '0' || str[0] > '9')){
            return false;
        }
        // 2 只有符号也无效
        if((str[0] == '-' || str[0] == '+') && str.length == 1){
            return false;
        }
        // 3 夹杂着非数字字符 无效
        for(int i = 1; i < str.length; i++){
            if(str[i] <'0' || str[i] > '9'){
                return false;
            }
        }
        return true;

    }

	}

下一个排列

给你一个整数数组 nums ，找出 nums 的字典序中的下一个排列。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

必须 原地 修改，只允许使用额外常数空间。

public void nextPermutation(int[] nums) {
       int i = nums.length - 2;
       // 1 倒着找升序对 [ i , i+ 1]
       while(i >= 0 && nums[i] >= nums[i + 1]) {
           i--;
       }
       // 2 从end -> i+1 倒着找比i大的数
       if(i >= 0){
           int j = nums.length - 1;
           while(nums[i] >= nums[j]){
               j--;
           }
           swap(nums, i, j);
       }
       // 3 将数组i+1以后的反转
       // 因为有两种情况：1） i< 0 说明本身就是字典序最大，直接翻转 2）[i+1, end]是降序需要翻转
       reverse(nums, i + 1);
   }
   public static void reverse(int[] nums, int i){
       int left = i;
       int right =  nums.length - 1;
       while(left < right){
           swap(nums, left, right);
           left++;
           right--;
       }
   }

   public static void swap(int[] nums, int i, int j){
       int tmp = nums[i];
       nums[i] = nums[j];
       nums[j] = tmp;
   }

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

1. s 和 e 记录上一个区间的边界
2. 然后复用interval数组来存储，最后复制数组size部分

class Solution {
    public int[][] merge(int[][] intervals) {
        	if (intervals.length == 0) {
			return new int[0][0];
		}
    // 先按照区间的左边界来排序
		Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
		int s = intervals[0][0];
		int e = intervals[0][1];// 
		int size = 0;
    // 然后复用interval数组来存储，最后复制数组size部分
		for (int i = 1; i < intervals.length; i++) {
			if (intervals[i][0] > e) {// 如果当前左边界大于e 说明没有覆盖 
				intervals[size][0] = s;// 可以更新size部分的s和e 然后size++
				intervals[size++][1] = e;
				s = intervals[i][0];
				e = intervals[i][1];// s e 更新为当前的左右边界
			} else {
				e = Math.max(e, intervals[i][1]); // 如果当前左边界小于或者等于 说明两个区间可以覆盖 先将e更新为这两个区间的最大右区间
			}
		}
		intervals[size][0] = s; // 最后还有一次size处的更新
		intervals[size++][1] = e;
		return Arrays.copyOf(intervals, size);
    }
}

x的平方根

==二分查找==

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

1. 使用 二分 <=就更新ans和L 到右边就更新R
2. 注意数据类型时long主要是为了两个整型相乘不会溢出

// x一定非负，输入可以保证
    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x < 3) {
            return 1;
        }
        // x >= 3
        long ans = 1;
        long L = 1;
        long R = x;
        long M = 0;
        while (L <= R) {
            M = (L + R) / 2;
            // 因为两个整数相乘可能会溢出
            if (M * M <= x) {
                ans = M;
                L = M + 1;
            } else {
                R = M - 1;
            }
        }
        return (int) ans;
    }

扩展：求出小数点后k位 其实思路与一样 只是换成double类型并且需要转换数格式

缺失的正数

给你一个未排序的整数数组，请你找出没有出现的最小的正整数 时间复杂度o(n)

除了打标记以外，我们还可以使用置换的方法，将给定的数组「恢复」成下面的形式：

如果数组中包含 x∈[1,N]x \in [1, N]x∈[1,N]，那么恢复后，数组的第 x−1x - 1x−1 个元素为 xxx。

在恢复后，数组应当有 [1, 2, …, N] 的形式，但其中有若干个位置上的数是错误的，每一个错误的位置就代表了一个缺失的正数。以题目中的示例二 [3, 4, -1, 1] 为例，恢复后的数组应当为 [1, -1, 3, 4]，我们就可以知道缺失的数为 2。

public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { 
              // ⚠️交换的条件---nums[i]∈[1,N] 且 nums[i]和本来应该在的位置的值nums[nums[i]-1]不相等
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }

用rand7()生成rand10()

用一个不等概率返回0和1的函数, 怎么加工一个函数0和1等概率返回

public int rand10() {
       int ans= 0;
       do{
           ans = f2();
       }while(ans >9);
       return ans + 1 ;
   }
   public int f() {
       int ans= 0;
       do{
           ans = rand7();
       }while(ans == 4);
       return ans < 4? 0:1;
   }

   // 0000~1111 0~15
   public int f2() {
       return (f() << 3) + (f() << 2) + (f() << 1 )+ f();
   }

找到两个有序数组的中位数(⚠️)/两个有序数组第k小

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //这里就主要处理 两个为空 一个为空 全不为空的三个情况
        int size = nums1.length + nums2.length;
        boolean e = (size & 1) == 0;
        if(nums1.length == 0 && nums2.length == 0) {
            return 0;
        }else if(nums1.length == 0){
            if(!e){
                return nums2[size/ 2];                   
            }else{
                return (double)(nums2[ size / 2- 1] + nums2[size / 2 ])/2;
            }
        }else if(nums2.length == 0){
            if(!e){
                return nums1[size/ 2];
            }else{
                return (double)(nums1[size / 2 - 1] + nums1[size / 2])/2;
            }
        }else{
            if(!e){
                return findKthNum(nums1, nums2, size / 2 + 1);
            }else{
                return (double)(findKthNum(nums1, nums2, size/2)+findKthNum(nums1, nums2, size/2 +1))/2D;
            }
        }

    //原型
    public static int getUpMedian(int[] arr1, int s1,int e1,int[] arr2, int s2, int e2){
        int mid1 = 0;
        int mid2 = 0;
        while(s1 < e1){
            //mid
            mid1 = (e1 + s1) >> 1;
            mid2 = (e2 + s2) >> 1;
            if(arr1[mid1] == arr2[mid2] ) return arr1[mid1];
            //奇数
            if(((e1 - s1 + 1) & 1) == 1){
                if(arr1[mid1] < arr2[mid2]){
                    if(arr1[mid1] >= arr2[mid2 - 1]) return arr1[mid1];
                    s1 = mid1 + 1;
                    e2 = mid2 - 1;
                }else{
                    if(arr2[mid2] >= arr1[mid1 - 1]) return arr2[mid2];
                    s2 = mid2 + 1;
                    e1 = mid1 - 1;
                }
            }
            //偶数
            else{
                if(arr1[mid1] > arr2[mid2]){
                    e1 = mid1;
                    s2 = mid2 + 1;
                }else{
                    e2 = mid2;
                    s1 = mid1 + 1;
                }
            }
        }
        //最后跳出循环 都只剩一个数
        return Math.min(arr1[s1], arr2[s2]);
    }



    //处理长度不同 返回Kth的情况
    public static int findKthNum(int[] arr1, int[] arr2, int k){
        int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
        int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
        int l = longs.length;
        int s = shorts.length;
        //1
        if(k <= s){
            return getUpMedian(longs, 0, k - 1, shorts, 0, k - 1);
        }
        //2
        if(k > l){
            if(longs[k - s - 1] >= shorts[s - 1]){
                return longs[k - s -1];
            }
            if(shorts[k - l - 1] >= longs[l - 1]){
                return shorts[k - l - 1];
            }
            return getUpMedian(longs, k - s, l - 1, shorts, k - l, s - 1);
        }
        //3
        if(longs[k - s - 1] >= shorts[s - 1]){
            return longs[k - s - 1];
        }
        return getUpMedian(longs, k - s, k - 1,shorts, 0 ,s - 1);
    }

翻转字符串中的单词

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
翻转后单词间应当仅用一个空格分隔。
翻转后的字符串中不应包含额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：“blue is sky the”

示例 2：

输入：s = " hello world "
输出：“world hello”
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。

思路:

1. 去除多余的空白：
   (1去掉字符串开头的空白字符
   (2去掉字符串末尾的空白字符
   (3将字符串间多余的空白字符去除
2. 翻转字符串：
3. 翻转每一个单词：
   (1 遍历sb 使用start 和 end来抓单词
   (2 翻转单词
   (3 更新start，去找下一个单词

// 1 去除多余的空白
    // 2 翻转字符串
    // 3 翻转每一个单词
    public String reverseWords(String s) {
        // 1
        StringBuilder sb = trimSpaces(s);

        // 2
        reverse(sb, 0, sb.length() - 1);

        // 3
        reverseEachWord(sb);

        return sb.toString();
    }

    // 1 去掉字符串开头的空白字符
    // 2 去掉字符串末尾的空白字符
    // 3 将字符串间多余的空白字符去除
    public StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        // 1 
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 2
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        // 3
        StringBuilder sb = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);

            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }

            ++left;
        }
        return sb;
    }

    // 翻转任意字符
    public void reverse(StringBuilder sb, int left, int right) {
        while (left < right) {
            char tmp = sb.charAt(left);
            sb.setCharAt(left++, sb.charAt(right));
            sb.setCharAt(right--, tmp);
        }
    }


    public void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0, end = 0;

        // 1 遍历sb 使用start 和 end来抓单词
        // 2 翻转单词
        // 3 更新start，去找下一个单词
        while (start < n) {
            // 1
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            // 2
            reverse(sb, start, end - 1);
            // 3
            start = end + 1;
            ++end;
        }
    }

字符串相乘

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

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:

输入: num1 = “123”, num2 = “456”
输出: “56088”

public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] /10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }

删除数组中的重复项

任何删除重复的都可以用快慢指针

/**
 * 删除有序数组中的重复项
 * @author chs
 * 任何删除重复的都可以用快慢指针
 */
public class Fre_017_RemoveDuplicatesFromSortedArray {
	public static int removeDuplicates(int[] nums) {
		if (nums == null) {
			return 0;
		}
		
		if (nums.length < 2) {
			return nums.length;
		}
		int done = 0;
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] != nums[done]) {
				nums[++done] = nums[i];
			}
		}
		return done + 1;
	}
}

去除重复字母

贪心➕单调栈？

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

输入：s = “bcabc”
输出：“abc”

示例 2：

输入：s = “cbacdcbc”
输出：“acdb”

public String removeDuplicateLetters(String s) {
       boolean[] vis = new boolean[26];
       int[] num = new int[26];
       for (int i = 0; i < s.length(); i++) {
           num[s.charAt(i) - 'a']++;
       }

       StringBuffer sb = new StringBuffer();
       for (int i = 0; i < s.length(); i++) {
           char ch = s.charAt(i);
           if (!vis[ch - 'a']) {
               while (sb.length() > 0 && sb.charAt(sb.length() - 1) > ch) {
                   if (num[sb.charAt(sb.length() - 1) - 'a'] > 0) {
                       vis[sb.charAt(sb.length() - 1) - 'a'] = false;
                       sb.deleteCharAt(sb.length() - 1);
                   } else {
                       break;
                   }
               }
               vis[ch - 'a'] = true;
               sb.append(ch);
           }
           num[ch - 'a'] -= 1;
       }
       return sb.toString();
   }

单词搜索

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

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

public void rotate(int[][] matrix) {
        int a = 0;
        int b = 0;
        int c = matrix.length - 1;
        int d = matrix[0].length - 1;
        while(a < c) {
            rotateEdge(matrix, a++, b++, c--, d--);
        }
    }

    public static void rotateEdge(int[][] m, int a, int b, int c, int d) {
        int tmp = 0;
        for (int i = 0; i < d - b; i++) {
            tmp = m[a][b + i];
            m[a][b + i] = m[c - i][b];
            m[c - i][b] = m[c][d - i];
            m[c][d - i] = m[a + i][d];
            m[a + i][d] = tmp;
        }
    }

多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

是一个超级水王问题

1遍历 使用 candidate和HP 来一次删除两个不同的数
2到最后 HP 不为0 则说明可能有水王 是当前的candidate
3再遍历一次找candi 如果 HP> n/2 说明就是水王 

public int majorityElement(int[] nums) {

        if(nums == null) {
            return -1;
        }
        int n = nums.length;
        int candi = 0;
        int HP = 0;
        for(int i  = 0; i < n; i++) {
            if(HP == 0) {
                candi = nums[i];
                HP++;
            }else if( nums[i] != candi) {
                HP--;
            }else {
                HP++;
            }
        }
        if(HP == 0) {
            return -1;
        }
        HP = 0;
        for(int i = 0; i < n ; i++) {
            if(nums[i] == candi) {
                HP++;
            }
        }
        if(HP > n / 2) {
            return candi;
        } else {
            return -1;
        }
    }
}

1 链表

1 反转链表

public ListNode reverseList(ListNode head) {
      ListNode pre = null;
      ListNode cur = head;
      while(cur != null) {
          ListNode next = cur.next;
          cur.next = pre;
          pre = cur;
          cur = next;
      }
      return pre;// ！返回的是pre
  }

反转链表二

就是反转链表中间一截

// 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点

// 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点

// 第 3 步：切断出一个子链表（截取链表）先标记再切断

// 第 4 步：[同反转链表](##1 反转链表##)，反转链表的子区间

// 第 5 步：接回到原来的链表中

public ListNode reverseBetween(ListNode head, int left, int right) {
        //1 需要一个虚拟头
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        //2 先找到反转部分的left前面pre
        ListNode pre = dummyNode;
        for(int i = 0; i < left - 1;i++) {
            pre = pre.next;
        }

        //2 从pre再走right - left + 1步 来到right节点
        ListNode rNode = pre;
        for(int i = 0; i < right - left + 1;i++) {
            rNode = rNode.next;
        }

        //3 切断这部分的链表
        ListNode lNode = pre.next;
        ListNode end = rNode.next;
        pre.next = null;
        rNode.next = null;

        //4 反转区间内的链表
        reverseLinkedList(lNode);

        //5 接回去
        pre.next = rNode;// ⚠️接回去的时候已经是反过来了
        lNode.next = end;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }

2 LRU缓存机制

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必0须以 O(1) 的平均时间复杂度运行。

1) 总的缓存结构 和方法调用

构造方法

private MyCache<Integer, Integer> cache;
	public Fre_278_LRUCache(int capacity){
		cache = new MyCache<>(capacity);
	}
	

1 get()

public int get(int key) {
		Integer ans = cache.get(key);
		return ans == null ? -1 : ans;
	}

2 put()

public void put(int key, int value) {
		cache.set(key, value);
	}

2）MyCache

构造方法

public static class MyCache<K, V> {
	private HashMap<K, Node<K, V>> keyNodeMap;
	private NodeDoubleLinkedList<K, V> nodeList;
	private final int capacity;
	
	public MyCache(int cap) {
		keyNodeMap = new HashMap<K, Node<K, V>>();
		nodeList = new NodeDoubleLinkedList<K, V>();
		capacity = cap;
	}

1 V get(K key) 通过key返回value 需要将node放到尾部

public V get(K key) {
		if(keyNodeMap.containsKey(key)) {
			Node<K, V> res = keyNodeMap.get(key);
			nodeList.moveNodeToTail(res);
			return res.value;
		}
		return null;
	}

2 void set(K key, V value) 更新与新增：放到尾部，超出内存就删除最长时间没有操作的

public void set(K key, V value) {
		if (keyNodeMap.containsKey(key)) {
			Node<K, V> node = keyNodeMap.get(key);
			node.value = value;
			nodeList.moveNodeToTail(node);
		} else {
			Node<K, V> newNode = new Node<K, V>(key, value);
			keyNodeMap.put(key, newNode);
			nodeList.addNode(newNode);
			if (keyNodeMap.size() == capacity + 1) {
				removeMostUnusedCache();
			}
		}
	}

3 void removeMostUnusedCache() 删去最长时间没有操作的缓存 ；在两个结构里面都删除

private void removeMostUnusedCache() {
			Node<K, V> removeNode = nodeList.removeHead();
			keyNodeMap.remove(removeNode.key);
		}

3) 双向链表结构

基于LRU机制的双向链表结构
private Node<K, V> head;
private Node<K, V> tail;

构造方法：将头尾置为空

public NodeDoubleLinkedList(){
	head = null;
	tail = null;
}

1 addNode() : 来新节点，挂到尾巴上

public void addNode(Node<K, V> newNode){
			if(newNode == null) {
				return;
			}
			if(head ==  null) {
				head = newNode;
				tail = newNode;
			} else {
				tail.next = newNode;
				newNode.last = tail;
				tail = newNode;
			}
		}

2 moveToTail() : （修改过的节点，要保证node在表中）更新到尾部

public void moveNodeToTail(Node<K, V> node) {
		 
		}

3 removeHead() : 将头节点移走，返回新的头节点

public static class NodeDoubleLinkedList<K, V> {
	
	public Node<K, V> removeHead() {
		if (head == null) {
			return null;
		}
		Node<K, V> res = head;
		if (head == tail) {
			head = null;
			tail = null;
		} else {
			head = res.next;
			res.next = null;
			head.last = null;
		}
		return res;
	}
}

3 K个一组翻转链表

1 先将第一组k凑齐 并且反转
2 再记录上一组的结尾节点
3 循环（当结尾.next != null)

(1)更新start (2)更新end 注意判空！！

（3） 反转 ：end 变头

(4） 上一组结尾连接到现在的开头end (5)更新lastEnd

public ListNode reverseKGroup(ListNode head, int k) {
       // 1
       ListNode start = head;
       ListNode end = getKEnd(start, k);
       if (end == null) {
           return head;
       }
       head = end;
       reverse(start, end);
       // 2
       ListNode lastEnd = start;
       // 3
       while (lastEnd.next != null) {
           // 1)
           start = lastEnd.next;
           // 2)
           end = getKEnd(start, k);
           if (end == null) {// ⚠️(注意判空！！！)
               return head;
           }
           // 3)
           reverse(start, end);
           // 4)
           lastEnd.next = end;
           // 5)
           lastEnd = start;
       }
       return head;
   }

   private ListNode getKEnd(ListNode start, int k) {
       while (--k != 0 && start != null) {
           start = start.next;
       }
       return start;
   }

   // 反转 
   // 1 end 往后移
   // 2 三个指针进行反转
   // 3 start反转后是结尾要连接到end
   private void reverse(ListNode start, ListNode end) {
       // TODO Auto-generated method stub
       end = end.next;//⚠️(注意要移动end指针)
       ListNode pre = null;
       ListNode cur = start;
       ListNode next = null;
       while (cur != end) {
           next = cur.next;
           cur.next = pre;
           pre = cur;
           cur = next;
       }
       start.next = end;
   }

4 合并两个有序链表

1. 先抓小头head
2. cur2抓大头 cur1 = head.next pre = head
3. 比较 c1 c2 谁小pre的next就指向谁 并且cur pre 后移

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null || l2 ==null){
            return l1 == null ? l2 : l1;
        }
        //抓大头
        ListNode head = l1.val <= l2.val ? l1 : l2;
        ListNode cur1 = head.next;
        //抓小头
        ListNode cur2 = head == l1 ? l2 : l1;
        ListNode pre = head;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                pre.next = cur1;
                cur1 = cur1.next;
            }else{
                pre.next = cur2;
                cur2 = cur2.next;
            }
            pre = pre.next;
        }
        pre.next = cur1 != null ? cur1 :cur2;
        return head;
}

合并k个链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

public class LianBiao_MergeMoreList {

  //对数器 ⚠️
	public static class ListNodeComparator implements Comparator<ListNode> {
		@Override
		public int compare(ListNode arg0, ListNode arg1) {
			// TODO Auto-generated method stub
			return arg0.val - arg1.val;
		}
	}
  
	public ListNode mergeKLists(ListNode[] lists) {
		if (lists == null) {
			return null;
		}
		// 1 定义一个对数器的小根堆
		PriorityQueue<ListNode> heap = new PriorityQueue<>(
				new ListNodeComparator());

   
		// 2 将每一条的head放在堆中
		for (int i = 0; i < lists.length; i++) {
			if (lists[i] != null) {// !!! 
				heap.add(lists[i]);
			}
		}
    if(heap.isEmpty()){ // ⚠️
            return null;
    }
		// 3 抓出head 将该条后面一个节点放入堆
		ListNode head = heap.poll();
		if (head.next != null) {// !!!
			heap.add(head.next);
		}
		ListNode pre = head;// 指针

		// 4 重复弹出连接结果表 再见弹出的下一个放入堆中
		while (!heap.isEmpty()) {
			ListNode cur = heap.poll();
			pre.next = cur;
			pre = cur;
			if (cur.next != null) {// !!!
				heap.add(cur.next);
			}
		}

		return head;

	}
}

5 相交链表

需要分有环和无环两种情况 [如何辨别有无环](##6 环形链表##)

无环链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

1. 需要两个指针；
2. 先用n记录两个链表长度大小以便分清楚谁长谁短，n长度差记得取绝对值；
3. 长的走n步到和短的一样长的起点；
4. 两个指针一起走到相等的地方 就是交点 返回；

public static ListNode getNoLoop(ListNode headA, ListNode headB) {
	  if(headA == null || headB == null){
	      return null;
	  }
	  ListNode cur1 = headA;
	  ListNode cur2 = headB;
	  int n = 0;
	  while(cur1 != null){
		  n++;
		  cur1 = cur1.next;
	  }
	  while(cur2 != null){
		  n--;
		  cur2 = cur2.next;
	  }
	   if(cur1 != cur2){
		  return null;
	  }
	  cur1 = n > 0 ? headA : headB;//cur1指向长的头
	  cur2 = (cur1 == headA) ? headB : headA;//cur2指向短头
	  //将两个链表长度差取绝对值
	  n = Math.abs(n);
	  
	  //将指向长链表的指针cur1往下移动n,到达和短链表cur2指针与相交点相同距离的位置
	  while(n != 0){
		  n--;
		  cur1 = cur1.next;
	  }
	  //两个指针向下 相遇点便是相交点
	  while(cur1 != cur2){
		  cur1 = cur1.next;
		  cur2 = cur2.next;
	  }
	  return cur1;
         
  }	

有环链表相交

有环的链表比较复杂 有三种情况

1 两个入环节点相同 即相交在入环前 (loop1 =loop2)

2 两个相交在环内相交 有两个相交点

3 两个不相交

public static ListNode bothLoop(ListNode headA,ListNode loop1,ListNode headB, ListNode loop2){
		ListNode cur1 = null;
		ListNode cur2 = null;
		if(loop1 == loop2){//2 
			//方法与两个无环链表方法一样只不过把loop1/2看作结尾
			cur1 = headA;
			cur2 = headB;
			int n = 0;
			while(cur1 != loop1){
				  n++;
				  cur1 = cur1.next;
			  }
			  while(cur2 != loop2){
				  n--;
				  cur2 = cur2.next;
			  }
			  if(cur1 != cur2){
				  return null;
			  }
			  cur1 = n > 0 ? headA : headB;
			  cur2 = (cur1 == headA) ? headB : headA;
			  n = Math.abs(n);
			  while(n != 0){
				  n--;
				  cur1 = cur1.next;
			  }
			  while(cur1 != cur2){
				  cur1 = cur1.next;
				  cur2 = cur2.next;
			  }
			  return cur1;
		}else{
			//loop1往后移动 如果在遇到自己之前遇到了loop2就是情况3
			cur1 = loop1.next;
			while(cur1 != loop1){
				if(cur1 == loop2){
					return loop1;//3
					}
				}
				return null;//1
			}
}

6 环形链表

返回入环节点，没有环就返回null；

1.先将从头节点快慢指针开始往后，如果两个指针相遇那一定有环，期间如果快指针到null，可以直接判断无环。

2.如果要找到入环节点，就将fast指针指向head，slow不动，然后让两个指针都只移动一步，最后一定会在入环处相遇。

public static ListNode hasCycle(ListNode head) {
        if(head == null || head.next == null || head.next.next == null){
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while(slow != fast){
            if(fast.next ==  null || fast.next.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

7 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

1. 找到原表的中点
   1. 快慢指针从head开走
   2. fast.next == null || fast.next.next = null 返回慢指针
2. 将右半端反转：[反转链表](##1 反转链表##)
3. 将左右端合并

public void reorderList(ListNode head) {
		 public void reorderList(ListNode head) {
        if(head == null) { // ⚠️判空
            return;
        }
        ListNode mid = middleNode(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next =null; // ⚠️分离
        l2 = reverse(l2);
        mergeList(l1, l2);
    }

    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre; // ⚠️返回的是pre
    }

    // 合并过程就是使用两个指针来标志两个的下一个
    public void mergeList(ListNode l1, ListNode l2) {
        ListNode l1_next;
        ListNode l2_next;
        while(l1 != null && l2 != null) {
            l1_next = l1.next;
            l2_next = l2.next;

            l1.next = l2;
            l1 = l1_next;

            l2.next = l1;
            l2 = l2_next;
        }
    }
	}

8 删除链表重复节点

设置虚拟节点

往后遍历 （条件：cur的下一个和下下个都是空）
2.1如果当前两个节点值相等就将当前cur.next的值保存在x;

​ 循环（第一个节点后面的节点是否有重复的）cur.next指向不等于该x值的节点
​ 2.2 不相等就直接next

public ListNode deleteDuplicates(ListNode head) {
		 if(head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while(cur.next != null && cur.next.next != null){ // 当前节点下一个和下下个不为空
            if(cur.next.val == cur.next.next.val){ // 两个节点相等
                int x = cur.next.val; 
                while(cur.next != null && cur.next.val == x){ // 遍历第一个节点后面的节点是否有重复的 
                    cur.next = cur.next.next;// 有就直接讲指针指向下下个
                }
            } else { // 两个节点不相等 指针后移
                cur = cur.next;
            }
        }
        return dummy.next;
}

9 排序链表

就是给链表排序

public static ListNode sortList(ListNode head) {
		// 1 遍历一遍链表的长度
		int N = 0;
		ListNode cur = head;
		while (cur != null) {
			N++;
			cur = cur.next;
		}
		// 2 len是每次分组节点数 一直乘二
		ListNode h = head;
		ListNode teamFirst = head;
		ListNode pre = null;
		for (int len = 1; len < N; len <<= 1) {
			while (teamFirst != null) {
				// 3 F就是将五个参数处理返回方便利用
				// 左组从哪到哪   ls le
				// 右组从哪到哪   rs re
				// 左 右  next
				ListNode[] f1 = f(teamFirst, len);
				// ls...le  rs...re -> merge去
				// 整体的头、整体的尾
				ListNode[] f2 = merge(f1[0], f1[1], f1[2], f1[3]);
				if (h == teamFirst) {
					h = f2[0];
					pre = f2[1];
				} else {
					pre.next = f2[0];
					pre = f2[1];
				}
				teamFirst = f1[4];// next
			}
			teamFirst = h;
			pre = null;
		}
		return h;
	}

	public static ListNode[] f(ListNode teamFirst, int len) {
		// 返回五个参数
		ListNode ls = teamFirst;
		ListNode le = teamFirst;
		ListNode rs = null;
		ListNode re = null;
		ListNode next = null;
		int pass = 0;
		while (teamFirst != null) {
			pass++;
			if (pass <= len) {
				le = teamFirst;
			}
			if (pass == len + 1) {
				rs = teamFirst;
			}
			if (pass > len) {
				re = teamFirst;
			}
			if (pass == (len << 1)) {
				break;
			}
			teamFirst = teamFirst.next;
		}
		// 左边结尾断开
		le.next = null;
		// 记录右边结尾的next并断开结尾断开 
		if (re != null) {
			next = re.next;
			re.next = null;
		}
		return new ListNode[] { ls, le, rs, re, next };
	}

	public static ListNode[] merge(ListNode ls, ListNode le, ListNode rs, ListNode re) {
		if (rs == null) {
			return new ListNode[] { ls, le };
		}
		ListNode head = null;
		ListNode pre = null;
		ListNode cur = null;
		ListNode tail = null;
		while (ls != le.next && rs != re.next) {
			if (ls.val <= rs.val) {
				cur = ls;
				ls = ls.next;
			} else {
				cur = rs;
				rs = rs.next;
			}
			if (pre == null) {
				head = cur;
				pre = cur;
			} else {
				pre.next = cur;
				pre = cur;
			}
		}
		if (ls != le.next) {
			while (ls != le.next) {
				pre.next = ls;
				pre = ls;
				tail = ls;
				ls = ls.next;
			}
		} else {
			while (rs != re.next) {
				pre.next = rs;
				pre = rs;
				tail = rs;
				rs = rs.next;
			}
		}
		return new ListNode[] { head, tail };
	}

10 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		//两个链表分长短
		//分为三个阶段 ：1 长短都还有节点 2 短没有节点 长有节点 3 长也走到没节点
		ListNode l = listLength(l1) > listLength(l2) ? l1 : l2;
		ListNode s = (l == l1) ? l2 : l1;
		ListNode curl = l;
		ListNode curs = s;
		
		int carry = 0;
		int curNum = 0;
		ListNode last = curl;
		
		
		//1 
		while(curs != null){
			curNum = curs.val + curl.val + carry;
			carry = curNum / 10;
			curl.val = curNum % 10;
			last = curl;//last一直在抓住最后一个节点
			curl = curl.next;
			curs = curs.next;
		}
		
		//2 
		while(curl != null){
			curNum =  curl.val + carry;
			carry = curNum / 10;
			curl.val = curNum % 10;
			last = curl;//last一直在抓住最后一个节点
			curl = curl.next;
		}
		
		//3 到
		if(carry != 0){
			last.next = new ListNode(1);
		}
		return l;
	}
	
	
	
	public static int listLength(ListNode l){
		int length = 0;
		while(l != null){
			length++;
			l = l.next;
		}
		return length;
	}

11 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

public class Fre_070_removeNthFromEnd {
 public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        while(k - 1 != 0){
            fast = fast.next;
            k--;
        }

        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

12 删除链表倒数第k个节点

public ListNode removeNthFromEnd(ListNode head, int n) {
       ListNode dummy = new ListNode(-1);
       dummy.next = head;
  			// 1 用两个指针截出n+1长度
       ListNode slow = dummy;
       ListNode fast = head;
       for(;n>0;n--){
           fast=fast.next;
       }
  			// 2 两个指针一直往后直到fast到结尾
       while(fast != null){
           fast = fast.next;
           slow = slow.next;
       }
  			// 3 slow在目标的前面一位 直接将next指针指向下下位 
       slow.next = slow.next.next;
       return dummy.next;// 使用虚拟节点以防删除的是头节点
   }

13 回文链表

需要convert 和 然后判断对称 然后再convert恢复回去

public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        // 1 现在slow就走到了中间（偶数是上中）
        // 2 将后半部分convert
        ListNode l1 = null; //pre
        ListNode l2 = slow.next;
        ListNode l3 = null;
        while(l2 != null){
            l3 = l2.next;
            l2.next = l1;
            l1 = l2;
            l2 = l3;
        }

        // 3 后面部分已经翻转 现在对比两部分是否对称
        boolean ans = true;
        l2 = head;
        l3 = l1;
        while(l3 != null){
            if(l2.val != l3.val){ // ⚠️比较val
                ans = false;
                break;
            }
            l2 = l2.next;
            l3 = l3.next;
        }

        // 4 把后半部分又恢复原样
        l2 = null;// pre
        l3 = null;// next
        while(l1 != null){
            l3 = l1.next;
            l1.next = l2;
            l2 = l1;
            l1 = l3;
        }
        slow.next = l2;

        return ans;
    }

14 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

删除重复元素 留下一个
直接快慢指针

public ListNode deleteDuplicates(ListNode head) {
       if(head == null){
           return null;
       }
       ListNode ans = head;
       ListNode left = head;
       ListNode right = head.next;

       while( right != null) {
           ListNode next = right.next;
           if(left.val == right.val) {
               left.next = next;
               right.next = null;
           } else{
               left =  right;
           }

           right = next;
       }
       return ans;
   }

15 复制带有随机指针的链表

/*
 * 深度复制带有rand的链表
 */
public class LiaoBiao_copyListWithRandom {
	public static class Node {
		public int value;
		public Node next;
		public Node rand;

		public Node(int data) {
			value = data;
		}
	}
	
	/*
	 * 最优解：人工构造关系
	 * 1 每一个节点后面加一个克隆节点
	 * 2 遍历关系 （同时复制rand
	 * 3 遍历分离（同时复制next
	 */
    public static Node copyListWithRandom(Node head){
    	if(head == null){ return null; }
    	Node cur = head;
    	Node next = null;
    	// 1
    	while(cur != null){
    		next = cur.next;
    		cur.next = new Node(cur.value);
    		cur.next.next = next;
    		cur = next;
    	}
    	
    	cur = head;
    	Node curCopy = null;
    	// 2
    	while(cur != null){
    		next = cur.next.next;
    		curCopy = cur.next;
    		curCopy.rand = cur.rand != null ? cur.rand.next : null;
    		cur = next;
    	}
    	
    	cur = head;
    	Node res = head.next;
    	// 3
    	while(cur != null){
    		next = cur.next.next;
    		curCopy = cur.next;
    		curCopy.next = cur.next != null ? cur.next.next : null;
    		cur = next;
    	}
    	return res;
	}
	
    /**
     * 使用hashMap一一对应关系
     * 1 遍历第一遍一一对应
     * 2 遍历第二遍复制关系
     * @param head
     * @return
     */
	public static Node copyListWithRandom2(Node head){
		HashMap<Node, Node> map = new HashMap<>();
		Node cur = head;
		// 1 
		while(cur != null){
			map.put(cur, new Node(cur.value));
			cur = cur.next;
		}
		
		cur = head;
		// 2
		while(cur != null){
			map.get(cur).next = map.get(cur.next);
			map.get(cur).rand = map.get(cur.rand);
			cur = cur.next;
		}
		
		return map.get(head);
		
	}
}

2 动态规划

具体步骤 可以参考[零钱兑换](###2 返回凑齐的所有方法数)

基础问题 背包问题

/**
 * 传入货物的重量和价值 不能超过bag背包容量，返回最大价值
 * 
 * @author chs
 *
 */
public class DP2_knapsack {
	/**
	 * 暴力递归
	 */
	public static int maxValue(int[] w, int[] v, int bag) {
		if (w == null || v == null || w.length == 0) {
			return 0;
		}
		return process(w, v, 0, bag);
	}

	public static int process(int[] w, int[] v, int i, int rest) {
		if (rest < 0) {
			return -1;
		}
		if (i == w.length) {
			return 0;
		}
		// 加上i
		int p1 = process(w, v, i + 1, rest - w[i]);
		// 没加
		int p2 = process(w, v, i + 1, rest);

		if (p1 != -1) {
			p1 += v[i];
		}
		return Math.max(p1, p2);
	}
   
	/**
	 * 动态规划版
	 */
	public static int dp(int[] w, int[] v, int bag) {
		if (w == null || v == null || w.length != v.length || w.length == 0) {
			return 0;
		}
		int N = w.length;
		int[][] dp = new int[N + 1][bag + 1];
		for(int i = N - 1; i >= 0; i --){
			for(int j = 0; j <= bag; j ++){
				int ans = 0;
				if(j - w[i] >= 0){
					ans = dp[i + 1][j - w[i]] + v[i];
				}else{
					ans = dp[i + 1][j];
				}
				dp[i][j] = Math.max(dp[i+1][j], ans);
			}
		}
		return dp[0][bag];

	}
	
	

1. 最大子数组和

用贪心

只需要一个pre反复更新记录以i为底的最大累加和，然后max存最大的

//用两个变量存
	public static int maxSubArray4(int[] nums){
		if (nums.length == 0 || nums == null) {
			return 0;
		}
        int max = nums[0];
        int pre = 0;
		for(int i = 0; i < nums.length; i++){
			pre = Math.max(pre + nums[i], nums[i]);
			max = Math.max(pre, max);
        }
		return max;
	}

如果需要返回该子数组

int res = nums[0], l = 0, r = 0;
for (int i = 0; i < nums.size(); i++) {
	if (nums[i - 1] < 0) {
		l = i;
	}
	nums[i] += max(0, nums[i - 1]);
	if (res < nums[i]) {
		r = i;
		res = nums[i];
	}
}

2. 买卖股票的最佳时机 maxProfit

(1) 从头至尾买一次一股 返回最大利润:

遍历一遍 min标记， max最大利润更新 就是找到最低点和最高点

class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice) {
                minprice = prices[i];
            } else if (prices[i] - minprice > maxprofit) {
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

(2) 买一股但是可以买无限次

遍历累加所有的爬坡

// 一股随便买
	// 相当于在每次爬坡前后买卖 将所有爬坡累加就行
	public static int maxProfit2(int[] prices) {
		if (prices == null || prices.length == 0) {
			return 0;
		}
		int ans = 0;
		for(int i = 1; i < prices.length; i++){
			ans += prices[i] - prices[i - 1] >= 0 ? prices[i] - prices[i - 1] : 0;
		}
		return ans;
	}

3. 最长回文子串

(1) 动态规划O(N^2)

/**
    * 自己改动态规划
    * @param s
    * @return
    */
   public String longestPalindrome33(String s) {
       if (s.length() < 2) {
           return s;
       }
       char[] str = s.toCharArray();
       int N = str.length;
       boolean[][] dp = new boolean[N][N];
       for(int i = 0; i < N; i++) {
           dp[i][i] = true;
       }
       //边填dp 边抓最长和该最长开始节点
       int max = 1;
       int index = 0;

      //按对角线遍历 
      // 最外循环不是dp的坐标
      // i代表了n - len 每个循环行是不变的 
      // j是横坐标L
       for(int i = N - 1; i > 0; i--){
           for(int L = 0; L < i; L++){
               int R = L + N - i;
               if(str[L] == str[R]){
                   if(R - L < 3){
                       dp[L][R] = true;
                   }else{
                       dp[L][R] = dp[L + 1][R - 1];
                   }
               }
               if(dp[L][R] && R - L + 1 > max){
                   max = R - L + 1;
                   index = L;	
               }
           }
       }
       return s.substring(index, index + max);
   }

(2) Manacher!

面试讲一讲

假设字符串str长度为N，想返回最长回文子串的长度

时间复杂度O(N)

Manacher算法核心

1）理解回文半径数组
2）理解所有中心的回文最右边界R，和取得R时的中心点C
3）理解 L…(i’)…C…(i)…R 的结构，以及根据i’回文长度进行的状况划分
4）每一种情况划分，都可以加速求解i回文半径的过程

最长回文子串就是我知道可以进行。

最长回文子序列

子序列就是三种情况 L+1 ~R 和 L ~ R-1 和 L +1 ~ R - 1

public int longestPalindromeSubseq(String s) {
      public int longestPalindromeSubseq(String s) {
       if(s.length() == 0 || s == ""){
           return 0;
       }

       char[] str = s.toCharArray();
       int N = str.length;
       int[][] dp = new int[N][N];

       for(int i = 0; i < N; i++){
           dp[i][i] = 1;
       }
       //对角线遍历
       for(int i = N - 1; i >= 0; i--){
         for(int L = 0; L < i; L++){
           int R = L + N - i;
           dp[L][R] = Math.max(dp[L + 1][R],dp[L][R - 1]);
           if(str[L] == str[R]){
             dp[L][R] = Math.max(dp[L + 1][R - 1] + 2, dp[L][R]);
           }
				}
       }
       return dp[0][N - 1];
      }