力扣高频50题，带个人代码，最简单规范的解法

 XX-YY-ZZ-W

XX用来初步定义难度的范围（用于决定应投入多少时间在复习该题上）：

按照难度进行排序，难度划分为：简单、中等和难。

简单题：基本不用复刷，完全掌握。

中等题：需要复刷1-2遍后可完全掌握。（中等-低，中等-高 建议隔1周复刷1次，总计1次；中等-高建议隔1周复刷1次，总计2次）

难题：需要至少刷2遍以上才能最终掌握（难-低 建议隔1周复刷1次，总计3次；难-中 建议隔1周复刷1次，总计4次；难-高 建议隔1周复刷1次，总计5次）。

YY代表细分定义后的难度（用于决定该复习一道题的次数和优先级）：

细分定义的难度划分为：低、中和高。

ZZ代表将该题列入该难度范围的原因：

包括：细节易错，思路缺乏，复杂度高，思路不清晰，原理不理解等。

W代表最近重做时能否独立做出：

1代表是在借鉴答案后完成，记忆不深刻，要在下次优先重做巩固。

目录

1、反转链表 

2、无重复字符的最长子串

3、锯齿形层序遍历

4、岛屿数量

5、买卖股票最佳时机 

6、两数之和

7、二叉树最近公共祖先

8、相交链表

9、最长回文子串

10、全排列

11、最长递增子序列

12、二叉树的层序遍历

13、二叉树的右视图

15、重排链表

16、二叉树中的最大路径和

17、有效的括号

18、环形链表

19、字符串相加（简单-高）

20、反转链表II（中等-低）

21、比较版本号

22、合并区间

23、排序数组（手撕快速排序）（中-高）

26、删除链表的导数第N个结点

27、环形链表II

28、无重复字符的最长子串

29、最小栈（简单-高）

30、X的平方根（简单-高）

31、K个一组翻转链表（难）

32、数组中第K个最大元素（难-低-细节易错）

33、三数之和（难-低-细节易错）

34、螺旋矩阵（难-低-思路不清晰-1）

35、下一个排列（难-高-细节易错）

36、合并K个排序链表（难-高-细节易错）

37、缺失的第一个正数（难）

38、编辑距离（难-高-原理不理解）

41、盛水最多的容器（中）

42、二分查找（易）

43、删除排序链表中的重复元素（中）

44、用栈实现队列（中-低）

45、合并区间（难-低）

46、比较版本号（中-高）

48、复原IP地址（难-低）

49、滑动窗口最大值（难-低）

50、 在排序数组中查找元素（中等-高）

51、最长公共子序列（难-低-原理不理解）

52、排序链表（难-中-思路不清晰）

53、删除链表中重复元素（中-低-原理不理解）

1、反转链表 

import java.util.*;

class ListNode{
    int val;
    ListNode next;
    ListNode(){};
    ListNode(int val){this.val = val;};
    ListNode(int val,ListNode next){this.val = val;this.next = next;}
}

public class Receive {
    public static ListNode head;
    public static void init(){
        head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
    }
    public static ListNode reverseList(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
    public static void main(String[] args){
        init();
        head = reverseList(head);
        ListNode p = head;
        while(p!=null){
            System.out.println(p.val);
            p=p.next;
        }
    }
}

2、无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.isEmpty()) return 0;
        int n = s.length();
        int left=0;
        int maxx = -Integer.MAX_VALUE;
        Set<Character> set = new HashSet<>();
        for(int right=0;right<n;right++){
            while(set.contains(s.charAt(right))){
                set.remove(s.charAt(left));
                left++;
            }
            set.add(s.charAt(right));
            maxx = Math.max(maxx,right-left+1);
        }
        return maxx;
    }
}

3、锯齿形层序遍历

import java.util.*;

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(){};
    public TreeNode(int val){
        this.val = val;
    }
}

public class Receive {
    public static List<List<Integer>> list;
    public static Queue<TreeNode> queue ;
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root){
        if(root==null) return list;
        queue = new ArrayDeque<>();
        list = new ArrayList<>();
        queue.offer(root);
        Boolean isLeft = true;
        while(!queue.isEmpty()){
            int n = queue.size();
            Deque<Integer> deque = new ArrayDeque<>();
            for(int i=0;i<n;i++){
                TreeNode node = queue.poll();
                if(isLeft){
                    deque.addLast(node.val);
                }else{
                    deque.addFirst(node.val);
                }
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }

            }
            isLeft = !isLeft;
            list.add(new ArrayList<>(deque));
        }
        return list;
    }
    public static void printTree(){
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i));
            if(i!=list.size()) System.out.print(",");
        }
    }
    public static void main(String[] args){
        TreeNode[] p = new TreeNode[8];
        p[0] = new TreeNode(3);
        p[1] = new TreeNode(9);
        p[2] = new TreeNode(20);
        p[3] = new TreeNode(15);
        p[4] = new TreeNode(7);
        p[0].left = p[1];
        p[0].right = p[2];
        p[2].left = p[3];
        p[2].right = p[4];
        zigzagLevelOrder(p[0]);
        printTree();
    }
}

