算法思想

二分查找

public int search(int key, int[] array) {
    int l = 0, h = array.length - 1;
    while (l <= h) {
        int mid = l + (h - l) / 2;
        if (key == array[mid]) return mid;
        if (key < array[mid])  h = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

实现时需要注意以下细节：

1. 在计算 mid 时不能使用 mid = (l + h) / 2 这种方式，因为 l + h 可能会导致加法溢出，应该使用 mid = l + (h - l) / 2。

2. 对 h 的赋值和循环条件有关，当循环条件为 l <= h 时，h = mid - 1；当循环条件为 l < h 时，h = mid。解释如下：在循环条件为 l <= h 时，如果 h = mid，会出现循环无法退出的情况，例如 l = 1，h = 1，此时 mid 也等于 1，如果此时继续执行 h = mid，那么就会无限循环；在循环条件为 l < h，如果 h = mid - 1，会错误跳过查找的数，例如对于数组 [1,2,3]，要查找 1，最开始 l = 0，h = 2，mid = 1，判断 key < arr[mid] 执行 h = mid - 1 = 0，此时循环退出，直接把查找的数跳过了。

3. l 的赋值一般都为 l = mid + 1。

求开方

Leetcode : 69. Sqrt(x) (Easy)

Input: 4
Output: 2
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

一个数 x 的开方 sqrt 一定在 0 ~ x 之间，并且满足 sqrt == x / sqrt 。可以利用二分查找在 0 ~ x 之间查找 sqrt。

public int mySqrt(int x) {
    if(x <= 1) return x;
    int l = 1, h = x;
    while(l <= h){
        int mid = l + (h - l) / 2;
        int sqrt = x / mid;
        if(sqrt == mid) return mid;
        else if(sqrt < mid) h = mid - 1;
        else l = mid + 1;
    }
    return h;
}

摆硬币

Leetcode : 441. Arranging Coins (Easy)

n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.

题目描述：第 i 行摆 i 个，统计能够摆的行数。

返回 h 而不是 l，因为摆的硬币最后一行不能算进去。

public int arrangeCoins(int n) {
    int l = 0, h = n;
    while(l <= h){
        int m = l + (h - l) / 2;
        long x = m * (m + 1L) / 2;
        if(x == n) return m;
        else if(x < n) l = m + 1;
        else h = m - 1;
    }
    return h;
}

可以不用二分查找，更直观的解法如下：

public int arrangeCoins(int n) {
    int level = 1;
    while (n > 0) {
        n -= level;
        level++;
    }
    return n == 0 ? level - 1 : level - 2;
}

有序数组的 Single Element

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

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

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

public int singleNonDuplicate(int[] nums) {
    int l = 0, h = nums.length - 1;
    while(l < h) {
        int m = l + (h - l) / 2;
        if(m % 2 == 1) m--; // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
        if(nums[m] == nums[m + 1]) l = m + 2;
        else h = m;
    }
    return nums[l];
}

贪心思想

贪心思想保证每次操作都是局部最优的，并且最后得到的结果是全局最优的。

分配饼干

Leetcode : 455. Assign Cookies (Easy)

Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2. 
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

题目描述：每个孩子都有一个满足度，每个饼干都有一个大小，只有饼干的大小大于一个孩子的满足度，该孩子才会获得满足。求解最多可以获得满足的孩子数量。

因为最小的孩子最容易得到满足，因此先满足最小孩子。给一个孩子的饼干应当尽量小又能满足该孩子，这样大饼干就能拿来给满足度比较大的孩子。

证明：假设在某次选择中，贪心策略选择给第 i 个孩子分配第 m 个饼干，并且第 i 个孩子满足度最小，第 m 个饼干为可以满足第 i 个孩子的最小饼干，利用贪心策略最终可以满足 k 个孩子。假设最优策略在这次选择中给 i 个孩子分配第 n 个饼干，并且这个饼干大于第 m 个饼干。我们发现使用第 m 个饼干去替代第 n 个饼干完全不影响后续的结果，因此不存在比贪心策略更优的策略，即贪心策略就是最优策略。

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int i = 0, j = 0;
    while(i < g.length && j < s.length){
        if(g[i] <= s[j]) i++;
        j++;
    }
    return i;
}

投飞镖刺破气球

Leetcode : 452. Minimum Number of Arrows to Burst Balloons (Medium)

Input:
[[10,16], [2,8], [1,6], [7,12]]
Output:
2

题目描述：气球在一个水平数轴上摆放，可以重叠，飞镖垂直射向坐标轴，使得路径上的气球都会刺破。求解最小的投飞镖次数使所有气球都被刺破。

从左往右投飞镖，并且在每次投飞镖时满足以下条件：

1. 左边已经没有气球了；
2. 本次投飞镖能够刺破最多的气球。

public int findMinArrowShots(int[][] points) {
    if(points.length == 0) return 0;
    Arrays.sort(points,(a,b) -> (a[1] - b[1]));
    int curPos = points[0][1];
    int ret = 1;
    for (int i = 1; i < points.length; i++) {
        if(points[i][0] <= curPos) {
            continue;
        }
        curPos = points[i][1];
        ret++;
    }
    return ret;
 }

股票的最大收益

Leetcode : 122. Best Time to Buy and Sell Stock II (Easy)

题目描述：一次交易包含买入和卖出，多个交易之间不能交叉进行。

对于 [a, b, c, d]，如果有 a <= b <= c <= d ，那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ，因此当访问到一个 prices[i] 且 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 添加加到收益中，从而在局部最优的情况下也保证全局最优。

public int maxProfit(int[] prices) {
    int profit = 0;
    for(int i = 1; i < prices.length; i++){
        if(prices[i] > prices[i-1]) profit += (prices[i] - prices[i-1]);
    }
    return profit;
}

种植花朵

Leetcode : 605. Can Place Flowers (Easy)

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

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

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int cnt = 0;
    for(int i = 0; i < flowerbed.length; i++){
        if(flowerbed[i] == 1) continue;
        int pre = i == 0 ? 0 : flowerbed[i - 1];
        int next = i == flowerbed.length - 1 ? 0 : flowerbed[i + 1];
        if(pre == 0 && next == 0) {
            cnt++;
            flowerbed[i] = 1;
        }
    }
    return cnt >= n;
}

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

