leetcode1 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。 

  1. //1.0 暴力枚举
  2. //时间复杂度O(n^2) 空间复杂度O(1)
  3. class Solution {
  4.     public int[] twoSum(int[] nums, int target) {
  5.         for(int i = 0; i<nums.length;i++){
  6.             for(int j = i+1;j<nums.length;j++){
  7.                 if(nums[j] == target - nums[i]){
  8.                     return new int[]{i,j};
  9.                 }
  10.             }
  11.         }
  12.         return new int[0];
  13.     }
  14. }
  16. //2.0 哈希表
  17. //时间复杂度O(n) 空间复杂度O(n) 哈希表可以减少查找target-num[i]的时间
  18. class Solution {
  19.     public int[] twoSum(int[] nums, int target) {
  20.         Map<Integer,Integer> map = new HashMap<Integer,Integer>();
  21.         for(int i = 0; i < nums.length;i++){
  22.             if(map.containsKey(target - nums[i])){
  23.                 return new int[]{i,map.get(target-nums[i])};
  24.             }
  25.             map.put(nums[i],i);
  26.         }
  27.         return new int[0];
  28.     }
  29. }

leetcode 48 旋转图像

  1. class Solution {
  2.     public void rotate(int[][] matrix) {
  3.         // 先转置后镜像对称
  4.         int len = matrix.length;
  5.         for(int i = 0; i<len;i++){
  6.             for(int j=i;j<len;j++){
  7.                 int tmp = matrix[i][j];
  8.                 matrix[i][j] = matrix[j][i];
  9.                 matrix[j][i] = tmp;    
  10.             }
  11.         }
  12.         for(int i=0;i<len;i++){
  13.             for(int j=0;j<len/2;j++){
  14.                 int tmp = matrix[i][j];
  15.                 matrix[i][j] = matrix[i][len-j-1];
  16.                 matrix[i][len-j-1] = tmp; 
  17.             }
  18.         }
  20.     }
  22. }

leetcode 56 合并区间

https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode-solution/

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.         int len = intervals.length;
  4.         // 根据intervals[i][0]的大小进行排序
  5.         Arrays.sort(intervals, (a,b)->(a[0]-b[0]));
  6.         List<int[]> res = new ArrayList<>();
  7.         for(int i=0;i<len;i++){
  8.             if(res.size()==0 || intervals[i][0]>res.get(res.size()-1)[1]){
  9.                 res.add(intervals[i]);
  10.             }else{
  11.                 res.get(res.size()-1)[1] = Math.max(res.get(res.size()-1)[1], intervals[i][1]);
  12.             }
  13.         }
  14.         return res.toArray(new int[res.size()][]);
  16.     }
  17. }

leetcode59 螺旋矩阵II

给你一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 

  1. //生成一个 n×n 空矩阵 mat，随后模拟整个向内环绕的填入过程：
  2. //定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n；
  3. //当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
  4. //执行 num += 1：得到下一个需要填入的数字；
  5. //更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。
  6. //使用num <= tar而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程/中被填充的问题。
  8. class Solution {
  9.     public int[][] generateMatrix(int n) {
  10.         int[][] matrix = new int[n][n]; 
  11.         int l=0,r=n-1,t=0,b=n-1;
  12.         int end = n*n;
  13.         int count = 1;
  14.         while(count<=end){
  15.             for(int i = l; i<=r; i++) matrix[t][i] = count++;//从左向右
  16.             t++;
  17.             for(int i = t; i<=b; i++) matrix[i][r] = count++;//从上到下
  18.             r--;
  19.             for(int i = r; i>=l; i--) matrix[b][i] = count++;//从右到左
  20.             b--;
  21.             for(int i = b; i>=t; i--) matrix[i][l] = count++;//从下到上
  22.             l++;
  24.         }
  25.         return matrix;
  26.     }
  27. }

leetcode 54 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5] 

  1. class Solution {
  2.     public List<Integer> spiralOrder(int[][] matrix) {
  4.         List<Integer> list = new ArrayList<Integer>();
  5.         int m = matrix.length;
  6.         int n = matrix[0].length;
  7.         int l=0,r=n-1,t=0,b=m-1;
  9.         while(true){
  10.             for(int i=l;i<=r;i++) list.add(matrix[t][i]);//从左到右
  11.             if(++t>b) break;
  12.             for(int i=t;i<=b;i++) list.add(matrix[i][r]);//从上到下
  13.             if(--r<l) break;
  14.             for(int i=r;i>=l;i--) list.add(matrix[b][i]);//从右到左
  15.             if(--b<t) break;
  16.             for(int i=b;i>=t;i--) list.add(matrix[i][l]);//从下到上
  17.             if(++l>r) break;
  18.         }
  19.         return list;
  21.     }
  22. }

剑指offer 03数组中重复的数字

  1. 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
  3. **示例 1：**

