版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434708
详细代码可以fork下Github上leetcode项目,不定期更新。
本次周赛主要分为以下4道题:
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;
}
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:
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更加直观。上述是迭代版本,你也可以用递归哟,这样就不需要记录是否为叶子结点咯。
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;
}
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:
二分题,还是挺简单的,对于每一行,对要猜的答案进行个数统计,kth-smallest的充分必要条件为:
所以二分很好写,有点类似区间搜索,[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才会增加。