Leetcode : 665. Non-decreasing Array (Easy)

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

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

在出现 nums[i] < nums[i - 1] 时，需要考虑的是应该修改数组的哪个数，使得本次修改能使 i 之前的数组成为非递减数组，并且 不影响后续的操作 。优先考虑令 nums[i - 1] = nums[i]，因为如果修改 nums[i] = nums[i - 1] 的话，那么 nums[i] 这个数会变大，那么就有可能比 nums[i + 1] 大，从而影响了后续操作。还有一个比较特别的情况就是 nums[i] < nums[i - 2]，只修改 nums[i - 1] = nums[i] 不能令数组成为非递减，只能通过修改 nums[i] = nums[i - 1] 才行。

public boolean checkPossibility(int[] nums) {
    int cnt = 0;
    for(int i = 1; i < nums.length; i++){
        if(nums[i] < nums[i - 1]){
            cnt++;
            if(i - 2 >= 0 && nums[i - 2] > nums[i]) nums[i] = nums[i-1];
            else nums[i - 1] = nums[i];
        }
    }
    return cnt <= 1;
}

判断是否为子串

Leetcode : 392. Is Subsequence (Medium)

s = "abc", t = "ahbgdc"
Return true.

public boolean isSubsequence(String s, String t) {
    for (int i = 0, pos = 0; i < s.length(); i++, pos++) {
        pos = t.indexOf(s.charAt(i), pos);
        if(pos == -1) return false;
    }
    return true;
}

