926打卡

1. 删除有序数组中的重复项（26）

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数

思想：双指针

class Solution {
    public int removeDuplicates(int[] nums) {
     if(nums==null||nums.length==0)return 0;
        int i =1;
        int index =1;
        while (i<nums.length){

            if (nums[i]!=nums[i-1]){
                nums[index]=nums[i];
                index++;
            }
            i++;

        }
       
        return  index;
    }
}

2. 移除元素（27）

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

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

3. 找出字符串中第一个匹配的字符（28）

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1

思想： KMP 算法，构造前缀，将两个字符拼接，找到前缀长度needle长度的位置

class Solution {
    public int strStr(String haystack, String needle) {
          int n = haystack.length(), m = needle.length();
        if (m == 0) {
            return 0;
        }
        int[] pi = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = pi[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;


    }
}

4. 两数相除（29）

给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。

整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。

返回被除数 dividend 除以除数 divisor 得到的 商 。

思想： 减法当除法，考虑32位，使用倍增

class Solution {
    public int divide(int dividend, int divisor) {
         // 考虑被除数为最小值的情况
         if(dividend == Integer.MIN_VALUE){
             if(divisor == 1)
             return Integer.MIN_VALUE;
             if (divisor ==-1)
             return Integer.MAX_VALUE;
         }
         // 考虑除数为最小值的情况
         if(divisor == Integer.MIN_VALUE)
         return dividend == Integer.MIN_VALUE? 1:0;
         // 考虑被除数为 0 的情况
         if (dividend==0)
         return 0;
         // 一般情况，使用类二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if(dividend >0){
            dividend = -dividend;
            rev = !rev;
        }
        if(divisor >0){
            divisor = -divisor;
            rev = !rev;
        }

        List<Integer> candidates = new ArrayList<>();
        candidates.add(divisor);

        int index = 0;
        // 注意溢出
        while(candidates.get(index)>=dividend - candidates.get(index)){
            candidates.add(candidates.get(index)+candidates.get(index));
            ++index; //倍增，使得除法变快
        }
        int ans =0;
        for(int i = candidates.size()-1;i>=0;--i){
            //dividend 是负数
            if(candidates.get(i) >= dividend){
                ans+=1<<i;
                dividend -=candidates.get(i);
            }

        }
        return rev? -ans :ans;

    }
}