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; } }