leetcode

解题思路

• 有序，二分查找
• 双指针
• cache缓存
• 有限空间，数组
• 图，BFS DFS
• 确认边界case、数据范围
• 沟通、确认思路
• 链表：通过dummy节点方便删除、修改操作。
• 整数运算注意溢出的情况

二维数组方向类

进行方向遍历。

常用类的API

• String.length()
• `String.isEmpty()
• StringBuilder.reverse()
• Arrays.sort(int[] arr)
• 数组：一维数组，int[] a = new int[len]; 二维数组，int[][] b = new int[length1][length2];

comparator

// 生成一个比较p类val值(int)的Comparator
Comparator.comparingInt(p -> p.val);
// 或者直接创建对象使用匿名内部类
new Comparator<XXX>() {
    public int compare(XXX x1, XXX x2) {
        return Integer.compare(x1.xxx, x2.xxx);
    }
}

常用技巧

二维数组

保存方向数组快速遍历

// 参数检查检查
// ...
// 保存长宽
int m = array.length;
int n = array[0].length;
Queue<int[]> queue = new ArrayDeque<>();
int[] dirx = new int[] {1,-1,0,0};
int[] diry = new int[] {0,0,1,-1};

while (!queue.isEmpty()) {
    int[] poll = queue.poll();
    int x = poll[0];
    int y = poll[1];
        for (int i = 0; i < 4; i++) {
            int newX = x + dirx[i];
            int newY = y + diry[i];
            if (newX >= 0 && newX < m && newY >=0 && newY < n) {
                // BFS处理
                queue.offer(new int[] {newX, newY});
            }   
        }
}

图相关模版

BFS

// 创建需要的数据结构
boolean[] visited = new boolean[length];
List<Integer> prev = new ArrayList();
List<Integer> next = new ArrayList();

// 初始化prev元素
prev.add(firstNode)

while (!prev.isEmpty() {
    for (int nodeIndex : prev) {
        // 根据具体的问题对每个node做处理
        doSomething(nodeIndex)
        // 记录下这个node已经访问过了
        visited[nodeIndex] = true;
        // 对从当前node可以直达的下一个node，如果没有访问过，加到next中
        for (adjacentNodeIndex in getAdjacentList(nodeIndex)node.adjacentList) {
            if (!visited[adjacentNodeIndex]) {
                next.add(adjacentNodeIndex)
            }
        }
    }
    // 交换prev next
    prev = next;
    next = new ArrayList();
}

DFS

int dfs(Graph graph, boolean[] visited, int index) {
    visited[index] = true;
    int[] adjacent = graph.adjacent(index);
    for (int adj : adjacent) {
        if (!visited[]) {
            // 递归处理货拿到dfs的结果，有的题目会要求汇总所有的节点的结果
            dfs(graph, visited, adj);
        }
    }
    // 对本节点执行某些操作，有可能会依赖从这个节点直接能够达到的邻接节点的结果
    doSomething(graph, index);
}

前100记录

3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

双指针思路 保存一个Map<Integer, Integer> key是char的int值，value是之前出现的index。 维护一个max记录最大值。 初始left=right=0; 结束条件为right==length 每次循环，判断，right的值是否在map中 如果在，则将left移动到index+1，并且从map中删除期间的value。并且put新的right的映射。 如果不在，则保存right的映射，right向右移动，并计算max

if (s == null || s.isEmpty()) {
            return 0;
        }
        int left = 0;
        int right = 0;
        Map<Integer, Integer> charIntValueToIndexMap = new HashMap<>();

        int max = 0;
        while (left <= right && right < s.length()) {
            int rightCharValue = s.charAt(right);
            Integer index = charIntValueToIndexMap.get(rightCharValue);
            if (index != null) {
                for (int i = left; i < index; i++) {
                    charIntValueToIndexMap.remove((int)s.charAt(i));
                }
                left = index + 1;
                charIntValueToIndexMap.put(rightCharValue, right);
                right++;
            } else {
                charIntValueToIndexMap.put(rightCharValue, right);
                right ++;
                max = Math.max(max, right - left);
            }
        }
        return max;

5 最长回文子串

思路：中心扩散法，对每个index，计算(index, index)和(index, index + 1 )开始查找最长的回文子串

public String longestPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        int maxLength = 0;
        int[] maxPair = new int[] {0, 0};
        for (int i = 0; i < s.length(); i++) {
            int[] pair1 = palindromePair(s, i, i);
            if (pair1[1] - pair1[0] > maxLength) {
                maxPair = pair1;
                maxLength = pair1[1] - pair1[0];
            }
            int[] pair2 = palindromePair(s, i, i + 1);
            if (pair2[1] - pair2[0] > maxLength) {
                maxPair = pair2;
                maxLength = pair2[1] - pair2[0];
            }
        }
        return s.substring(maxPair[0], maxPair[1] + 1);
    }

    private int[] palindromePair(String s, int startLeft, int startRight) {
        boolean isPalindromePair = false;
        while (startLeft >= 0 && startRight < s.length()
            && s.charAt(startLeft) == s.charAt(startRight)) {
            isPalindromePair = true;
            startLeft--;
            startRight++;
        }
        return isPalindromePair ? new int[]{startLeft + 1, startRight - 1} : new int[]{startLeft, startLeft};
    }

7. Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

需要注意溢出的情况

8. String to Integer

分阶段处理各个部分的值，注意

• 空格
• 正负号
• 32位溢出
• 尾部非数字字符

public int myAtoi(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int result = 0;
        // ignore ' ' char
        int index = 0;
        while (index < s.length() && s.charAt(index) == ' ') {
            index++;
        }
        int sign = 1;
        if (index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')) {
            sign = s.charAt(index) == '+' ? 1 : -1;
            index++;
        }
        while (index < s.length()) {
            int digit = s.charAt(index) - '0';
            if (digit < 0 || digit > 9) {
                break;
            }
            if (result > (Integer.MAX_VALUE - digit) / 10) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            result = result * 10 + digit;
            index ++;
        }
        return result * sign;
    }

23. Merge K sorted List

使用一个PriorityQueue<ListNode>保存当前最小的Node的队列。 注意判空和head、tail的处理。

public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            ListNode result = null;
            ListNode tail = null;
            PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(p -> p.val));
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] != null) {
                    priorityQueue.add(lists[i]);
                }
            }
            while (!priorityQueue.isEmpty()) {
                ListNode poll = priorityQueue.poll();
                ListNode next = poll.next;
                poll.next = null;
                if (next != null) {
                    priorityQueue.add(next);
                }
                if (result == null) {
                    result = poll;
                    tail = poll;
                } else {
                    tail.next = poll;
                    tail = poll;
                }
            }
            return result;
        }

25 Reverse every K List 链表K个一组翻转

解题思路：在纸上模拟，处理好prev、next。

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode tail = head;
        for (int i = 1; i < k; i++) {
            tail = tail.next;
            if (tail == null) {
                return head;
            }
        }
        ListNode nextHead = tail.next;
        tail.next = null;
        ListNode[] listNodes = doReverse(head);
        ListNode newHead = listNodes[0];
        ListNode newTail = listNodes[1];
        newTail.next = reverseKGroup(nextHead, k);
        return newHead;
    }

    // [head,tail]
    private ListNode[] doReverse(ListNode head) {
        // null check
        ListNode newHead = null;
        ListNode newTail = head;
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return new ListNode[] {newHead, newTail};
    }

42. Trapping Rain Water

接雨水

解题思路：定义一个leftHighest数组，记录每个index上左边最高的height（包含自己），再定义一个rightHighest为每个index上右边最高的height（包含自己） leftHighest(index) = max(leftHighest(index-1), height(index)) 每个index上能够接到的雨水为min(leftHighest, rightHighest) - height(index)。 把这些加起来就是最终结果

public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        // 解题思路：定义一个leftHighest数组，记录每个index上左边最高的height（包含自己），再定义一个rightHighest为每个index上右边最高的height（包含自己）
        // leftHighest(index) = max(leftHighest(index-1), height(index))
        // 每个index上能够接到的雨水为min(leftHighest, rightHighest) - height(index)。
        // 连续大于0的能接到的雨水的和的最大值就是最终结果。
        int[] leftHighest = new int[height.length];
        int[] rightHighest = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            leftHighest[i] = i == 0 ? height[i] : Math.max(leftHighest[i - 1], height[i]);
        }
        for (int i = height.length - 1; i >=0;  i--) {
            rightHighest[i] = i == height.length - 1 ? height[i] : Math.max(rightHighest[i + 1], height[i]);
        }
        int[] contained = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            if (i == 0 || i == height.length - 1) {
                contained[i] = 0;
            } else {
                contained[i] = Math.min(leftHighest[i - 1], rightHighest[i + 1]) - height[i];
                contained[i] = Math.max(contained[i], 0);
            }
        }
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            result += contained[i];
        }
        return result;
    }

16. 3Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

固定第一个数，双指针确定另外两个数

45. Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

解决方法：层级遍历

if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return 0;
        }
        int step = 0;
        /**
         * BFS层次遍历。
         */
        List<Integer> currentLevel = new ArrayList<>();
        List<Integer> nextLevel = new ArrayList<>();
        int[] visited = new int[nums.length];
        currentLevel.add(0);
        while (!currentLevel.isEmpty()) {
            step ++;
            for (int index : currentLevel) {
                int jump = nums[index];
                if (index + jump >= nums.length - 1) {
                    return step;
                }
                for (int i = index; i < Math.min(index + jump + 1, nums.length); i++) {
                    if (visited[i] == 0) {
                        visited[i] = 1;
                        nextLevel.add(i);
                    }
                }
            }
            currentLevel = nextLevel;
            nextLevel = new ArrayList<>();
        }
        return step;

18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n a, b, c, and d are distinct. nums[a] + nums[b] + nums[c] + nums[d] == target You may return the answer in any order.

解题思路：保存两个数字的和和对应的index的映射。

19. remove倒数第N个节点。

删除节点需要记录previous，为了简化实现，在head节点前增加一个dummy节点。

记录两个指针，first, second。 second用于确认结尾，first用于记录倒数第(n+1)个节点。 先从dummy开始遍历n次，second不断右移，到了n次后，这时first指向dummy。 然后first和second一起右移，直到second.next==null。 这时first.next就是倒数第n个节点，然后通过first.next = first.next.next完成移除。

ListNode dummy = new ListNode(0, head);
        ListNode first;
        ListNode second = dummy;
        for (int i = 0; i < n; i++) {
            second = second.next;
        }
        first = dummy;
        while (second.next != null) {
            second = second.next;
            first = first.next;
        }
        if (first.next != null) {
            first.next = first.next.next;
        }
        return dummy.next;

39. Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

解题思路: dfs路径遍历。通过Set去重。

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return Collections.emptyList();
        }
        LinkedList<Integer> path = new LinkedList<>();
        Set<List<Integer>> result = new HashSet<>();
        dfs(candidates, target, path, result);
        return new ArrayList<>(result);
    }

    private void dfs(int[] candidates, int target, LinkedList<Integer> path, Set<List<Integer>> result) {
        if (target == 0) {
            ArrayList<Integer> thisResult = new ArrayList<>(path);
            Collections.sort(thisResult);
            result.add(thisResult);
            return;
        }
        for (int i = 0; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                path.add(candidates[i]);
                dfs(candidates, target - candidates[i], path, result);
                path.removeLast();
            }
        }
    }

17. Letter Combinations of a Phone Number

解题思路：从后向前遍历，从map获取letters进行遍历保存结果。

public List<String> letterCombinations(String digits) {
        Map<String, List<String>> digitToLettersMap = new HashMap<>();
        digitToLettersMap.put("2", split("abc"));
        digitToLettersMap.put("3", split("def"));
        digitToLettersMap.put("4", split("ghi"));
        digitToLettersMap.put("5", split("jkl"));
        digitToLettersMap.put("6", split("mno"));
        digitToLettersMap.put("7", split("pqrs"));
        digitToLettersMap.put("8", split("tuv"));
        digitToLettersMap.put("9", split("wxyz"));

        List<String> result = new ArrayList<>();
        for (int i = digits.length() - 1; i >= 0; i--) {
            List<String> newResult = new ArrayList<>();
            String digit = digits.substring(i, i + 1);
            List<String> letters = digitToLettersMap.get(digit);
            for (String letter : letters) {
                if (result.isEmpty()) {
                    newResult.add(letter);
                } else {
                    for (String r : result) {
                        newResult.add(letter + r);
                    }
                }
            }
            result = newResult;
        }
        return result;
    }

    private static List<String> split(String letters) {
        List<String> result = new ArrayList<>();
        for (int i = 0; i < letters.length(); i++) {
            result.add(letters.substring(i, i + 1));
        }
        return result;
    }

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

先排序。 通过visited记录是否使用过，进行回溯遍历。 按照位置进行遍历，遍历到最后一个时，加入到result中。 由于是排序过的，所以在选择元素时，对于重复的未访问过的数据进行过滤跳过。

public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        dfs(new int[nums.length], 0, new LinkedList<>(), nums, result);
        return result;
    }

    private void dfs(int[] visited, int count, LinkedList<Integer> path, int[] nums, List<List<Integer>> result) {
        if (count == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 1 || (i > 0 && nums[i - 1] == nums[i] && visited[i-1] == 0)) {
                continue;
            }
            visited[i] = 1;
            path.add(nums[i]);
            dfs(visited, count + 1, path, nums, result);
            path.removeLast();
            visited[i] = 0;
        }
    }

24. Swap Nodes in Pairs

链表反转，在head之前增加一个dummy方便修改next操作。

public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        doSwapTwo(dummy);
        return dummy.next;
    }

    private void doSwapTwo(ListNode node) {
        if (node.next == null || node.next.next == null) {
            return;
        }
        ListNode oldNext = node.next;
        ListNode newNext = oldNext.next;
        node.next = newNext;
        oldNext.next = newNext.next;
        newNext.next = oldNext;
        doSwapTwo(oldNext);
    }

82. Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

解题思路：记录dummy节点用于删除。 然后判断next是否和next.next相等，如果是，找到第一个不相等的next进行替换，并继续当前节点判断。 否则迭代下一个next。

public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(Integer.MAX_VALUE, head);
        doDeleteDuplicate(dummy);
        return dummy.next;
    }

    private void doDeleteDuplicate(ListNode node) {
        if (node.next == null || node.next.next == null) {
            return;
        }
        ListNode next = node.next;
        int currentNextVal = next.val;
        if (next.next.val == currentNextVal) {
            while (next != null && next.val == currentNextVal) {
                next = next.next;
            }
            node.next = next;
        } else {
            node = node.next;
        }
        doDeleteDuplicate(node);
    }

407 trapRainWater II

解题思路：

保存一个二维数组water[][]，记录接完后所有位置的高度。 初始化时，设置所有的值都为maxHeight（height最大值）。 然后从外层开始进行BFS。 对于每个节点，如果water[i][j]小于周围的water，则修改周围的water为max(water[i][j], 周围的height)，并将周围的这个点放到队列继续遍历。

public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) {
            return 0;
        }
        int result = 0;
        int m = heightMap.length;
        int n = heightMap[0].length;
        int maxHeight = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                maxHeight = Math.max(maxHeight, heightMap[i][j]);
            }
        }
        // 接水之后的高度（包含自身高度）
        int[][] water = new int[m][n];
        int[] dirx = new int[]{1, -1, 0, 0};
        int[] diry = new int[]{0, 0, 1, -1};
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    water[i][j] = heightMap[i][j];
                    queue.add(new int[]{i, j});
                } else {
                    water[i][j] = maxHeight;
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x = poll[0], y = poll[1];
            for (int i = 0; i < 4; i++) {
                int newX = x + dirx[i];
                int newY = y + diry[i];
                if (newX >= 0 && newX < m && newY >= 0 && newY < n) {
                    if (water[x][y] < water[newX][newY]) {
                        water[newX][newY] = Math.max(water[x][y], heightMap[newX][newY]);
                        queue.offer(new int[]{newX,newY});
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result += water[i][j] - heightMap[i][j];
            }
        }
        return result;
    }

86 分隔链表

思路：创建两个链表，记录头尾节点，最后再拼接起来。

public ListNode partition(ListNode head, int x) {
        ListNode leftDummy = new ListNode();
        ListNode leftTail = leftDummy;
        ListNode rightDummy = new ListNode();
        ListNode rightTail = rightDummy;
        while (head != null) {
            ListNode next = head.next;
            int val = head.val;
            if (val < x) {
                leftTail.next = head;
                leftTail = head;
            } else {
                rightTail.next = head;
                rightTail = head;
            }
            head.next = null;
            head = next;
        }
        leftTail.next = rightDummy.next;
        return leftDummy.next;
    }

876 链表中间节点

思路：快慢指针，循环条件判断fast不为null并且fast.next不为null能够处理奇数偶数两种情况

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

141 环形链表

思路：快慢指针

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

142 形成环的相交节点

思路：画图，计算距离。慢节点走了k, 链表头到环起点为m，则从起点到第一次相交点为(k-m)。 而快指针再走k-m次也是到相交节点，所以把慢节点从head开始，重新再次相交的点为结果。

public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

160 两个链表的相交节点

思路：将第一个链表尾节点和第二个链表头相连，转换成题目142。注意返回结果前把链表恢复。

另一种解决方法上保存一个visited set用于判断重复。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode tail = headA;
        while (tail.next != null) {
            tail = tail.next;
        }
        tail.next = headB;
        ListNode fast = headA;
        ListNode slow = headA;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            tail.next = null;
            return null;
        }
        slow = headA;
        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }
        tail.next = null;
        return slow;
    }