leetcode100-1

哈希

​ 利用哈希集合或者哈希表来解题

1. 两数之和

public class A1_1 {
    public int[] twoSum(int[] nums, int target) {
        int length = nums.length;
        //暴力解法
        for (int i = 0; i < length; i++) {
            int before = nums[i];
            for (int j = i+1; j < length; j++) {
                int after = nums[j];
                if((before + after) == target){
                    return new int[]{i,j};
                }

            }
        }
        //进阶解法，借用hash表
//        Map<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < length; i++) {
//            if(map.containsKey(target - nums[i])){
//                return new int[]{map.get(target - nums[i]),i};
//            }
//            map.put(nums[i],i);
//        }
        return null;
    }
}

49. 字母异位词分组

题意：把是字母异味词的字符放到一个集合里，输出所有集合

public class A_49 {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sortStr = Arrays.toString(chars);
            if(map.containsKey(sortStr)){
                map.get(sortStr).add(str);
            }else{
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(sortStr,list);
            }
        }
        return new ArrayList<>(map.values());
    }
    public static void main(String[] args) {
        A_49 ins = new A_49();
        System.out.println(ins.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
    }
}

128. 最长连续序列

结题思路：

1、利用set存储所有元素，O(1)时间内判断是否拥有某个元素

2、外层遍历nums，只穷举set没有num-1的数，这样只需要递归往num+1的方向查找，整体来说外层一次for循环遍历了n次，内层while总共加起来=n次，总共2n次，所以时间复杂度是O(N)

public class A_128{
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i]-1)){
                continue;
            }else{
                int cur = nums[i];
                int continueLength = 1;
                while(set.contains(cur+1)){
                    cur++;
                    continueLength++;
                }
                max = Math.max(max,continueLength);
            }
        }
        return max;
    }

    public static void main(String[] args){
        A_128 instance = new A_128();
        System.out.println(instance.longestConsecutive(new int[]{100,4,200,1,3,2}));
        System.out.println(instance.longestConsecutive(new int[]{1,2,0,1}));
    }
}

双指针

283. 移动零

public void moveZeroes(int[] nums) {
	int j = 0;
    for (int i = 0; i < nums.length; i++) {
        if(nums[i] == 0){
            //1、找到0
            //2、找到0右边的非0
            j = Math.max(j,i+1);
            while(j < nums.length && nums[j] == 0){
                j++;
            }
            if(j < nums.length){
                swap(nums,i,j);
            }
        }

    }
}

public void swap(int[] nums,int left,int right){
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

public static void main(String[] args){
    A1_283 instance = new A1_283();
    int[] nums = {1,0,1};
    instance.moveZeroes(nums);
    for(int num : nums){
        System.out.print(num+ " ");

    }
}

11. 盛最多水的容器

结题思路：左右指针分别位于2端，假设 leftValue < rightValue，则向右移动leftIndex（因为即便向左移动了右端，左值与右值的较小数也不会大于左值，但2端的宽度变小，面积必然小于移动前，因此向左移动右端只会越来越小，这个左指针对应的数不会作为容器的边界了，一开始在左端，因此只能向右移动）

public int maxArea(int[] height) {
    int area = 0;
    int beforeMax = 0;
    int l = 0;
    int r = height.length-1;
    while(l < r){
        int left = height[l];
        int right = height[r];
        beforeMax = (r - l) * Math.min(left,right);
        area = Math.max(beforeMax,area);
        if(left < right){
            l++;
        }else{
            r--;
        }
    }
    return area;
}

public static void main(String[] args) {
    A2_11 ins = new A2_11();
    int[] nums = {1,8,6,2,5,4,8,3,7};
    System.out.println(ins.maxArea1(nums));
}

15. 三数之和

​ 解题思路：从暴力解法出发，思考如何降低复杂度。排序后，固定第一个数，问题转化成第二个数+第三个数之和=某个固定数，利用双指针指向第2、3个数。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    if(nums == null || nums.length <3){
        return result;
    }
    Arrays.sort(nums);
    //排序后，固定第一位,后两位用双指针，类似与2数之和=0
    for (int i = 0; i < nums.length; i++) {
        int first = nums[i];
        //第一个数大于0，提前结束
        if(first > 0){
            break;
        }
        //前一个数和当前数相等，跳过当前数
        if(i > 0 && nums[i] == nums[i-1] ) {
            continue;
        }
        //采用双指针
        int l = i+1;
        int r = nums.length - 1;
        while(l < r){
            int second = nums[l];
            int third = nums[r];
            int sum = first + second + third;
            if(sum == 0){
                result.add(Arrays.asList(first,second,third));
                //左移和后移动左边界和右边界重复的情况
                while(l < r && nums[l] == nums[l+1]){
                    l++;
                }
                while(l < r && nums[r] == nums[r-1]){
                    r--;
                }
                l++;
                r--;
            }else if(sum > 0){
                r--;
            }else {
                l++;
            }
        }


    }
    return result;
}

