Huahua's Tech Road

花花酱 LeetCode 1219. Path with Maximum Gold

By zxi on October 5, 2019

In a gold mine grid of size m * n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

Every time you are located in a cell you will collect all the gold in that cell.
From your position you can walk one step to the left, right, up or down.
You can’t visit the same cell more than once.
Never visit a cell with 0 gold.
You can start and stop collecting gold from any position in the grid that has some gold.

Example 1:

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

Example 2:

Input: grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
Output: 28
Explanation:
[[1,0,7],
 [2,0,6],
 [3,4,5],
 [0,3,0],
 [9,0,20]]
Path to get the maximum gold, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7.

Constraints:

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
There are at most 25 cells containing gold.

Solution: DFS

Time compleixty: O(4^25) ???
Space complexity: O(25)

C++

// Author: Huahua

class Solution {

public:

int getMaximumGold(vector<vector<int>>& g) {

int n = g.size();

int m = g[0].size();

int ans = 0;

function<int(int, int)> dfs = [&](int x, int y) {

if (x < 0 || x >= m || y < 0 || y >= n || g[y][x] == 0) return 0;

int c = 0;

swap(c, g[y][x]);

int r = c + max({dfs(x - 1, y), dfs(x + 1, y), dfs(x, y - 1), dfs(x, y + 1)});

swap(c, g[y][x]);

return r;

};

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j)

ans = max(ans, dfs(j, i));

return ans;

}

};

花花酱 LeetCode 1218. Longest Arithmetic Subsequence of Given Difference

By zxi on October 5, 2019

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

Example 1:

Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:

Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4

Solution: DP

dp[i] := max length of sequence ends with x
dp[x] = max(0, dp[x – diff]) + 1

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int longestSubsequence(vector<int>& arr, int d) {

unordered_map<int, int> dp;

int ans = 0;

for (int x : arr)

ans = max(ans, dp[x] = dp[x - d] + 1);

return ans;

}

};

花花酱 LeetCode 1217. Play with Chips

By zxi on October 5, 2019

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

Move the i-th chip by 2 units to the left or to the right with a cost of 0.
Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

Example 1:

Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Example 2:

Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.

Constraints:

1 <= chips.length <= 100
1 <= chips[i] <= 10^9

Solution: Math

We can choose either:
1. move all odd positions to an arbitrary even position and move the rest to the same position
2. move all even positions to an arbitrary odd position and move the rest to the same position
ans = min(# of odd pos, # of even pos)

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minCostToMoveChips(vector<int>& chips) {

int odd = 0;

int even = 0;

for (int p : chips) {

if (p % 2) {

++odd;

} else {

++even;

}

return min(odd, even);

}

};

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

By zxi on October 3, 2019

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

Solution: Recursion

Similar to LC 105

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[postorder[pe]];

int pm = ps + (im - is) - 1;

auto root = new TreeNode(postorder[pe]);

root->left = buildTree(is, im - 1, ps, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe - 1);

return root;

};

return buildTree(0, inorder.size() - 1, 0, postorder.size() - 1);

}

};

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

By zxi on October 3, 2019

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

Solution: Recursion

Preprocessing: use a hashtable to store the index of element in preorder array.

For an element in inorder array, find the pos of it in preorder array in O(1), anything to the left will be the leftchild and anything to the right will be the right child.

e.g.
buildTree([9, 3, 15, 20, 7], [3, 9, 20, 15, 7]):
root = TreeNode(9) # inorder[0] = 9
root.left = buildTree([3], [3])
root.right = buildTree([15, 20, 7], [20, 15, 7])
return root

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

unordered_map<int, int> pos;

for (int i = 0; i < inorder.size(); i++)

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[preorder[ps]];

int pm = ps + (im - is);

auto root = new TreeNode(preorder[ps]);

root->left = buildTree(is, im - 1, ps + 1, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe);

return root;

};

return buildTree(0, inorder.size() - 1, 0, preorder.size() - 1);

}

};

花花酱 LeetCode 1219. Path with Maximum Gold

Solution: DFS

C++

花花酱 LeetCode 1218. Longest Arithmetic Subsequence of Given Difference

Solution: DP

C++

花花酱 LeetCode 1217. Play with Chips

Solution: Math

C++

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Solution: Recursion

C++

Related Problems