4、岛屿数量

class Solution {
    public int line;
    public int row;
    public int numIslands(char[][] grid) {
        line = grid.length;
        row = grid[0].length;
        int num=0;
        for(int i=0;i<line;i++){
            for(int j=0;j<row;j++){
                if(grid[i][j]=='1'){
                    num++;
                    dfs(grid,i,j);
                }
            }
        }
        return num;
    }

    public void dfs(char[][] grid,int i,int j){
        if(i<0 || i>= line || j<0 || j>= row || grid[i][j]=='0'){
            return;
        }
        grid[i][j]='0';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
}

5、买卖股票最佳时机 

class Solution {
    int maxx = -Integer.MAX_VALUE;
    int minn = Integer.MAX_VALUE;
    public int maxProfit(int[] prices) {
        int n = prices.length;
        for(int i=0;i<n;i++){
            minn = Math.min(minn,prices[i]);
            maxx = Math.max(maxx,prices[i]-minn);
        }
        return maxx;
    }
}

6、两数之和

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

7、二叉树最近公共祖先

class Solution {
    Map<TreeNode,TreeNode> parent = new HashMap<>();
    Set<TreeNode> set = new HashSet<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while(p!=null){
            set.add(p);
            p = parent.get(p);
        }
        while(q!=null){
            if(set.contains(q)){
                return q;
            }
            q = parent.get(q);
        }
        return null;
    }

    public void dfs(TreeNode head){
        if(head==null) return;
        if(head.left != null){
            parent.put(head.left,head);
            dfs(head.left);
        }
        if(head.right != null){
            parent.put(head.right,head);
            dfs(head.right);
        }
    }
}

8、相交链表

public class Solution {
    public Set<ListNode> set = new HashSet<>();
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p = headA;
        while(p!=null){
            set.add(p);
            p=p.next;
        }
        ListNode q = headB;
        while(q!=null){
            if(set.contains(q)){
                return q;
            }
            q = q.next;
        }
        return null;
    }  
}

9、最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        if(n<=1) return s;
        int start=0,end=0;
        for(int i=0;i<n-1;i++){
            int len1 = getSubStr(s,i,i);
            int len2 = getSubStr(s,i,i+1);
            int len = Math.max(len1,len2);
            if(len>end-start){
                start = i-(len-1)/2;
                end = i+len/2;
            }
        }
        return s.substring(start,end+1);
    }

    public int getSubStr(String s,int left,int right){
        while(left>=0 && right<=s.length()-1 && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        return right-left-1;
    }
}

10、全排列

class Solution {
    List<List<Integer>> list = new ArrayList<>();
    Deque<Integer> deque = new ArrayDeque<>();
    int[] flag;
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        flag = new int[n+1];
        dfs(nums,0);
        return list;
    }
    public void dfs(int[] nums,int cnt){
        if(cnt==nums.length){
            list.add(new ArrayList<>(deque));
        }
        for(int i=0;i<nums.length;i++){
            if(flag[i]==0){
                deque.addLast(nums[i]);
                flag[i]=1;
                dfs(nums,cnt+1);
                flag[i]=0;
                deque.removeLast();
            }
        }
    }
}

11、最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
       int n = nums.length;
       if(n==0) return 0;
       int maxx = 1;
       int[] dp = new int[n+1];
       for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
                maxx = Math.max(dp[i],maxx);
            }
       }
       return maxx;
    }
}

12、二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> list = new ArrayList<>();
       if(root==null) return list;
       Deque<TreeNode> deque = new ArrayDeque<>();
       deque.offer(root);
       while(!deque.isEmpty()){
            int n = deque.size();
            List<Integer> l = new ArrayList<>();
            for(int i=0;i<n;i++){
                TreeNode x = deque.poll();
                l.add(x.val);
                if(x.left!=null){
                    deque.offer(x.left);
                }
                if(x.right!=null){
                    deque.offer(x.right);
                }
            }
            list.add(l);
       }
       return list;
    }
}

13、二叉树的右视图

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null) return res;
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while(!deque.isEmpty()){
            int n = deque.size();
            for(int i=0;i<n;i++){
                TreeNode x = deque.poll();
                if(i==n-1) res.add(x.val);
                if(x.left!=null){
                    deque.offer(x.left);
                }
                if(x.right!=null){
                    deque.offer(x.right);
                }
            }
        }
        return res;

    }
}