/**
     * 双指针 + map(结合两数字之和的解法)
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if(null == nums || nums.length < 3){
            return result;
        }
        Map<Integer,Integer> map = new HashMap<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //重复则存取大的下标
            map.put(nums[i],i);
        }
        for (int i = 0; i < nums.length; i++) {
            if(i>0 && nums[i]== nums[i-1]){
                continue;
            }
            for (int j = i+1; j < nums.length; j++) {
                if(j != i+1 && nums[j]== nums[j-1]){
                    continue;
                }
                int pre = -(nums[i] + nums[j]);
                if(map.containsKey(pre) && map.get(pre) > j){
                    result.add(Arrays.asList(nums[i],nums[j],pre));
                }
            }
        }
        return result;
    }

42. 接雨水

​ 结题思路：对于每个格子来说，当前格子能接到的雨水取决于左右2边是否都大于当前高度，且当前格子的水量=min（左边最高高度，右边最高高度）- 当前高度，先通过遍历维护每个格子的左、右最高高度，减少时间复杂度

​ 想通过

//简化左右边最高列的算法
public int trap1(int[] height) {
    if(height.length < 3){
        return 0;
    }
    int sum = 0;
    int[] leftHeight = new int[height.length];
    int[] rightHeight = new int[height.length];
    for (int i = 1; i < height.length; i++) {
        leftHeight[i] = Math.max(height[i-1],leftHeight[i-1]);
    }
    for (int i = height.length-2; i >=0; i--) {
        rightHeight[i] = Math.max(height[i+1],rightHeight[i+1]);
    }
    for (int i = 0; i < height.length; i++) {

        int cur = height[i];
        int relativeMin = Math.min(leftHeight[i],rightHeight[i]);
        if(relativeMin <= cur){
            sum += 0;
        }else{
            sum += (relativeMin - cur);
        }
    }
    return sum;
}

滑动窗口

3. 无重复字符的最长子串

​ 解题思路：滑动窗口，顾名思义，可以通过问题映射控制窗口的2边，先滑动右边，达到特殊条件时，缩小左边，直至右边划到终点。该题就是通过map来判断是否应该继续右边滑动，

public int lengthOfLongestSubstring(String s) {
    int left = 0;
    int right = 0;
    int count = 0;

    Map<Character,Integer> map = new HashMap<>();
    while (right < s.length()){
        char c = s.charAt(right);

        if(map.containsKey(c) && map.get(c) >= left){
            //更新重复字符的下标
            count = Math.max(count,right - left);
            left = map.get(c) + 1;
            map.put(c,right);
        }else{
            map.put(c,right);
            count = Math.max(count,right - left + 1);
        }

        right++;
    }
    return count;
}

438. 找到字符串中所有字母异位词

结题思路：窗口的滑动条件比第一题复杂：初始化p的字符数组然后维护数组每个元素不小于0。 开始向右滑动窗口，减去并相应字符，如果频率小于0就收缩左侧边界直到频率不再小于0。窗口长度与p长度一致时达成条件

public List<Integer> findAnagrams(String s, String p) {
    int pLength = p.length();
    List<Integer> result = new ArrayList<>();
    //pCount维护还需要的下标数量
    int[] pCount= new int[26];
    for (int i = 0; i < pLength; i++) {
        ++pCount[p.charAt(i) - 'a'];
    }
    int l = 0;
    int r = 0;
    while(r < s.length()){
        char rChar = s.charAt(r);
        --pCount[rChar - 'a'];
        //右边走过头了，左移直到pCount[rChar - 'a'] = 0:效果等同于l跳到窗口内左边第一个rChar的下一个位置
        while(pCount[rChar - 'a'] < 0 && l <= r){
            ++pCount[s.charAt(l) - 'a'];
            l++;
        }
        //pCount的字母数量保证起大于等于0,此时数量一致代表满足条件
        if(r - l + 1 == pLength){
            result.add(l);
        }
        r++;
    }
    return result;

}

/**
 * 滑动窗口+map：维护需要p字符的数量
 * @param s
 * @param p
 * @return
 */
public List<Integer> findAnagrams1(String s, String p) {
    int pLength = p.length();
    List<Integer> result = new ArrayList<>();
    Map<Character,Integer> needCount = new HashMap<>();
    for (int i = 0; i < pLength; i++) {
        char c = p.charAt(i);
        needCount.put(c,needCount.getOrDefault(c,0)+1);
    }
    int l = 0;
    int r = 0;
    while(r < s.length()){
        char rchar = s.charAt(r);
        //需要数量-1
        needCount.put(rchar,needCount.getOrDefault(rchar,0)-1);
        while(needCount.get(rchar) < 0 && l <= r){
            char lchar = s.charAt(l);
            needCount.put(lchar,needCount.get(lchar)+1);
            l++;
        }
        if(r - l + 1 == pLength){
            result.add(l);
        }
        r++;
    }
    return result;

}

子串

560. 和为 K 的子数组

​ 解题思路：pre[i] = [0..i]的所有数的和，则pre[i] = pre[i-1] + nums[i] ,那么sum[j..i] = k则表示为

pre[i] - pre[j-1] = k ==> pre[j-1] = pre[i] - k，如果pre[j-1]存在，则结果集加一

/**
 * 前缀和+hash法
 * @param nums
 * @param k
 * @return
 */
