- 5.21在长度为2n的数组里找出重复n次元素
- 解析
- 思路
- 5.22 --数组中的重复数据
- 代码如下
- 5.23 乘积小于k的子数组
- 思路---- 滑动窗口的应用
- 代码
- 5.24子数组范围的和
- 滑动窗口的实现
- 注意---题目给的·返回函数是longlong 类型
- 代码
- 关于代码需要注意的地方
- 5.25----谁先赢
- 思路----记录谁删除的次数多谁赢
- 暴力代码---水题
- 5.26----最长连续序列
- 坑
- 代码
- 关键判断
- 5.27 ---跳跃游戏
- 思路
- 动态规划--
int cmp(const void *a,const void *b){
return *(int *)a > *(int *)b;
}
int repeatedNTimes(int* nums, int numsSize) {
qsort (nums, numsSize, sizeof(int), cmp);
int cur = numsSize/2;
if (nums[cur] == nums[cur + 1]) {
return nums[cur];
} else {
return nums[cur - 1];
}
}
思路
这个题刚开始脑子冒出来的思路就是直接桶数组不幸的是结果直接告诉我超时了，你说总不能把到手的offer白白送走吧！
这时候注意到了题目中的提示，总共只有n加一个未知数，那么我们可以这样想
排序后的数组从中间砍一半 要么前面的的数字是出现次数一半的树木要么是后面的数字
中心思想直接排序找到中间的数字即可，代码如上
5.22 --数组中的重复数据思路：直接双指针方法，我们把数组进行一次排序，题目给出的数组的数据不是出现一次就是出现了2次
对数组数据排序之后 一个指针在前一个在后 直接遍历数组
指针i = 0， j = 1
若相等 i移动2个，j移动2个 把目标数字存到数组
否则i++ j++
int cmp(const void *a, const void *b){
return *(int*)a - *(int*)b;
}
int* findDuplicates(int* nums, int numsSize, int* returnSize){
int *arr = (int*)malloc(sizeof(int)*numsSize);
int cnt = 0;
int index = 0;
qsort(nums, numsSize, sizeof(nums[0]), cmp);
for(int i=1;i
if(nums[i] == nums[index]){
arr[cnt] = nums[i];
cnt++;
}
index = i;
}
*returnSize = cnt;
return arr;
}
5.23 乘积小于k的子数组
思路---- 滑动窗口的应用
-
题目中给了我们一个数组，比较幸运的是题目指示要求我们返回成绩乘积小于k的数组的个数而不是返回新的数组
-
滑动窗口-我们可以维护两个指针一个是left 另一个是right 开始嵌套循环输入 我
[10 5 2 6]. 第一次 10 < k，count ++ 然后 right 指针 是=指向left + 1，nowsum = nums[left] nowsum *= num[right]//这样我们不会错过某些数字 一旦nowsum 大于 k break循环 这样子最后的count 就是我们得到的乘积小于 k的子数组的个数
int numSubarrayProductLessThanK(int* nums, int numsSize, int k){
int left = 0, right = 0, count = 0;
for (left = 0; left < numsSize; left++) {
if (nums[left] < k) {
count++;
int nowsum = nums[left];
right = left + 1;
while (right < numsSize) {
nowsum *= nums[right];
if (nowsum < k) {
count++;
} else {
break;
}
right++;
}
}
}
return count;
}
5.24子数组范围的和
滑动窗口的实现
和昨天的题很相似 昨天的题目帮住我学习了怎么找到子数组的问题 今天的体题只要我们在在子数组里加一个判断找出最大值和最小值即可
注意—题目给的·返回函数是longlong 类型[-31372,86677,70463,37727,-91683,-41347,-90576,-82174,-84198,-5148,-12591,-34156,49770,9666,-77075,-57678,-31101,-47531,-86306,-91337,-89507,-24917,-87692,-39171,98075,17787,-42549,34352,-70752,71832,70055,-1026,3784,2190,-36669,959,50619,97129,77088,54049,51707,72052,59230,-96834,-14048,-9619,84853,99362,69885,74086,-28737,23060,-63323,13156,-72998,94336,-75409,58266,-86800,-54564,80773,40687,-47207,43609,-56556,21192,-48024,-58907,1629,-65561,-68397,31862,-2201,-34966,43542,-59201,-3637,-21936,-93559,49435,23249,-54299,70508,-90795,-3620,-33894,43927,10208,-7390,86931,48175,81859,95058,-16614,38066,-99361,63621,-99285,-47111,29933,73901,60455,46586,-84117,35256,-89853,33383,-91662,82979,-48835,-93877,-80929,-98904,-47773,69451,85183,-14449,-51496,75765,35062,12456,35254,-16363,80792,-3414,9244,62961,-52057,56344,-50277,-26870,-63323,54993,75596,-93637,-78526,-3058,-30560,82233,-50795,-5290,-641,-83040,13524,86725,23735,29280,43938,-43995,-8992,-83717,-62090,74538,58682,-56550,-8638,61528,-87974]
如果是int这个样例就过不去-不得不说力扣的样例还是很烦人的
代码long long subArrayRanges(int* nums, int numsSize){
int left = 0, right = 0;
long long sum = 0;
long long maxnum;
long long minnum;
for (left = 0; left < numsSize; left++) {
maxnum = nums[left];
minnum = nums[left];
right = left + 1;
while (right < numsSize) {
if (nums[right] > maxnum) {
maxnum = nums[right];
} else if (nums[right] < minnum) {
minnum = nums[right];
}
right++;
sum += (maxnum - minnum);
}
}
return sum;
}
关于代码需要注意的地方
- 我们的数组的下标可以用 int 因为不会超出 int 类型的范围
- 但是我们的最大最小值需要longlong来开 这样才不会超界限
- 同理sum也是一样的
bool winnerOfGame(char * colors) {
int successiveA = 0;
int successiveB = 0;//连续B的个数
int chooseA = 0;
int chooseB = 0;//连续达到3个选择随着连续数增加
for(int i = 0; colors[i] != ' '; i++) {
if(colors[i] == 'A') {
successiveA++;
successiveB = 0;
if(successiveA >= 3)
chooseA++;
} else if(colors[i] == 'B') {
successiveB++;
successiveA = 0;
if(successiveB >= 3)
chooseB++;
}
}
if(chooseA > chooseB){
return 1;
} else {
return 0;
}
}
5.26----最长连续序列
坑
[1,2,0,0] 排序之后的思路最长是 2 但实际是 3 因为题目给的是一个乱序的 而不是排好序的 我们不要按照坑来走代码
int cmp (const void *a, const void *b) {
return *(int*) a - *(int*) b;
}
int longestConsecutive(int* nums, int numsSize) {
if (numsSize == 0) {
return 0;
}
qsort(nums, numsSize, sizeof(int), cmp);
int maxlen = 0;
int curlen = 1;
for (int i = 1; i
if (nums[i] - nums[i - 1] == 1) {
curlen++;
} else if(nums[i] - nums[i - 1] != 1 && nums[i] != nums[i -1]){
if (curlen > maxlen) {
maxlen = curlen;
}
curlen = 1;
} else if (nums[i] == nums[i - 1]) {
continue;
}
}
if (curlen > maxlen) {
maxlen = curlen;
}
return maxlen;
}
关键判断
if (curlen > maxlen) {
maxlen = curlen;
}
return maxlen;
5.27 —跳跃游戏
思路
因为题目考察能否跑到最后一个点
所以可以设一个变量
max = 0；该变量是用来记录遍历到当前数组能跑到的最远的地方的
- 由于小于该变量的下标都能遍历所以只需要更新能跑到的最远处就行
- 而如果下标大于了最远处则说明跑不到最后则return false
- 而如果跑完了则可以直接return true
bool canJump(int* nums, int numsSize) {
int max = 0;
for (int i = 0; i < numsSize; i++) {
if (i > max) {
return 0;
} else {
if (max < i + nums[i]) {
max = i + nums[i];
}
}
}
return 1;
}
