主要目录
零、写在前面
一、主要知识点
1.十进制的数位数是否为偶数
2.前缀和
二、课后习题
1295. 统计位数为偶数的数字
主要思想
结果分析
540. 有序数组中的单一元素
主要思想
结果分析
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
主要思想
结果分析
1991. 找到数组的中间位置、724. 寻找数组的中心下标
主要思想
结果分析
26. 删除有序数组中的重复项
主要思想
结果分析
1018. 可被 5 整除的二进制前缀
主要思想
结果分析
1015. 可被 K 整除的最小整数
主要思想
结果分析
1869. 哪种连续子字符串更长
主要思想
结果分析
三、今日总结
零、写在前面
这是打卡的第十八天，今天题目比较简单，就是题量巨大，补充一个知识点，主要知识点在
《算法零基础100讲》(第18讲) 线性枚举(二) - 统计法入门https://blog.csdn.net/WhereIsHeroFrom/article/details/120875708
https://blog.csdn.net/WhereIsHeroFrom/article/details/120875708
一、主要知识点
1.十进制的数位数是否为偶数
主要利用到的思想就是先确定位数，然后看是否为偶数。
bool weishu(int n){ int count = 0; //初始化个数 while(n){ count ++; n /= 10; //数数 } return !(count & 1); //判断是否为偶数 }
2.前缀和
有个东西我们可以求一个数组的前缀和，很多题都需要用到。
int pivotIndex(int* nums, int numsSize){ int total = 0, sum = 0; for(int i = 0; i < numsSize;i++) total += nums[i]; //统计全和 for(int i = 0; i < numsSize;sum += nums[i],i++) if(sum * 2 == total - nums[i]) return i; //sum统计前缀和进行判断 return -1; }
二、课后习题
1295. 统计位数为偶数的数字
1295. 统计位数为偶数的数字
https://leetcode-cn.com/problems/find-numbers-with-even-number-of-digits/
主要思想
从前到后扫描，用变量计数，更新结果就好了。。看代码
bool weishu(int n){ //判断是否为偶数，看知识点 int count = 0; while(n){ count ++; n /= 10; } return !(count&1); } int findNumbers(int* nums, int numsSize){ int count = 0; for(int i = 0;i < numsSize;i++) if(weishu(nums[i])) count++;//满足条件的计数 return count; }
结果分析
总觉得，力扣的4ms和0ms差距不大 233
540. 有序数组中的单一元素
540. 有序数组中的单一元素
https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
主要思想
利用二分的思想，判断中间的值是否和后面的值相等。其中含有只有一个元素的串的长度一定为奇数。
int singleNonDuplicate(int* nums, int numsSize){ int low = 0,high = numsSize - 1;//二分初始值 while(low < high){ //二分跳出条件 int mid = (low + high) /2; //二分中间位置 if(mid % 2 == 1) mid--; //只判断偶数位 if(nums[mid] == nums[mid + 1]) low = mid +2;//中间两个相同，所以直接返回高位 else high = mid; //无法判断中间位置，但是后面个数为偶数 所以返回前面 } return nums[low]; }
结果分析
凑合，还行。
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
主要思想
两个指针，一个在前，一个在后，一共往后扫找偶数，一个往前扫找奇数，找到后交换就行了呗。
int* exchange(int* nums, int numsSize, int* returnSize){ int i = 0 , j = numsSize - 1; *returnSize = numsSize; while(i < j){ while((nums[i]&1)&&i < j) //找到第一个偶数 i++; while((!(nums[j]&1))&& i < j) //找到第一个奇数 j--; if(i < j){ nums[i] = nums[i] ^ nums[j];//交换i j对应元素 nums[j] = nums[i] ^ nums[j]; nums[i] = nums[i] ^ nums[j]; } else break; } return nums; }
结果分析
还行吧。