public int subarraySum2(int[] nums, int k) {
   int count = 0;
   //前缀和
   int pre = 0;
   //key：pre=前缀和，value=出现的次数
   Map<Integer,Integer> dataMap = new HashMap<>();
   //初始化空集的场景
   dataMap.put(0,1);
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        pre += num;
        if(dataMap.containsKey(pre-k)){
            count += dataMap.get(pre-k);
        }
        dataMap.put(pre,dataMap.getOrDefault(pre,0) + 1);
    }
    return count;
}

239. 滑动窗口最大值

​ 解题思路：基础解法是滑动窗口，窗口内的维护逻辑利用大顶堆，值大的在堆顶，每次取出堆顶时，判断堆顶元素的下标是不是超过左边界，因此堆的存储内容是int[],第一个元素存储值，第二个元素存储下标

/**
 * 利用大顶堆
 * @param nums
 * @param k
 * @return
 */
public int[] maxSlidingWindow2(int[] nums, int k) {
    int length = nums.length;
    int[] ras = new int[length-k+1];
    Queue<int[]> queue = new PriorityQueue<int[]>((e1,e2) -> {
        if(e2[0] != e1[0]){
            return e2[0] - e1[0];
        }else{
            return e2[1] - e1[1];
        }
    });
    for (int i = 0; i < length; i++) {
        int num = nums[i];
        queue.offer(new int[]{num,i});
        while(queue.peek()[1] <= i - k){
            queue.poll();
        }
        if(i >= k-1){
            ras[i-k+1] = queue.peek()[0];
        }
    }

    return ras;
}

/**
 * 利用单调递减队列（双端队列）,存储下标值
 * @param nums
 * @param k
 * @return
 */
public int[] maxSlidingWindow(int[] nums, int k) {
    //单调递减队列，存储的是nums的下标值
    LinkedList<Integer> queue = new LinkedList();
    // 窗口个数
    int[] result = new int[nums.length - k + 1];
    for (int right = 0; right < nums.length; right++) {
        // 如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
        // 直到，队列为空或当前考察元素小于新的队尾元素
        while(!queue.isEmpty() && nums[right] > nums[queue.getLast()]){
            queue.removeLast();
        }
        queue.addLast(right);
        int left = right - k + 1;
        //判断左窗口是否已超过队首下标
        if(queue.peekFirst() < left){
            queue.removeFirst();
        }
        //窗口是否已形成
        if(right + 1 >= k ){
            result[left] = nums[queue.peekFirst()];
        }
    }
    return result;
}

76. 最小覆盖子串

解题思路：该题的突破点还是在滑动窗口内，使用合适的数据结构配合，来确认窗口内是否满足覆盖t的所有字符，而且t中字符存在重复的场景；

1、适用int[] tFreq来表示t中需要出现字符的次数

2、使用needCount表示窗口内还缺少的t中字符的个数，用该变量来判断是否满足串口覆盖t

3、其中tFreq的某个字符频次<0时，比如=-1，其实是非t中字符出现了，原本是0，r右移多出了一个无关字符-1，l右移时，对应加上1即可

public String minWindow(String s, String t) {
        int sLength = s.length();
        int tLength = t.length();
        int match = 0;
        if(sLength < tLength){
            return "";
        }
        String result = "";
        int[] tNeedCount = new int[128];
        for (int i = 0; i < tLength; i++) {
            tNeedCount[t.charAt(i)]++;
        }
        int l,r;
        l = r = 0;
        while (r < sLength){
            //1、向右扩展，直到数量满足
            char rchar = s.charAt(r);
            if(tNeedCount[rchar] > 0){
                match++;
            }
            tNeedCount[rchar]--;
            if(match == tLength){
                //2、左边尝试收缩
                while(tNeedCount[s.charAt(l)] < 0){
                    tNeedCount[s.charAt(l)]++;
                    l++;
                }
                //3、处理结果
                result = (r-l+1 < result.length() || result.isEmpty())?s.substring(l,r+1):result;
                //右移左边界，开始下一轮探索
                tNeedCount[s.charAt(l++)]++;
                --match;
            }
            r++;
        }
        return result;
    }

普通数组

53. 最大子数组和

解题思路：f(x) = Math.max(nums[x],nums[x]+f(x-1)),f(x):以x结尾的连续子数组的最大和

/**
 * 动态规划
 * f(x) = Math.max(nums[x],nums[x]+f(x-1)),f(x):以x结尾的连续子数组的最大和
 * {-2,1,-3,4,-1,2,1,-5,4}
 * {-2,-1,-3,4,3,5,6,1,5}
 * @param nums
 * @return
 */
public int maxSubArray1(int[] nums) {
    //pre代表f(x-1)
    int pre = 0;
    int maxAns = nums[0];
    for (int x : nums) {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
}

56. 合并区间

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals,(e1,e2) -> e1[0] - e2[0]);
    List<int[]> result = new ArrayList<>();
    for (int i = 0; i < intervals.length; i++) {
        if(i == 0){
            result.add(intervals[0]);
            continue;
        }
        int[] pre = result.get(result.size()-1);
        int[] cur = intervals[i];
        if(pre[1] < cur[0]){
            result.add(cur);
        }else {
            //合并到上一个区间
            pre[1] = Math.max(pre[1],cur[1]);
        }
    }

    return result.toArray(new int[result.size()][]);
}