分隔字符串使同种字符出现在一起

Leetcode : 763. Partition Labels (Medium)

Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

public List<Integer> partitionLabels(String S) {
    List<Integer> ret = new ArrayList<>();
    int[] lastIdxs = new int[26];
    for(int i = 0; i < S.length(); i++) lastIdxs[S.charAt(i) - 'a'] = i;
    int startIdx = 0;
    while(startIdx < S.length()) {
        int endIdx = startIdx;
        for(int i = startIdx; i < S.length() && i <= endIdx; i++) {
            int lastIdx = lastIdxs[S.charAt(i) - 'a'];
            if(lastIdx == i) continue;
            if(lastIdx > endIdx) endIdx = lastIdx;
        }
        ret.add(endIdx - startIdx + 1);
        startIdx = endIdx + 1;
    }
    return ret;
}

根据身高和序号重组队列

Leetcode : 406. Queue Reconstruction by Height(Medium)

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 个位置中。

public int[][] reconstructQueue(int[][] people) {
    if(people == null || people.length == 0 || people[0].length == 0) return new int[0][0];
    Arrays.sort(people, new Comparator<int[]>() {
       public int compare(int[] a, int[] b) {
           if(a[0] == b[0]) return a[1] - b[1];
           return b[0] - a[0];
       }
    });
    int n = people.length;
    List<int[]> tmp = new ArrayList<>();
    for(int i = 0; i < n; i++) {
        tmp.add(people[i][1], new int[]{people[i][0], people[i][1]});
    }
    int[][] ret = new int[n][2];
    for(int i = 0; i < n; i++) {
        ret[i][0] = tmp.get(i)[0];
        ret[i][1] = tmp.get(i)[1];
    }
    return ret;
}

双指针

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。

从一个已经排序的数组中找出两个数，使它们的和为 0

Leetcode ：167. Two Sum II - Input array is sorted (Easy)

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

使用双指针，一个指针指向元素较小的值，一个指针指向元素较大的值。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。

如果两个指针指向元素的和 sum == target，那么得到要求的结果；如果 sum > target，移动较大的元素，使 sum 变小一些；如果 sum < target，移动较小的元素，使 sum 变大一些。

public int[] twoSum(int[] numbers, int target) {
    int i = 0, j = numbers.length - 1;
    while (i < j) {
        int sum = numbers[i] + numbers[j];
        if (sum == target) return new int[]{i + 1, j + 1};
        else if (sum < target) i++;
        else j--;
    }
    return null;
}

反转字符串中的元音字符

Leetcode : 345. Reverse Vowels of a String (Easy)

Given s = "leetcode", return "leotcede".

使用双指针，指向待反转的两个元音字符，一个指针从头向尾遍历，一个指针从尾到头遍历。

private HashSet<Character> vowels = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));
public String reverseVowels(String s) {
    if(s.length() == 0) return s;
    int i = 0, j = s.length() - 1;
    char[] result = new char[s.length()];
    while(i <= j){
        char ci = s.charAt(i);
        char cj = s.charAt(j);
        if(!vowels.contains(ci)){
            result[i] = ci;
            i++;
        } else if(!vowels.contains(cj)){
            result[j] = cj;
            j--;
        } else{
            result[i] = cj;
            result[j] = ci;
            i++;
            j--;
        }
    }
    return new String(result);
}

两数平方和

Leetcode : 633. Sum of Square Numbers (Easy)

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

题目描述：判断一个数是否为两个数的平方和，例如 5 = 1² + 2²。

public boolean judgeSquareSum(int c) {
    int left = 0, right = (int) Math.sqrt(c);
    while(left <= right){
        int powSum = left * left + right * right;
        if(powSum == c) return true;
        else if(powSum > c) right--;
        else left++;
    }
    return false;
}

回文字符串

Leetcode : 680. Valid Palindrome II (Easy)

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

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