15、重排链表

class Solution {
    public void reorderList(ListNode head) {
        if(head==null){
            return ;
        }
        ListNode mid = middle(head);
        ListNode l1 = head;
        ListNode l2 = mid.next;
        mid.next = null;
        l2 = reverse(l2);
        merge(l1,l2);
    }

    public void merge(ListNode l1,ListNode l2){
        ListNode tmp1;
        ListNode tmp2;
        while(l1!=null && l2!=null){
            tmp1 = l1.next;
            tmp2 = l2.next;
            l1.next = l2;
            l1 = tmp1;
            l2.next = l1;
            l2 = tmp2;
        }
    }

    public ListNode reverse(ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode nex = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nex;
        }
        return prev;
    }

    public ListNode middle(ListNode head){
        ListNode tail = head;
        ListNode mid = head;
        while(tail != null && tail.next != null){
            tail = tail.next.next;
            mid = mid.next;
        }
        return mid;
    }
}

16、二叉树中的最大路径和

class Solution {
    Integer res = -Integer.MAX_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root){
        if(root==null) return 0;
        int left = Math.max(dfs(root.left),0); //有些节点值为负数
        int right = Math.max(dfs(root.right),0);
        int val = root.val + left + right; 
        res = Math.max(res,val);
        return Math.max(left + root.val , right + root.val); //返回值为左右路径较大的一支
    }
}

17、有效的括号

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        int n = s.length();
        for(int i=0;i<n;i++){
            char x = s.charAt(i);
            if(x=='(' || x=='[' || x=='{'){
                deque.push(x);
                continue;
            }
            if(deque.isEmpty()){
                return false;
            }
            char y = deque.pop();
            if(!(y=='(' && x==')' || y=='[' && x==']' || y=='{' && x=='}')){
                return false;
            }
        }
        return deque.isEmpty();
    }
}

18、环形链表

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head , slow = head;
        while(fast != null && fast.next != null){
            if(fast==null) return false;
            slow = slow.next;
            fast = fast.next.next;
            if(fast==slow) return true;
        }
        return false;
    }
}

19、字符串相加（简单-高）

class Solution {
    public String addStrings(String num1, String num2) {
        int n1 = num1.length(),n2 = num2.length();
        int i=n1-1,j=n2-1,add = 0;
        StringBuffer buf = new StringBuffer();
        while(i>=0 || j>=0){
            int x = i>=0 ? num1.charAt(i)-'0' : 0;
            int y = j>=0 ? num2.charAt(j)-'0' : 0;
            i--;j--;
            int left = (x+y+add)%10;
            add = (x+y+add)/10;
            buf.append(left);
        }
        if(add>0) buf.append(add);
        buf.reverse();
        return buf.toString();
    }
}

20、反转链表II（中等-低）

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0,head);
        ListNode pre = dummy,rightNode = dummy;
        for(int i=0;i<left-1;i++){
            pre = pre.next;
        }
        ListNode leftNode = pre.next;
        for(int j=0;j<right;j++){
            rightNode = rightNode.next;
        }
        ListNode after = rightNode.next;
        pre.next=null; //易错点1:要让pre、rightNode先指向空
        rightNode.next=null;
        reverseNode(leftNode);
        pre.next = rightNode; //易错点2:因为链表指向反转，所以pre的下一个节点要指向反转链表的最右节点，leftNode的下一个节点要指向after。
        leftNode.next = after;
        return dummy.next;
    }
    public ListNode reverseNode (ListNode head){
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

21、比较版本号

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int n1 = v1.length;
        int n2 = v2.length;
        for(int i=0;i<n1||i<n2;i++){
            int x=0,y=0;
            if(i<n1){
                x = Integer.valueOf(v1[i]);
            }
            if(i<n2){
                y = Integer.valueOf(v2[i]);
            }
            if(x<y){
                return -1;
            }else if(x>y){
                return 1;
            }
        }
        return 0;
    }
}

22、合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        if(n==0) return new int[0][2];
        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals,new Comparator<int[]>(){ //先进行排序
            public int compare(int[] o1,int[] o2){
                return o1[0]-o2[0];
            }
        });
        for(int i=0;i<n;i++){
            int x = intervals[i][0];
            int y = intervals[i][1];
            int j = i+1;
            while(j<n && intervals[j][0]<=y){
                y=Math.max(y,intervals[j][1]);
                i = j++; //注意这种写法
            }
            list.add(new int[]{x,y}); //注意这种写法
        }
        return list.toArray(new int[list.size()][]); //将Array转化为int[]
    }
}

23、排序数组（手撕快速排序）（中-高）

pivot：中心点，轴心

