12/26/2018
LeetCode 84 Largest Rectangle in Histogram

Problem

Largest Rectangle in Histogram

Read More

12/26/2018
LeetCode 85 Maximal Rectangle

Problem

Maximal Rectangle

Read More

12/26/2018
LeetCode 948 Bag of Tokens

Problem

⭐️⭐️⭐️⭐️

估计是从某个桌游得到的启发, 说给一个数组表示coins with power和一个initial powere P. 现在规则是:

  1. 可以用手里现存的power去买数组中的一个coin.
  2. 也可以用手里的coin去跟数组中的任意一个coin作交换.

现在问玩家最多能得到几个coin.

Read More

12/26/2018
LeetCode 127 Word Ladder

Problem

⭐️⭐️⭐️⭐️⭐️

Word Ladder

Read More

12/26/2018
LeetCode 126 Word Ladder II

#Problem

Word Ladder II

#Solution

#Solution #1 BFS + backtracking without optimization

简单粗暴的方法还是比较容易想, 分两步:

  1. 先利用BFS做Word Ladder I 的事情, 计算出最短的距离. 一边计算一边构建一个undirected graph, 包含start to end的所有可能路径.
  2. 然后利用DFS做搜索, 并且维护一个depth, 没往下走一步depth加一, 如果depth已经到达了最短的距离, 但所在节点并不是endWord的话, 就回溯找其他路. 总有一条path, 从start to end的长度为第一步所求到的最短距离.

很遗憾. 这个方法超时了.

#Solution #2 BFS + DFS with Optimization

优化的方法是在第一步BFS的过程中, 利用一个hash map记录start到每一个结点的最短距离.

那么在第二步DFS的过程中, 我们就不需要一个一个的尝试, 不行了还得回溯. 我们可以利用那个distance的hash map, 在继续往下之前, check下一个结点的最短距离是否是当前结点最短距离加一. 是的话就继续, 不是的话就根本不需要visit那个结点了.

#Code

#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
// https://leetcode.com/problems/word-ladder-ii/discuss/40475/My-concise-JAVA-solution-based-on-BFS-and-DFS
class Solution {
public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
final List<List<String>> res = new ArrayList<>();
final Set<String> dict = new HashSet<>(wordList);
if (!dict.contains(endWord)) return res;
final Map<String, Set<String>> graph = new HashMap<>();
final Map<String, Integer> dist = new HashMap<>();
bfs(beginWord, endWord, dict, graph, dist);
if (!dist.containsKey(endWord) || dist.get(endWord) == 0) return res;
final List<String> list = new ArrayList<>(Arrays.asList(beginWord));
dfs(beginWord, endWord, graph, dist, res, list);
return res;
}
private void bfs(final String beginWord, final String endWord, final Set<String> dict,
final Map<String, Set<String>> graph, final Map<String, Integer> dist) {
final Queue<String> queue = new LinkedList<>();
queue.add(beginWord);
dist.put(beginWord, 1);
int depth = 0;
while (!queue.isEmpty()) {
final int size = queue.size();
depth++;
for (int i = 0; i < size; i++) {
final String curr = queue.poll();
graph.put(curr, new HashSet<>());
if (curr.equals(endWord)) return;
final char[] chs = curr.toCharArray();
for (int k = 0; k < chs.length; k++) {
final char save = chs[k];
for (char c = 'a'; c <= 'z'; c++) {
if (c != save) {
chs[k] = c;
final String nextWord = new String(chs);
if (dict.contains(nextWord)) {
graph.putIfAbsent(nextWord, new HashSet<>());
graph.get(curr).add(nextWord);
if (!dist.containsKey(nextWord)) {
dist.put(nextWord, depth + 1);
queue.add(nextWord);
}
}
chs[k] = save;
}
}
}
}
}
}
private void dfs(final String beginWord, final String endWord, final Map<String, Set<String>> graph, final Map<String, Integer> dist,
final List<List<String>> res, final List<String> list) {
if (beginWord.equals(endWord)) {
res.add(new ArrayList<>(list));
return;
}
final int len = dist.get(beginWord);
for (final String adj : graph.get(beginWord)) {
if (dist.get(adj) == len + 1) {
list.add(adj);
dfs(adj, endWord, graph, dist, res, list);
list.remove(list.size() - 1);
}
}
}
}

12/26/2018
LeetCode 671 Second Minimum Node In a Binary Tree

Problem

Second Minimum Node In a Binary Tree

Read More

12/26/2018
LeetCode 849 Maximize Distance to Closest Person

Problem

给一个数组表示座位. 1表示有人, 0表示没人. 现在要找出一个空位置使得离最近的人的距离最远.

Read More

12/26/2018
LeetCode 377 Combination Sum IV

Problem

⭐️⭐️⭐️⭐️⭐️
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
Read More

12/26/2018
LeetCode 92 Reverse Linked List II

Problem

Reverse Linked List from m to n

Read More

12/26/2018
LeetCode 830 Positions of Large Groups

Problem

⭐️

Positions of Large Groups

Read More

12/23/2018
LeetCode 167 Two Sum II

Problem

⭐️

Two sum of sorted array

Read More

12/23/2018
LeetCode 873 Length of Longest Fibonacci Subsequence

Problem

⭐️⭐️⭐️⭐️⭐️

给一个数组, 找出Longest fibonacci subsequences.

Read More

12/23/2018
LeetCode 829 Consecutive Numbers Sum

Problem

⭐️⭐️⭐️⭐️

给一个数字, 问有多少个解法使得consecutive numbers的和能等于这个数.

比如:

1
2
3
4
5
6
7
8
9
10
11
Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3
Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Read More

12/23/2018
LeetCode 191 Number of 1 Bits

Problem

⭐️⭐️

Number of 1 Bits

Read More

12/23/2018
LeetCode 155 Min Stack

Problem

⭐️⭐️

Min Stack

Read More

12/23/2018
LeetCode 856 Score of Parentheses

Problem

⭐️⭐️⭐️⭐️

说给一个balanced的parentheses string. 算score的rule如下:

() = 1
AB = A + B, 意思是()() = 1 + 1
(A) = 2 A, 意思是(()) = 2 1

Read More

12/23/2018
LeetCode 730 Count Different Palindromic Sequences

Problem

⭐️⭐️⭐️⭐️⭐️

给一个字符串, 找出有多少个 palindromic subsequences

Read More

12/23/2018
LeetCode 877 Stone Game

Problem

⭐️⭐️⭐️⭐️⭐️

说给一个数组表示石头数量. 两个人开始比赛, 每次只能从两端拿石头, 拿到最后谁拿得多就赢. 问第一个PLAYER是否有办法能guarantee win.

Read More

12/09/2018
LeetCode 442 Find All Duplicates in an Array

Problem

⭐️⭐️

Find All Duplicates in an Array

Read More

12/09/2018
LeetCode 536 Construct Binary Tree from String

Problem

⭐️⭐️⭐️
1
2
3
4
5
6
7
8
Input: "4(2(3)(1))(6(5))"
Output: return the tree root node representing the following tree:
4
/ \
2 6
/ \ /
3 1 5
Read More

© 2019 ReeeStart with help from Hexo and Twitter Bootstrap. Theme by Freemind.