版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434791
详细代码可以fork下Github上leetcode项目,不定期更新。
本次周赛主要分为以下4道题:
Problem:
Given an m * n matrix M initialized with all 0’s and several update operations. Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means Mi should be added by one for all 0 <= i < a and 0 <= j < b. You need to count and return the number of maximum integers in the matrix after performing all the operations.
Example:
Input:undefined m = 3, n = 3 operations = [2,2,3,3] Output: 4 Explanation:undefined Initially, M =undefined [0, 0, 0, 0, 0, 0, 0, 0, 0] After performing 2,2, M =undefined [1, 1, 0, 1, 1, 0, 0, 0, 0] After performing 3,3, M =undefined [2, 2, 1, 2, 2, 1, 1, 1, 1] So the maximum integer in M is 2, and there are four of it in M. So return 4.
Note:
只说关键点,每次更新都是从(0,0)到(a,b),所以只需要分别更新a,b为所有操作的最小值即可。
代码如下:
public int maxCount(int m, int n, int[][] ops) {
int x = m;
int y = n;
for (int[] op : ops){
x = Math.min(x, op[0]);
y = Math.min(y, op[1]);
}
return x * y;
}
初始化为m和n,表明没有任何操作更新时,直接返回整个数组个数。
Problem:
Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings. You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.
Example 1:
Input: “Shogun”, “Tapioca Express”, “Burger King”, “KFC” Output: “Shogun” Explanation: The only restaurant they both like is “Shogun”.
Example 2:
Input: “Shogun”, “Tapioca Express”, “Burger King”, “KFC” Output: “Shogun” Explanation: The restaurant they both like and have the least index sum is “Shogun” with index sum 1 (0+1).
Note:
意思是说找共同喜欢的饭店,且index之和最小。一道map题,把list1中的key和下标记录到map中,接着如果在list2中存在同样的key,便更新下标和,同时记录最小sum,但最小sum的记录存在信息缺失。(index1 + index2 < list1.length,在扫描key时,可能会把list1中的key记录进来,而此key是不在list2中的),所以我的做法是把list1的长度加入进来,这样,index1 + index2 > list1.length, 排除这种情况。
代码如下:
public String[] findRestaurant(String[] list1, String[] list2) {
Map<String,Integer> map = new HashMap<>();
for (int i = 0; i < list1.length; i++){
map.put(list1[i], i);
}
int add = list1.length;
int min = 1 << 30;
for (int i = 0; i < list2.length; i++){
if (map.containsKey(list2[i])){
int value = map.get(list2[i]);
map.put(list2[i], value + add + i);
min = Math.min(min, value + add + i);
}
}
List<String> ans = new ArrayList<>();
for (String key : map.keySet()){
int value = map.get(key);
if (value == min){
ans.add(key);
}
}
return ans.toArray(new String[0]);
}
Problem:
A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range 0, N - 1. Sets SK for 0 <= K < N are defined as follows: SK = { AK, A[AK], A[A[AK]], … }. Sets SK are finite for each K and should NOT contain duplicates. Write a function that given an array A consisting of N integers, return the size of the largest set SK for this array.
Example :
Input: A = 5,4,0,3,1,6,2 Output: 4 Explanation:undefined A0 = 5, A1 = 4, A2 = 0, A3 = 3, A4 = 1, A5 = 6, A6 = 2. One of the longest SK: S0 = {A0, A5, A6, A2} = {5, 6, 2, 0}
Note:
union find, 尝试了递归,发现stack over flow,所以改成了迭代,需要注意,在搜索路径上,已经搜过的结点可以标记为-1,下次不需要再遍历。遍历所有可能的环,更新最大即可。
代码如下:
public int arrayNesting(int[] nums) {
int size = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] == -1) continue;
int next = nums[i];
int step = 1;
while (next != i){
step++;
int tmp = nums[next];
nums[next] = -1;
next = tmp;
}
size = Math.max(size, step);
}
return size;
}
Problem:
Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.
Example :
Input: 5 Output: 5 Explanation:undefined Here are the non-negative integers <= 5 with their corresponding binary representations: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.
Note:
这道题较难,让我们求非连续1的所有可能的个数,当然关键问题在于要≤n\le n的情况。
≤n\le n困扰了我很久,但此问题其实可以归简为求:
给定指定位数n,求在给定位数下非连续1的个数。
例如:
n = 2;
00
01
10
11
ans = 3;
n = 3;
000
001
010
011
100
101
110
111
ans = 5
其实是一道排列组合题,排列组合题多半可以用递归式写出来,也就是说它是一道DP题,如何构建?
从 n-1 -> n 如何append?
假设f[n]为n位情况下,非连续1的个数,
则:
f[n] = "0"f[n-1] + "1"f[n-1];
分出一位,我们构建递归式,可以是0,也可以是1,所以有两种情况,但上述递归式有问题。
主要在于:"1"f[n-1],如果f[n-1]是非连续1的个数,而f[n-1]的解,并没有约束开头不能是"1",所以
"1"f[n-1] = "10"f[n-2] + "11"f[n-2];
而"11"f[n-2]是非法的,所以:
f[n] = "0"f[n-1] + "10"f[n-2];
得:
f[n] = f[n-1] + f[n-2];
这样,我们可以求得任何位数的非连续1的个数。
但,该问题是让我们求≤n\le n的非连续1的个数,小于等于很关键,它的性质该如何利用?
例如:
num = 18
二进制表示如下:
18 = 0b10010
num = 1 0 0 1 0
pos = 4 3 2 1 0
开始利用f[n],构建解。
当pos = 4 时,我们知道该位为1,那么它就存在两种情况:
1 X X X X = num
0 X X X X < num
= num 的暂且可以不考虑,而 < num 的这种情况,非连续1的个数为:f[4]
因为第一位是0,所以4位数的任何非连续1都是它的解。
接着看 = num 的情况,因为本来就是1,所以pos--;
pos = 3; 该位为9,由于 < num 的性质,不可能出现这位为1的情况,所以直接pos--;
pos = 2; 同上。
pos = 1;
1 0 0 1 X
1 0 0 0 X
同样存在两种情况,需要加上f[1];
上述情况num中并不存在连续的1,但给定的num也可能存在连续的1,如:
num = 12;
二进制表示如下:
12 = 0b1100;
num = 1 1 0 0;
pos = 3 2 1 0;
pos = 3时,可0可1
1 X X X
0 X X X f[3]
pos = 2时,可0可1?
不能为1,而只能为0!否则会出现连续1,所以只能是:
1 0 X X f[2]
直接跳出循环(因为f[2]已经包含了 1 0 X X的所有情况)。
代码如下:
public int findIntegers(int num) {
int[] f = new int[32];
f[0] = 1;
f[1] = 2;
for (int i = 2; i <= 31; i++) {
f[i] = f[i - 1] + f[i - 2];
}
int pos = 31;
while (pos >= 0 && ((num & (1 << pos)) == 0))
pos--;
if (pos == -1)
return 1;
int res = 0;
int pre = 0;
for (int i = pos; i >= 0; i--) {
if (((num >> i) & 0x01) == 1) {
res += f[i];
if (pre == 1){
res --;
break;
}
pre = 1;
}else{
pre = 0;
}
}
return res + 1;
}