partition：分割，划分

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    public void quickSort(int[] nums,int begin,int end){
        if(begin>=end) return; //易错1:易漏
        int pivot = partition(nums,begin,end);
        quickSort(nums,begin,pivot-1);
        quickSort(nums,pivot+1,end);
    }

    public int partition(int[] nums,int begin,int end){
        int index = nums[begin]; //取begin为index的下标
        int left = begin+1,right = end;  //begin要+1，如果取end为index下标，right要-1
        while(left<=right){
            while(left<=right && nums[left]<index){
                left++;
            }
            while(left<=right && nums[right]>index){
                right--;
            }
            if(left<=right){ //再次判断left<=right
                swap(nums,left,right);
                left++;
                right--;
            }
        }
        swap(nums,right,begin); //交换index的下标begin和right，如果index下标为end要交换left
        return right; //如果取begin为index的下标返回right，如果取end为index下标返回left
    }

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

26、删除链表的导数第N个结点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy , slow = dummy;;
        for(int i=0;i<=n;i++){
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

27、环形链表II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode p = head;
        Set<ListNode> set = new HashSet<>();
        while(p!=null){
            if(set.contains(p)){
                return p;
            }
            set.add(p);
            p=p.next;
        }
        return null;
    }
}

28、无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Set<Character> set = new HashSet<>();
        int right=0,left=0;
        int maximum = 0;
        while(right<n){
            char x = s.charAt(right);
            if(!set.contains(x)){ 
                set.add(x);
                right++;
            }else{
                set.remove(s.charAt(left)); //关键在于此，收缩左边界是删除left下标位置的元素，直到不包含这个重复元素
                left++;
            }
            maximum = Math.max(maximum,right-left);
        }  
        return maximum;
    }
}

29、最小栈（简单-高）

class MinStack {
    Deque<Integer> deque;
    Deque<Integer> minDeque;

    public MinStack() {
        deque = new ArrayDeque<>();
        minDeque = new ArrayDeque<>();
        minDeque.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        deque.push(x);
        minDeque.push(Math.min(x,minDeque.peek()));
    }
    
    public void pop() {
        deque.pop();
        minDeque.pop();
    }
    
    public int top() {
        return deque.peek();
    }
    
    public int getMin() {
        return minDeque.peek();
    }
}

30、X的平方根（简单-高）

class Solution {
    public int mySqrt(int x) {
        if(x==0) return 0; //小心x为0，为导致除0异常
        int left = 0,right = x,ans=0;
        while(left<=right){
            int mid = (left - right)/2 + right; //避免超界
            if(mid==x/mid) return mid;
            else if(mid<x/mid){
                ans=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return ans;
    }
}

31、K个一组翻转链表（难）

难点1：

难点2：

难点3：

重点1：

代码：

32、数组中第K个最大元素（难-低-细节易错）

规范点：buildHeap最好改成buildMaxHeap。maxHeap最好改成maxHeapify。

易错点1：不是maxHeap(nums,i/2)而是maxHeap(nums,0,heapSize)因为从0开始表示从堆顶开始调整，还需要传入堆的大小，这个堆大小在改变中。

易错点2：这里不是nums[left]>nums[i]而是nums[left]>nums[maxPos]，因为比较的是left下标和maxPos下标的元素值大小。

易错点3：这里要保证left和right<heapSize。

易错点4：maxHeap(nums,maxPos,heapSize)这个递归调用是放在if语句里面，只有当交换位置后才需要继续调整。

代码：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        buildHeap(nums,heapSize);
        for(int i=nums.length-1;i>=nums.length-k+1;i--){
            swap(nums,0,i);
            heapSize--;
            //易错1:不是maxHeap(nums,i/2)而是maxHeap(nums,0,heapSize)因为从0开始表示从堆顶开始调整，还需要传入堆的大小，这个堆大小在改变中。
            maxHeap(nums,0,heapSize); 
        }
        return nums[0];
    }
    public void buildHeap(int[] nums,int heapSize){
        for(int i=heapSize/2;i>=0;i--){
            maxHeap(nums,i,heapSize);
        }
    }
    public void maxHeap(int[] nums,int i,int heapSize){
        int left = i*2+1,right = i*2+2;
        int maxPos = i;
        //易错2:这里不是nums[left]>nums[i]而是nums[left]>nums[maxPos]，因为比较的是left下标和maxPos下标的元素。
        if(left<heapSize && nums[left]>nums[maxPos]){  //易错3:这里要保证left和right<heapSize
            maxPos=left;
        }
        if(right<heapSize && nums[right]>nums[maxPos]){
            maxPos=right;
        }
        if(maxPos!=i){
            swap(nums,maxPos,i);
            maxHeap(nums,maxPos,heapSize); //易错4:这个递归调用是放在if语句里面，只有当交换位置后才需要继续调整
        }
        
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i]; 
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

33、三数之和（难-低-细节易错）

易错点1：数组不一定按照正序排列，所以要排序

易错点2：third记录的是末元素的下标，一开始写成third=nums[n-1]是错的

易错点3：second>first+1而不能是second>=first+1，不能取等，如果取等会和first重复

易错点4：向左移动third下标时使用的是while

易错点5：最后装入列表的要是3个元素，而不是3个元素的下标

class Solution {
    public List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums); //易错点1:数组不一定按照正序排列，所以要排序
        for(int first=0;first<n;first++){
            if(first>=1&&nums[first]==nums[first-1]){
                continue;
            }
            int target = -nums[first];
            //nums[second]+nums[third]= -nums[first] ;
            int third = n-1; //易错点2:一开始写成third=nums[n-1]是错的
            for(int second=first+1;second<n;second++){
                if(second>first+1&&nums[second]==nums[second-1]){ //易错点3:second>first+1而不能是second>=first+1
                    continue;
                }
                while(second<third&&nums[third]+nums[second]>target){ //易错点4:这里使用的是while
                    third--;
                }
                if(third<=second) break;
                //nums[second]+nums[third]+nums[first]>0 ;
                if(nums[third]+nums[second]==target){
                    List<Integer> l = new ArrayList<>();
                    l.add(nums[first]); //易错点5装入列表的要是3个元素，而不是3个元素的下标
                    l.add(nums[second]);
                    l.add(nums[third]);
                    ans.add(l);
                }
            }
        }
        return ans;
    }
}

