发表于 | 分类于

Design a data structure that supports all following operations in average O(1) time.
Note: Duplicate elements are allowed.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

解法1：

自己写的怎么都没过OA,这个AC的答案是网上抄的[捂脸]。主要的思想和没有duplicates的版本很相似。区别就是这里对于每一个数字，要存储的是出现的index的list。删除操作的时候，把末尾的元素直接写到被删除的元素的位置。同时维护一下两个index的list.
对于需要删除的数字，去掉list中相应的位置
对于末尾的数字，在list中加入要删除的数字的位置
在队列中把要删除的元素的位置置换为末尾的元素
删除队列末尾的元素（因为已经放到了队列中间去了)
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class RandomizedCollection {
    ArrayList<Integer> result;
    HashMap<Integer, LinkedHashSet<Integer>> map;
    public RandomizedCollection() {
        result = new ArrayList<Integer>();
        map = new HashMap<Integer, LinkedHashSet<Integer>>();
    }
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        // Add item to map if it doesn't already exist.
        boolean alreadyExists = map.containsKey(val);
        if(!alreadyExists) {
            map.put(val, new LinkedHashSet<Integer>());
        }
        map.get(val).add(result.size());
        result.add(val);
        return !alreadyExists;
    }
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if(!map.containsKey(val)) {
            return false;
        }
        // Get arbitary index of the ArrayList that contains val
        LinkedHashSet<Integer> valSet = map.get(val);
        int indexToReplace = valSet.iterator().next();
        // Obtain the set of the number in the last place of the ArrayList
        int numAtLastPlace = result.get(result.size() - 1);
        LinkedHashSet<Integer> replaceWith = map.get(numAtLastPlace);
        // Replace val at arbitary index with very last number
        result.set(indexToReplace, numAtLastPlace);
        // Remove appropriate index
        valSet.remove(indexToReplace);
        // Don't change set if we were replacing the removed item with the same number
        if(indexToReplace != result.size() - 1) {
            replaceWith.remove(result.size() - 1);
            replaceWith.add(indexToReplace);
        }
        result.remove(result.size() - 1);
        // Remove map entry if set is now empty, then return
        if(valSet.isEmpty()) {
            map.remove(val);
        }
        return true;
    }
    /** Get a random element from the collection. */
    public int getRandom() {
        // Get linearly random item
        Random random = new Random();
        return result.get(random.nextInt(result.size()));
        // return result.get((int)(Math.random() * result.size()));
    }
}
/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

发表于 | 分类于

Given two words (beginWord and endWord), and a dictionary’s word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Return

1
2
3
4
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

Note:

Return an empty list if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

解法1：

这题挺繁琐的。思想不难，难的是优化。用到的几个知识点总结一下：
一个是建立邻接链表来给DFS使用，也就是说，先用一次bfs来遍历出字典中所有word的前驱word.　从start开始，第一步就找出所有能转换为start的word。以此类推。
同时，为了dfs中的优化，每一步时同时记录当前word能到达下一个word的最小步数。
这里用一个distance来记录。当开始跑dfs的时候，distance就可以用来判断下一个变化的word是不是最短路上的。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        Map<String, Integer> distance = new HashMap<String, Integer>();
        Set<String> dict = new HashSet<String>();
        for (String ss : wordList) {
            dict.add(ss);
        }
        if (!dict.contains(endWord)) {
            return res;
        }
        dict.add(beginWord);
        dict.add(endWord);
        List<String> ladder = new ArrayList<String>();
        bfs(map, distance, beginWord, endWord, dict);
        dfs(res, ladder, endWord, beginWord, map, distance);
        return res;
    }
    private void bfs(Map<String, List<String>> map, Map<String, Integer> distance, String start, String end, Set<String> dict) {
        Queue<String> q = new LinkedList<String>();
        q.offer(start);
        distance.put(start, 0);
        // Create an adjacent list
        for (String s : dict) {
            map.put(s, new ArrayList<String>());
        }
        while (!q.isEmpty()) {
            String current = q.poll();
            List<String> candidates = getCandidates(current, dict);
            for (String candidate : candidates) {
                map.get(candidate).add(current);    // reverse put
                // record the minimum length to the start point
                if (!distance.containsKey(candidate)) {
                    distance.put(candidate, distance.get(current) + 1);
                    q.offer(candidate);
                }
            }
        }
    }
    private void dfs(List<List<String>> res, List<String> ladder, String current, String start, Map<String, List<String>> map,
                    Map<String, Integer> distance) {
        ladder.add(current);
        if (current.equals(start)) {
            Collections.reverse(ladder);
            res.add(new ArrayList<String>(ladder));
            Collections.reverse(ladder);
        } else {
            for (String next : map.get(current)) {
                if (distance.containsKey(next) && distance.get(next) == distance.get(current) - 1) {
                    dfs(res, ladder, next, start, map, distance);
                }
            }
        }
        ladder.remove(ladder.size() - 1);
    }
    private List<String> getCandidates(String word, Set<String> wordList) {
        List<String> candidates = new ArrayList<String>();
        for (int i = 0; i < word.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                if (c != word.charAt(i)) {
                    String modified = word.substring(0, i) + c + word.substring(i + 1);
                    if (wordList.contains(modified)) {
                        candidates.add(modified);
                        }                    
                }
            }
        }
        return candidates;
    }
}

