leetcode刷题速度（LeetCode刷题第一周）

数组：内存空间连续 
    
    
    
，数据类型统一
     


     


     


   ，下标从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[0] || 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 < nums[mid]){ right = mid -1;//往左区间缩 }else{ left = mid +1; } mid = (left + right) >> 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; // } }

69x 的平方根

class Solution { public int mySqrt(int x) { // 使用二分查找 int left = 0; int right = x; int ans = -1; while(left <= right){ int mid = (left + right) >> 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 <= right){ int mid = (left + right) >> 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 < nums.length; fastPoint++){ // if(nums[fastPoint] != val){ // nums[solwPoint] = nums[fastPoint]; // solwPoint++; // } // } // return solwPoint; // 方法三：注意元素的顺序可以改变 
    
    
    
，使用相向指针
     


     


     


   ，时间复杂度O(n) int rightPoint = nums.length - 1; int leftPoint = 0; while(rightPoint >= 0 && nums[rightPoint] == val){ rightPoint--; } while(leftPoint <= rightPoint){ if(nums[leftPoint] == val){ nums[leftPoint] = nums[rightPoint--]; } leftPoint++; while(rightPoint >= 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 <= rightPoint){ if(Math.pow(nums[leftPoint], 2) > 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 < nums.length; right++){ sum += nums[right]; while(sum >= 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<Integer, Integer> map = new HashMap<>();//用哈希表记录被使用的篮子数量
     
     
     
 ，以及每个篮子中的水果数量 for(int right = 0; right < fruits.length; right++){ map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);//往篮子里面放水果 while(map.size() > 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 <= buttom; i++){ arr[i][right] = index++; } right--; for(int i = right; 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<Integer> spiralOrder(int[][] matrix) { int top = 0; int buttom = matrix.length - 1; int left = 0; int right = matrix[0].length - 1; List<Integer> list = new ArrayList<Integer>(); 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 <= right) list.add(matrix[i][right]); } right--; for(int i = right; i >= left; i--){ if(top <= buttom) list.add(matrix[buttom][i]); } buttom--; for(int i = buttom; i >= 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 <= right) arr[index++] = matrix[i][right]; } right--; for(int i = right; i >= left; i--){ if(top <= buttom) arr[index++] = matrix[buttom][i]; } buttom--; for(int i = buttom; i >= top; i--){ if(left <= right) arr[index++] = matrix[i][left]; } left++; } return arr; } }