34、螺旋矩阵（难-低-思路不清晰-1）

规范：行用rows表示。列用columns表示。标志数组用visited来表示。具体数组下标行用row表示，列用column表示。数组下一个位置下标行用nextRow表示，列用nextColumn表示。

重点1：通过总数来控制流程 for(int i=0;i<total;i++)

重点2：在index = (index+1)%4这里更改了index，下面row和column的index都改变了，实现转向

重点3：这里是row+direction[index][1]而不是matrix[i][j]+direction[index][1]，要得到的是下标。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        //行用rows表示。columns用line表示。标志数组用visited来表示。具体数组下标行用row列用column即可。数组下一个位置下标行用nextRow列用nextColumn。
        int rows = matrix.length;
        int columns = matrix[0].length;
        int[][] directions = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
        int[][] visited = new int[rows+1][columns+1];
        List<Integer> res = new ArrayList<>();
        int row=0,column=0,index=0;
        int total = rows*columns;
        for(int i=0;i<total;i++){ //重点1:通过总数来控制流程
            visited[row][column]=1;
            res.add(matrix[row][column]);
            //重点3:这里是i+direction[index][1]而不是matrix[i][j]+direction[index][1]，得到的是下标
            int nextRow = row+directions[index][0]; 
            int nextColumn = column+directions[index][1];
            if(nextRow<0 || nextRow>=rows || nextColumn<0 || nextColumn >= columns || visited[nextRow][nextColumn]==1){
                index = (index+1)%4; //重点2:在这里更改了index，下面i和j的index都改变了，实现转向
            }
            row += directions[index][0];
            column += directions[index][1];

            
        }
        return res;
    }
}

35、下一个排列（难-高-细节易错）

易错点1：i>=0漏了，nums[i]是>=nums[i+1]，等于不可漏掉

易错点2：nums[i]>=nums[j]，等于不可漏掉

易错点3：reverse不包含在if语句内

易错点4：是i+1不是i，是n-1不是n 

代码：

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n-2;
        while(i>=0 && nums[i]>=nums[i+1]){ //易错点1:i>=0漏了，nums[i]是>=nums[i+1]，等于不可漏掉
            i--;
        }
        if(i>=0){
        int j = n-1;
        while(j>=0 && nums[i]>=nums[j]){ //易错点2: nums[i]>=nums[j]，等于不可漏掉
            j--;
        }
        swap(nums,i,j);
        }
        reverse(nums,i+1,n-1); //易错点3:reverse不包含在if语句内
        //易错点4:是i+1不是i，是n-1不是n  
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void reverse(int[] nums,int i,int j){
        while(i<j){
            swap(nums,i,j);
            i++;j--;
        }
    }
}

36、合并K个排序链表（难-高-细节易错）

易错点1：继承Comparable里面还要写<Status>

易错点2：方法名叫作compareTo，参数是这个类的类型

易错点3：加入的元素是类类型，必须用Node(参数，参数)形式传递

易错点4：要取的是类的ListNode的元素

易错点5：取的是当前节点的下一个节点不为空

易错点6：加入的元素是类类型，必须用Node(参数，参数)形式传递

代码：