发表于 | 分类于 
1
2
3
4
Follow up for "Find Minimum in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

解法1：

当有重复数字的时候，最差的情况会退化成O(N)的算法。在原来算法的基础上还要判断两个数字是否相等。如果相等的时候，只能排除掉一个数而不是一半的数字。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return Integer.MAX_VALUE;
        }
        int start = 0, end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[start] == nums[end]) {
                start++;
            } else if (nums[start] > nums[end]) {
                if (nums[mid] < nums[end]) {
                    end = mid;
                } else if (nums[mid] == nums[end]) {
                    end--;
                } else {
                    start = mid;
                }                
            } else {
                // nums[start] < nums[end]
                end = mid;
            }
        }
        if (nums[start] <= nums[end]) {
            return nums[start];
        }
        return nums[end];
    }
}

发表于 | 分类于

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

解法1：

归位的思想。把每一个数字放到他该在的位置上。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int firstMissingPositive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 1;
        }
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] <= n && nums[i] > 0 && nums[i] != nums[nums[i] - 1]) {
                int temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
}

发表于 | 分类于

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

解法1：

复杂度要求比较高，算来算去能用的也只有HashMap了。这个解法不太常见，用一个map存储一个range。
对于任意一个数，low和high都是数字本身。然后在map之内寻找下限和上限。寻找到之后更新res。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int res = 0;
        for (int num : nums) {
            if (map.containsKey(num)) continue;
            int low = num;
            int high = num;
            if (map.containsKey(num - 1)) low = map.get(num - 1);
            if (map.containsKey(num + 1)) high = map.get(num + 1);
            res = Math.max(res, high - low + 1);
            map.put(num, num);
            map.put(low, high);
            map.put(high, low);
        }
        return res;
    }
}

解法2：

这个解法清楚多了，首先把所有数据加入一个hashset. 之后对于每一个数，往下以及往上找到所有在set中的数据。 然后更新一下range。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int num : nums) {
            set.add(num);
        }
        int res = 0;
        for (int num : nums) {
            int down = num - 1;
            while (set.contains(down)) {
                set.remove(down);
                down--;
            }
            int upper = num + 1;
            while (set.contains(upper)) {
                set.remove(upper);
                upper++;
            }
            res = Math.max(res, upper - down - 1);
        }
        return res;
    }
}

解法3: DFS –> StackOverflow

这个解法空间浪费很严重。。不过也是一种思路。leetcode上会stack overflow

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    int count = 0;
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        for (int num : nums) {
            dfs(set, num);
        }
        return count;
    }
    private int dfs(Set<Integer> set, int current) {
        if (!set.contains(current)) return 0;
        set.remove(current);
        int smaller = dfs(set, current - 1);
        int bigger = dfs(set, current + 1);
        count = Math.max(smaller + bigger + 1, count);
        return smaller + bigger + 1;
    }
}

发表于 | 分类于

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

For example, given the following matrix:

1
2
3
4
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 6.

解法1：

