LeetCode Weekly Contest 47解题思路
LeetCode Weekly Contest 47解题思路
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434708
LeetCode Weekly Contest 47解题思路
详细代码可以fork下Github上leetcode项目，不定期更新。
赛题
本次周赛主要分为以下4道题：
- Leetcode 665. Non-decreasing Array
- Leetcode 666. Path Sum IV
- Leetcode 667. Beautiful Arrangement II
- Leetcode 668. Kth Smallest Number in Multiplication Table
Leetcode 665. Non-decreasing Array
Problem:
Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element. We define an array is non-decreasing if arrayi <= arrayi + 1 holds for every i (1 <= i < n).
Example 1:
Input: 4,2,3 Output: True Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
Example 2:
Input: 4,2,1 Output: False Explanation: You can’t get a non-decreasing array by modify at most one element.
Note:
The n belongs to 1, 10,000.
思路：直接检测出合法状态（说白了，就是找到合法状态的充分必要条件），开始构思。
第一：可以找寻所有arrai < arrai - 1 的状态，对其计数，所以很简单，如果非法状态>=2，直接return false.
可以想象，cnt = 0 ，说明arra是非递减的，一定合法，直接return true。
那么cnt = 1的情况呢？我是提交时才发现的问题，主要是因为单纯的计数cnt，有一种状态检测不出，即在检测到非法状态的下标j后，前数组满足非递减，后数组满足非递减，而删除j后，这两种状态不能合法叠加。
删除即合并，想复杂了，合并的情况直接考察是否满足即可，那么删除j还是删除j-1？如果删除j，这意味着j+1的元素和j-1的元素符合非递减，需要检测一波。如果删除j-1，需要检测j元素和j-2的元素是否符合非递减。
所以该问题就是两个步骤：找非法状态，非法状态太多，不符合，非法状态在指定范围内，检测能否合并，是个模拟啊！
代码如下：
public boolean checkPossibility(int[] nums) {
int n = nums.length;
int cnt = 0;
int j = -1;
for (int i = 1; i < n; ++i){
if (nums[i] < nums[i - 1]){
cnt ++;
j = i;
}
}
if (cnt == 0) return true;
if (cnt == 1){
if (j == 1 || (j - 2 >= 0) && nums[j] >= nums[j - 2]) return true;
if (j == n - 1 || (j + 1 < n) && nums[j + 1] >= nums[j - 1]) return true;
}
return false;
}discuss还有一种做法，代码简单，思路还是一个，只不过更有技巧性，巧妙的改变值，来替代合并操作。
也分为两种情况，要么i-2的元素比i小，要么比i大，比i小的将i-1改为i，比i大的将i改为i-1，接着再来检测。
代码如下：
public boolean checkPossibility(int[] nums) {
int n = nums.length;
int cnt = 0;
for (int i = 1; i < n; ++i){
if (nums[i] < nums[i - 1]){
cnt ++;
if (i - 2 >= 0 && nums[i - 2] > nums[i]) nums[i] = nums[i - 1];
else nums[i - 1] = nums[i];
}
}
return cnt <= 1;
}Leetcode 666. Path Sum IV
Problem:
If the depth of a tree is smaller than 5, then this tree can be represented by a list of three-digits integers. For each integer in this list:
- The hundreds digit represents the depth D of this node, 1 <= D <= 4.
- The tens digit represents the position P of this node in the level it belongs to, 1 <= P <= 8. The position is the same as that in a full binary tree.
- The units digit represents the value V of this node, 0 <= V <= 9.
Given a list of ascending three-digits integers representing a binary with the depth smaller than 5. You need to return the sum of all paths from the root towards the leaves.
Example 1:
Input: 113, 215, 221 Output: 12 Explanation:undefined The tree that the list represents is: 3 / \ 5 1 The path sum is (3 + 5) + (3 + 1) = 12.
Example 2:
Input: 113, 221 Output: 4 Explanation:undefined The tree that the list represents is:undefined 3 \ 1 The path sum is (3 + 1) = 4.
思路：
这道题我的思路很暴力，从叶子结点开始搜索一条有效路径，并且累加，当然搜索路径的过程中，被访问过的结点一定不属于叶子结点，用一个visited数组记录，接着直到所有的叶子结点被访问过，程序结束。
至于如何访问叶子结点到根结点的路径，可以直接借用堆的建树规则。
我的初级代码如下：
public int pathSum(int[] nums) {
int sum = 0;
int i = nums.length - 1;
boolean[] leaf = new boolean[nums.length];
Arrays.fill(leaf, true);
while (i >= 0){
if (leaf[i]){
int val = nums[i] % 10;
int pos = nums[i] / 10 % 10;
int dep = nums[i] / 100;
int layer = dep;
sum += val;
for (int k = 1; k < dep; ++k){
for (int j = i - 1; j >= 0; --j){
int pp = nums[j] / 10 % 10;
int vl = nums[j] % 10;
int ll = nums[j] / 100;
if ((pos + 1) / 2== pp && ll < layer){
leaf[j] = false;
sum += vl;
pos = pp;
layer = ll;
break;
}
}
}
i--;
}
else i--;
}
return sum;
}当然你可以用for循环，因为if和else都需要i–，所以代码如下：
public int pathSum(int[] nums) {
int sum = 0;
int n = nums.length;
boolean[] leaf = new boolean[nums.length];
Arrays.fill(leaf, true);
for (int i = n - 1; i >= 0; --i){
if (leaf[i]){
int val = nums[i] % 10;
int pos = nums[i] / 10 % 10;
int dep = nums[i] / 100;
int layer = dep;
sum += val;
for (int k = 1; k < dep; ++k){
for (int j = i - 1; j >= 0; --j){
int pp = nums[j] / 10 % 10;
int vl = nums[j] % 10;
int ll = nums[j] / 100;
if ((pos + 1) / 2== pp && ll < layer){
leaf[j] = false;
sum += vl;
pos = pp;
layer = ll;
break;
}
}
}
}
}
return sum;
}当然，如果面对一棵大树，上述代码理论上还不够快，因为我们可以直接定位每一层的结点，思路还是一个，只是先用map记录层数和位置，接着拿到叶子结点后， 直接定位，代码如下：
public int pathSum(int[] nums) {
int sum = 0;
int n = nums.length;
boolean[][] nleaf = new boolean[5][12];
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums){
int val = num % 10;
int pos = num / 10 % 10;
int dep = num / 100;
map.put(dep * 8 + pos, val);
}
for (int i = n - 1; i >= 0; --i){
int val = nums[i] % 10;
int pos = nums[i] / 10 % 10;
int dep = nums[i] / 100;
if (!nleaf[dep][pos]){
sum += val;
for (int k = 1; k < dep; ++k){
pos = (pos + 1 ) / 2;
int key = (dep - k) * 8 + pos;
nleaf[dep - k][pos] = true;
sum += map.get(key);
}
}
}
return sum;
}当然map你也可以用一个二维数组做，这里就不写了，map更加直观。上述是迭代版本，你也可以用递归哟，这样就不需要记录是否为叶子结点咯。
Leetcode 667. Beautiful Arrangement II
Problem:
Given two integers n and k, you need to construct a list which contains n different positive integers ranging from 1 to n and obeys the following requirement:undefined Suppose this list is a1, a2, a3, … , an, then the list |a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an| has exactly k distinct integers. If there are multiple answers, print any of them.
Example 1:
Input: n = 3, k = 1 Output: 1, 2, 3 Explanation: The 1, 2, 3 has three different positive integers ranging from 1 to 3, and the 1, 1 has exactly 1 distinct integer: 1.
Example 2:
Input: n = 3, k = 2 Output: 1, 3, 2 Explanation: The 1, 3, 2 has three different positive integers ranging from 1 to 3, and the 2, 1 has exactly 2 distinct integers: 1 and 2.
Note:
The n and k are in the range 1 <= k < n <= 104.
思路：
此题其实很简单，因为k一定比n小，而我们知道，对于1toN的整数来说，最大的gap为n-1，所以当给定一个k时，一定优先满足k的gap，再满足k-1的gap，直到k=0。
这里可以证明下，假设某个数a，优先满足较小的gap，那么下一个数为a+k′a + k'，再下一个数满足最大的k，则有a′=a+k′−ka' = a + k' - k，很显然a′<aa' < a，如果取a=1a = 1，则有a′<1a' < 1，属于非法状态。因此为了避免上述情况的发生，优先满足k，再k′k'。
那么，从哪个数开始构建数组呢？从a=1a = 1，因为当a=2,k=n−1a = 2, k = n - 1的情况出现时，会有2+n−1=n+12 + n - 1 = n + 1，也属于非法状态。所以有了从1开始，先加k，接着减（k - 1），直到k=0k = 0。
那么如何保证没有被安排的元素是否会出现新的gap？哈哈，其实也很好理解，因为在构造时，我们的策略是一加一减，把一加一减看成一个整体，两次操作，末尾元素+1，那么当迭代结束时，末尾元素为：1+(k+1)/2{1 + (k + 1) / 2}，下一个被安排的元素为k+2k + 2，而它们之间的gap在1,k的范围之内。
举个简单的例子就能理解了：
n = 12, k = 5;
+5-4+3-2+1
1 6 2 5 3 4 | 7 8 9 10 11 12
n = 12, k = 6;
+6-5+4-3+2-1
1 7 2 6 3 5 4 | 8 9 10 11 12所以代码如下：
public int[] constructArray(int n, int k) {
int[] ans = new int[n];
ans[0] = 1;
int j = 0;
boolean[] used = new boolean[n + 1];
used[1] = true;
used[0] = true;
while (k > 0){
j ++;
if (j % 2 != 0){
ans[j] = ans[j - 1] + k;
used[ans[j]] = true;
}
else{
ans[j] = ans[j - 1] - k;
used[ans[j]] = true;
}
k--;
}
for (int i = 1; i < used.length; ++i){
if (!used[i]){
ans[++j] = i;
}
}
return ans;
}有了上述结论，这初级代码可以优化成：
public int[] constructArray(int n, int k) {
int[] ans = new int[n];
ans[0] = 1;
int j = 0;
int iter = k;
while (iter > 0){
j ++;
if (j % 2 != 0){
ans[j] = ans[j - 1] + iter;
}
else{
ans[j] = ans[j - 1] - iter;
}
iter--;
}
for (int i = k + 2; i <= n; ++i){
ans[++j] = i;
}
return ans;
}Leetcode 668. Kth Smallest Number in Multiplication Table
Problem:
Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table? Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.
Example 1:
Input: m = 3, n = 3, k = 5 Output:undefined Explanation:undefined The Multiplication Table: 1 2 3 2 4 6 3 6 9 The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Example 2:
Input: m = 2, n = 3, k = 6 Output:undefined Explanation:undefined The Multiplication Table: 1 2 3 2 4 6 The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).
Note:
- The m and n will be in the range 1, 30000.
- The k will be in the range 1, m * n
二分题，还是挺简单的，对于每一行，对要猜的答案进行个数统计，kth-smallest的充分必要条件为：
- 不超过x的数不少于k个
- 小于x的数有不到k个
所以二分很好写，有点类似区间搜索，[lo, hi)，其中lo满足 count(lo) < k，而count(hi) >= k，如何写count函数？对于每一行分别统计，一开始想用binarySearch，但没必要，统计函数为：cnt += Math.min(mid / i, n);
嘿嘿，整体代码如下：
public int findKthNumber(int m, int n, int k) {
int lo = 0, hi = 1000000000;
while (hi - lo > 1){
int mid = (lo + hi) / 2;
int cnt = 0;
for (int i = 1; i <= m; ++i){
cnt += Math.min(mid / i, n);
}
if (cnt < k){
lo = mid;
}
else{
hi = mid;
}
}
return hi;
}起初纠结 hi为什么是最终的答案，该答案一定会在m*n这张表里么？答案是一定的，因为if-else在更新mid时，始终满足lo < k && hi >= k，如果hi不在表里，那么计数器是不会increase的，那么自然的也不可能是这个答案了，所以只有hi在表格里时，counter才会增加。
腾讯云开发者