class Solution {
    //ptr
    class Status implements Comparable<Status>{ //易错点1:继承Comparable里面还要写<Status>
        int val;
        ListNode ptr;
        Node(int val,ListNode ptr){
            this.val = val;
            this.next = ptr;
        } 
        public int compareTo(Status status){ //易错点2:方法名叫作compareTo，参数是这个类的类型
            return this.val-status.val;
        }
    }
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for(ListNode node:lists){
            if(node!=null) pq.add(new Status(node.val,node)); //易错点3:加入的元素是类类型，必须用Node(参数，参数)形式传递
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(!pq.isEmpty()){   
            Status p = pq.poll();
            tail.next = p.ptr; //易错点4:要取的是类的ListNode的元素
            tail = tail.next;
            if(p.ptr.next!=null){ //易错点5:取的是当前节点的下一个节点不为空
                pq.add(new Status(p.ptr.next.val,p.ptr.next)); //易错点6:加入的元素是类类型，必须用Node(参数，参数)形式传递
            }
        }
        return dummy.next;
    }
}

37、缺失的第一个正数（难）

重点1：因为数组下标要>=0和<n，所以nums[i]>0,nums[i]<=n。
重点2：本题的思路是将从1开始的数放入数组，而数组以0开头，所以必须是nums[i]-1来和i比。
重点3：比如当i=0是nums[i]为4，要比较nums[3]的值是否和nums[0]相同，如果相同代表4已经放在了合适的位置就不必再交换了，很妙的思路。

代码：

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            //重点1:因为数组下标要>=0和<n，所以nums[i]>0,nums[i]<=n
            //重点2:本题的思路是将从1开始的数放入数组，而数组以0开头，所以必须是nums[i]-1来和i比
            //重点3:比如当i=0是nums[i]为4，要比较nums[3]的值是否和nums[0]相同，如果相同代表4已经放在了合适的位置就不必再交换了，很妙的思路
            while(nums[i]>0 && nums[i]<=n && nums[nums[i]-1]!=nums[i]){ 
                swap(nums,nums[i]-1,i);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

38、编辑距离（难-高-原理不理解）

易错点1：判断是否其中一个串为空时，返回的是另一个串长度

易错点2：i和j需要从0一直遍历到n和m，而不是小于n和m

重点1：假如第i-1个元素和第j-1个元素相同，只需要加上1个元素就相等，不需要做任何操作。如果第i-1个元素和低j-1个元素不相同，需要修改1次，所以+1

重点2：不需要设置min变量，而是直接返回dp[n1][n2]所存储的值。

class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        if(n1*n2==0) return n+m; //易错点1:其中一个串为空，返回另一个串长度
        int[][] dp = new int[n+1][m+1];
        for(int i=0;i<=n;i++){ //易错点2:i和j需要从0一直遍历到n和m，而不是小于n和m
            dp[i][0] = i;
        }
        for(int j=0;j<=m;j++){
            dp[0][j] = j;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                int left = dp[i-1][j]+1; //在B添加字符？
                int down = dp[i][j-1]+1; //在A添加字符？
                int left_down = dp[i-1][j-1];
                //重点1:假如第i-1个元素和第j-1个元素相同，只需要加上1个元素就相等，不需要做任何操作
                //如果第i-1个元素和低j-1个元素不相同，需要修改1次，所以+1
                if(word1.charAt(i-1)!=word2.charAt(j-1)){ 
                    mid += 1;
                }
                dp[i][j] = Math.min(mid,Math.min(left,right));
            }
        return dp[n1][n2]; //重点2:不需要设置min变量，而是直接返回dp[n1][n2]所存储的值。
    }
}

41、盛水最多的容器（中）

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int left=0,right=n-1;
        int maxWater = 0;
        while(left<right){
            maxWater=Math.max((right-left)*Math.min(height[right],height[left]),maxWater);
            if(height[left]<=height[right]){ //哪边矮就移动指针，双指针哪边挫（内）卷哪边
                left++;
            }else{
                right--;
            }
        }
        return maxWater;
    }
}

42、二分查找（易）

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0 , right = n-1;
        while(left<=right){
            int mid = (left-right)/2+right;
            if(nums[mid]==target) return mid;
            else if(nums[mid]<target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return -1;
    }
}

43、删除排序链表中的重复元素（中）

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return null;
        ListNode cur = head;
        while(cur!=null && cur.next!=null){
            if(cur.val==cur.next.val){ //如果元素相等，让指针指向下下个元素
                cur.next = cur.next.next;
            }else{ //否则让指针移动到下一个位置
                cur=cur.next;
            }
        }
        return head;
    }
}

44、用栈实现队列（中-低）

实现思路：设置两个栈，第1个栈用于装入新元素，第2个栈用于将第1个栈的元素逆序，从而形成队列。