输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 

  2. ```java
  3. //1.0 使用HashSet 时间复杂度O(n) 空间复杂度O(n)
  4. class Solution {
  5.     public int findRepeatNumber(int[] nums) {
  6.         Set<Integer> dic = new HashSet<Integer>();
  7.         for(int num : nums){
  8.             if(dic.contains(num)){
  9.                 return num;
  10.             }
  11.             dic.add(num);
  12.         }
  13.         return -1;
  14.     }
  15. }
  17. //2.0 原地交换
  18. class Solution {
  19.     public int findRepeatNumber(int[] nums) {
  20.         int temp;
  21.         int len = nums.length;
  22.         for(int i=0;i<len;i++){
  23.             while(nums[i]!=i){
  24.             if(nums[i] == nums[nums[i]]) return nums[i];
  25.             temp = nums[nums[i]];
  26.             nums[nums[i]] = nums[i];
  27.             nums[i] = temp;
  28.             }
  29.         }
  30.         return -1;
  31.     }
  32. }
  2. -  leetcode 66 加一 
  3. ```java
  4. //v1.0 考虑全为9时特殊情况，新建一个数组，比较麻烦，有时间可思考简单方法
  5. class Solution {
  6.     public int[] plusOne(int[] digits) {
  7.         int carry = 0;
  8.         int len = digits.length;
  9.         boolean allNine = true;
  10.         for(int i=0;i<len;i++){
  11.             if(digits[i]==9){
  12.                 continue;
  13.             }else{
  14.                 allNine = false;
  15.                 break;
  16.             }
  17.         }
  18.         if(allNine){
  19.             int[] res = new int[len+1];
  20.             res[0] = 1;
  21.             return res;
  22.         }else{
  23.             int sum = digits[len-1]+1;
  24.             digits[len-1] = sum%10;
  25.             carry = sum/10;
  26.             if(carry==1){
  27.                 for(int i =len-2;i>=0;i--){
  28.                     int temp = digits[i]+carry;
  29.                     digits[i] = temp%10;
  30.                     carry = temp/10;
  31.                 }
  32.                 return digits;
  33.             }else{
  34.                 return digits;
  35.             }
  36.         }
  37.     }  
  38. }
  • leetcode 560 和为K的子数组 
    1. //v1.0 暴力解法
    2. class Solution {
    3.  public int subarraySum(int[] nums, int k) {
    4.      int res = 0;
    5.      int len = nums.length;
    6.      for(int i=0;i<len;i++){
    7.          int sum=0;
    8.          for(int j=i;j<len;j++){
    9.              sum+=nums[j];
    10.              if(sum==k) res++;
    11.          }       
    12.      }
    13.      return res;
    14.  }
    15. }
    16. //v2.0 使用前缀+hashmap
    17. class Solution {
    18.  public int subarraySum(int[] nums, int k) {
    19.      int res = 0;
    20.      int len = nums.length;
    21.      int sum=0;
    22.      Map<Integer,Integer> map = new HashMap<>();//map来存储前缀信息
    23.      map.put(0,1);
    24.      for(int i=0;i<len;i++){
    25.          sum+=nums[i];
    26.          if(map.containsKey(sum-k)){
    27.              res+=map.get(sum-k);
    28.          }
    29.          map.put(sum,map.getOrDefault(sum,0)+1); //维护map
    30.      }
    31.      return res;
    32.  }
    33. }

    leetcode1248 统计优美子数组

    1. //v1.0 暴力解法 超时
    2. class Solution {
    3.  public int numberOfSubarrays(int[] nums, int k) {
    4.      int res=0;
    5.      int flag=0;
    6.      int len = nums.length;
    7.      for(int i=0;i<len;i++){
    8.          flag=0;
    9.          for(int j=i;j<len;j++){
    10.              if(nums[j]%2==1) flag++;
    11.              if(flag==k) res++;
    12.          }
    13.      }
    14.      return res;
    15.  }
    16. }
    17. //v2.0 前缀和+hashmap查找
    18. class Solution {
    19.  public int numberOfSubarrays(int[] nums, int k) {
    20.      int res=0;
    21.      int flag=0;
    22.      int len = nums.length;
    23.      Map<Integer,Integer> map = new HashMap<>();
    24.      map.put(0,1);
    25.      for(int i=0;i<len;i++){
    26.          if(nums[i]%2==1) flag++;
    27.          if(map.containsKey(flag-k)){
    28.              res+=map.get(flag-k);
    29.          }
    30.          map.put(flag,map.getOrDefault(flag,0)+1);
    31.      }
    32.      return res;
    33.  }
    34. }

leetcode31 下一个排列

  1. class Solution {
  2.     public void nextPermutation(int[] nums) {
  3.         int len = nums.length;
  4.         if(len==1){
  5.             return;
  6.         }
  7.         // 从数组中的倒数开始遍历，若找到nums[i]<nums[i+1]，则从nums[i+1]到nums[len-1]中找到比nums[i]大，但是相对而言最小的与nums[i]交换，之后的数组进行排序
  8.         int i= len-2;
  9.         for(;i>=0;i--){
  10.             if(nums[i]<nums[i+1]){
  11.                 break;
  12.             }
  13.         }
  14.         if(i==-1){
  15.             Arrays.sort(nums);
  16.             return;
  17.         }
  18.         int index = i+1;
  19.         for(int j=i+1;j<len;j++){
  20.             if(nums[j]>nums[i]&&nums[j]<nums[index]){
  21.                 index = j;
  22.             }
  23.         }
  24.         swap(nums,index,i);
  25.         Arrays.sort(nums, i+1, len);
  27.     }
  28.     public void swap(int[] nums, int i, int j){
  29.         int tmp = nums[i];
  30.         nums[i] = nums[j];
  31.         nums[j] = tmp;
  32.     }
  33. }

