版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434659
详细代码可以fork下Github上leetcode项目,不定期更新。
本次周赛主要分为以下4道题:
Problem:
Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input:undefined 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True
Example 2:
Input:undefined 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False
典型的TWO SUM,可以采用HashSet,或者中序遍历BST采用两指针方法,时间复杂度均为O(n)O(n)
两指针代码如下:
public boolean findTarget(TreeNode root, int k) {
if (root == null) return false;
nodes = new ArrayList<>();
inorder(root);
int lf = 0, rt = nodes.size() - 1;
while (lf < rt){
int sum = nodes.get(lf) + nodes.get(rt);
if (sum < k){
lf ++;
}
else if (sum > k){
rt --;
}
else{
return true;
}
}
return false;
}
List<Integer> nodes;
public void inorder(TreeNode root){
if (root == null) return;
inorder(root.left);
nodes.add(root.val);
inorder(root.right);
}
HashSet版:
public boolean findTarget(TreeNode root, int k) {
return find(root, new HashSet<>(), k);
}
public boolean find(TreeNode root, HashSet<Integer> mem, int k){
if (root == null) return false;
if (mem.contains(k - root.val)) return true;
mem.add(root.val);
return find(root.left, mem, k) || find(root.right, mem, k);
}
Problem:
Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:
Construct the maximum tree by the given array and output the root node of this tree.
嘿,这周咋都是树题,还是采用递归,先找到对应的最大val的index,进行划分,递归的求解即可。
代码如下:
public TreeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length - 1);
}
TreeNode root = null;
public TreeNode build(int[] nums, int i, int j){
if (i > j) return null;
int idx = findMax(nums, i, j);
TreeNode root = new TreeNode(nums[idx]);
root.left = build(nums, i, idx - 1);
root.right = build(nums, idx + 1, j);
return root;
}
public int findMax(int[] nums, int i, int j){
int max = nums[i];
int id = i;
for (int index = i; index <= j; ++index){
if (max < nums[index]){
max = nums[index];
id = index;
}
}
return id;
}
Problem:
Print a binary tree in an m*n 2D string array following these rules:
Example 1:
Input: 1 / 2 Output: [“”, “1”, “”, “2”, “”, “”]
Example 2:
Input: 1 / \ 2 5 /undefined 3undefined /undefined 4undefined Output: [“”, “”, “”, “”, “”, “”, “”, “1”, “”, “”, “”, “”, “”, “”, “” “”, “3”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”, “”]
Note:
依旧递归,先计算树的深度,先把List的空填满,接着对于每一个结点都安排在区间的中间即可。
代码如下:
public List<List<String>> printTree(TreeNode root) {
List<List<String>> ans = new ArrayList<>();
if (root == null) return ans;
int layer = layer(root);
int size = (1 << layer) - 1;
for (int i = 0; i < layer; ++i){
ans.add(new ArrayList<>());
for (int j = 0; j < size; ++j){
ans.get(i).add("");
}
}
dfs(ans, root, 0, 0, size);
return ans;
}
public void dfs(List<List<String>> ans, TreeNode root, int layer, int i, int j){
if (root == null) return;
int mid = (i + j) / 2;
ans.get(layer).set(mid, root.val + "");
dfs(ans,root.left, layer + 1, i, mid - 1);
dfs(ans,root.right, layer + 1, mid + 1, j);
}
public int layer(TreeNode root){
if (root == null) return 0;
int lf = layer(root.left) + 1;
int rt = layer(root.right) + 1;
return Math.max(lf, rt);
}
Problem:
Given an array A (index starts at 1) consisting of N integers: A1, A2, …, AN and an integer B. The integer B denotes that from any place (suppose the index is i) in the array A, you can jump to any one of the place in the array A indexed i+1, i+2, …, i+B if this place can be jumped to. Also, if you step on the index i, you have to pay Ai coins. If Ai is -1, it means you can’t jump to the place indexed i in the array. Now, you start from the place indexed 1 in the array A, and your aim is to reach the place indexed N using the minimum coins. You need to return the path of indexes (starting from 1 to N) in the array you should take to get to the place indexed N using minimum coins. If there are multiple paths with the same cost, return the lexicographically smallest such path. If it’s not possible to reach the place indexed N then you need to return an empty array.
Example 1:
Input: 1,2,4,-1,2, 2 Output: 1,3,5
Exampel 2:
Input: 1,2,4,-1,2, 1 Output: []
Note:
一道DP加路径找回,dpi表示抵达第i个位置的最小代价,转移函数如下:
dp[i] = Math.min(dp[i], dp[i - j] + A[i])
其中 i - j < i的所有状态
紧接着判断dp[n-1]的值,是否INF,如果INF表明没有抵达位置n-1的路径。
反之,我们用-dp[n-1]来标注出路径,并且向回找。
搜索所有负权值的路径,构建出“最小路径”
代码如下:
static final int INF = 1 << 29;
public List<Integer> cheapestJump(int[] A, int B) {
List<Integer> ans = new ArrayList<>();
int n = A.length;
if (n == 0) return ans;
int[] dp = new int[n];
Arrays.fill(dp, INF);
dp[0] = A[0];
for (int i = 1; i < n; ++i){
if (A[i] == -1) continue;
for (int j = B; j >= 1; --j){
if (i - j >= 0){
dp[i] = Math.min(dp[i], dp[i - j] + A[i]);
}
}
}
if (dp[n - 1] == INF) return ans;
dp[n - 1] = -dp[n -1];
for (int i = n - 2; i >= 0; --i){
for (int j = B; j >= 1; --j){
if (i + j >= n) continue;
if (dp[i] + A[i + j] == -dp[i + j]){
dp[i] = -dp[i];
}
}
}
ans.add(1);
int cur = 0;
int i = 1;
while (i < n){
int min = INF;
int id = -1;
for (int j = i; j < n; ++j){
if (dp[j] <= 0 && Math.abs(dp[j]) == Math.abs(dp[cur]) + A[j]){
if (min > A[j]){
min = A[j];
id = j;
}
}
}
if (id != -1){
ans.add(id + 1);
cur = id;
i = id;
}
i ++;
}
return ans;
}
当然根据题目意思,也只会生成一条最优路径,所以上述while循环可以直接简化成:
while (i < n){
// int min = INF;
int id = -1;
for (int j = i; j < n; ++j){
if (dp[j] <= 0 && Math.abs(dp[j]) == Math.abs(dp[cur]) + A[j]){
id = j;
break;
// if (min > A[j]){
// min = A[j];
// id = j;
// }
}
}
if (id != -1){
ans.add(id + 1);
cur = id;
i = id;
}
i ++;
}
题目要求我们求解字典序最小的情况,即达到目的地有多条最优路径时,输出最优路径字典序最小。
接下来的做法需要知道这样一个事实,就论此题,当存在多条最优路径时,长度较长的最优路径,字典序较小。
比如:
A = 0 0 0 0 0
1 2 3 4 5
B = 3
那么我们有最优路径:
1 3 5
1 2 4 5
证明的关键在于位置2为什么一定会存在。
假设位置2不存在,这就意味着,如果存在多条最优路径,必然是如下形式:
最优路径1:1 3 5
可能路径2:1 3 4 5
可能路径3:1 4 5
但上述可能路径可以根据性质推得均不可能存在,因为假设2存在,必然有新的最优路径为1 4 5而不需要经过位置3.
假设3存在,自然比1 3 5还要最优,所以只会出现1 2 4 5这种位置,那么字典序自然是较小的。
接着我们可以采用逆序DAG的做法,通过一次遍历解决上述最优路径+字典序最小的选择。
代码如下:
static final int INF = 1 << 29;
public List<Integer> cheapestJump(int[] A, int B) {
int n = A.length;
List<Integer> ans = new ArrayList<>();
if (n == 0) return ans;
int[] dp = new int[n];
int[] path = new int[n];
Arrays.fill(dp, INF);
dp[n - 1] = A[n - 1];
for (int i = n - 2; i >= 0; --i){
if (A[i] == -1) continue;
for (int j = 1; j <= B; ++j){
if (i + j >= n || dp[i + j] < 0) continue;
if (dp[i + j] + A[i] < dp[i]){
dp[i] = dp[i + j] + A[i];
path[i] = i + j;
}
}
}
if (dp[0] == INF) return ans;
ans.add(1);
int cur = 0;
while (cur < n - 1){
ans.add(path[cur] + 1);
cur = path[cur];
}
return ans;
}
所以问题的关键在于for循环中变量的【顺序】,这里从后往前构建的原因在于方便从1开始输出路径,最优路径前向和后向结果是一样的。而path和j出现的顺序在于输出字典序最小的情况,因为dpi每次更新时,都是【临近】更新,而如果dpi已经达到最优,根据“>”的特性,后续的【i+j】不会被更新到,那么自然地,从1开始的最优路径,一定是长度最长的,而我们证明了,长度最长的一定是字典序最小的。