leetcode

> 编程语言

Open source

参考@CyC2018的leetcode题解。Java工程师LeetCode刷题必备。主要根据LeetCode的tag进行模块划分，每部分都选取了比较经典的题目，题目以medium和easy为主，少量hard题目。

697 stars0 likes2 views

Website GitHub

About

算法思想
数据结构相关
- 栈和队列
- 哈希表
- 字符串
- 数组与矩阵
  - 1-n 分布
  - 有序矩阵
- 链表
- 树
  - 递归
  - 层次遍历
  - 前中后序遍历
  - BST
  - Trie
- 图
- 位运算
参考资料

算法思想

二分查找

java

public int search(int key, int[] array) {
    int l = 0, h = array.length - 1;
    while (l  0) {
        n -= level;
        level++;
    }
    return n == 0 ? level - 1 : level - 2;
}

有序数组的 Single Element

Leetcode : 540. Single Element in a Sorted Array (Medium)

xml

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

题目描述：一个有序数组只有一个数不出现两次，找出这个数。

java

public int singleNonDuplicate(int[] nums) {
    int l = 0, h = nums.length - 1;
    while(l  (a[1] - b[1]));
    int curPos = points[0][1];
    int ret = 1;
    for (int i = 1; i  0，那么就把 prices[i] - prices[i-1] 添加加到收益中，从而在局部最优的情况下也保证全局最优。

```java
public int maxProfit(int[] prices) {
    int profit = 0;
    for(int i = 1; i  prices[i-1]) profit += (prices[i] - prices[i-1]);
    }
    return profit;
}

种植花朵

Leetcode : 605. Can Place Flowers (Easy)

xml

Input: flowerbed = [1,0,0,0,1], n = 1
Output: True

题目描述：花朵之间至少需要一个单位的间隔。

java

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int cnt = 0;
    for(int i = 0; i = n;
}

修改一个数成为非递减数组

Leetcode : 665. Non-decreasing Array (Easy)

xml

Input: [4,2,3]
Output: True
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

题目描述：判断一个数组能不能只修改一个数就成为非递减数组。

在出现 nums[i] = 0 && nums[i - 2] > nums[i]) nums[i] = nums[i-1]; else nums[i - 1] = nums[i]; } } return cnt (); int[] lastIdxs = new int[26]; for(int i = 0; i endIdx) endIdx = lastIdx; } ret.add(endIdx - startIdx + 1); startIdx = endIdx + 1; } return ret; }


**根据身高和序号重组队列** 

[Leetcode : 406. Queue Reconstruction by Height(Medium)](https://leetcode.com/problems/queue-reconstruction-by-height/description/)

```html
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

题目描述：一个学生用两个分量 (h, k) 描述，h 表示身高，k 表示排在前面的有 k 个学生的身高比他高或者和他一样高。

为了在每次插入操作时不影响后续的操作，身高较高的学生应该先做插入操作，否则身高较小的学生原先正确插入第 k 个位置可能会变成第 k+1 个位置。

身高降序、k 值升序，然后按排好序的顺序插入队列的第 k 个位置中。

…

java public boolean judgeSquareSum(int c) { int left = 0, right = (int) Math.sqrt(c); while(left c) right--; else left++; } return false; }


**回文字符串** 

[Leetcode : 680. Valid Palindrome II (Easy)](https://leetcode.com/problems/valid-palindrome-ii/description/)

```html
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

题目描述：字符串可以删除一个字符，判断是否能构成回文字符串。

java

public boolean validPalindrome(String s) {
    int i = 0, j = s.length() -1;
    while(i = 0 || j >= 0){
        if(i  nums2[j]) nums1[idx] = nums1[i--];
        else nums1[idx] = nums2[j--];
        idx--;
    }
}

判断链表是否存在环

Leetcode : 141. Linked List Cycle (Easy)

使用双指针，一个指针每次移动一个节点，一个指针每次移动两个节点，如果存在环，那么这两个指针一定会相遇。

java

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

最长子序列

Leetcode : 524. Longest Word in Dictionary through Deleting (Medium)

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output:
"apple"

题目描述：可以删除 s 中的一些字符，使得它成为字符串列表 d 中的一个字符串。要求在 d 中找到满足条件的最长字符串。

java

public String findLongestWord(String s, List d) {
    String ret = "";
    for (String str : d) {
        for (int i = 0, j = 0; i  0)) {
                    ret = str;
                }
            }
        }
    }
    return ret;
}

排序

快速选择

一般用于求解 Kth Element 问题，可以在 O(n) 时间复杂度，O(1) 空间复杂度完成求解工作。

与快速排序一样，快速选择一般需要先打乱数组，否则最坏情况下时间复杂度为 O(n2)。

堆排序

堆排序用于求解 TopK Elements 问题，通过维护一个大小为 K 的堆，堆中的元素就是 TopK Elements。当然它也可以用于求解 Kth Element 问题，因为最后出堆的那个元素就是 Kth Element。快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，所有小于等于 Kth Element 的元素都是 TopK Elements。可以看到，快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。

Kth Element

Leetocde : 215. Kth Largest Element in an Array (Medium)

排序：时间复杂度 O(nlgn)，空间复杂度 O(1) 解法

java

public int findKthLargest(int[] nums, int k) {
        int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
}

堆排序 ：时间复杂度 O(nlgk)，空间复杂度 O(k)

java

public int findKthLargest(int[] nums, int k) {
    PriorityQueue pq = new PriorityQueue<>();
    for(int val : nums) {
        pq.offer(val);
        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

快速选择 ：时间复杂度 O(n)，空间复杂度 O(1)

java

public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo  k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }

    private int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        while(true) {
            while(i  lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    private void exch(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private boolean less(int v, int w) {
        return v ();
    Map map = new HashMap<>();
    for(int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    List[] bucket = new List[nums.length + 1];
    for(int key : map.keySet()) {
        int frequency = map.get(key);
        if(bucket[frequency] == null) {
            bucket[frequency] = new ArrayList<>();
        }
        bucket[frequency].add(key);
    }

    for(int i = bucket.length - 1; i >= 0 && ret.size() i 表示第 i 个节点与根节点的路径长度，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 dij。利用这个结论，可以求解最短路径  **最优解**  问题：第一次遍历到目的节点，其所经过的路径为最短路径，如果继续遍历，之后再遍历到目的节点，所经过的路径就不是最短路径。

在程序实现 BFS 时需要考虑以下问题：

- 队列：用来存储每一轮遍历的节点
- 标记：对于遍历过得节点，应该将它标记，防止重复遍历；

**计算在网格中从原点到特定点的最短路径长度** 

```html
[[1,1,0,1],
[1,0,1,0],
[1,1,1,1],
[1,0,1,1]]

…

DFS

广度优先搜索一层一层遍历，每一层遍历到的所有新节点，要用队列先存储起来以备下一层遍历的时候再遍历；而深度优先搜索在遍历到一个新节点时立马对新节点进行遍历：从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用 DFS 对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS 常用来求解这种 可达性 问题。

在程序实现 DFS 时需要考虑以下问题：

栈：用栈来保存当前节点信息，当遍历新节点返回时能够继续遍历当前节点。也可以使用递归栈。
标记：和 BFS 一样同样需要对已经遍历过得节点进行标记。

查找最大的连通面积

Leetcode : 695. Max Area of Island (Easy)

xml

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

java

public int maxAreaOfIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int max = 0;
    for(int i = 0; i = m || j = n) return 0;
    if(grid[i][j] == 0) return 0;
    grid[i][j] = 0;
    return dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1) + 1;
}

