目录
- 一、概念
- 二、模板
- 三、例题
- 题：1550. 存在连续三个奇数的数组
- 解：
- 题：1295. 统计位数为偶数的数字
- 解：
- 题：540. 有序数组中的单一元素
- 解：
- 题：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
- 解：
- 题：1991. 找到数组的中间位置
- 解：
- 题：724. 寻找数组的中心下标
- 题：26. 删除有序数组中的重复项
- 解：
- 题：1018. 可被 5 整除的二进制前缀
- 解：
- 题：1015. 可被 K 整除的最小整数
- 解：
- 题：1869. 哪种连续子字符串更长
- 解：
- 题：LCP 01. 猜数字
- 解：
- 题：1603. 设计停车系统
- 解：
详情请看英雄哥的专栏，以下是Java版
一、概念
计数器、枚举
二、模板
看例题
三、例题
题：1550. 存在连续三个奇数的数组
给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
示例 1：
输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。
示例 2：
输入：arr = [1,2,34,3,4,5,7,23,12]
输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。
提示：
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
解：
解题思路：枚举
AC代码：
class Solution {
public boolean threeConsecutiveOdds(int[] arr) {
int len = arr.length;
for(int i = 0; i <= len - 3; i ++) {
if((arr[i] & 1) != 0 && (arr[i+1] & 1) != 0 && (arr[i+2] & 1) != 0){
return true;
}
}
return false;
}
}题：1295. 统计位数为偶数的数字
给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。
示例 1：
输入：nums = [12,345,2,6,7896]
输出：2
解释：
12 是 2 位数字（位数为偶数）
345 是 3 位数字（位数为奇数）
2 是 1 位数字（位数为奇数）
6 是 1 位数字 位数为奇数）
7896 是 4 位数字（位数为偶数）
因此只有 12 和 7896 是位数为偶数的数字
示例 2：
输入：nums = [555,901,482,1771]
输出：1
解释：
只有 1771 是位数为偶数的数字。
提示：
1 <= nums.length <= 500
1 <= nums[i] <= 10^5
解：
解题思路：枚举
AC代码：
class Solution {
public int findNumbers(int[] nums) {
int cnt = 0;
for(int num : nums) {
if((cnt(num) & 1) == 0) cnt ++;
}
return cnt;
}
int cnt(int x) {
int cnt = 0;
while(x > 0) {
cnt ++;
x = x / 10;
}
return cnt;
}
}题：540. 有序数组中的单一元素
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
示例 1:
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: nums = [3,3,7,7,10,11,11]
输出: 10
提示:
1 <= nums.length <= 105
0 <= nums[i] <= 105
解：
解题思路：位运算
AC代码：
class Solution {
public int singleNonDuplicate(int[] nums) {
int res = 0;
for(int num : nums) {
res ^= num;
}
return res;
}
}解题思路：暴力枚举
AC代码：
class Solution {
public int singleNonDuplicate(int[] nums) {
for(int i = 0; i < nums.length - 2; i += 2) {
if(nums[i] != nums[i + 1]) return nums[i];
}
return nums[nums.length - 1];
}
}解题思路：二分
AC代码：
class Solution {
public int singleNonDuplicate(int[] nums) {
int l = 0, r = nums.length - 1;
while(l < r) {
int mid = l + r >> 1;
if(mid % 2 != 0) mid --; // 调整mid为偶下标
if(nums[mid] == nums[mid+1]) {
l = mid + 2; // 等于后一个数，说明目标在mid后边
}else {
r = mid; // 不等于后一个数，说明目标数可能是
}
}
return nums[l];
}
}题：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
0 <= nums.length <= 50000
0 <= nums[i] <= 10000
解：
解题思路：双指针
AC代码：
class Solution {
public int[] exchange(int[] nums) {
int i = 0, j = nums.length - 1;
while(i < j) {
while(i < j && (nums[i] & 1) == 1) i ++;
while(i < j && (nums[j] & 1) == 0) j --;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}
}题：1991. 找到数组的中间位置
给你一个下标从 0 开始的整数数组 nums ，请你找到 最左边 的中间位置 middleIndex（也就是所有可能中间位置下标最小的一个）。
中间位置middleIndex是满足 nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1] 的数组下标。
如果 middleIndex == 0，左边部分的和定义为 0 。类似的，如果 middleIndex == nums.length - 1，右边部分的和定义为 0 。
请你返回满足上述条件 最左边 的 middleIndex，如果不存在这样的中间位置，请你返回-1 。
示例 1：
输入：nums = [2,3,-1,8,4]
输出：3
解释：
下标 3 之前的数字和为：2 + 3 + -1 = 4
下标 3 之后的数字和为：4 = 4
示例 2：
输入：nums = [1,-1,4]
输出：2
解释：
下标 2 之前的数字和为：1 + -1 = 0
下标 2 之后的数字和为：0
示例 3：
输入：nums = [2,5]
输出：-1
解释：
不存在符合要求的 middleIndex 。
示例 4：
输入：nums = [1]
输出：0
解释：
下标 0 之前的数字和为：0
下标 0 之后的数字和为：0
提示：
1 <= nums.length <= 100
-1000 <= nums[i] <= 1000
解：
解题思路：前缀和
AC代码：
class Solution {
public int findMiddleIndex(int[] nums) {
int total = Arrays.stream(nums).sum();
int sum = 0;
for(int i = 0; i < nums.length; i ++) {
if(sum == total - sum - nums[i]) return i;
sum += nums[i];
}
return -1;
}
}题：724. 寻找数组的中心下标
题：26. 删除有序数组中的重复项
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列
解：
解题思路：双指针
AC代码：
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 0) return 0;
int i = 0, j = 0;
for(; j < nums.length; j ++) {
if(nums[i] < nums[j]){
i ++;
if(i < j) nums[i] = nums[j];
}
}
return i + 1;
}
}题：1018. 可被 5 整除的二进制前缀
给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。
返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
示例 1：
输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 整除，因此 answer[0] 为真。
示例 2：
输入：[1,1,1]
输出：[false,false,false]
示例 3：
输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]
示例 4：
输入：[1,1,1,0,1]
输出：[false,false,false,false,false]
提示：
1 <= A.length <= 30000
A[i] 为 0 或 1
解：
解题思路：遍历
AC代码：
class Solution {
public List<Boolean> prefixesDivBy5(int[] nums) {
List<Boolean> res = new ArrayList<>();
int prefix = 0;
for(int num : nums) {
prefix = ((prefix << 1)+ num) % 5;
res.add(prefix == 0);
}
return res;
}
}题：1015. 可被 K 整除的最小整数
给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。
返回 n 的长度。如果不存在这样的 n ，就返回-1。
注意： n 不符合 64 位带符号整数。
示例 1：
输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。
示例 2：
输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。
示例 3：
输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。
提示：
1 <= k <= 105
解：
解题思路：数学
AC代码：
class Solution {
public int smallestRepunitDivByK(int k) {
if(k % 2 == 0 || k % 5 == 0) return -1; // 2和5的倍数一定不行
int num = 1;
int len = 1; // 数字长度
while(num % k != 0) {
num = num % k;
num = num * 10 + 1;
len ++;
}
return len;
}
}题：1869. 哪种连续子字符串更长
给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串，返回 true ；否则，返回 false 。
- 例如，s = “110100010” 中，由 1 组成的最长连续子字符串的长度是 2 ，由 0 组成的最长连续子字符串的长度是 3 。
注意，如果字符串中不存在 0 ，此时认为由 0 组成的最长连续子字符串的长度是 0 。字符串中不存在 1 的情况也适用此规则。
示例 1：
输入：s = "1101"
输出：true
解释：
由 1 组成的最长连续子字符串的长度是 2："1101"
由 0 组成的最长连续子字符串的长度是 1："1101"
由 1 组成的子字符串更长，故返回 true 。
示例 2：
输入：s = "111000"
输出：false
解释：
由 1 组成的最长连续子字符串的长度是 3："111000"
由 0 组成的最长连续子字符串的长度是 3："111000"
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。
示例 3：
输入：s = "110100010"
输出：false
解释：
由 1 组成的最长连续子字符串的长度是 2："110100010"
由 0 组成的最长连续子字符串的长度是 3："110100010"
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。
提示：
1 <= s.length <= 100
s[i] 不是 '0' 就是 '1'
解：
解题思路：遍历字符串
AC代码：
class Solution {
public boolean checkZeroOnes(String s) {
int len0 = 0, len1 = 0;
int max0 = 0, max1 = 0;
for(char ss : s.toCharArray()) {
if(ss == '0') {
len0 ++;
len1 = 0;
}else {
len1 ++;
len0 = 0;
}
max0 = Math.max(len0, max0);
max1 = Math.max(len1, max1);
}
return max1 > max0;
}
}题：LCP 01. 猜数字
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
示例 1：
输入：guess = [1,2,3], answer = [1,2,3]
输出：3
解释：小A 每次都猜对了。
示例 2：
输入：guess = [2,2,3], answer = [3,2,1]
输出：1
解释：小A 只猜对了第二次。
限制：
guess 的长度 = 3
answer 的长度 = 3
guess 的元素取值为 {1, 2, 3} 之一。
answer 的元素取值为 {1, 2, 3} 之一。
解：
解题思路：枚举
AC代码：
class Solution {
public int game(int[] guess, int[] answer) {
int cnt = 0;
for(int i = 0; i < guess.length; i ++) {
if(guess[i] == answer[i]) cnt ++;
}
return cnt;
}
}题：1603. 设计停车系统
请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类：
- ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类，三个参数分别对应每种停车位的数目。
- bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型：大，中，小，分别用数字 1， 2 和 3 表示。
一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位，请返回 false ，否则将该车停入车位并返回 true 。
示例 1：
输入：
["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
输出：
[null, true, true, false, false]
解释：
ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ，因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ，因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ，因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ，因为没有空的大车位，唯一一个大车位已经被占据了
提示：
0 <= big, medium, small <= 1000
carType 取值为 1， 2 或 3
最多会调用 addCar 函数 1000 次
解：
解题思路：枚举
AC代码：
class ParkingSystem {
int big, medium, small;
public ParkingSystem(int big, int medium, int small) {
this.big = big;
this.medium = medium;
this.small = small;
}
public boolean addCar(int carType) {
if (carType == 1) {
if (big > 0) {
big--;
return true;
}
} else if (carType == 2) {
if (medium > 0) {
medium--;
return true;
}
} else if (carType == 3) {
if (small > 0) {
small--;
return true;
}
}
return false;
}
}