数组在算法中有很广的应用，很多算法都是在数组的基础上进行的
为了写出正确的程序，我们必须要明确变量的含义，在遇见 bug 时使用小数据量进行调试，并且考虑各种边界情况，当认为 bug 解决后，再使用大数据量进行测试
二分搜索
常见的二分搜索法如下
public class Test {public static void main(String[] args) {int[] arr = {1,4,6,8,9,10,23,45,78};System.out.println(new Test().binarySearch(arr, arr.length, 10));}int binarySearch(int[] arr, int n, int target){int l = 0, r = n-1; //在 [0...n-1] 的范围中搜索 targetwhile(l <= r){int mid = (r+l)/2;if(arr[mid] == target)return mid;else if( arr[mid] > target )r = mid-1; //在 [l...mid-1] 中搜索elsel = mid+1; //在 [mid+1...r] 中搜索}return -1;}}
但是以上的这种二分搜索法其实是有缺陷的，因为 r+l 可能会导致整数溢出，为了避免溢出问题，应该避免使用加法而改为使用
int mid = l + (r-l)/2;
Leetcode 283 移动零
基础解法
最简单的思路：通过一次扫描记录下所有非 0 元素的位置，然后将对应位置的元素按照次序填充到原数组 (从头开始按相对顺序填)，最后剩下的位置使用 0 填充
class Solution {
public void moveZeroes(int[] nums) {
if(nums.length <=0)
return;
//扫描一遍，将不为 0 的元素顺序存储，即获得其相对位置和值
LinkedList<Integer> integers = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
if(nums[i] != 0) {
integers.add(nums[i]);
}
}
for (int i = 0; i < integers.size(); i++) {
nums[i] = integers.get(i);
}
for (int i = integers.size(); i < nums.length; i++）{
nums[i] = 0;
}
}
}
双指针解法
额外设置一个索引 i，让该索引指向每一个没有被覆盖的元素，而另一则索引 j 则不断后移，遇到非 0 元素时就将该元素赋值到索引 i 处，然后索引 i 后移
最后将 i 及之后的元素赋值为 0
class Solution {
public void moveZeroes(int[] nums) {
int i = 0, j = 0;
for(; j<nums.length; j++){
if(nums[j] != 0){
nums[i] = nums[j];
i++;
}
}
for(int x = i; x < nums.length; x++){
nums[x] = 0;
}
}
}
更进一步的，可以直接交换非 0 元素和 0 元素的位置，一次循环即可
class Solution {
public void moveZeroes(int[] nums) {
int i = 0, j = 0;
for(; j<nums.length; j++){
if(nums[j] != 0){
//这里的优化是：如果数组中只有非 0 元素的话，
//这就会导致数组中的每个元素都自己和自己交换了下位置，为了优化这种情况下的算法，
//应该只有当指向非0元素的索引和执行0元素的索引不同时，再进行交换
if(i != j){
int tmp = nums[j];
nums[j] = nums[i];
nums[i] = tmp;
i++;
}
else
i++;
}
}
}
}
Leetcode 27 移除元素
这道题的思路与上面的题大致相同
首先，我们通过两个索引，其中一个索引 A 不断的后移，不为目标值时，就将另一个索引 B 指向的值覆盖掉，然后将索引后移
最后通过一次遍历就将所有不为目标值的值覆盖到数组前面，最后返回的索引 B 的大小就是移除后的数组的新长度
class Solution {
public int removeElement(int[] nums, int val) {
if(nums.length == 0)
return 0;
int i = 0, j = 0;
for(; j < nums.length ; j++){
if(nums[j] != val){
nums[i] = nums[j];
i++;
}
}
return i;
}
}
Leetcode 26 删除数组中的重复项
这个问题中，值得注意的是所给的数组是一个已经排序好了的数组
因此依然可以使用双指针法，在这道题中，我们先让两个指针的位置错开来，假设指针 B 指向索引 1，指针 A 指向索引 0
- 当 nums[B] == nums[A] 时，说明重复了，指针 B 后移一位
- 当 nums[B] != nums[A] 时，说明没有重复。
- 假设这时的指针 B 在上一轮是没有移动过的 (即没有重复元素导致指针 B 后移一位)，那么指针 A 和指针 B 应该指向同一个值，让其自身覆盖自身，然后再移动指针 B，继续错位
- 假设这时的指针 B 在上一轮是移动过的了，则指针 B 和指针 A 之间必然存在一个和指针 A 当前指向元素相同的重复元素，因此先让指针 A 后移指向后面的重复元素，然后指针 B 指向的没有重复的元素覆盖该重复元素，最后指针 B 继续移动即可
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
//如果相等，则跳过，j++
for (int j = 1; j < nums.length; j++) {
//跳过了所有重复项，j 此时不与 i 重复
//此时使用不与 i 重复的 j 覆盖掉 i+1
//然后下次循环再看是否还有重复项，有的话继续覆盖
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
//最后返回 i+1 是因为 i 的下标是从 0 开始的
return i+1;
}
}
Leetcode 80 删除数组中的重复项 II
这道题是上面的升级版，但是思路差不多，需要注意的就是这题中，只有当两个指针指向的两个元素相隔为 2 以上且相等时，才代表该数字重复了两次以上，需要被覆盖掉。通过移动其中一个指针来找到与其不相同的元素来覆盖
class Solution {
public int removeDuplicates(int[] nums) {
int i = 2;
for(int j = 2; j<nums.length ; j++){
if(nums[j] != nums[i-2]){
nums[i++] = nums[j];
}
}
return i;
}
}
计数排序
Leetcode 75 颜色分类
首先，可以使用常规的排序算法来解决这个问题 ( 面试的时候尽量选择高效的算法 )，甚至使用语言中内置的排序方法来解决
//快排版
class Solution {
public void sortColors(int[] nums) {
if(nums.length == 0)
return;
quickSort(nums, 0, nums.length-1);
}
public void quickSort(int[] nums, int left, int right){
int center = 0;
if(left < right){
center = findCenter(nums, left, right);
quickSort(nums, center+1, right);
quickSort(nums, left, center-1);
}
}
public int findCenter(int[] nums, int left, int right){
int temp = nums[left];
while( left < right ){
while( left < right && temp <= nums[right] )
right--;
nums[left] = nums[right];
while( left < right && temp >= nums[left])
left++;
nums[right] = nums[left];
}
nums[left] = temp;
return left;
}
}
//内置排序方法
class Solution {
public void sortColors(int[] nums) {
Arrays.sort(nums);
}
}
虽然做出了这道题，但是很明显并不是最优解，因为并没有用到题目中的特殊条件：只有三种取值
其实，我们可以通过一遍扫描数组，统计出数组中各有多少个 0, 1, 2 ，然后将对应数目的值赋值回数组即可
class Solution {
public void sortColors(int[] nums) {
if(nums.length == 0 )
return;
sortByNums(nums);
}
public void sortByNums(int[] nums){
int i=0, j=0, k=0;
for (int num : nums) {
if(num == 0)
i++;
else if (num == 1)
j++;
else
k++;
}
for (int z = 0; z < nums.length; z++) {
if(z < i)
nums[z] = 0;
else if(z >= i && z < i+j)
nums[z] = 1;
else
nums[z] = 2;
}
}
}
可以发现，效率提高了很多很多很多…….！
这种方式就是计数排序的思路，当对数字较为有限的数组进行排序时，可以使用这种排序
但是！！！在上面这种方法中，我们依然对数组进行了两遍扫描，是否有什么优化能够对数组只进行一遍扫描呢？
答案是有的，由于我们只有三种值，那么我们就可以利用三路快排的思想， 将 0 1 2 分为三个区间
在这张图中，有三个索引用来限定范围：zero，two，i
zero 限定 0 的最大索引值和 1 的最小索引值，i 限定 1 的最大索引值和 2 的最小索引值，而 two 则只限定 2 的起始索引值
在遇到不属于对应区间的值时，交换即可
class Solution {
public void sortColors(int[] nums) {
sortByThreeLoad(nums);
}
/*
以 1 为支点，进行三路排序
*/
public void sortByThreeLoad(int[] nums){
int zero = -1; // 0 的索引，为 -1 代表 nums[0...zero] 这个区间内没有元素，当有元素时，进行+1，区间扩大
int two = nums.length; // 2 的索引，为 n 代表 nums[two...len-1] 这个区间中没有元素，当有元素时，进行-1，区间扩大
for (int i = 0; i < two; ) {
if(nums[i] == 1)
i++;
else if( nums[i] == 2 ){
/*
* 将 two 减小，然后将当前为 2 的元素交换到 two 的位置上
* */
two--;
int tmp = nums[i];
nums[i] = nums[two];
nums[two] = tmp;
}
else{
zero++;
int tmp = nums[i];
nums[i] = nums[zero];
nums[zero] = tmp;
// i++ 的原因是交换了一个元素到 0 的区间中，当 0 的范围增大时，i 也需要向后移动，以搜索后面的元素
i++;
}
}
}
}
可以看见，三路排序更进一步的减少了内存开销
双指针
Leetcode 88 合并两个有序数组
我首先想到的方法是：将 nums2 所有的数先并到 nums1 中，代替一部分 ( 也可能是全部 ) 的 0，然后对 m+n 部分进行排序即可
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len = nums1.length + n;
for (int i = m, j=0; i < len && j < n; i++, j++) {
nums1[i] = nums2[j];
}
Arrays.sort(nums1, 0, m+n);
}
}
但是仔细一想，既然两个数组都是有序的，那么就可以从他们的最大值开始比起 ( 两个索引 )，如果 nums2 的最大值比 nums1 的最大值还大，那就把这个最大值填充到 m+n-1 处 ( 这个位置相当于两个数组后并后的最后一个位置，尾索引 )，然后尾索引-1。循环步骤直到 nums1 和 nums2 的索引小于 0 位置
最后如果 nums2 的索引不为 0 的话，继续朝 nums1 中放入 nums2 的元素即可 ( 这时插入的元素都是比 nums1 中元素小的 )
上述步骤通过画图可以非常容易理解
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int nums1Right = m-1;
int nums2Right = n-1;
int mergeNums = m+n-1;
while(nums2Right >= 0 && nums1Right >= 0)
nums1[mergeNums--] =
(nums1[nums1Right] < nums2[nums2Right]) ?
nums2[nums2Right--] : nums1[nums1Right--];
while( nums2Right >= 0 )
nums1[mergeNums--] = nums2[nums2Right--];
}
}
Leetcode 215 第 K 个最大元素
这个，emmm，最简单的思路就是排序，然后返回倒数第 k 个元素( length - k ) 即可
class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums.length < 1)
return nums[0];
Arrays.sort(nums);
return nums[nums.length-k];
}
}
Leetcode 167 两数之和 II
最简单的暴力解法就是双层循环，虽然时间复杂度为 O(n)
由于题目给的条件是有序数组，因此可以尝试使用二分搜索，当检索到第 i 个元素时，对剩下的元素检索是否存在 target-nums[i] 这个元素
class Solution {
public int[] twoSum(int[] numbers, int target) {
if(numbers.length==0)
return new int[]{};
int i1=0, j1=0;
for (int i = 0; i < numbers.length; i++) {
//对剩下的 i+1 个元素进行检查
j1 = binarySearch(numbers, target - numbers[i], i+1);
if(j1 != -1){
//索引+1
int[] re = {i+1, j1+1};
return re;
}
}
return new int[]{};
}
public int binarySearch(int[] nums, int target, int left){
int l = left, r = nums.length-1;
while(l <= r){
int mid = l + (r-l)/2;
if(nums[mid] == target) return mid;
else if(nums[mid] > target) r=mid-1;
else l=mid+1;
}
return -1;
}
}
这个题同样也存在更优解，双指针是一个在数组问题中很常用的思路
假设有两个指针，i 和 j 各在数组一端，然后将 num[i] + nums[j] 与 target 作比较，并存在以下三种情况
- nums[i] + nums[j] == target 时，返回 i+1，j+1 组成的数组
- nums[i] + nums[j] < target 时，左指针向右移动，增大相加结果，继续查找
- nums[i] + nums[j] > tartget 时，右指针向左移动，减少相加结果，继续查找
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length-1;
while(l < r){
if(numbers[l] + numbers[r] == target)
return new int[]{l+1, r+1};
else if(numbers[l] + numbers[r] < target)
l++;
else
r--;
}
return new int[]{-1, -1};
}
}
这种双指针解法又被称为对撞指针
Leetcode 125 验证回文串
这题没什么好说的，依旧是对撞指针的思想，但是注意一个很坑的地方。。有一个测试用例是 0P，0 和 P 刚好相差 32，和大小写字母的相差位数相同，因此使用 +32 的方案是不行的，这时可以先将原字符串同时转为小写或大写，避免了两个指针下大小写字母的比对
class Solution {
public boolean isPalindrome(String s) {
int i = 0, j = s.length()-1;
String s1 = s.toUpperCase();
while ( i < j ){
if(s1.charAt(i) == s1.charAt(j)) {
i++;
j--;
}
else if ((s1.charAt(i) >= 32 && s1.charAt(i) <= 47) | (s.charAt(i) >= 58 && s.charAt(i) <=64) | (s.charAt(i) >= 91 && s.charAt(i) <= 96) | (s.charAt(i) >= 123 && s.charAt(i) <= 126 ) )
i++;
else if ((s1.charAt(j) >= 32 && s1.charAt(j) <= 47) | (s.charAt(j) >= 58 && s.charAt(j) <=64) | (s.charAt(j) >= 91 && s.charAt(j) <= 96) | (s.charAt(j) >= 123 && s.charAt(j) <= 126 ))
j--;
else
return false;
}
return true;
}
}
写了这个之后看题解才发现有个 API。。Character.isLetterOrDigit()。。可以直接判断是否属于字母或者数字，因此可以改为这样
class Solution {
public boolean isPalindrome(String s) {
int i = 0, j = s.length()-1;
String s1 = s.toUpperCase();
while ( i < j ){
if(s1.charAt(i) == s1.charAt(j)) {
i++;
j--;
}
else if (!Character.isLetterOrDigit(s1.charAt(i)))
i++;
else if (!Character.isLetterOrDigit(s1.charAt(j)))
j--;
else
return false;
}
return true;
}
}
只有当字符不为字母或数字，又或者两个指针指向的字符相同时才会跳过当前指向的字符，前者只移动一个指针，后者移动两个指针
Leetcode 345 反转字符串中的元音
这题也是十分简单的对撞指针，遇到元音交换即可，但是需要注意一个坑，就是大写和小写都算元音
class Solution {
public String reverseVowels(String s) {
int i = 0, j = s.length()-1;
StringBuilder builder = new StringBuilder(s);
while (i < j){
if (isYuanYin(builder.charAt(i)) && isYuanYin(builder.charAt(j))) {
char tmp = builder.charAt(i);
builder.replace(i, i+1, builder.charAt(j)+"");
builder.replace(j, j+1, tmp+"");
i++;
j--;
}else if (!isYuanYin(builder.charAt(i)) && !isYuanYin(builder.charAt(j))){
i++;
j--;
}else if(!isYuanYin(builder.charAt(i)))
i++;
else
j--;
}
return builder.toString();
}
public boolean isYuanYin(char c){
return c == 'a' || c == 'e' || c == 'i' || c == 'o'
|| c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
}
Leetcode 11 盛最多水的容器
个人感觉这题其实考到的是木桶效应
这题的意思是，相当于把选取出来的两条线当成木桶的两个边界 (二维平面下)， 然后根据木桶效应选出最短的那条边，与剩下的其它所有边进行两两组合，又由于木桶效应， 所以能存下的水 = min(edge1, edge2) * arr.length - (i+(arr.length-j))，有了这个公式以后就很简单了，我们只需要不断记录当前的最大值，同时两端更新当前的最短木板，寻找更长的木板来尝试找到最大值即可
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length-1;
int max = 0;
while ( i < j ){
int minEdge = Math.min(height[i], height[j]);
int hasMax = minEdge * (height.length - (i + (height.length - j)));
if(hasMax > max){
max = hasMax;
}else if (height[i] < height[j]){
i++;
}else
j--;
}
return max;
}
}
Leetcode 941 有效的山脉数组
这题使用双指针可以很快地解决，但是需要先明确几个边界条件
- 当最高山峰在最左边或最右边时，不是一个山脉数组
- 当相邻的山峰等大时，不是一个山脉数组
从题意中可以看出 arr[i] > arr[i-1] … > arr[0] 和 a[i] > arr[i+1] … > arr[length-1] 是山脉数组成立的条件，因此可以看出这个数组里面有且只有一个最大值，因此可以设置两个指针，一个从头开始，一个从尾开始，寻找该最大值，并且前面的值一定比后面的值小，如果大了，则说明找到了当前认为的最高山峰，对应指针停止，最后比较两个指针找到的山峰的索引是不是同一个
class Solution {
public boolean validMountainArray(int[] A) {
if (A.length < 3) {
return false;
}
int l = 0, r = A.length-1;
while ( l+1 < A.length && A[l]<A[l+1] ) l++;
while ( r > 0 && A[r]<A[r-1]) r--;
//找到的最高山峰不能是最左边或是最右边的
return l == r && l>0 && r<A.length-1;
}
}
Leetcode 15 三数之和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if(nums.length < 3) return new ArrayList<>();
List<List<Integer>> lists = new ArrayList<>();
List<Integer> list = new ArrayList<>();
Arrays.sort(nums);
int l, r;
for (int i = 0; i < nums.length; i++) {
if(i > 0 && nums[i] == nums[i - 1]) continue;
l = i+1;
r = nums.length - 1;
//每次搜索就将可以与 nums[i] 相加等于 0 的三元组加入数组中
while ( l < r ){
int sum = nums[i]+nums[l]+nums[r];
if(sum > 0) r--;
else if(sum < 0) l++;
else{
list.add(nums[i]);
list.add(nums[l]);
list.add(nums[r]);
lists.add(new ArrayList<>(list));
list.clear();
//qa
while(l < r && nums[l] == nums[l + 1]) l++;
while(l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
}
}
}
return lists;
}
}
滑动窗口
Leetcode 209 长度最小的子数组
这个问题也可以从暴力解法开始思考，最简单暴力方法就是使用 O( n ) 的双层循环来遍历出所有的连续子数组，然后比较
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length+1;
int sum = 0;
for (int k = 0; k < nums.length; k++) {
sum = 0;
for (int l = k; l < nums.length; l++) {
sum += nums[l];
// l-k 就是连续子数组的长度
if(sum >= s && l-k < len){
len = l-k;
}
}
}
//如果比一开始的 len 要大，说明无解，返回 0
if(len >= nums.length+1)
return 0;
return len+1;
}
}
虽然可以 ac，但这显然不是我们所追求的时间复杂度
暴力解法存在的一个问题就是其存在大量重复的运算，譬如
nums[i…j] 的这个连续子数组本身就包含了 num[i…j-1…j-2…j-3…i+1] 这么多的连续子数组的合
因此我们可以这么思考
- 如果我们的 nums[i…j] 这个连续子数组的合是小于目标值 s 的，那么就可以将子数组后移一位，增大子数组范围
- 反之如果连续子数组的合大于等于了 s，那么就让 i 前进，缩小连续子数组
- 每一轮的增大范围或者缩小范围后都判断当前的合是否大于等于目标值，并保存更短的连续子数组长度 len
i 和 j 两个索引就像是一个窗口一样规定了一个条件范围内的数值，同时又在不停的移动来找到满足条件的值
有了以上的思路就可以很容易的写出代码了
class Solution {
public int minSubArrayLen(int s, int[] nums) {
//nums[l...r] 代表滑动窗口
int l = 0, r = -1;
int sum = 0;
int len = nums.length;
//直到无连续子数组可选
while( l < nums.length ){
//累加，寻找符合的连续子数组
if( r+1 < nums.length && sum < s ) {
r++;
sum += nums[r];
}else{
sum -= nums[l];
l++;
}
//如果在一轮中导致了 sum >= s，则找到一组连续子数组，记录其长度
if( sum >= s)
len = Math.min(len, r-l);
}
if(len >= nums.length)
return 0;
return len+1;
}
}
Leetcode 3 无重复字的最长子串
首先在这题中需要注意的是
- 字符串中的字符可以是任意的 ASCII 字符
- 字符串中的字符大小写敏感，a 和 A 不属于同一字符
这题的解法也可以使用滑动窗口解决
- 如果 s[i…j] 中没有重复字符，则 j 后移，尝试更长的无重复子串，直到与子串中的某个字符重复
- 如果 s[i…j] 中有重复字符了，则 i 后移，缩小范围查找无重复子串，直到将重复的字符排除在窗口外
- 在每轮结束时取出当前轮次找到最长的子串
- 重复 1~3 步，直到 i == s.length()
现在最重要的问题就是，如何判断一个即将被纳入窗口的字符是否与原来的子串中的字符有所重复？
一个可行的解决方法是：设置一个长度为 256 的 boolean 数组 ( 其他类型也可，看自己 )，
在即将纳入一个字符时，判断 boolean 数组 arr[ASCII] 的位置上是否为 true，如果为 true 则代表出现了重复字符；如果不为 true，则纳入最长子串，将对应位置的值改为 true
对应的，如果有重复字符了，i 在后移的过程中，不断将原本被标志了其在子串中的字符置为 false，表示没有重复，这样就保证了当重复的字符被踢出后，j 再次后移时不会造成错误
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() == 0)
return 0;
boolean[] freq = new boolean[256];
int l = 0, r = -1;
int len = 0;
while ( l < s.length() ){
/*
256 对应 256 个字符，根据其 ASCII 来标识对应位置字符是否已经有了
*/
if(r+1 < s.length() && !freq[s.charAt(r+1)]){
r++;
freq[s.charAt(r)] = true;
}else{
freq[s.charAt(l)] = false;
l++;
}
len = Math.max(len, r-l);
}
return len+1;
}
}
Leetcode 438 找到字符串中所有字母异位词
这道题的关键是：如何判断两个字符串的所有字母都是异位词。一个很简单的方式是词频统计，如果同等长度下的两个字符串中的字母出现的频率相同，说明是异位词
class Solution {
public List<Integer> findAnagrams(String s, String p) {
//记录s的每个字符和出现的次数
Map<Character,Integer> smap = new HashMap<>();
//记录p的每个字符和出现的次数
Map<Character,Integer> pmap = new HashMap<>();
for(char ch : p.toCharArray()){
pmap.put(ch,pmap.getOrDefault(ch,0)+1);
}
List<Integer> res = new ArrayList<>();
//候选字符的个数
int count = 0;
int len = p.length();
int left = 0;
int right = 0;
while(right < s.length()){
char ch = s.charAt(right);
smap.put(ch,smap.getOrDefault(ch,0) + 1);
// 如果 p 中包含当前字符，且s的窗口中该字符出现次数小于等于p中该字符，
// 则该字符可以作为候选字符，count加一
if(pmap.containsKey(ch) && smap.get(ch) <= pmap.get(ch)){
count++;
}
//当候选字符个数等于p长度，说明s窗口中当前的字符是p的异位，此时left为起始索引
if(count == len){
res.add(left);
}
//当窗口大小等于p长度时，窗口左边需要收缩一个字符
if(right - left + 1 >= len){
char leftChar = s.charAt(left);
//判断收缩的这个字符是否是候选字符，是则count减一
if(pmap.containsKey(leftChar) && smap.get(leftChar) <= pmap.get(leftChar)){
count--;
}
//窗口收缩一个字符
smap.put(leftChar,smap.getOrDefault(leftChar,1) - 1);
left++;
}
right++;
}
return res;
}
}
牛客 S2 巅峰赛第五场 怕 npy 的牛牛
和找到无重复最长子串很像，但是具体实现可能有差别
我们可以设立三个变量
- nnum：n 出现的次数
- pnum：p 出现的次数
- ynum：y 出现的次数
我们同样设立两个指针代表窗口的左边界和右边界，遍历一遍字符串，当遇到 n / p / y 时，将对应的计数 +1，并扩大右边界
当三个计数的值都 >= 1 时
- 如果当前左边界索引的是三者之一，则将对应的次数 -1，然后左边界 +1，进行窗口缩小
- 否则继续向左搜索，直到三个计数中的其中之一小于 1
在这样一次循环中，我们就找到了不含 npy 字符串的窗口，然后与原来的最长长度进行比较，保存较长的
class Solution {
public int Maximumlength (String s) {
// write code here
if(s.length() == 0)
return 0;
int l = 0, r = -1;
int len = 0;
int nnum = 0, ynum = 0, pnum = 0;
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == 'n') nnum++;
if(s.charAt(i) == 'p') pnum++;
if(s.charAt(i) == 'y') ynum++;
//右边界一直自增
r++;
//当同时存在 npy 三个字母时，收缩左边界，直到其中一个不存在
while(nnum >= 1 && ynum >= 1 && pnum >= 1){
if(s.charAt(l) == 'n') nnum--;
if(s.charAt(l) == 'p') pnum--;
if(s.charAt(l) == 'y') ynum--;
l++;
}
//每次收缩完成代表找到一个
len = Math.max(len, r-l);
}
return len+1;
}
}
剑指 Offer 03 数组中重复的数字
it’s so easy，使用查找表即可
class Solution {
public int findRepeatNumber(int[] nums) {
boolean[] visited = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
if(visited[nums[i]]){
return nums[i];
}
visited[nums[i]] = true;
}
return -1;
}
}
剑指 Offer 53 在排序数组中查找数字 I
一般而言，如果题目出现了排序数组这个关键词，那么大概率就代表面试官想听见你说二分查找算法了，当然你也可以直接一巴掌给他甩过去，直接给他说哈希表 yyds (
class Solution {
public int search(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
return map.getOrDefault(target, 0);
}
}
好了，当你 AC 后就会看见与二分的差距了，面试官这时候就会回你一巴掌，并直接叫你爪巴
所以还是老老实实二分计数好了
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return 0;
int r = nums.length - 1, l = 0;
int count = 0;
int mid = 0;
while (l <= r){
mid = (l+r) / 2;
//查询到退出循环，此时 mid 指向的元素就是 target
//但是并不能保证查找到的就一定是第一个为 target 的元素
//所以在后面需要向前和向后遍历，找到所有相同的元素来计数
if(nums[mid] == target){
count++;
break;
}else if(nums[mid] < target){
l = mid+1;
}else{
r = mid-1;
}
}
//向前和向后查找相同大小的元素，避开已经计数的 mid
for (int i = mid+1; i<nums.length && nums[i] == target; i++) {
count++;
}
for (int i = mid-1; i >= 0 && nums[i] == target; i--) {
count++;
}
return count;
}
}
Leetcode 34 在排序数组中查找第一个和最后一个位置
如果想很 (找不到) 简 ( 工 ) 单 (作)的话，直接调 API 即可
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
Arrays.fill(res,-1);
if(nums.length == 0) {
return res;
}
List<Integer> list = Arrays.stream(nums).boxed().collect(Collectors.toList());
int one = list.indexOf(target);
res[0]=one;
int two = list.lastIndexOf(target);
res[1]=two;
return res;
}
}
当然，在实际面试的时候，如果你这么写了，估计面试官：回去等通知吧
有序数组中的搜索问题，首先应该想到的就是二分，对于这道题的，如果不考虑进阶的话，我们可以在一次二分搜索后获得下标，然后从获得的下标处朝两端进行搜索，当搜索的元素不是 target 时，就搜索到了左边界和右边界
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
Arrays.fill(res,-1);
if(nums.length == 0) {
return res;
}
//先找到一个 target 的位置
int mid = binarySearchFirst(nums, target);
//因为是有序的，所以可以根据这个 target 的位置分为向前和向后搜索
//并不断更新
if(mid != -1){
int first = mid;
int last = mid;
for (int i = first-1; i >= 0; i--) {
if(nums[i] == target){
first = i;
}
}
for (int i = last+1; i < nums.length; i++) {
if(nums[i] == target){
last = i;
}
}
res[0] = first;
res[1] = last;
}
return res;
}
private int binarySearchFirst(int[] nums, int target){
int left = 0, right = nums.length-1;
while (left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] > target){
right = mid-1;
}else if(nums[mid] < target){
left = mid+1;
}else{
return mid;
}
}
return -1;
}
}
这种解法虽然可以通过，但是如果数组中全是 target 的情况下，时间复杂度会退化为 O(N)，因此我们思考一下，有没有办法在一次二分搜索中，只搜索出 target 的某一个边界
- 我们不能在搜索到 target 时就直接进行返回
- 在 left 的移动过程中，会不断将比 target 小的元素排除在左侧，因此在二分搜索完毕后，left 要么指向了左边界的 target，要么越界，要么指向了第一个比 target 大的元素；这样我们就可以合并 nums[mid] >= target 的情况，只让 right 移动
这样我们就找到了左边界private int firstSearch(int[] nums, int target){ int left = 0; int right = nums.length - 1; //如果当前值小于目标值，应该移动 left //如果大于等于target，移动right //这样left的含义就是左侧有多少个元素小于target了 //如果left越界，或者left索引的元素依然不等于target (此时left索引到第一个比target大的元素上 )，说明没有该元素 while (left <= right){ int mid = left+(right - left)/2; if(nums[mid] < target){ left = mid+1; }else if(nums[mid] >= target){ right = mid-1; } } //检查是否越界以及是否是左边界 if(left >= nums.length || nums[left] != target){ return -1; } return left; }
同理，如果我们想要找到右边界，只需要在 nums[mid] > target 的情况下，不断移动 right，使得其右侧的所有元素都大于 target，这样我们也就找到了右边界 ( 或者没找到返回 -1 )private int lastSearch(int[] nums, int target){ int left = 0; int right = nums.length - 1; //如果当前值小于目标值，应该移动 left //如果大于等于target，移动right //这样right的含义就是右侧有多少个元素大于target了 while (left <= right){ int mid = left+(right - left)/2; if(nums[mid] <= target){ left = mid+1; }else if(nums[mid] > target){ right = mid-1; } } //检查是否越界 if(right < 0 || nums[right] != target){ return -1; } return right; }
Leetcode 35 搜索插入位置
<br />这题。。是不是和上一题有异曲同工之妙？只要理解了上一题的边界搜索思想，其实也就不难做这一题了，我们只要保证 left 左边的元素都比 target 小；或者 right 右边的元素都比target 大，这样的 left / right 就是我们想要的插入位置
class Solution {
public int searchInsert(int[] nums, int target) {
return binarySearch(nums, target);
}
private int binarySearch(int[] nums, int target){
int left = 0, right = nums.length-1;
while (left <= right){
int mid = left+(right-left)/2;
if(nums[mid] >= target){
right = mid-1;
}else{
left = mid+1;
}
}
return left;
}
}
若有收获，就点个赞吧
0 人点赞