这题是运用了Largest Rectangle Area那题的解法。因为这题可以看成是一行一行的数字叠加起来，组成了一个histogram，求最大的面积。
那么实际的算法就是对于每一层，计算一个当前累积的histogram，然后再求一个最大面积就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int res = 0;
        int[] heights = new int[matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                heights[j] = matrix[i][j] - '0' == 0 ? 0 : heights[j] + 1;
            }
            // calculate the maximum rectangle in histogram
            Stack<Integer> stack = new Stack<Integer>();
            for (int j = 0; j < heights.length; j++) {
                int height = heights[j];
                while (!stack.empty() && height < heights[stack.peek()]) {
                    int last = heights[stack.pop()];
                    int width = stack.empty() ? j : j - stack.peek() - 1;
                    res = Math.max(res, last * width);
                }
                stack.push(j);
            }
        }
        return res;
    }
}

发表于 | 分类于

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]
The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

解法1： Math

参考这篇解释
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length;
            int n = nums2.length;
            if (m > n) {
                return findMedianSortedArrays(nums2, nums1);
            }
            int start = 0, end = m, half = (m + n + 1) / 2;
            // Satisfy both condition, calculate the medium
            int max_of_left = 0, min_of_right = 0, i = 0, j = 0;
            while (start <= end) {
                i = (start + end) / 2;
                j = half- i;
                if (i < m && j > 0 && nums2[j - 1] > nums1[i]) {
                    start = i + 1;
                } else if (i > 0 && j < n && nums1[i - 1] > nums2[j]) {
                    end = i - 1;
                } else {
                    if (i == 0) {
                        max_of_left = nums2[j - 1];
                    }
                    else if (j == 0) {
                        max_of_left = nums1[i - 1];
                    } else {
                        max_of_left = Math.max(nums1[i - 1], nums2[j - 1]);
                    }
                    break;
                }
            }
           // Check if the total number of elements is odd or even
            if ((m + n) % 2 == 1) {
                return max_of_left;
            }
            if (i == m) {
                min_of_right = nums2[j];
            } else if (j == n) {
                min_of_right = nums1[i];
            } else {
                min_of_right = Math.min(nums1[i], nums2[j]);
            }
            return (max_of_left + min_of_right)/2.0;
        }
}

解法2： Kth Value

这个解法比较好理解一点，也不容易错，要考虑的edge case容易一些。
基本的思想就是先要写出一个find kth element in a two sorted array的function。
这个function可以用递归的方式实现，而每一次递归，两个array都需要去掉当中一个的一半。
想法就是：
如果第一个array的长度是0，那么第k个一定在第二个array的k-1位置。
如果k==1，那么第k个就是当前比较的array的第一个的最小值
如果都不是，那么可以把两个array都砍两半。假设是A和B。
比较A和B的中点，一个是pa = k/2，另一个就是k - pa， 为的是保证左右两半都是k个数。
然后比较这两个数，如果mA < mB，则说明前pa个数都不是第k个数的备选，可以抛掉。相反同理
如果ma == mB，则说明已经找到第k个数，返回即可。

等kth function写出来之后，就可以按照总长度是奇数还是偶数。
如果是奇数，就直接求total / 2的数，
如果是偶徐，需要把中间两个数的平均数返回。
总的时间复杂度是O(logM + logN) = O(logMN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int total = m + n;
        if (total % 2 == 0) {
            return (findKth(nums1, 0, nums2, 0, total / 2) + findKth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
        } else {
            return findKth(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }
    private double findKth(int[] nums1, int i, int[] nums2, int j, int k) {
        int len1 = nums1.length - i;
        int len2 = nums2.length - j;
        if (len1 > len2) {
            return findKth(nums2, j, nums1, i, k);
        }
        if (len1 == 0) return nums2[j + k - 1];
        if (k == 1) return Math.min(nums1[i], nums2[j]);
        int pa = Math.min(len1, k / 2);
        int pb = k - pa;
        if (nums1[i + pa - 1] < nums2[j + pb - 1]) {
            return findKth(nums1, i + pa, nums2, j, k - pa);
        } else if (nums1[i + pa - 1] > nums2[j + pb - 1]) {
            return findKth(nums1, i, nums2, j + pb, k - pb);
        } else {
            return nums1[i + pa - 1];
        }
    }
}

发表于 | 分类于

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

解法1：

自己写的版本比较繁琐，先用binary search来查找插入的位置，然后把interval插入，然后再merge interval。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<Interval>();
        if (intervals.size() == 0 && newInterval == null) {
            return res;
        } else if (intervals.size() == 0) {
            res.add(newInterval);
            return res;
        }
        int position = binarySearch(intervals, newInterval);
        // Insert into the intervals;
        if (position < intervals.size()) {
          intervals.add(position, newInterval);
        } else {
          intervals.add(newInterval);
        }
        // Merge Intervals using intervals
        Interval last = intervals.get(0);
        res.add(last);
        for (int i = 1; i < intervals.size(); i++) {
          Interval current = intervals.get(i);
          // check if we need to merge
          if (current.start <= last.end) {
            last.end = Math.max(last.end, current.end);
          } else {
            res.add(current);
            last = current;
          }
        }
        return res;
    }
    private int binarySearch(List<Interval> intervals, Interval newInterval) {
      // return the first interval that the start is larger than newInterval's start
      int start = 0, end = intervals.size() - 1;
      while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        Interval temp = intervals.get(mid);
        if (temp.start <= newInterval.start) {
          start = mid;
        } else {
          end = mid;
        }
      }
      if (intervals.get(start).start >= newInterval.start) {
        return start;
      }
      if (intervals.get(end).start >= newInterval.start) {
        return end;
      }
      return intervals.size();
    }
}

