[知识总结] 【CodeTop x LeetCode】Page 1 ： 1-20面试高频算法题题解

之后博主会出一个系列专门记录CodeTop高频算法题的一个详解，一次更新20道，也就是一页的数量。更多答案也可以关注我的GitHub算法仓库——Algorithm

（大家可以根据我每道题打的星来衡量这道题的难易，星越少越难）

所有代码都是在力扣上提交通过的，保证代码的正确无误

基础数据结构：

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

206.反转链表

这应该是链表里最基础、最常问的一道算法题了，相比链表简单的插入删除要复杂一些，可以根据代码把图画一遍方便理解，但还是容易忘，记住要点是一个 while 循环里四行ListNode的交换操作：

public ListNode reverseList(ListNode head) {
        ListNode prev = null, next = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

146.LRU缓存机制

这道题在Java里可以通过LinkedHashMap实现，但是面试肯定不能这么说，需要使用 哈希表 + 双向链表 ，可以说又是一道大量链表的操作题，有助于锻炼对链表操作的理解：

class LRUCache {
         //双向链表
        class DLinkedNode {
            int key;
            int value;
            DLinkedNode prev;
            DLinkedNode next;
            DLinkedNode() {}
            DLinkedNode(int _key, int _value) {
                key = _key;
                value = _value;
            }
        }

        private Map<Integer, DLinkedNode> cache = new HashMap<>();
        private int size;
        private int capacity;
        private DLinkedNode head, tail;

        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            // 使用伪头部和伪尾部节点
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                return -1;
            }
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cache.get(key);
            if (node == null) {
                if (size >= capacity) {
                    removeTail();
                    size--;
                }
                addToHead(new DLinkedNode(key, value));
                size++;
            }else {
                node.value = value;
                moveToHead(node);
            }
        }
        //加入头部
        private void addToHead(DLinkedNode node) {
            node.prev = head;
            node.next = head.next;
            node.next.prev = node;
            head.next = node;
            cache.put(node.key, node);
        }
        //移动到头部
        private void moveToHead(DLinkedNode node) {
            removeNode(node);
            addToHead(node);
        }
        //移除尾部
        private void removeTail() {
            removeNode(tail.prev);
        }
        //删除节点，记者也要更新哈希表
        private void removeNode(DLinkedNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            cache.remove(node.key);
        }
    }

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

这道题的最优解是使用滑动窗口，同时需要用到Set集合，我认为还是比较有难度的

public int lengthOfLongestSubstring(String s) {
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            int rk = -1, ans = 0;
            for (int i = 0; i < n; i++) {
                if (i != 0) {
                    occ.remove(s.charAt(i - 1));
                }
                while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                    occ.add(s.charAt(rk + 1));
                    rk++;
                }
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }

215.数组中的第K个最大的数

主要考查排序，大家可以把它当作考堆排的算法题。

25.K个一组翻转链表

在第一道翻转链表的基础上难度又提升了一级，需要使用到递归（这道题我当时做了好久没做出来....）

public ListNode reverseKGroup(ListNode head, int k) {
            // 如果头节点为null或者节点只有一个直接返回
            if (head == null || head.next == null) {
                return head;
            }
            //保存每一段反转的头尾指针
            ListNode tail = head;
            //循环k次，找到尾部
            for (int i = 0; i < k; i++) {
                //如果不够k个就结束了，这一段不反转直接返回头部
                if (tail == null) {
                    return head;
                }
                tail = tail.next;
            }
            //反转后记录这一段的头部
            ListNode newHead = reverse(head, tail); // [ )
            //这里的head其实按这一段的顺序已经是指向尾部了
            // 这里的head.next需要指向下一段的头部（就是它反转后的tail）
            //每一段反转后，一开始的head最后指向尾，一开始的tail最后指向头
            head.next = reverseKGroup(tail, k);
            return newHead;
        }

        //根据头尾指针反转，每一段反转后，一开始的head最后指向尾，一开始的tail最后指向头
        public ListNode reverse(ListNode head, ListNode tail) {
            ListNode pre = null, next = null;
            while (head != tail) {
                next = head.next;
                head.next = pre;
                pre = head;
                head = next;
            }
            return pre;
        }

补充题4. 手撕快速排序

就是考快排

15.三数之和

最优解：排序+双指针

public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>();
            int lastA = -9999999;
            for (int i = 0; i < nums.length-2; i++) {
                if (nums[i] > 0) {
                    return result;
                }
                if (nums[i] == lastA) {
                    continue;
                }
                lastA = nums[i];
                int lastLeft = -9999999;
                int right = nums.length;
                for (int j = i+1; j < right - 1; j++) {
                    if (nums[j] == lastLeft) {
                        continue;
                    }
                    for (int k = right - 1; k > j; k--) {
                        if (nums[i] + nums[j] + nums[k] == 0) {
                            List<Integer> temp = new ArrayList<>();
                            temp.add(nums[i]);
                            temp.add(nums[j]);
                            temp.add(nums[k]);
                            result.add(temp);
                            right = k;
                            break;
                        }
                    }
                    lastLeft = nums[j];
                }
            }
            return result;
        }

53.最大子序和

动态规划，但是空间复杂度是O(1)，每次只保存当前的最优解

public int maxSubArray(int[] nums) {
            int res = nums[0];
            for (int i = 1; i < nums.length; i++) {
                if (nums[i-1] > 0) {
                    nums[i]+=nums[i-1];
                }
                res = res > nums[i] ? res:nums[i];
            }
            return res;
        }

1.两数之和