只有在第2个栈为空的情况下才需要重新装入元素，不然直接取出（第2个栈中的）元素即可。

class MyQueue {

    //两个栈，一个栈装新元素，一个栈负责倒出来逆序
    public Deque<Integer> deque ;
    public Deque<Integer> res; 

    public MyQueue() {
        deque = new ArrayDeque<>();
        res = new ArrayDeque<>();
    }
    
    public void push(int x) {
        deque.push(x);
    }
    
    public int pop() {
        if(res.isEmpty()){  //只有在第2个栈没元素的前提下才需要重新装入元素，不然直接取即可。
            while(!deque.isEmpty()){
                 res.push(deque.pop());
            }
        }  
        return res.pop();
    }
    
    public int peek() {
        if(res.isEmpty()){
            while(!deque.isEmpty()){
                 res.push(deque.pop());
            }
        }  
        return res.peek();
    }
    
    public boolean empty() {
        return deque.isEmpty() && res.isEmpty();
    }
}

45、合并区间（难-低）

 难点1：对int[][]二维数组进行排序。

重点1：将Array转化为int[][]，第1维要加大小。

代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        Arrays.sort(intervals,new Comparator<int[]>(){ //难点1：对int[][]二维数组进行排序
            public int compare(int[] o1,int[] o2){
                return o1[0]==o2[0]?o1[1]-o2[1]:o1[0]-o2[0];
            }
        });
        int n = intervals.length;
        for(int i=0;i<n;i++){
            int x = intervals[i][0];
            int y = intervals[i][1];
            int j=i+1;
            while(j<n && y>=intervals[j][0]){
                y = Math.max(y,intervals[j][1]);
                i = j++; //重点1:对i进行更新的同时对j递增
            }
            list.add(new int[]{x,y});
        }
        return list.toArray(new int[list.size()][]); //重点2:将Array转化为int[][],第1维要加大小
    }
}

46、比较版本号（中-高）

易错点1："."代表任意字符，要加转义字符"\\."

代码：

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] str1 = version1.split("\\."); //易错点1:"."代表任意字符，要加转义字符"\\."
        String[] str2 = version2.split("\\.");
        int n1 = str1.length;
        int n2 = str2.length;
        int i=0,j=0;
        while(i<n1 || j<n2){
            int x = i<n1 ? toNumber(str1[i]) : 0; //重点:使用三目运算符来简化对长度的处理
            int y = j<n2 ? toNumber(str2[j]) : 0;
            i++;j++;
            if(x<y) return -1;
            else if(x>y) return 1;
            else continue;
        }
        return 0;
    }

    public int toNumber(String s){
        int n = s.length();
        int res = 0;
        for(int i=0;i<n;i++){ //易错点1:从高位往低位走
            res = res*10 + (s.charAt(i)-'0');
        }
        return res;
    }
}

48、复原IP地址（难-低）

易错点1：dfs(s,segId+1,segEnd+1); 传入的第2个参数要为segEnd+1。

重点1：注意规范，修改命名习惯：4改成SEG_COUNT；list改成ans；arr改成segments；seg改成segId；pos改成segStart；num改成addr。

代码：

class Solution {
    //SEG_COUNT。list改成ans。arr改成segments。seg改成segId。pos改成segStart。num改成addr
    public List<String> ans = new ArrayList<>();
    int SEG_COUNT = 4;
    public int[] segments = new int[4];
    public List<String> restoreIpAddresses(String s) {
        dfs(s,0,0);
        return ans;
    }
    public void dfs(String s,int segId,int segStart){
        if(segStart==s.length()){
            if(segId==SEG_COUNT){
                StringBuffer buf = new StringBuffer();
                for(int i=0;i<SEG_COUNT;i++){
                    buf.append(segments[i]);
                    if(i!=SEG_COUNT-1) buf.append('.');
                }
                ans.add(buf.toString());
            }
            return;
        }
        if(segId==SEG_COUNT){
            return;
        }
        if(s.charAt(segStart)=='0'){
            segments[segId] = 0; //易错1:把segId和segStart要用segId
            dfs(s,segId+1,segStart+1);
            return;
        }
        int addr = 0;
        for(int segEnd=segStart;segEnd<s.length();segEnd++){
            addr = addr*10 + s.charAt(segEnd)-'0';
            if(addr>=0 && addr<=255){
                segments[segId] = addr;
                dfs(s,segId+1,segEnd+1); //易错点2:传入的第2个参数要为segEnd+1
            }else{
                break;
            }
        }
    }
}

49、滑动窗口最大值（难-低）

重点1：构造一个优先队列，元素为数组

重点2：熟练掌握添加(add)数组元素，取队首元素(peek),剔除队首元素(poll)。

易错点1：要剔除元素的左边界范围是小于等于i-k