解法2：

不需要用binary search来查找插入位置，而是在一边遍历的情况下用另一个指针pos来维护该插入的位置。这个思想在其他的题目中也见过。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> res = new ArrayList<Interval>();
        int pos = 0;    // find an insert position for newInterval
        for (Interval it : intervals) {
            if (it.end < newInterval.start) {
                res.add(it);
                pos++;
            } else if (newInterval.end < it.start) {
                res.add(it);
            } else {
                newInterval.start = Math.min(it.start, newInterval.start);
                newInterval.end = Math.max(it.end, newInterval.end);
            }
        }
        res.add(pos, newInterval);
        return res;
    }
}

发表于 | 分类于

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

Note:
You can assume that you can always reach the last index.

解法1：Greedy O(N) Time O(1) Space

这题可以作为复习Greedy Algorithm的一个很好的范例。最核心的思想和Jump Game一样，用一个变量维护上一步可以走到的最远距离。如果当前的距离比他远，则说明需要额外的一步。同时维护一个下一步可以走到的最远距离，便是在当前的最远距离和i + nums[i]中取最大值即可。

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public int jump(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // Greedy
        int cur = 0;
        int last = 0;
        int step = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > last) {
                last = cur;
                step++;
                if (last >= nums.length) {
                    return step;
                }
            }
            cur = Math.max(cur, i + nums[i]);
        }
        return step;
    }
}

解法2：Greedy O(N) Time O(N) Space, DP thinking

用一个dp数组来存储每一个点所需要的最少步数。
然后从0开始扫描，找出当前点所能到的最远距离。然后从下一位置开始扫描，对于每一个可以到达的点都更新最少的步数，也就是dp[j] = dp[i] + 1。到此，j位置上的结果已经找出，不会再有比他步数更少的解了。
最后返回dp[n-1]即可。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int jump(int[] nums) {
        int[] dp = new int[nums.length];
        // dp pointer
        int j=1;
        for (int i=0; i<nums.length; i++) {
            int loc= nums[i] + i;
            while (j<=loc && j<nums.length) {
                dp[j] = dp[i] + 1;
                j++;
            }
        }
        return dp[dp.length-1];
    }
}

发表于 | 分类于

Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:

Row R and column C both contain exactly N black pixels.
For all rows that have a black pixel at column C, they should be exactly the same as row R

The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input:                                            
[['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'W', 'B', 'W', 'B', 'W']]
N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
        0    1    2    3    4    5         column index                                            
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
row index
Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels.
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.

Note:

The range of width and height of the input 2D array is [1,200].

解法1：

很繁琐的一道题。。。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        if (picture == null || picture.length == 0 || picture[0].length == 0) return 0;
        int m = picture.length, n = picture[0].length;
        int[] cols = new int[n];
        Map<String, Integer> map = new HashMap<>(); // Use a hashMap to store the rows string that satisfy that row pixel count is N
        for (int i = 0; i < m; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 'B') {
                    cols[j]++;
                    count++;
                }
            }
            if (count == N) {
                String curRow = new String(picture[i]);
                map.put(curRow, map.getOrDefault(curRow, 0) + 1);
            }
        }
        int res = 0;
        for (String row : map.keySet()) {
            if (map.get(row) != N) continue;
            for (int i = 0; i < n; i++) {
                if (row.charAt(i) == 'B' && cols[i] == N) {
                    res += N;
                }
            }
        }
        return res;
    }
}