leetcode36 有效的数独

  1. class Solution {
  2.     public boolean isValidSudoku(char[][] board) {
  3.         //验证某个数字在行中是否已经存在
  4.         boolean[][] rowValid = new boolean[9][9];
  5.         //验证某个数字在列中是否已经存在
  6.         boolean[][] columnValid = new boolean[9][9];
  7.         //验证某个数字在块中是否已经存在
  8.         boolean[][] blockVaild = new boolean[9][9];
  10.         for(int i=0;i<9;i++){
  11.             for(int j=0;j<9;j++){
  12.                 if(board[i][j]=='.'){
  13.                     continue;
  14.                 }
  15.                 int num = board[i][j]-'1';
  16.                 int row = i;
  17.                 int column = j;
  18.                 int block = i/3*3+j/3;
  19.                 if(rowValid[i][num]||columnValid[j][num]||blockVaild[block][num]){
  20.                     return false;
  21.                 }
  22.                 rowValid[i][num] = true;
  23.                 columnValid[j][num] = true;
  24.                 blockVaild[block][num] = true;
  25.             }
  26.         }
  27.         return true;
  28.     }
  29. }

leetcode128 最长连续序列

  1. class Solution {
  2.     public int longestConsecutive(int[] nums) {
  3.         int res = 0;
  4.         Set<Integer> set = new HashSet<>();
  5.         for(int num:nums){
  6.             set.add(num);
  7.         }
  8.         for(int num:set){
  9.             if(!set.contains(num-1)){
  10.                 int tmpLen = 1;
  11.                 int tmpNum = num;
  12.                 while(set.contains(tmpNum+1)){
  13.                     tmpLen++;
  14.                     tmpNum++;
  15.                 }
  16.                 res = Math.max(res, tmpLen);
  17.             }
  18.         }
  19.         return res;
  20.     }
  21. }

leetcode 287 寻找重复数

  1. class Solution {
  2.     public int findDuplicate(int[] nums) {
  3.         int slow = nums[0];
  4.         int quick = nums[nums[0]];
  5.         while(slow!=quick){
  6.             slow = nums[slow];
  7.             quick = nums[nums[quick]];
  8.         }
  9.         int tmp = 0;
  10.         while(tmp!=slow){
  11.             tmp = nums[tmp];
  12.             slow = nums[slow];
  13.         }
  14.         return slow;
  15.     }
  16. }

leetcode 560 和为K的子数组

  1. // v1.0 前缀和
  2. class Solution {
  3.     public int subarraySum(int[] nums, int k) {
  4.         int len = nums.length;
  5.         int[] preSum = new int[len+1];
  6.         for(int i=1;i<=len;i++){
  7.             preSum[i] = preSum[i-1] + nums[i-1];
  8.         }
  9.         int res = 0;
  10.         for(int i=0;i<len;i++){
  11.             for(int j=i+1;j<len+1;j++){
  12.                 if((preSum[j]-preSum[i])==k){
  13.                     res++;
  14.                 }
  15.             }
  16.         }
  17.         return res;
  19.     }
  20. }
  22. // v2.0 前缀和+哈希表
  23. class Solution {
  24.     public int subarraySum(int[] nums, int k) {
  25.         int len = nums.length;
  26.         int preSum = 0;
  27.         Map<Integer,Integer> map = new HashMap<>();
  28.         map.put(0,1);
  29.         int res = 0;
  30.         for(int i=0;i<len;i++){
  31.             preSum+=nums[i];
  32.             res += map.getOrDefault(preSum-k,0);
  33.             map.put(preSum, map.getOrDefault(preSum,0)+1);
  34.         }
  35.         return res;
  36.     }
  37. }

leetcode581 最短无序连续子数组

  1. class Solution {
  2.     public int findUnsortedSubarray(int[] nums) {
  3.         // 从左往右，记录最大值，若当前值小于最大值，则说明需要调整
  4.         int len = nums.length, high = -1, max = Integer.MIN_VALUE;
  5.         for(int i=0; i<len; i++){
  6.             max = Math.max(max, nums[i]);
  7.             if(nums[i]<max){
  8.                 high = i;
  9.             }
  10.         }
  12.         // 从右往左，记录最小值，若当前值大于最小值，则说明需要调整
  13.         int low = -1, min = Integer.MAX_VALUE;
  14.         for(int i=len-1;i>=0;i--){
  15.             min = Math.min(min, nums[i]);
  16.             if(nums[i]>min){
  17.                 low = i;
  18.             }
  19.         }
  20.         return low+high==-2? 0:high-low+1;
  22.     }
  23. }