哈希表，空间换时间，每次存这个数，找哈希表里的另一半target-nums[i]

    public int[] twoSum(int[] nums, int target) {
        Map<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 null;
    }

141.环形链表

经典链表题：快慢指针，相遇则有环，任意一个为null则无环

    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        while (head != null && fast != null) {
            head = head.next;
            fast = fast.next;
            if (fast != null) {
                fast = fast.next;
            }else {
                break;
            }
            if (head == fast) {
                return true;
            }
        }
        return false;
    }

21.合并两个有序链表

思路：递归

   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            if (l1.val < l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else {
                l2.next = mergeTwoLists(l2.next, l1);
                return l2;
            }
        }

102.二叉树的层序遍历

典型的队列题目

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    ArrayDeque<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> level = new ArrayList<>();
        int curLevelSize = queue.size();
        for (int i = 0; i < curLevelSize; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
                if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        res.add(level);
    }
    return res;
}

160.相交链表

两个指针分别移动，到末尾之后移到对方链表上继续移动，相等时返回

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            ListNode pA = headA;
            ListNode pB = headB;
            while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

121.买卖股票的最佳时机

一次for循环，每次记录最小值，以及更新最大利润

    public int maxProfit(int[] prices) {
        int res = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            if (min > prices[i]) {
                min = prices[i];
            }else {
                res = Math.max(res, prices[i] - min);
            }
        }
        return res;
    }

88.合并两个有序数组

根据有序和空位这两个特点，我们从nums1末尾开始比较插入

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int n1 = m -1;
    int n2 = n -1;
    while (n2 >= 0) {
        if (n1 >= 0 && nums1[n1] >= nums2[n2]) {
            nums1[n1+n2+1] = nums1[n1];
            n1--;
        }else {
            nums1[n1+n2+1] = nums2[n2];
            n2--;
        }
    }
}

103.二叉树的锯齿形层次遍历

这道题我也是按自己的方法去写的，也是有些麻烦，用了队列和集合倒来倒去

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) {
        return res;
    }
    Queue<Object[]> queue = new ArrayDeque<>();
    Object[] arr = new Object[2];
    arr[0] = root;
    arr[1] = 1;
    queue.offer(arr);
    int cur = 1;
    List<Integer> list = new ArrayList<>();
    List<Object[]> tempList = new ArrayList<>();
    while (queue.size() != 0) {
        Object[] temp = queue.poll();
        TreeNode tn = (TreeNode)temp[0];
        Integer floor = (Integer)temp[1];
        if (tn != null) {
            if (floor % 2 == 0) {
                if (tn.right != null) {
                    tempList.add(new Object[]{tn.right, floor + 1});
                }
                if (tn.left != null) {
                    tempList.add(new Object[]{tn.left, floor + 1});
                }
            }else {
                if (tn.left != null) {
                    tempList.add(new Object[]{tn.left, floor + 1});
                }
                if (tn.right != null) {
                    tempList.add(new Object[]{tn.right, floor + 1});
                }
            }
            if (cur == floor) {
                list.add(tn.val);
            }else {
                res.add(list);
                list = new ArrayList<>();
                list.add(tn.val);
                cur = floor;
            }
        }
        if (queue.size() == 0) {
            while (tempList.size() > 0) {
                queue.offer(tempList.get(tempList.size() - 1));
                tempList.remove(tempList.size() - 1);
            }
        }
    }
    res.add(list);
    return res;
}

236.二叉树的最近公共祖先（LCA）

思路是递归，但是难点在于节点的判断：

class Solution {
    private TreeNode ans;
    public Solution() {
        this.ans = null;
    }
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root.val == p.val || root.val == q.val);
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }
}

10.有效的括号

正常的思路是用栈来做的，但是可以取巧，把括号替换为空字符串来判断：

public boolean isValid(String s) {
    boolean res = false;
    while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
        s = s.replace("()", "");
        s = s.replace("[]", "");
        s = s.replace("{}", "");
    }
    if (s.length() == 0) {
        res = true;
    }
    return res;
}

415.字符串相加

模拟加法计算：

public String addStrings(String num1, String num2) {
    if (num2.length() > num1.length()) {
        String temp = num1;
        num1 = num2;
        num2 = temp;
    }
    int yu = 0;
    String s = "";
    for (int i = 1; i <= num1.length(); i++) {
        int sum = 0;
        int a = Integer.valueOf(num1.charAt(num1.length() - i) + "");
        if (i <= num2.length()) {
            int b = Integer.valueOf(num2.charAt(num2.length() - i) + "");
            sum = a+b+yu;
        }else {
            sum = a+yu;
        }
        if (sum >= 10) {
            yu = 1;
            s = (sum-10) + s;
        }else {
            yu = 0;
            s = sum + s;
        }
    }
    if (yu == 1) {
        s = 1 + s;
    }
    return s;
}

5. 最长回文子串

经典动态规划，动规思路：判断一个字符串是否回文=头尾相等+中间部分回文，dp数组代表了所有长度子串是否回文：

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    int len = s.length();
    String res = s.charAt(0) + "";
    boolean[][] dp = new boolean[len][len];
    for (int j = 0; j < len; j++) {
        for (int i = 0; i <= j; i++) {
            if (i == j) {
                dp[i][j] = true;
            }else {
                dp[i][j] = ((dp[i + 1][j - 1]) || (j - i < 3)) && (s.charAt(i) == s.charAt(j));
            }
            if (dp[i][j] && j - i > res.length() - 1) {
                res = s.substring(i, j+1);
            }
        }
    }
    return res;
}