189. 轮转数组

解题思路：这里采用额外空间结题

1、利用额外数组存储计算后的值

2、利用翻转算法

public void rotate(int[] nums, int k) {
    int length = nums.length;
    int addK = k % length;
    if(addK == 0){
        return;
    }else{
        int[] result = new int[length];
        for (int i = 0; i < length; i++) {
            int nextIndex = (i + addK) % length;
            result[nextIndex] = nums[i];
        }
        for (int i = 0; i < result.length; i++) {
            nums[i] = result[i];
        }
    }
}

238. 除自身以外数组的乘积

题解：f(i)=beforeMulti(i) * afterMulti(i):i之前数组的乘积 + i之后元素素组的乘积

/**
 * beforeMulti[i]:i之前数组的乘积
 * afterMulti[i]:i之后元素素组的乘积
 * f(i)=beforeMulti(i) * afterMulti(i):i之前数组的乘积 + i之后元素素组的乘积
 * @param nums
 * @return
 */
public int[] productExceptSelf2(int[] nums) {
    int[] result = new int[nums.length];
    int[] beforeMulti = new int[nums.length];
    int[] afterMulti = new int[nums.length];
    int multi = 1;
    for (int i = 0; i < nums.length; i++) {
        if(i == 0){
            beforeMulti[i] = multi;
        }else{
            beforeMulti[i] = beforeMulti[i-1] * nums[i-1];
        }
    }
    multi = 1;
    for (int i = nums.length-1; i >= 0; i--) {
        if(i == nums.length-1){
            afterMulti[i] = multi;
        }else{
            afterMulti[i] = afterMulti[i+1] * nums[i+1];
        }
    }
    for (int i = 0; i < nums.length; i++) {
        result[i] = beforeMulti[i] * afterMulti[i];
    }
    return result;
}

41. 缺失的第一个正数

​ 题解：如果利用map，可以遍历一次后维护所有key，遍历x属于1到N+1,判断key如果不存在x，则答案=x

1、但是map的空间复杂度=O(N)，map可以在O(1)时间内判断x是否出现过

2、我们要找的数就在 [1, N + 1] 里，最后 N + 1 这个元素我们不用找。因为在前面的 N 个元素都找不到的情况下，我们才返回 N + 1；那么，我们可以采取这样的思路：就把 1 这个数放到下标为 0 的位置， 2 这个数放到下标为 1 的位置，按照这种思路整理一遍数组。然后我们再遍历一次数组，第 1 个遇到的它的值不等于下标的那个数，就是我们要找的缺失的第一个正数。这个思想就相当于我们自己编写哈希函数，这个哈希函数的规则特别简单，那就是数值为 i 的数映射到下标为 i - 1 的位置。

/**
 * 把数组当成hash
 * @param nums
 * @return
 */
public int firstMissingPositive(int[] nums) {
    int length = nums.length;
    for (int i = 0; i < length; i++) {
        while(0 < nums[i] && nums[i] <= length && nums[nums[i]-1] != nums[i]){
            swap(nums,i,nums[i]-1);
        }
    }
    for (int i = 0; i < length; i++) {
        if(nums[i] != i+1){
            return i+1;
        }
    }
    return length + 1;
}