public boolean validPalindrome(String s) {
    int i = 0, j = s.length() -1;
    while(i < j){
        if(s.charAt(i) != s.charAt(j)){
            return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
        }
        i++;
        j--;
    }
    return true;
}
private boolean isPalindrome(String s, int l, int r){
    while(l < r){
        if(s.charAt(l) != s.charAt(r))
            return false;
        l++;
        r--;
    }
    return true;
}

归并两个有序数组

Leetcode : 88. Merge Sorted Array (Easy)

题目描述：把归并结果存到第一个数组上。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1; // 需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值
    int idx = m + n - 1;
    while(i >= 0 || j >= 0){
        if(i < 0) nums1[idx] = nums2[j--];
        else if(j < 0) nums1[idx] = nums1[i--];
        else if(nums1[i] > nums2[j]) nums1[idx] = nums1[i--];
        else nums1[idx] = nums2[j--];
        idx--;
    }
}

判断链表是否存在环

Leetcode : 141. Linked List Cycle (Easy)

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

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 中的一个字符串，找出能构成的最长字符串。如果有多个相同长度的结果，返回按字典序排序的最大字符串。

public String findLongestWord(String s, List<String> d) {
    String ret = "";
    for (String str : d) {
        for (int i = 0, j = 0; i < s.length() && j < str.length(); i++) {
            if (s.charAt(i) == str.charAt(j)) j++;
            if (j == str.length()) {
                if (ret.length() < str.length()
                        || (ret.length() == str.length() && ret.compareTo(str) > 0)) {
                    ret = str;
                }
            }
        }
    }
    return ret;
}

排序

快速选择

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

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

堆排序

堆排序用于求解 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)

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

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

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

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

public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > 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 < hi && less(a[++i], a[lo]));
            while(j > 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 < w;
    }
}

桶排序

出现频率最多的 k 个数

Leetcode : 347. Top K Frequent Elements (Medium)

Given [1,1,1,2,2,3] and k = 2, return [1,2].

设置若干个桶，每个桶存储出现频率相同的数，并且桶的下标代表桶中数出现的频率，即第 i 个桶中存储的数出现的频率为 i。把数都放到桶之后，从后向前遍历桶，最先得到的 k 个数就是出现频率最多的的 k 个数。

public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> ret = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    for(int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    List<Integer>[] 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() < k; i--) {
        if(bucket[i] != null) {
            ret.addAll(bucket[i]);
        }
    }
    return ret;
}

搜索

深度优先搜索和广度优先搜索广泛运用于树和图中，但是它们的应用远远不止如此。

BFS

广度优先搜索的搜索过程有点像一层一层地进行遍历，每层遍历都以上一层遍历的结果作为起点，遍历一个长度。需要注意的是，遍历过的节点不能再次被遍历。

第一层：

• 0 -> {6,2,1,5};

第二层：

• 6 -> {4}
• 2 -> {}
• 1 -> {}
• 5 -> {4,3}

第三层：

• 4 -> {}
• 3 -> {}

可以看到，每一轮遍历的节点都与根节点路径长度相同。设 d_i 表示第 i 个节点与根节点的路径长度，推导出一个结论：对于先遍历的节点 i 与后遍历的节点 j，有 d_i<=d_j。利用这个结论，可以求解最短路径等 最优解 问题：第一次遍历到目的节点，其所经过的路径为最短路径，如果继续遍历，之后再遍历到目的节点，所经过的路径就不是最短路径。

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

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

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

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

1 表示可以经过某个位置。

