286. Walls and Gates
-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room.
For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
DFS BFS都可以做，需要注意的是以门为起点去向下延伸，而不是以房间开始
public void wallsAndGates(int[][] rooms) {
for (int i = 0; i < rooms.length; i++)
for (int j = 0; j < rooms[0].length; j++)
if (rooms[i][j] == 0) dfs(rooms, i, j, 0);
}
private void dfs(int[][] rooms, int i, int j, int d) {
// 注意rooms[i][j] < d
if (i < 0 || i >= rooms.length || j < 0 || j >= rooms[0].length || rooms[i][j] < d) return;
rooms[i][j] = d;
dfs(rooms, i - 1, j, d + 1);
dfs(rooms, i + 1, j, d + 1);
dfs(rooms, i, j - 1, d + 1);
dfs(rooms, i, j + 1, d + 1);
}
class Solution {
public void wallsAndGates(int[][] rooms) {
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < rooms.length; i++) {
// find gate
for (int j = 0; j < rooms[i].length; j++) {
if (rooms[i][j] == 0) {
queue.offer(new int[]{i, j});
}
}
}
int[] dx = {0, 0, -1, 1};
int[] dy = {1, -1, 0, 0};
while (!queue.isEmpty()) {
int[] cor = queue.poll();
int i = cor[0], j = cor[1];
for (int idx = 0; idx < 4; idx++) {
if (i + dx[idx] >= 0 && i + dx[idx] <= rooms.length - 1 && j + dy[idx] >= 0 && j + dy[idx] <= rooms[0].length - 1 && rooms[i + dx[idx]][j + dy[idx]] == Integer.MAX_VALUE) {
rooms[i + dx[idx]][j + dy[idx]] = rooms[i][j] + 1;
queue.offer(new int[]{i + dx[idx], j + dy[idx]});
}
}
}
}
}
DFS & BFS
516. Longest Palindromic Subsequence
subsequence和substring不一样 比如 bbbab 最长的sub sequency是bbbb，所以返回4
memo search比较好理解，helper函数传入头尾指针，如果头尾的字符相同，那么该字符串的最长回文长度就是2+中间部分的最长回文长度，进行递归。如果头尾的字符不同，那么头指针+1尾指针不动，或尾-1头不动。查过的substring用memo记录。helper函数传入头尾指针和memo二维数组。memo[i][j]表示以i, j分割出的substring的最长回文长度
Palindromic常用套路dp[i][j]
Palindromic还有一种方法叫做extend，定义中心pivot然后向两边扩展，pivot可以是a，也可以是aa这种
class Solution {
public int longestPalindromeSubseq(String s) {
if (s == null || s.length() == 0) {
return 0;
}
return helper(s, 0, s.length() - 1, new Integer[s.length()][s.length()]);
}
public int helper(String s, int start, int end, Integer[][] memo) {
if (memo[start][end] != null) {
return memo[start][end];
}
if (start > end) {
return 0;
}
if (start == end) {
return 1;
}
if (s.charAt(start) == s.charAt(end)) {
memo[start][end] = 2 + helper(s, start + 1, end - 1, memo);
} else {
memo[start][end] = Math.max(helper(s, start + 1, end, memo), helper(s, start, end - 1, memo));
}
return memo[start][end];
}
}
DFS + Memo Search
380. Insert Delete GetRandom O(1)
设计一个数据结构支持O(1)的插入删除返回随机数
hash支持O1的insert和delete但无法返回随机数，list可以通过index支持O1的删除和插入
所以用hashmap保存value-index信息，同时也维护一个arraylist
答案只删除array list的最后位置，如果不是要swap
Random rand = new Random();
rand.nextInt(n) //不包括n
DATA STRUCTURE
673. Number of Longest Increasing Subsequence
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
找到最长递增子序列的个数
思路来自于找最长连续递增子序列的长度，一个DP数组记录截止到当前位置最长的递增子序列长度，另一个DP数组记录到当前位置的子序列，有几种可能构造出最长长度。何时更新第二个DP数组是复杂的地方。
DP写法需要学习
- DP数组在哪初始化
- 全局变量在何处更新
class Solution {
public int findNumberOfLIS(int[] nums) {
int N = nums.length;
if (N <= 1) return N;
int[] lengths = new int[N]; //lengths[i] = length of longest ending in nums[i]
int[] counts = new int[N]; //count[i] = number of longest ending in nums[i]
Arrays.fill(counts, 1);
for (int j = 0; j < N; ++j) {
for (int i = 0; i < j; ++i) if (nums[i] < nums[j]) {
if (lengths[i] >= lengths[j]) {
lengths[j] = lengths[i] + 1;
counts[j] = counts[i];
} else if (lengths[i] + 1 == lengths[j]) {
counts[j] += counts[i];
}
}
}
int longest = 0, ans = 0;
for (int length: lengths) {
longest = Math.max(longest, length);
}
for (int i = 0; i < N; ++i) {
if (lengths[i] == longest) {
ans += counts[i];
}
}
return ans;
}
}
DP
208. Implement Trie (Prefix Tree)
class TrieNode {
public boolean isWord;
public TrieNode[] children;
public TrieNode() {
children = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
// start search from root
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.children[c - 'a'] == null) {
cur.children[c - 'a'] = new TrieNode();
}
cur = cur.children[c - 'a'];
}
cur.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
// start search from root
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
return cur.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
// start search from root
TrieNode cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.children[c - 'a'] == null) {
return false;
}
cur = cur.children[c - 'a'];
}
return true;
}
}
212. Word Search II
给一个char的矩阵和单词list，找出list中在矩阵中的单词
Trie + backtracking (典型题）
20. Valid Parentheses
22. Generate Parentheses
给一个n是左右括号有几对，返回所有的左右括号组合
dfs做，找出所有可能性，搞清什么时候可以加左括号，什么时候可以加右括号
helper(int left, int right, int n, String temp, List<String> res)
// base case
temp.legnth() == n * 2
241. Different Ways to Add Parentheses
2 * 3 - 4 * 5 可以在各处加括号，返回所有可能的结果
每个运算符分成左右两个部分，两部分再递归调用自己，分治！
如何判断进来的是只有数字的字符串比较重要：res的size是0
23.Merge K sorted array
Merge K个排好序的链表
Divide&Conquer
57. Insert Interval
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]
分析出三种情况很重要，
1 有交集（交集的子情况也比较多，但两种不相交比较好找），就把待merge数组的start end，再继续去merge
2 interval在待merge数组的前面，把interval加进result
3 interval在待merge数组的后面，把两个数组都加进result，并把merge数组改成null，之后都不管了
最后别忘了如果merge数组不是null的话 将其加入result
// 如果没有排过序
Collections.sort(list, new Comparator<Interval> {
@override
public int compare(Interval i1, Intervali2) {
return i1.start -i2.start;
}
});
253. Meeting Rooms II
同类型题
283. Move Zeroes
Given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].
两个指针做，用for循环比用while更好理清思路，不是说非得上来就声明两根指针，一根指针声明，另一根在for循环里
Two pointer
621. Task Scheduler
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
算个数和给出真正的顺序是有差别的，不必纠结于先A还是先B，开始想复杂了。实际上n+1个坑，从频率高到低从pq里poll出来填进坑里，再放进tempList，所以在这个size是n+1的slot里，每个任务出现一次，如果pq里没任务了但计数器还没到n+1，就说明需要加idle，统计个数即可。把tempList的task如果freq大于1，再丢回pq
Comparator<Task> comp = (t1, t2) -> t2.count - t1.count
PriorityQueue
325. Maximum Size Subarray Sum Equals k
Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)
Subarray类题目需要想到前缀和数组，优化➕Hashmap
sum(i~j) = PrefixSum(j+1) - PrefixSum(i) PrefixSum[0] = 0
** Subarray + Hashmap**
class Solution {
public int maxSubArrayLen(int[] nums, int k) {
if(nums == null || nums.length == 0) return 0;
int length = nums.length, sum = 0, maxSubLen = 0;
//Using a hash map to store the sum of all the values before and include nums[i]
Map<Integer, Integer> map = new HashMap();
for(int i = 0; i < length; i++) {
sum += nums[i];
if(sum == k) {
maxSubLen = Math.max(maxSubLen, i + 1);
} else if(map.containsKey(sum - k)) {
maxSubLen = Math.max(maxSubLen, i - map.get(sum - k));
}
if(!map.containsKey(sum)) {
map.put(sum, i);
}
}
return maxSubLen;
}
}
523. Continuous Subarray Sum
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
思路好想，但是乘除法有点绕， 把余树放进map里
public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return false;
}
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
// hold the position
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (k != 0) {
sum = sum % k;
}
if (map.containsKey(sum)) {
// make sure at least subarray has more than 2 elements
if (i - map.get(sum) > 1) {
return true;
}
} else {
map.put(sum, i);
}
}
return false;
}
238. Product of Array Except Self
For example, given [1,2,3,4], return [24,12,8,6]. 要求O(n)
Two passes，第一趟用一个变量记录index左边的乘积，第二趟记录右边的成积，再乘起来
554. Brick Wall
Input:
[[1,2,2,1],
[3,1,2],
[1,3,2],
[2,4],
[3,1,2],
[1,3,1,1]]
Output: 2
用hashmap存每个边出现的频率不难想，在于一遍就能得出结论，而不是再遍历map一遍去找最大值，每次往map里放完东西，都更新一遍最大值
class Solution {
public int leastBricks(List<List<Integer>> wall) {
Map<Integer, Integer> map = new HashMap<>();
// 主要是这个count
int count = 0;
for(int i = 0; i < wall.size(); i++) {
int sum = 0;
for(int j = 0; j < wall.get(i).size() - 1; j++) {
sum = sum + wall.get(i).get(j);
map.put(sum, map.getOrDefault(sum, 0) + 1);
count = Math.max(count, map.get(sum));
}
}
return wall.size() - count;
}
}
*Hashmap
209. Minimum Size Subarray Sum
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
解法比较高级，1+3+1+3=8>7，所以让8减第一个元素尝试去缩小window，更新最小值，然后减第二个直到不能缩小，指针停下。
while循环三步走，先update最值，删开头尝试新可能性，最后挪start
public int minSubArrayLen(int s, int[] nums) {
int sum = 0, start = 0, res = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
while (sum >= s) {
res = Math.min(res, (i - start + 1));
sum -= nums[start];
start++;
}
}
return (res == Integer.MAX_VALUE) ? 0 : res;
}
Sliding Window
- Minimum Window Substring
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
思路和上题一样，找最小的窗口
Sliding Window
class Solution {
public String minWindow(String s, String t) {
Map<Character, Integer> map = new HashMap<>();
for (char c : t.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
int start = 0, minSize = Integer.MAX_VALUE, minStart = 0, count = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
map.put(c, map.get(c) - 1);
if (map.get(c) >= 0) {
count++;
}
}
// A -1, B 0， 存在负数的可能
while (count == t.length()) {
// update
if (i - start + 1 < minSize) {
minSize = i - start + 1;
minStart = start;
}
// delete first
char r = s.charAt(start);
if (map.containsKey(r)) {
map.put(r, map.get(r) + 1);
// 注意是 > 0, 过剩了再减 AAB
if (map.get(r) > 0) {
count--;
}
}
start++;
}
}
return (minSize == Integer.MAX_VALUE) ? "" : s.substring(minStart, minStart + minSize);
}
}
239. Sliding Window Maximum
** Deque **
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
Therefore, return the max sliding window as [3,3,5,5,6,7].
Find max value of each sliding window
用双端队列，LinkedList实现
队列里存index，不存值，
每进来一个新值，1）看是不是要poll出最老的元素 2）进来的新值如果比之前的值大，pollLast，因为用不到他们
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0) {
return nums;
}
int[] result = new int[n - k + 1];
LinkedList<Integer> dq = new LinkedList<>();
for (int i = 0; i < n; i++) {
// peek, poll针对队头（最早进入的元素）
if (!dq.isEmpty() && dq.peek() < i - k + 1) {
dq.poll();
}
while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offer(i);
if (i - k + 1 >= 0) {
result[i - k + 1] = nums[dq.peek()];
}
}
return result;
}
}
网友评论