【98】Validate Binary Search Tree
【99】Recover Binary Search Tree
【100】Same Tree
【101】Symmetric Tree
【104】Maximum Depth of Binary Tree
【105】Construct Binary Tree from Preorder and Inorder Traversal
【106】Construct Binary Tree from Inorder and Postorder Traversal
【108】Convert Sorted Array to Binary Search Tree
【109】Convert Sorted List to Binary Search Tree
【110】Balanced Binary Tree
【111】Minimum Depth of Binary Tree
【112】Path Sum
【113】Path Sum II
【114】Flatten Binary Tree to Linked List
【116】Populating Next Right Pointers in Each Node
【117】Populating Next Right Pointers in Each Node II
【124】Binary Tree Maximum Path Sum
【129】Sum Root to Leaf Numbers
【130】Surrounded Regions
【133】Clone Graph
【199】Binary Tree Right Side View
【200】Number of Islands
【207】Course Schedule
【210】Course Schedule II
【257】Binary Tree Paths
【261】Graph Valid Tree
【301】Remove Invalid Parentheses
【323】Number of Connected Components in an Undirected Graph
【329】Longest Increasing Path in a Matrix
【332】Reconstruct Itinerary
【337】House Robber III
【339】Nested List Weight Sum （2019年2月12日）
给了一个嵌套的list，每个元素当前的权重 = 当前的深度* 数字的大小。最外面一层深度为1，然后逐层递增。返回整个列表的权重。
1 /**
2 * // This is the interface that allows for creating nested lists.
3 * // You should not implement it, or speculate about its implementation
4 * class NestedInteger {
5 * public:
6 * // Constructor initializes an empty nested list.
7 * NestedInteger();
8 *
9 * // Constructor initializes a single integer.
10 * NestedInteger(int value);
11 *
12 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
13 * bool isInteger() const;
14 *
15 * // Return the single integer that this NestedInteger holds, if it holds a single integer
16 * // The result is undefined if this NestedInteger holds a nested list
17 * int getInteger() const;
18 *
19 * // Set this NestedInteger to hold a single integer.
20 * void setInteger(int value);
21 *
22 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
23 * void add(const NestedInteger &ni);
24 *
25 * // Return the nested list that this NestedInteger holds, if it holds a nested list
26 * // The result is undefined if this NestedInteger holds a single integer
27 * const vector<NestedInteger> &getList() const;
28 * };
29 */
30 class Solution {
31 public:
32 int depthSum(vector<NestedInteger>& nestedList) {
33 return depthSum(nestedList, 1);
34 }
35 int depthSum(vector<NestedInteger>& nestedList, int level) {
36 int ans = 0;
37 for (int idx = 0; idx < nestedList.size(); ++ idx) {
38 if (nestedList[idx].isInteger()) {
39 ans += nestedList[idx].getInteger() * level;
40 } else {
41 ans += depthSum(nestedList[idx].getList(), level + 1);
42 }
43 }
44 return ans;
45 }
46 };
View Code
【364】Nested List Weight Sum II （2019年2月12日）
给了一个嵌套的list，每个元素当前的权重 = 当前的深度* 数字的大小。深度最里面一层为1，然后逐层递增。返回整个列表的权重。
题解：先计算下深度最深有多少，然后在逐层遍历。
1 /**
2 * // This is the interface that allows for creating nested lists.
3 * // You should not implement it, or speculate about its implementation
4 * class NestedInteger {
5 * public:
6 * // Constructor initializes an empty nested list.
7 * NestedInteger();
8 *
9 * // Constructor initializes a single integer.
10 * NestedInteger(int value);
11 *
12 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
13 * bool isInteger() const;
14 *
15 * // Return the single integer that this NestedInteger holds, if it holds a single integer
16 * // The result is undefined if this NestedInteger holds a nested list
17 * int getInteger() const;
18 *
19 * // Set this NestedInteger to hold a single integer.
20 * void setInteger(int value);
21 *
22 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
23 * void add(const NestedInteger &ni);
24 *
25 * // Return the nested list that this NestedInteger holds, if it holds a nested list
26 * // The result is undefined if this NestedInteger holds a single integer
27 * const vector<NestedInteger> &getList() const;
28 * };
29 */
30 class Solution {
31 public:
32 int maxDepth = 0;
33 int depthSumInverse(vector<NestedInteger>& nestedList) {
34 getMaxDepth(nestedList, 1);
35 int curDepth = maxDepth;
36 return calRes(nestedList, curDepth);
37 }
38 void getMaxDepth(const vector<NestedInteger>& nestedList, int curDepth) {
39 maxDepth = max(maxDepth, curDepth);
40 for (auto& element : nestedList) {
41 if(!element.isInteger()) {
42 getMaxDepth(element.getList(), curDepth + 1);
43 }
44 }
45 return;
46 }
47 int calRes(const vector<NestedInteger>& nestedList, int curDepth) {
48 int res = 0;
49 for (auto& ele : nestedList) {
50 if (ele.isInteger()) {
51 res += ele.getInteger() * curDepth;
52 } else {
53 res += calRes(ele.getList(), curDepth - 1);
54 }
55 }
56 return res;
57 }
58 };
View Code
【366】Find Leaves of Binary Tree
【394】Decode String
【417】Pacific Atlantic Water Flow
【430】Flatten a Multilevel Doubly Linked List
【439】Ternary Expression Parser
【472】Concatenated Words （2018年12月18日，算法群，类似题目 140）
【473】Matchsticks to Square
【488】Zuma Game
【489】Robot Room Cleaner
【490】The Maze
【491】Increasing Subsequences
【494】Target Sum
【499】The Maze III
【505】The Maze II
【513】Find Bottom Left Tree Value
【514】Freedom Trail
【515】Find Largest Value in Each Tree Row
【529】Minesweeper
【531】Lonely Pixel I
【533】Lonely Pixel II
【542】01 Matrix
【546】Remove Boxes
【547】Friend Circles
【559】Maximum Depth of N-ary Tree
【576】Out of Boundary Paths
【638】Shopping Offers (2018年12月24日，算法群)
有几种商品，每种商品有特定的单价，也有几种商品组合的special offer，给了一个购买清单，（每种商品买几个）。问最小花费。组合价格可以随便用很多次都可以。
Input: [2,5], [[3,0,5],[1,2,10]], [3,2] Output: 14 Explanation: There are two kinds of items, A and B. Their prices are $2 and $5 respectively. In special offer 1, you can pay $5 for 3A and 0B In special offer 2, you can pay $10 for 1A and 2B. You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
题解：dfs，商品最差是个数*单价的累加和。我们在每一层dfs中尝试用一个组合价去递归，遍历所有解集找出答案。
1 class Solution {
2 public:
3 int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
4 n = price.size();
5 m = special.size();
6 vector<int> allZero(n, 0);
7 string str = vec2str(allZero);
8 memo[str] = 0;
9 int ret = dfs(price, special, needs);
10 return ret;
11 }
12 int n, m;
13 unordered_map<string, int> memo;
14 inline string vec2str(const vector<int>& needs) {
15 string ret = to_string(needs[0]);
16 for (int i = 1; i < n; ++i) {
17 ret = ret + ";" + to_string(needs[i]);
18 }
19 return ret;
20 }
21 int dfs (vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
22 string strNeeds = vec2str(needs);
23 if (memo.find(strNeeds) != memo.end()) {
24 return memo[strNeeds];
25 }
26 int ret = 0;
27 for (int i = 0; i < n; ++i) {
28 ret += price[i] * needs[i];
29 }
30 for (auto& sp : special) {
31 bool canCal = true;
32 auto newNeeds = needs;
33 for (int i = 0; i < n; ++i) {
34 if (newNeeds[i] < sp[i]) {
35 canCal = false;
36 break;
37 }
38 newNeeds[i] -= sp[i];
39 }
40 if (canCal) {
41 ret = min(ret, sp.back() + dfs(price, special, newNeeds));
42 }
43 }
44 memo[strNeeds] = ret;
45 return ret;
46 }
47 };
View Code
【664】Strange Printer
【679】24 Game
【685】Redundant Connection II
【690】Employee Importance
【694】Number of Distinct Islands
【695】Max Area of Island
【711】Number of Distinct Islands II
【721】Accounts Merge
【733】Flood Fill
【737】Sentence Similarity II
【743】Network Delay Time
【749】Contain Virus
【753】Cracking the Safe
【756】Pyramid Transition Matrix
【778】Swim in Rising Water
【785】Is Graph Bipartite?
【802】Find Eventual Safe States
【827】Making A Large Island
【834】Sum of Distances in Tree
【839】Similar String Groups
【841】Keys and Rooms
【851】Loud and Rich
【863】All Nodes Distance K in Binary Tree
【872】Leaf-Similar Trees
【886】Possible Bipartition
【897】Increasing Order Search Tree