数组：内存空间连续，数据类型统一，下标从0开始
二分查找
704
class Solution { public int search(int[] nums, int target) { // 方法一：暴力解法 // for(int i = 0; i < nums.length; i++){ // if(nums[i] == target){//找到目标值 // return i; // } // } // return -1; // 方法二：二分查找（元素有序且无重复元素），使用迭代，执行速度快，但是内存消耗大 // return binarySearch(nums, target, 0, nums.length-1); // 方法三：二分查找，参考代码随想录的左闭右闭区间 // 上来先处理边界条件 if(target nums[nums.length - 1]){ return -1; } int left = 0; int right = nums.length - 1;//右闭区间 int mid = (left + right) >> 1; while(left <= right){//因为取得数组区间左右都是闭的，所以取等号的时候也能满足条件，还不需要退出循环 if(target == nums[mid]){ return mid; }else if(target > 1; } return -1; } // public int binarySearch(int[] nums, int target, int start, int end){ // int mid = (start+end)/2; // int find = -1; // if(start > end){//没有找到 // return -1; // } // if(target == nums[mid]){ // return mid; // }else if(target < nums[mid]){ // find = binarySearch(nums, target, start, mid-1); // }else{ // find = binarySearch(nums, target, mid+1, end); // } // return find; // }}69、x的平方根
class Solution { public int mySqrt(int x) { // 使用二分查找 int left = 0; int right = x; int ans = -1; while(left > 1; if((long)mid*mid <= x){ ans = mid; left = mid + 1; }else{ right = mid - 1; } } return ans; }}367、有效的完全平方数
class Solution { public boolean isPerfectSquare(int num) { int left = 0, right = num; while(left > 1; if((long) mid * mid == num){ return true; }else if((long) mid * mid < num){ left = mid + 1; }else{ right = mid - 1; } } return false; }}移除元素
27
class Solution { public int removeElement(int[] nums, int val) {// 原地移除，所有元素// 数组内元素可以乱序 // 方法一：暴力解法，不推荐，时间复杂度O(n^2) // int right = nums.length;//目标数组长度，右指针 // for(int i = 0; i < right; i++){ // if(val == nums[i]){ // right--;//找到目标数值，目标数长度减一，右指针左移 // for(int j = i; j < right; j++){ // nums[j] = nums[j + 1];//数组整体左移一位（数组元素不能删除，只能覆盖） // } // i--;//左指针左移 // } // } // return right; // 方法二：快慢指针，时间复杂度O(n) // int solwPoint = 0; // for(int fastPoint = 0; fastPoint = 0 && nums[rightPoint] == val){ rightPoint--; } while(leftPoint = 0 && nums[rightPoint] == val){ rightPoint--; } } return leftPoint; }}26、删除排序数组中的重复项
class Solution { public int removeDuplicates(int[] nums) {// 相对顺序一致，所以不能使用相向指针。// 考虑使用快慢指针 if(nums.length == 1){ return 1; } int slowPoint = 0; for(int fastPoint = 1; fastPoint < nums.length; fastPoint++){ if(nums[slowPoint] != nums[fastPoint]){ nums[++slowPoint] = nums[fastPoint]; } } return slowPoint + 1; }}283、移动零
class Solution { public void moveZeroes(int[] nums) {// 要保持相对顺序，不能用相向指针 int slowPoint = 0; for(int fastPoint = 0; fastPoint < nums.length; fastPoint++){ if(nums[fastPoint] != 0){ nums[slowPoint++] = nums[fastPoint];//所有非零元素移到左边 } } for(; slowPoint < nums.length; slowPoint++){ nums[slowPoint] = 0;//把数组末尾置零 } }}844、比较含退格的字符串
class Solution { public boolean backspaceCompare(String s, String t) { // 从前往后的话不确定下一位是不是"#"，当前位需不需要消除，所以采用从后往前的方式 int countS = 0;//记录s中"#"的数量 int countT = 0;//记录t中"#"的数量 int rightS = s.length() - 1; int rightT = t.length() - 1; while(true){ while(rightS >= 0){ if(s.charAt(rightS) == '#'){ countS++; }else{ if(countS > 0){ countS--; }else{ break; } } rightS--; } while(rightT >= 0){ if(t.charAt(rightT) == '#'){ countT++; }else{ if(countT > 0){ countT--; }else{ break; } } rightT--; } if(rightT < 0 || rightS < 0){ break; } if(s.charAt(rightS) != t.charAt(rightT)){ return false; } rightS--; rightT--; } if(rightS == -1 && rightT == -1){ return true; } return false; }}有序数组的平方
977
class Solution { public int[] sortedSquares(int[] nums) {// 用相向的双指针 int[] arr = new int[nums.length]; int index = arr.length - 1; int leftPoint = 0; int rightPoint = nums.length - 1; while(leftPoint Math.pow(nums[rightPoint], 2)){ arr[index--] = (int)Math.pow(nums[leftPoint], 2); leftPoint++; }else{ arr[index--] = (int)Math.pow(nums[rightPoint], 2); rightPoint--; } } return arr; }}长度最小的子数组
209
class Solution { public int minSubArrayLen(int target, int[] nums) {// 注意是连续子数组 // 使用滑动窗口，实际上还是双指针 int left = 0; int sum = 0; int result = Integer.MAX_VALUE; for(int right = 0; right = target){ result = Math.min(result, right - left + 1); sum -= nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; }}904、水果成篮
class Solution { public int totalFruit(int[] fruits) {// 此题也可以使用滑动窗口 int maxNumber = 0; int left = 0; Map map = new HashMap();//用哈希表记录被使用的篮子数量，以及每个篮子中的水果数量 for(int right = 0; right 2){//放进去的水果不符合水果类型 map.put(fruits[left], map.get(fruits[left]) - 1); if(map.get(fruits[left]) == 0){ map.remove(fruits[left]); } left++; } maxNumber = Math.max(maxNumber, right - left + 1); } return maxNumber; }}螺旋矩阵 II
59
class Solution { public int[][] generateMatrix(int n) { // 方法一：直接按序输出 int[][] arr = new int[n][n]; int top = 0; int buttom = n - 1; int left = 0; int right = n - 1;; int index = 1; while(left <= right && top <= buttom && index <= n*n){ for(int i = left; i <= right; i++){ arr[top][i] = index++; } top++; for(int i = top; i = left; i--){ arr[buttom][i] = index++; } buttom--; for(int i = buttom; i >= top; i--){ arr[i][left] = index++; } left++; } return arr; }}54
class Solution { public List spiralOrder(int[][] matrix) { int top = 0; int buttom = matrix.length - 1; int left = 0; int right = matrix[0].length - 1; List list = new ArrayList(); while(left <= right && top <= buttom){ for(int i = left; i <= right; i++){ if(top <= buttom) list.add(matrix[top][i]); } top++; for(int i = top; i <= buttom; i++){ if(left = left; i--){ if(top = top; i--){ if(left <= right) list.add(matrix[i][left]); } left++; } return list; }}29 、顺时针打印矩阵
class Solution { public int[] spiralOrder(int[][] matrix) { if(matrix.length == 0){ return new int[0]; } int top = 0; int buttom = matrix.length - 1; int left = 0; int right = matrix[0].length - 1; int[] arr = new int[matrix.length*matrix[0].length]; int index = 0; while(left <= right && top <= buttom){ for(int i = left; i <= right; i++){ if(top <= buttom) arr[index++] = matrix[top][i]; } top++; for(int i = top; i <= buttom; i++){ if(left = left; i--){ if(top = top; i--){ if(left <= right) arr[index++] = matrix[i][left]; } left++; } return arr; }}