# LeetCode Weekly Contest 47解题思路

## 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 array[i] <= array[i + 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].

```    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还有一种做法，代码简单，思路还是一个，只不过更有技巧性，巧妙的改变值，来替代合并操作。

```    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: 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: The tree that the list represents is: 3 \ 1 The path sum is (3 + 1) = 4.

```    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;
}```

```    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;
}```

```    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;
}```

## 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: 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.

```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: Explanation: 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: Explanation: 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]

• 不超过x的数不少于k个
• 小于x的数有不到k个

```    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;
}```

0 条评论

• ### 挑战程序竞赛系列（23）：3.2折半枚举

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（21）：3.2反转

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### 挑战程序竞赛系列（19）：3.1最小化第k大的值

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### vs---错误收集并自己解决后归纳

1。C++编译时，出现这样的错误 d:\program files\microsoft visual studio\vc98\include\stdio.h(3...

• ### 1545 最简单排序

个人博客：double.win 1545 最简单排序  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

• ### P2658 汽车拉力比赛

题目描述 博艾市将要举行一场汽车拉力比赛。 赛场凹凸不平，所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500)，每个单元格的海拔范围在0到10^9之...

• ### BZOJ3143: [Hnoi2013]游走(期望DP 高斯消元)

Description 一个无向连通图，顶点从1编号到N，边从1编号到M。  小Z在该图上进行随机游走，初始时小Z在1号顶点，每一步小Z以相等的概率随机选 择当...

• ### #628 DIV2 题解

组样例，每组给一个和个数 。将同一个序列重复次得到一个新序列，问可以从新序列中严格最长上升子序列长度为多少。

• ### 数组的简单练习题

1.将一个给定的整型数组转置输出， 例如： 源数组，1 2 3 4 5 6 转置之后的数组，6 5 4 3 2 1

• ### cf1000F. One Occurrence(线段树 set)

首先把询问离线，预处理每个数的\(pre, nxt\)，同时线段树维护\(pre\)(下标是\(pre\)，值是\(i\))，同时维护一下最大值