前两题简单不记录了
第3题-滑动子数组的美丽值-6390
示例 1：
1
2
3
4
5
6
| 输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。
|
示例 2：
1
2
3
4
5
6
7
| 输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。
|
示例 3：
1
2
3
4
5
6
7
8
| 输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。
|
提示：
1
2
3
4
5
| n == nums.length
1 <= n <= 105
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50
|
+++++++++++++++
思路：由于提示中给出的数据范围很小，-50到50，因此暴力解法就可以
定义一个数量数组，用来存储num中元素的数量，存储k个区间内元素的数量，再遍历数组求前x最小的值
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n = nums.length;
int res[] = new int[n-k+1];
int cnt[] = new int[101];
for (int i = 0;i<n;i++){
nums[i]+=50;
}
for (int i = 0;i<k;i++){
cnt[nums[i]]++;
}
int index = 0;
res[index++] = findMin(cnt,x);
for (int i = 1;i<n-k+1;i++){
cnt[nums[i-1]]--;
cnt[nums[i+k-1]]++;
res[index++] = findMin(cnt,x);
}
return res;
}
public int findMin(int cnt[],int x){
for (int i = 0;i<cnt.length;i++){
x = x-cnt[i];
if (x<=0) return i<50?i-50:0;
}
return 0;
}
}
|
自己写的超时，代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public static int[] getSubarrayBeauty(int[] nums, int k, int x) {
int n = nums.length;
List<Integer> list = new ArrayList<>();
for (int i =0 ;i<n;i++){
list.add(nums[i]);
}
int res[] = new int[n-k+1];
int index = 0;
for (int i =0 ;i<n-k+1;i++){
List<Integer> list1 = new ArrayList<>(list.subList(i, i + k));
Collections.sort(list1);
if (list1.get(x-1)<0){
res[index++]=list1.get(x-1);
}else {
res[index++] = 0;
}
}
return res;
}
}
|
第4题-使数组所有元素都变为1的最小操作数
示例 1：
1
2
3
4
5
6
7
8
| 输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。
|
示例 2：
1
2
3
| 输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。
|
+++++++++++++
思路：分三种情况讨论：
（1）如果数组中所有的数的最大公约数不为1，则无法变为1
（2）如果数组本来就包含1，则次数为数组的长度-1的个数
（3）找到最小的时最大公约数为1的操作次数，最后的结果为=找到1的最小操作数 + n-1.
代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public int minOperations(int[] nums) {
int n = nums.length;
int count = 0;
for (int i =0 ;i<n;i++){
if (nums[i]!=1) count++;
}
if (count!=n) return count;
int gcd = nums[0];
for (int i = 0;i<n;i++){
gcd = gcd(gcd,nums[i]);
if (gcd==1) break;
}
if (gcd>1) return -1;
for (int l = 2;l<=n;l++){
for (int i = 0,j = l-1;j<n;i++,j++){
int g = 0;
for (int k = i;k<=j;k++){
g = gcd(nums[k],g);
if (g==1) return l-1+n-1;
}
}
}
return -1;
}
public int gcd(int a,int b){
while (b!=0){
int t = a%b;
a = b;
b = t;
}
return a;
}
}
|