算法-数组|704.二分查找、35.搜索插入的位置 34. 在排

作者: 激扬飞雪 | 来源:发表于2022-11-16 21:05 被阅读0次

一、 LeetCode 704 二分查找

题目连接： https://leetcode.cn/problems/binary-search/
思路：使用两个变量定义左右边界，如[left, right] 使tartget和mid的位置的比较，比mid位置的值大，则说明target在右区间，既修改left = mid + 1；如果target比mid位置的值小，则说明target在左区间，既修改right = mid - 1；如果相等则返回mid的索引。都没找到则返回-1；

定义[left, right]区间查找

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) /  2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

使用[left, right)

class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                return mid;
            }
        }
        return -1;
    }
}

二、 LeetCode 35 搜索插入的位置

题目连接： https://leetcode.cn/problems/search-insert-position/
思路：使用二分查找[left, right)，找到了既mid位置的值，没有找到则返回right的位置索引

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (target < nums[0]) return 0;
        if (target > nums[nums.length - 1]) return nums.length;
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid;
            } else {
                return mid;
            }
        }
        return right;
    }
}

三、LeetCode 34 在排序数组中查找元素的第一个和最后一个位置

题目连接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
思路：使用二分查找法找到target的索引，如果为找到返回[-1, -1],如果找到了index，在分别向左边循环查找左边界，向右边循环查找右边界

class Solution {
    private int binarySearch(int[] nums, int target){
        int left = 0;
        int 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;
    }
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        if (target < nums[0] || target > nums[nums.length - 1]) return new int[]{-1, -1};
        int index = binarySearch(nums, target);
        if (index == -1) return new int[]{-1, -1};
        int left = index;
        int right = index;
        while (left - 1 >= 0 && (nums[left - 1] == nums[index])) {
            left--;
        }
        while (right + 1 <= nums.length - 1 && (nums[right + 1] == nums[index])) {
            right++;
        }
        return new int[]{left, right};
    }
}

四、 69. x 的平方根

题目连接：https://leetcode.cn/problems/sqrtx
思路：使用二分查找法分别尝试[0, x /2] ，相等的mid返回，不相等的最后取出right值返回

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        int left = 1;
        int right = x / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid > x / mid) {
                right = mid - 1;
            } else if (mid < x / mid) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return right;
    }
}

五、 367. 有效的完全平方数

题目连接：https://leetcode.cn/problems/valid-perfect-square/
思路：使用二分查找法，如果num / mid == mid并且没有余数则返回true

class Solution {
   public boolean isPerfectSquare(int num) {
       if (num == 0 || num == 1) return true;
       int left = 1;
       int right = num / 2;
       while (left <= right) {
           int mid = left + (right - left) / 2;
           if (mid > num / mid) {
               right = mid - 1;
           } else if (mid < num / mid) {
               left = mid + 1;
           } else {
               if (num % mid == 0) {
                   return true;
               } else {
                   return false;
               }
           }
       }
       return false;
   }
}

另一种写法：使用mid * mid == num判断，注意left, right ,mid, temp可能会超过int的最大值因此使用long定义变量

class Solution {
    public boolean isPerfectSquare(int num) {
        long left = 0;
        long right = num;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long temp = mid * mid;
            if (temp > num) {
                right = mid - 1;
            } else if (temp < num) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

六、 27. 移除元素

题目连接：https://leetcode.cn/problems/remove-element/
思路：定义快慢指针，在快指针里搜索非val的值更新到slow指针的数组里面

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) return 0;
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
}

七、26. 删除有序数组中的重复项

题目连接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
思路：使用快慢指针，快指针和慢指针指的内容不相等，即和以前的元素不一样的时候，slow++ 在更新slow内容

class Solution {
    public int removeDuplicates(int[] nums) {
        int slowIndex = 0;
        for (int fastIndex = 1; fastIndex < nums.length; fastIndex++) {
            if (nums[slowIndex] != nums[fastIndex]) {
                nums[++slowIndex] = nums[fastIndex];
            }
        }
        return slowIndex + 1;
    }
}

八、283. 移动零

题目连接：https://leetcode.cn/problems/move-zeroes/
思路：使用快慢指针，使得非0的数字移动到左边，剩下的slowIndex后面的都重置成0

class Solution {
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++){
            if (nums[fastIndex] != 0) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        for (int i = slowIndex; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

九、844. 比较含退格的字符串

题目连接：https://leetcode.cn/problems/backspace-string-compare/
思路：1、使用栈结构特性，遇到'#'弹出最后一个元素（注意判断栈是否为空），遇到非'#'就入栈，最后一次弹出栈得到的字符串做比较，这里可以使用StringBuilder模拟入栈（append）出栈(deleteCharAt)操作
2、使用双指针，从字符串的后面向前遍历，遇到'#'计数+1，不是'#'计数-1,直到计数等于0停止下来，比较两个位置的字符是否相等，不相等则返回false，相等i-- j--继续比较，如果遍历结束了既i < 0 || j < 0 则退出while(true) 判断两个是否到遍历完了，都遍历完了则返回true

1、使用栈的方式

class Solution {
    private String getString(String s) {
        if (s == null ||s.length() == 0) return s;
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if (c == '#') {
                if (stringBuilder.length() != 0) {
                    stringBuilder.deleteCharAt(stringBuilder.length() - 1);
                }
            } else {
                stringBuilder.append(c);
            }
        }
        return stringBuilder.toString();
    }
    public boolean backspaceCompare(String s, String t) {
        return getString(s).equals(getString(t));
    }
}

2、使用双指针

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1;
        int j = t.length() - 1;
        int sNumber = 0;
        int tNumber = 0;
        while (true) {
            while (i >= 0) {
                if (s.charAt(i) == '#') sNumber++;
                else {
                    if (sNumber > 0) sNumber--;
                    else break;
                }
                i--;
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') tNumber++;
                else {
                    if (tNumber > 0) tNumber--;
                    else break;
                }
                j--;
            }
            if (i < 0 || j < 0) break;
            if (s.charAt(i) != t.charAt(j)) return false;
            i--;
            j--;
        }
        return i == -1 && j == -1;
    }
}

十、977. 有序数组的平方

题目连接：https://leetcode.cn/problems/squares-of-a-sorted-array/
思路：使用首尾指针，取平方最大的值放在结果集的最右边

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int[] result = new int[nums.length];
        int j = result.length - 1;
        while (left <= right) {
            int leftValue = nums[left] * nums[left];
            int rightValue = nums[right] * nums[right];
            if (leftValue > rightValue) {
                result[j--] = leftValue;
                left++;
            } else {
                result[j--] = rightValue;
                right--;
            }
        }
        return result;
    }
}