易错点2：结果数组大小为n-k+1,结果数组赋值i-k+1

代码：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //重点1:构造一个优先队列，元素为数组
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o2[0]==o1[0]?o2[1]-o1[1]:o2[0]-o1[0];
            }
        });
        for(int i=0;i<k;i++){
            pq.add(new int[]{nums[i],i}); //重点2:熟练掌握添加(add)数组元素，取队首元素(peek),剔除队首元素(poll)。
        }
        int[] ans = new int[nums.length-k+1]; //易错点2:结果数组大小为n-k+1,结果数组赋值i-k+1
        ans[0] = pq.peek()[0];
        for(int i=k;i<nums.length;i++){
            pq.add(new int[]{nums[i],i});
            while(pq.peek()[1]<=i-k){ //易错点1:要剔除元素的左边界范围是小于等于i-k
                pq.poll();
            }
            ans[i-k+1] = pq.peek()[0];
        }
        return ans;
    }
}

50、 在排序数组中查找元素（中等-高）

注意点1：直接把first和end设置为-1如果没有nums[mid]==target可以直接返回-1更加方便。

重点1：想获得最右侧边界的值，让left指针为mid+1，直接在右半部分接着搜索。

代码：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n = nums.length;
        int left=0,right=n-1;
        int first=-1,end=-1; //注意点1:直接把first和end设置为-1如果没有nums[mid]==target可以直接返回-1更加方便。
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==target){
                first = mid; //用first和end来记录mid
                right = mid-1; //重点1:想获得最左侧边界的值，让right指针为mid-1，直接在左半部分接着搜索。
            }else if(nums[mid]<target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        left=0;right=n-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]==target){
                end = mid;
                left = mid+1; //重点1:想获得最右侧边界的值，让left指针为mid+1，直接在右半部分接着搜索。
            }else if(nums[mid]<target){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return new int[]{first,end};
    }
}

51、最长公共子序列（难-低-原理不理解）

代码：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(),n2 = text2.length();
        int[][] dp = new int[n1+1][n2+1];
        //当i为0或j为0代表text为空，此时公共子序列长度为0。
        //dp[i-1][j-1]存储的是text1[0到i-1]，text2[0到j-1]的公共子序列长度。
        for(int i=1;i<=n1;i++){
            int x = text1.charAt(i-1);
            for(int j=1;j<=n2;j++){
                int y = text2.charAt(j-1);
                if(x==y){ //代表text1[0:i-1]和text2[0:j-1]含有公共子序列。
                    dp[i][j] = dp[i-1][j-1]+1; //加上“1”个公共元素。
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[n1][n2];
    }
}

52、排序链表（难-中-思路不清晰）

重点1：在一个类里能定义多个相同函数名但参数不同的函数。

易错1：如果头节点下一个节点为尾节点要让头结点下一个节点置空，不然会返回尾结点。

易错2：求中点的时候，判断条件要是不等于尾结点，并且如果要访问fast.next.next结点，只需要fast.next不为null即可。

易错3：合并过程前期是比大小，最后是收尾阶段，收尾只收不为null的节点。

代码：

​
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head,null); //重点1:能用相同函数名不同参数重写
    }
    public ListNode sortList(ListNode head,ListNode tail){
        if(head==null) return head;
        if(head.next==tail){
            head.next =null; //易错1:head.next要置为null
            return head;
        }
        
        ListNode slow = head,fast = head;
        while(fast!=tail && fast.next!=tail){ //易错2:不是不等于null而是tail，fast!=tail&&fast.next!=tail
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head,mid);
        ListNode list2 = sortList(mid,tail);
        ListNode sorted = merge(list1,list2);
        return sorted;
    }
    public ListNode merge(ListNode list1,ListNode list2){
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy,temp1 = list1,temp2 = list2;
        while(temp1!=null && temp2!=null){
            if(temp1.val<=temp2.val){
                temp.next = temp1;
                temp1 = temp1.next;
            }else{
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if(temp1!=null){ //易错3:最后收尾，只需要收不为null的节点
            temp.next = temp1;
        }else if(temp2!=null){
            temp.next = temp2;
        }
        return dummy.next;
    }
}

​

53、删除链表中重复元素（中-低-原理不理解）

易错点1：p.next也要不为null

重点1：不相等时，取消对相等元素的链接

重点2：相等时，直接移动到下一个节点

代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return null;
        ListNode dummy = new ListNode(-1000,head);
        ListNode p = dummy;
        while(p!=null && p.next!=null){ //易错点1:p.next也要不为null
            if(p.val==p.next.val){ //重点1:不相等时，取消对相等元素的链接
                p.next = p.next.next;
            }else{ //重点2:相等时，直接移动到下一个节点
                p = p.next;   
            }
        }
        return head;
    }
}