public static void swap(int[] arr,int left,int right){
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

矩阵

73. 矩阵置零

public void setZeroes(int[][] matrix) {
    int xLength = matrix.length;
    int yLength = matrix[0].length;
    //利用2个一维数组表示，x和y轴上是否出现过0
    boolean[] x = new boolean[xLength];
    boolean[] y = new boolean[yLength];
    for (int i = 0; i < xLength; i++) {
        for (int j = 0; j < yLength; j++) {
            if (matrix[i][j] == 0) {
                x[i] = y[j] = true;
            }
        }
    }
    for (int i = 0; i < xLength; i++) {
        for (int j = 0; j < yLength; j++) {
            if (x[i] || y[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

54. 螺旋矩阵

**解题思路:**从左到右，上到下，右到左，下到上轮流遍历

private List<Integer> spiralOrder1(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if(Objects.isNull(matrix) || matrix.length == 0){
        return result;
    }

   int left = 0;
   int right = matrix[0].length - 1;
   int top = 0;
   int bottom = matrix.length - 1;
   int x = 0,y = 0;
   int resultCount = (right+1) * (bottom+1);
   while(resultCount != result.size()){
       //从左到右
       for (int i = left; i <= right && resultCount != result.size(); i++) {
           result.add(matrix[top][i]);
       }
       top++;
       //从上到下
       for (int i = top; i <= bottom && resultCount != result.size(); i++) {
           result.add(matrix[i][right]);
       }
       right--;
       //从右到左
       for (int i = right; i >= left && resultCount != result.size(); i--) {
           result.add(matrix[bottom][i]);
       }
       bottom--;
       //从下到上
       for (int i = bottom; i >= top && resultCount != result.size(); i--) {
           result.add(matrix[i][left]);
       }
       left++;
   }
    return result;
}

48. 旋转图像

/**
	 * 原地旋转
  * 1、找规律，旋转90度后
  * [i,j] => [j,n-1-i]
  * [j,n-1-i] => [n-1-i,n-1-j]
  * [n-1-i,n-1-j] => [n-1-j,i]
  * [n-1-j,i] => [i,j]
  *
  * 调整顺序得
  * [n-1-j,i] => [i,j]
  * [n-1-i,n-1-j] => [n-1-j,i]
  * [j,n-1-i] => [n-1-i,n-1-j]
  * [i,j] => [j,n-1-i]
  *
  * 2、利用一个临时变量存储[i,j]
  * @param matrix
  */
 public void rotate1(int[][] matrix) {
     int n = matrix.length;
     for (int i = 0; i < (n+1) / 2; i++) {
         for (int j = 0; j < n / 2; j++) {
             int temp = matrix[i][j];
             matrix[i][j] = matrix[n-1-j][i];
             matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
             matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
             matrix[j][n-1-i] = temp;
         }
     }
 }

/**
  * 新增一个辅助数组
  * [i,j] => [j,n-1-i] ==> matrix_new[j,n-1-i] = 则matrix[i,j]
  * @param matrix
  */
 public void rotate(int[][] matrix) {
     int n = matrix.length;
     int[][] matrix_new = new int[n][n];
     for (int i = 0; i < n; ++i) {
         for (int j = 0; j < n; ++j) {
             matrix_new[j][n-i-1] = matrix[i][j];
         }
     }
     for (int i = 0; i < n; ++i) {
         for (int j = 0; j < n; ++j) {
             matrix[i][j] = matrix_new[i][j];
         }
     }
 }

240. 搜索二维矩阵 II

/**
 * 从左下角开始查找，
 * 当前位置 = target，true，
 * 当前位置 > target，向上找、
 * 当前位置 < target，向右找、
 * @param matrix
 * @param target
 * @return
 */
public boolean searchMatrix1(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;
    int i = row-1;
    int j = 0;
    while(i >= 0 && j <= col-1){
        if(matrix[i][j] == target){
            return true;
        }else if(matrix[i][j] > target){
            i--;
        }else{
            j++;
        }
    }
    return false;
}

链表

160. 相交链表

解题思路：

1、利用List存储某一个链表，让后遍历第二个链表

2、利用a + b + c = b + c +a的原理，两边同时遍历，遍历到尾后从另一个链表头从新开始，如果有交点，则会在交点相遇；

/**
 * 利用a + b + c = b + c  +a的原理，两边同时遍历，遍历到尾后从另一个链表头从新开始，
 * 如果有交点，则会在交点相遇；
 * @param headA 
 * @param headB
 * @return
 */
public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
        return null;
    }
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

206. 反转链表

解题思路：

1、迭代处理

2、递归算法

	/**
    * 递归算法
    *
    * @param head
    * @return
    */
   public ListNode reverseList1(ListNode head) {
       ListNode listNode = head;
       if (head != null && head.next != null) {
           listNode = reverseList1(head.next);
           head.next.next = head;
           head.next = null;
       }
       return listNode;
   }
/**
    * 迭代
    * @param head
    * @return
    */
   public ListNode reverseList(ListNode head) {
       ListNode prev = null;
       ListNode curr = head;
       while(curr != null){
           ListNode temp = curr.next;
           curr.next = prev;
           prev = curr;
           curr = temp;

       }
       return prev;
   }

234. 回文链表

/**
 * 先转化成数组
 * @param head
 * @return
 */
public boolean isPalindrome2(ListNode head) {
    List<ListNode> list = new ArrayList<>();
    ListNode cur = head;
    while(null != cur){
        list.add(cur);
        cur = cur.next;
    }
    int beginIndex = 0;
    int lastIndex = list.size()-1;
    while(beginIndex < lastIndex){
        if(list.get(beginIndex).val != list.get(lastIndex).val){
            return false;
        }
        beginIndex++;
        lastIndex--;
    }
    return true;
}

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while(curr != null){
        ListNode temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;

    }
    return prev;
}
/**
     * 反转链表-整个流程可以分为以下五个步骤：
     * 1、找到前半部分链表的尾节点。
     * 2、反转后半部分链表。
     * 3、判断是否回文。
     * 4、恢复链表。
     * 5、返回结果。
     * @param head
     * @return
     */
public boolean isPalindrome1(ListNode head) {
    if(head == null){
        return false;
    }
    ListNode left = head;
    ListNode rigth = head;
    while (rigth.next != null && rigth.next.next!=null){
        rigth = rigth.next.next;
        left = left.next;
    }
    ListNode reverseHead = reverseList(left.next);
    ListNode leftNodeHead = head;
    ListNode rightNodeHead = reverseHead;
    while(rightNodeHead != null){
        if(leftNodeHead.val != rightNodeHead.val){
            return false;
        }
        rightNodeHead = rightNodeHead.next;
        leftNodeHead = leftNodeHead.next;
    }
    reverseHead = reverseList(reverseHead);
    return true;
}

141. 环形链表

解题思路：

1、利用list，一边遍历一边判断是否包含

2、快慢指针

public boolean hasCycle(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    while(head != null){
        if(nodes.contains(head)){
            return true;
        }
        nodes.add(head);
        head = head.next;

    }
    return false;
}

/**
 * 快慢指针
 * @param head
 * @return
 */
public boolean hasCycle1(ListNode head) {
    ListNode slow = new ListNode(0,head);
    ListNode fast = new ListNode(0,head);;
    while((slow != null && fast != null)){
        slow = slow.next;
        fast = fast.next == null?null:fast.next.next;
        if(fast != null && slow == fast){
            return true;
        }
    };
    return false;
}

142. 环形链表 II

public ListNode detectCycle(ListNode head) {
    List<ListNode> nodes = new ArrayList<>();
    while(head != null){
        if(nodes.contains(head)){
            return head;
        }
        nodes.add(head);
        head = head.next;

    }
    return null;
}

/**
 * 快慢指针法
 * 1、假设存在环，a:head到入环点,b:入环点到快慢指针的相交点,c:相交点到入环点的距离
 * 则根据快慢指针有：a+b+n(b+c) = 2(a+b) => a = (n-1)(b+c)+c
 * 即：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。
 * 即一个从相遇点出发，一个从开头出发，会在入环点相交
 * @param head
 * @return
 */
public ListNode detectCycle(ListNode head) {
    ListNode slow = new ListNode(0,head);
    ListNode fast = new ListNode(0,head);
    while((slow != null && fast != null)){
        slow = slow.next;
        fast = fast.next == null?null:fast.next.next;
        if(slow != null && slow == fast){
            ListNode preHead = new ListNode(0,head);
            while(preHead != slow){
                preHead = preHead.next;
                slow = slow.next;
            }
            return slow;
        }
    };
    return null;
}

21. 合并两个有序链表

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
       ListNode pre = new ListNode(-1);
       ListNode cur = pre;
       while(list1 != null && list2 != null){
           if(list1.val <= list2.val){
               cur.next = list1;
               list1 = list1.next;
           }else{
               cur.next = list2;
               list2 = list2.next;
           }
           cur = cur.next;
       }
       if(list1 != null){
           cur.next = list1;
       }
       if(list2 != null){
           cur.next = list2;
       }
       return pre.next;
   }

2. 两数相加

解题思路：关键点——标志位int add = 0表示是否进一位

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode list1 = l1;
    ListNode list2 = l2;
    ListNode pre = new ListNode(-1);
    ListNode cur = pre;
    int add = 0;
    while(list1 !=null || list2 !=null || add == 1){
        int val1 = list1 != null?list1.val:0;
        int val2 = list2 != null?list2.val:0;
        int value = (val1 + val2 + add) % 10;
        add = (val1 + val2 + add) >= 10 ? 1:0;
        cur.next = new ListNode(value);
        cur = cur.next;
        list1 = list1!=null?list1.next:null;
        list2 = list2!=null?list2.next:null;
    }
    return pre.next;
}

19. 删除链表的倒数第 N 个结点

/**
 * 双指针：
 * 1：2个指针先间隔n的距离
 * 2:2个指针同步向后移动，直至后一个指针移动到尾部
 * 3:做删除操作
 * @param head
 * @param n
 * @return
 */
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode pre = new ListNode(-1);
    pre.next = head;
    ListNode first = pre;
    ListNode second = pre;
    while(n-- > 0){
        first = first.next;
    }
    while(first !=null && first.next != null){
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return pre.next;
}

/**
 * 利用list
 * @param head
 * @param n
 * @return
 */
public ListNode removeNthFromEnd2(ListNode head, int n) {
    List<ListNode> nodes = new ArrayList<>();
    ListNode pre = new ListNode(0);
    nodes.add(pre);
    pre.next = head;
    ListNode cur = head;
    while (cur != null){
        nodes.add(cur);
        cur = cur.next;
    }
    nodes.get(nodes.size() - n - 1).next = nodes.get(nodes.size() - n).next;
    return nodes.get(0).next;
}

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

/**
 * 借助双指针first、second
 * 双指针的前置指针 pre
 * @param head
 * @return
 */
public ListNode swapPairs(ListNode head) {
    ListNode dummyHead = new ListNode(-1,head);
    ListNode cur = dummyHead;
    while(cur.next != null && cur.next.next != null){
        ListNode first = cur.next;
        ListNode second = cur.next.next;
        first.next = second.next;
        second.next = first;
        cur.next = second;
        cur = first;
    }
    return dummyHead.next;
}
/**
 * 递归
 * 双指针的前置指针 pre
 * @param head
 * @return
 */
public ListNode swapPairs1(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode newHead = head.next;
    head.next = swapPairs1(newHead.next);
    newHead.next = head;
    return newHead;
}

25. K 个一组翻转链表

解题思路：解法与2个一组翻转链表基本一致，区别在于维护步长n，尝试找n个一组，才翻转，并且维护翻转前后的pre和next

/**
 * 递归算法
 * 1、找出反转前的原head(反转后的尾结点),反转前的尾结点newHead(反转之后的头结点)
 * 2、temp = newHead.next,临时存储待反转的后续节点,newHead.next = null，以便反转
 * 3、反转head->newHead这个链表
 * 4、head.next = 递归(newHead.next)1-4点
 * @param head
 * @param k
 * @return
 */
public ListNode reverseKGroup(ListNode head, int k) {
    if(k == 1 || head == null){
        return head;
    }
    ListNode newHead = head;
    int n = k;
    while (n > 1 && newHead.next != null){
        newHead = newHead.next;
        n--;
    }
    if(n != 1){
        return head;
    }else{
        ListNode temp = newHead.next;
        newHead.next = null;
        reverse(head);
        head.next = reverseKGroup(temp,k);
    }
    return newHead;
}

private ListNode reverse(ListNode head) {
    ListNode newHead = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = newHead;
        newHead = curr;
        curr = next;
    }
    return newHead;
}

/**
 * 迭代法
 * 1、尝试遍历k个节点
 * 2、遍历k个，则借助begin，end 翻转之后
 * 3、没有遍历完成，则保持原样
 * @param head
 * @param k
 * @return
 */
public ListNode reverseKGroup1(ListNode head, int k) {
    if(k == 1 || head == null){
        return head;
    }
    ListNode dump = new ListNode(0);
    dump.next = head;
    ListNode pre = dump;
    ListNode begin = dump;
    ListNode end = dump;
    while(end.next != null){
        int n = k;
        begin = pre.next;
        while(n > 0 && end.next != null){
            n--;
            end = end.next;
        }
        if(n==0){
            ListNode temp = end.next;
            end.next = null;
            pre.next = reverse(begin);
            pre = begin;
            end = pre;
            end.next = temp;

        }

    }
    return dump.next;
}

138. 随机链表的复制

解法一：遍历2次

第一次：根据next组装next链，且维护新旧节点的map，第二次根据map组装random链

/**
 * 遍历2次 + hasmap
 * @param head
 * @return
 */
public Node copyRandomList1(Node head) {
    if(head == null){
        return null;
    }
    Node oriDummyHead = new Node(-1);
    Node dummyHead = new Node(-1);
    oriDummyHead.next = head;
    dummyHead.next = new Node(head.val);
    Node newCur = dummyHead;
    Node cur = oriDummyHead.next;
    Map<Node,Node> nodeMap = new HashMap<>();

    while(cur != null){
        newCur.next = new Node(cur.val);
        newCur = newCur.next;
        nodeMap.put(cur,newCur);

        cur = cur.next;
    }
    cur = oriDummyHead.next;
    newCur = dummyHead.next;
    while(newCur != null){
        newCur.random = nodeMap.get(cur.random);
        cur = cur.next;
        newCur = newCur.next;
    }
    return dummyHead.next;
}

解法二：递归+维护新旧节点关系map

递归时，组装next、random链表时从map中取，没则新建维护进map

Map<Node,Node> nodeMap = new HashMap<>();
public Node copyRandomList2(Node head) {
    if(head == null){
        return null;
    }
    if(nodeMap.containsKey(head)){
        return nodeMap.get(head);
    }else{
        Node newNode = new Node(head.val);
        nodeMap.put(head,newNode);
        newNode.next = copyRandomList2(head.next);
        newNode.random = copyRandomList2(head.random);
        return newNode;
    }
}

解法三：A->B->C ==> A->A’->B->B’->C->C’

1、复制copy节点， A->A’->B->B’->C->C’
2、维护random节点，A’的random节点=A的random节点的next
3、利用next属性断开新链表得到A’->B’->C’

/**
 * 影子复制法
 * 1、利用next遍历一次，复制节点位于源节点的下一个节点
 * 2、再利用next遍历一次，copy.random = cur.random == null?null:cur.random.next;
 * 3、再利用next遍历一次，分开复制节点和源节点，返回复制链表节点
 * @param head
 * @return
 */
public Node copyRandomList(Node head) {
    if(head == null){
        return null;
    }
    Node cur = head;
    while (cur != null){
        Node node = new Node(cur.val);
        node.next = cur.next;
        cur.next = node;
        cur = node.next;
    }
    cur = head;
    while (cur != null){
        Node copyNode = cur.next;
        Node random = cur.random;
        if(random != null){
            copyNode.random = random.next;
        }
        cur = cur.next.next;
    }
    cur = head;
    Node newHead = head.next;
    while (cur != null){
        Node copyNode = cur.next;
        cur.next = copyNode.next;
        if(null != cur.next){
            copyNode.next = cur.next.next;
        }
        cur = cur.next;
    }
    return newHead;
}

148. 排序链表

解法一(推荐)：自顶向下归并排序

/**
 * 利用归并排序，自上而下
 * @param head
 * @return
 */
public ListNode sortList1(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode slow = head;
    ListNode fast = head;
    while(fast.next != null && fast.next.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode newHead = slow.next;
    slow.next = null;
    return mergeTwoLists(sortList1(head),sortList1(newHead));
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1 == null){
        return list2;
    }
    if(list2 == null){
        return list1;
    }
    if(list1.val <= list2.val){
        list1.next = mergeTwoLists(list1.next,list2);
        return list1;
    }else{
        list2.next = mergeTwoLists(list1,list2.next);
        return list2;
    }
}

解法二：自底向上归并排序

/**
 * 自底向上
 * 归并思路
 * 先假设步长=1，然后步长=2,4,8
 * 每个步长都循环执行找到头结点1,2。合并1,2。知道最后一个节点
 * @param head
 * @return
 */
public ListNode sortList2(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    int length = 0;
    ListNode cur = head;
    while(cur != null){
        length++;
        cur = cur.next;
    }
    ListNode dummyHead = new ListNode(0,head);
    for (int i = 1; i < length; i = (i << 1)) {


        ListNode pre = dummyHead;
        cur = pre.next;

        while(cur != null){
            ListNode head1 = cur;
            for (int j = 1; j < i && cur.next != null; j++) {
                cur = cur.next;
            }
            ListNode head2 = cur.next;
            cur.next = null;
            cur = head2;
            for (int j = 1; j < i && cur!= null && cur.next != null; j++) {
                cur = cur.next;
            }
            ListNode next = null;
            if(cur != null){
                next = cur.next;
                cur.next = null;

            }
            pre.next = mergeTwoLists(head1,head2);

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

    }
    return dummyHead.next;
    
}

23. 合并 K 个升序链表

解法解析：类似合并2个有序队列，区别在于方法入参变成ListNode[] lists

/**
 * 递归算法= fx(lists)
 * 1、每次找出lists数组中最小的节点list
 * 2、lists[list的下标] = list.next
 * 3、list.next = f(lists)
 * 4、return list;
 * @param lists
 * @return
 */
public ListNode mergeKLists(ListNode[] lists) {
    if(null == lists){
        return null;
    }
    ListNode lessNode = null;
    int index = -1;
    for (int i = 0; i < lists.length; i++) {
        ListNode list = lists[i];
        if(null == lessNode || (null != list && list.val < lessNode.val)){
            lessNode = list;
            index = i;
        }
    }
    if(lessNode == null){
        return null;
    }
    lists[index] = lists[index].next;
    lessNode.next = mergeKLists(lists);
    return lessNode;
}

146. LRU 缓存

解法一：Queue+Map

比较慢：queue ArrayBlockingQueue对删除操作较慢

public class LRUCache2{
    Queue<Integer> queue;
    Map<Integer,Integer> map = new HashMap<>();
    private Integer capacity;
    public LRUCache2(int capacity) {
        queue = new ArrayBlockingQueue<Integer>(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            queue.remove(key);
            queue.add(key);
            return map.get(key);
        }
        return -1;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
           queue.remove(key);
           queue.add(key);
        }else{
            if(map.size() == capacity){
                Integer poll = queue.poll();
                map.remove(poll);
            }
            queue.add(key);

        }
        map.put(key,value);
    }

解法二：自定义双向链表+Map

封装方法doAddToHead、doRemoveNode

public class LRUCache3{
    public static class ListNode{
        ListNode next;
        ListNode pre;
        int key;
        int val;
        public ListNode(int key,int val){
            this.key = key;
            this.val = val;
        }
        public ListNode(){
        }
        @Override
        public String toString(){
            return "ListNode{"+ ", key=" + key + ", val=" + val + "next=" + next +'}';
        }
    }
    private int capacity;
    private ListNode head,tail;
    private Map<Integer,ListNode> dataMap;
    public LRUCache3(int capacity){
        this.capacity = capacity;
        head = new ListNode();
        tail = new ListNode();
        head.next = tail;
        tail.pre = head;
        dataMap  = new HashMap<>();
    }
    public void put(int key,int value) {
        ListNode node = new ListNode(key,value);
        if(dataMap.containsKey(key)){
            ListNode oldNode = dataMap.get(key);
            //移除节点
            doRemoveNode(oldNode);
            //加入头结点
            doAddToHead(node);
            dataMap.put(key,node);
        }else{
            dataMap.put(key,node);
            doAddToHead(node);
            if(dataMap.size() > capacity){
                //移除尾节点
                ListNode lastNode = tail.pre;
                dataMap.remove(lastNode.key);
                doRemoveNode(lastNode);
            }
        }

    }
    public int get(int key) {
        if(dataMap.containsKey(key)){
            //移除节点
            ListNode node = dataMap.get(key);
            doRemoveNode(node);
            //加入头结点
            doAddToHead(node);
            return node.val;
        }else{
            return -1;
        }
    }
    private void doAddToHead(ListNode node){
        if(node == null){
            return;
        }
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }
    private void doRemoveNode(ListNode node){
        if(node == null){
            return;
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
}

解法三：Java自带实现

public class LRUCache1 extends LinkedHashMap<Integer,Integer>{
//    方法一：利用java自带的实现

    private Integer capacity;
    public LRUCache1(int capacity) {
        super(capacity,0.75F,true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key,-1);
    }

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

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return super.size() > capacity;
    }
}

图论

回溯

二分查找1

栈

堆

贪心算法

动态规划

多维动态规划