public int minPathLength(int[][] grids, int tr, int tc) {
    int[][] next = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int m = grids.length, n = grids[0].length;
    Queue<Position> queue = new LinkedList<>();
    queue.add(new Position(0, 0, 1));
    while (!queue.isEmpty()) {
        Position pos = queue.poll();
        for (int i = 0; i < 4; i++) {
            Position nextPos = new Position(pos.r + next[i][0], pos.c + next[i][1], pos.length + 1);
            if (nextPos.r < 0 || nextPos.r >= m || nextPos.c < 0 || nextPos.c >= n) continue;
            if (grids[nextPos.r][nextPos.c] != 1) continue;
            grids[nextPos.r][nextPos.c] = 0;
            if (nextPos.r == tr && nextPos.c == tc) return nextPos.length;
            queue.add(nextPos);
        }
    }
    return -1;
}
private class Position {
    int r, c, length;
    public Position(int r, int c, int length) {
        this.r = r;
        this.c = c;
        this.length = length;
    }
}

DFS

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

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

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

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

查找最大的连通面积

Leetcode : 695. Max Area of Island (Easy)

[[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]]

public int maxAreaOfIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int max = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 1) max = Math.max(max, dfs(grid, i, j));
        }
    }
    return max;
}
private int dfs(int[][] grid, int i, int j){
    int m = grid.length, n = grid[0].length;
    if(i < 0 || i >= m || j < 0 || 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)

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.

public int findCircleNum(int[][] M) {
    int n = M.length;
    int ret = 0;
    boolean[] hasFind = new boolean[n];
    for(int i = 0; i < n; i++) {
        if(!hasFind[i]) {
            dfs(M, i, hasFind);
            ret++;
        }
    }
    return ret;
}
private void dfs(int[][] M, int i, boolean[] hasFind) {
    hasFind[i] = true;
    int n = M.length;
    for(int k = 0; k < n; k++) {
        if(M[i][k] == 1 && !hasFind[k]) {
            dfs(M, k, hasFind);
        }
    }
}

矩阵中的连通区域数量

Leetcode : 200. Number of Islands (Medium)

11110
11010
11000
00000
Answer: 1

private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    m = grid.length;
    n = grid[0].length;
    int ret = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                ret++;
            }
        }
    }
    return ret;
}
private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
    grid[i][j] = '0';
    for (int k = 0; k < direction.length; k++) {
        dfs(grid, i + direction[k][0], j + direction[k][1]);
    }
}

输出二叉树中所有从根到叶子的路径

Leetcode : 257. Binary Tree Paths (Easy)

  1
/  \
2    3
\
  5

["1->2->5", "1->3"]

public List<String> binaryTreePaths(TreeNode root) {
    List<String> ret = new ArrayList();
    if(root == null) return ret;
    dfs(root, "", ret);
    return ret;
}
private void dfs(TreeNode root, String prefix, List<String> 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)

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’。

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

private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int m, n;
public void solve(char[][] board) {
    if (board == null || board.length == 0) return;
    m = board.length;
    n = board[0].length;
    for (int i = 0; i < m; i++) {
        dfs(board, i, 0);
        dfs(board, i, n - 1);
    }
    for (int i = 0; i < n; i++) {
        dfs(board, 0, i);
        dfs(board, m - 1, i);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'T') board[i][j] = 'O';
            else if (board[i][j] == 'O') board[i][j] = 'X';
        }
    }
}
private void dfs(char[][] board, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') return;
    board[r][c] = 'T';
    for (int i = 0; i < direction.length; i++) {
        dfs(board, r + direction[i][0], c + direction[i][1]);
    }
}

从两个方向都能到达的区域

Leetcode : 417. Pacific Atlantic Water Flow (Medium)

Given the following 5x5 matrix:
  Pacific ~   ~   ~   ~   ~
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

题目描述：左边和上边是太平洋，右边和下边是大西洋，内部的数字代表海拔，海拔高的地方的水能够流到低的地方，求解水能够流到太平洋和大西洋的所有位置。