图的连通分量

Leetcode : 547. Friend Circles (Medium)

xml

Input:
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle.
The 2nd student himself is in a friend circle. So return 2.

java

public int findCircleNum(int[][] M) {
    int n = M.length;
    int ret = 0;
    boolean[] hasFind = new boolean[n];
    for(int i = 0; i = m || j = n || grid[i][j] == '0') return;
    grid[i][j] = '0';
    for (int k = 0; k 2->5", "1->3"]

java

public List binaryTreePaths(TreeNode root) {
    List ret = new ArrayList();
    if(root == null) return ret;
    dfs(root, "", ret);
    return ret;
}

private void dfs(TreeNode root, String prefix, List ret){
    if(root == null) return;
    if(root.left == null && root.right == null){
        ret.add(prefix + root.val);
        return;
    }
    prefix += (root.val + "->");
    dfs(root.left, prefix, ret);
    dfs(root.right, prefix, ret);
}

填充封闭区域

Leetcode : 130. Surrounded Regions (Medium)

xml

For example,
X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

题目描述：使得被 'X' 的 'O' 转换为 'X'。

先填充最外侧，剩下的就是里侧了。

…

N 皇后

Leetcode : 51. N-Queens (Hard)

题目描述：在 n*n 的矩阵中摆放 n 个皇后，并且每个皇后不能在同一行，同一列，同一对角线上，要求解所有的 n 皇后解。

一行一行地摆放，在确定一行中的那个皇后应该摆在哪一列时，需要用三个标记数组来确定某一列是否合法，这三个标记数组分别为：列标记数组、45 度对角线标记数组和 135 度对角线标记数组。

45 度对角线标记数组的维度为 2*n - 1，通过下图可以明确 (r,c) 的位置所在的数组下标为 r + c。

135 度对角线标记数组的维度也是 2*n - 1，(r,c) 的位置所在的数组下标为 n - 1 - (r - c)。

…

在矩阵中寻找字符串

Leetcode : 79. Word Search (Medium)

xml

For example,
Given board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

…

分割整数构成字母字符串

Leetcode : 91. Decode Ways (Medium)

题目描述：Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

…

html len = 1 : [4], [5], [6], [3] => tails[0] = 3 len = 2 : [4, 5], [5, 6] => tails[1] = 5 len = 3 : [4, 5, 6] => tails[2] = 6


对于一个元素 x，如果它大于 tails 数组所有的值，那么把它添加到 tails 后面；如果 tails[i-1] i 位于 tails 数组的位置时就可以使用二分查找。

```java
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] tails = new int[n];
    int size = 0;
    for(int i = 0; i  key) eIdx = mIdx;
        else sIdx = mIdx + 1;
    }
    return sIdx;
}

最长摆动子序列

Leetcode : 376. Wiggle Subsequence (Medium)

要求：使用 O(n) 时间复杂度求解。

使用两个状态 up 和 down。

java

public int wiggleMaxLength(int[] nums) {
    int len = nums.length;
    if (len == 0) return 0;
    int up = 1, down = 1;
    for (int i = 1; i  nums[i - 1]) up = down + 1;
        else if (nums[i] i 与 S2j 值是否相等，分为两种情况：

① 当 S1i==S2j 时，那么就能在 S1 的前 i-1 个字符与 S2 的前 j-1 个字符最长公共子序列的基础上再加上 S1i 这个值，最长公共子序列长度加 1 ，即 dp[i][j] = dp[i-1][j-1] + 1。

② 当 S1i != S2j 时，此时最长公共子序列为 S1 的前 i-1 个字符和