private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public List<int[]> pacificAtlantic(int[][] matrix) {
    List<int[]> ret = new ArrayList<>();
    if (matrix == null || matrix.length == 0) return ret;
    this.m = matrix.length;
    this.n = matrix[0].length;
    this.matrix = matrix;
    boolean[][] canReachP = new boolean[m][n];
    boolean[][] canReachA = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        dfs(i, 0, canReachP);
        dfs(i, n - 1, canReachA);
    }
    for (int i = 0; i < n; i++) {
        dfs(0, i, canReachP);
        dfs(m - 1, i, canReachA);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (canReachP[i][j] && canReachA[i][j]) {
                ret.add(new int[]{i, j});
            }
        }
    }
    return ret;
}
private void dfs(int r, int c, boolean[][] canReach) {
    if(canReach[r][c]) return;
    canReach[r][c] = true;
    for (int i = 0; i < direction.length; i++) {
        int nextR = direction[i][0] + r;
        int nextC = direction[i][1] + c;
        if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
                || matrix[r][c] > matrix[nextR][nextC]) continue;
        dfs(nextR, nextC, canReach);
    }
}

Backtracking

回溯是 DFS 的一种，它不是用在遍历图的节点上，而是用于求解 排列组合 问题，例如有 { ‘a’,’b’,’c’ } 三个字符，求解所有由这三个字符排列得到的字符串。

在程序实现时，回溯需要注意对元素进行标记的问题。使用递归实现的回溯，在访问一个新元素进入新的递归调用时，需要将新元素标记为已经访问，这样才能在继续递归调用时不用重复访问该元素；但是在递归返回时，需要将该元素标记为未访问，因为只需要保证在一个递归链中不同时访问一个元素，可以访问已经访问过但是不在当前递归链中的元素。

数字键盘组合

Leetcode : 17. Letter Combinations of a Phone Number (Medium)

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
    List<String> ret = new ArrayList<>();
    if (digits != null && digits.length() != 0) {
        combination("", digits, 0, ret);
    }
    return ret;
}
private void combination(String prefix, String digits, int offset, List<String> ret) {
    if (offset == digits.length()) {
        ret.add(prefix);
        return;
    }
    String letters = KEYS[digits.charAt(offset) - '0'];
    for (char c : letters.toCharArray()) {
        combination(prefix + c, digits, offset + 1, ret);
    }
}

在矩阵中寻找字符串

Leetcode : 79. Word Search (Medium)

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.

private static int[][] shift = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static boolean[][] visited;
private int m;
private int n;
public boolean exist(char[][] board, String word) {
    if (word == null || word.length() == 0) return true;
    if (board == null || board.length == 0 || board[0].length == 0) return false;
    m = board.length;
    n = board[0].length;
    visited = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, 0, i, j)) return true;
        }
    }
    return false;
}
private boolean dfs(char[][] board, String word, int start, int r, int c) {
    if (start == word.length()) {
        return true;
    }
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(start) ||  visited[r][c] ) {
        return false;
    }
    visited[r][c] = true;
    for (int i = 0; i < shift.length; i++) {
        int nextR = r + shift[i][0];
        int nextC = c + shift[i][1];
        if (dfs(board, word, start + 1, nextR, nextC)) return true;
    }
    visited[r][c] = false;
    return false;
}

IP 地址划分

Leetcode : 93. Restore IP Addresses(Medium)

Given "25525511135",
return ["255.255.11.135", "255.255.111.35"].

private List<String> ret;
public List<String> restoreIpAddresses(String s) {
    ret = new ArrayList<>();
    doRestore(0, "", s);
    return ret;
}
private void doRestore(int k, String path, String s) {
    if (k == 4 || s.length() == 0) {
        if (k == 4 && s.length() == 0) {
            ret.add(path);
        }
        return;
    }
    for (int i = 0; i < s.length() && i <= 2; i++) {
        if (i != 0 && s.charAt(0) == '0') break;
        String part = s.substring(0, i + 1);
        if (Integer.valueOf(part) <= 255) {
            doRestore(k + 1, path.length() != 0 ? path + "." + part : part, s.substring(i + 1));
        }
    }
}