纯编程题

1.两数之和（简单）

1108. IP地址无效化（简单）

344.反转字符串（简单）

剑指 Offer 58 - I. 翻转单词顺序（简单）

125.验证回文串 （简单）

9.回文数（简单）

58.最后一个单词的长度（简单）

剑指Offer 05.替换空格（简单）

剑指Offer 58 - II.左旋转字符串（简单）

26.删除排序数组中的重复项（简单）

剑指Offer 67.把字符串转换成整数（中等）经典atoi()，注意范围越界处理

找规律题

面试题01.08.零矩阵（简单）

  1. class Solution {
  2.     public void setZeroes(int[][] matrix) {
  3.         int x = matrix[0].length, y = matrix.length;
  4.         boolean colExisted = false;
  5.         for(int row = 0; row < y; row++) {
  6.             if(matrix[row][0] == 0) {
  7.                 colExisted = true;
  8.             }
  9.             for(int col = 1; col < x; col++) {
  10.                 if(matrix[row][col] == 0) {
  11.                     matrix[row][0] = matrix[0][col] = 0;
  12.                 }
  13.             }
  14.         }
  16.         for(int row = y - 1; row >= 0; row--) {
  17.             for(int col = 1; col < x; col++) {
  18.                 if(matrix[row][0] == 0 || matrix[0][col] == 0) {
  19.                     matrix[row][col] = 0;
  20.                 }
  21.             }
  22.             if(colExisted) {
  23.                 matrix[row][0] = 0;
  24.             }
  25.         }
  26.     }
  27. }

剑指Offer 61.扑克牌中的顺子 （中等）

排序+遍历

  1. class Solution {
  2.     public boolean isStraight(int[] nums) {
  3.         // 先排序
  4.         Arrays.sort(nums);
  5.         int joker = 0;
  6.         for(int i = 0; i < nums.length - 1; i++) {
  7.             if(nums[i] == 0) {
  8.                 joker ++;
  9.                 continue;
  10.             }
  11.             // 相等直接返回 false
  12.             if(nums[i] == nums[i + 1]) {
  13.                 return false;
  14.             }
  15.             if(nums[i] + 1 != nums[i + 1]) {
  16.                 int diff = nums[i + 1] - nums[i] - 1;
  17.                 if(diff > joker) {
  18.                     return false;
  19.                 }
  20.                 joker -= diff;
  21.             }
  22.         }
  23.         return true;
  24.     }
  25. }

题解-优化

解题思路：

根据题意，此 5 张牌是顺子的 充分条件 如下：

  1. 除大小王外，所有牌 无重复 ；
  2. 设此 5 张牌中最大的牌为 max ，最小的牌为 min （大小王除外），则需满足：max - min < 5

因而，可将问题转化为：此 5 张牌是否满足以上两个条件？

纯编程和找规律-习题解析-week01 - 图1

作者：jyd

链接：https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/

Set 集合 + 遍历

解题思路：

  • 用 Set 集合判重
  • max - min < 5
    1. class Solution {
    2.   public boolean isStraight(int[] nums) {
    3.       Set<Integer> set = new HashSet<>();
    4.       int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    5.       for(int num : nums) {
    6.           if(num == 0) {
    7.               continue;
    8.           }
    9.           if(set.contains(num)) {
    10.               return false;
    11.           }
    12.           set.add(num);
    13.           min = Math.min(min, num);
    14.           max = Math.max(max, num);
    15.       }
    16.       return max - min < 5;
    17.   }
    18. }

排序+遍历

解题思路：

  • 排序
  • 排序完后遍历数组，nums[i] == nums[i + 1] 进行判重，记录 joker 牌的数量，那么最小值为 nums[joker]，最大值为nums[n - 1]
    1. class Solution {
    2.   public boolean isStraight(int[] nums) {
    3.       int joker = 0, n = nums.length;
    4.       Arrays.sort(nums);
    5.       for(int i = 0; i < n - 1; i++) {
    6.           if(nums[i] == 0) {
    7.               joker++;
    8.               continue;
    9.           }
    10.           if(nums[i] == nums[i + 1]) {
    11.               return false;
    12.           }
    13.       }
    14.       return nums[n - 1] - nums[joker] < 5;
    15.   }
    16. }

面试题16.11.跳水板（简单）

  1. class Solution {
  2.     public int[] divingBoard(int shorter, int longer, int k) {
  3.         // 边界条件
  4.         if(k == 0) {
  5.             return new int[0];
  6.         }
  7.         if (shorter == longer) {
  8.             return new int[]{shorter * k};
  9.         }
  10.         int[] res = new int[k+1];
  11.         for(int i = 0; i <= k; i++) {
  12.             res[i] = shorter * (k - i) + longer * i;
  13.         }
  14.         return res;
  15.     }
  16. }

面试题01.05.一次编辑（中等）

  1. class Solution {
  2.     public boolean oneEditAway(String first, String second) {
  4.         if((first.length() == 0 && second.length() == 0) 
  5.         || (first.length() == 0 && second.length() == 1) 
  6.         || (first.length() == 1 && second.length() == 0)) {
  7.             return true;
  8.         }
  9.         int fl =  first.length(), sl = second.length();
  10.         int diff = Math.abs(fl - sl);
  11.         // 两字符串长度相差不能超过1
  12.         if(diff > 1) {
  13.             return false;
  14.         } else {
  15.             // 不管是插入还是删除最终两字符串只会有一个字符不同
  16.             int minLength = sl <= fl ? sl : fl, differentNums = 0;
  17.             int fIdx = 0, sIdx = 0, idx = 0;
  18.             while(fIdx < fl && sIdx < sl) {
  19.                 if(first.charAt(fIdx) != second.charAt(sIdx)) {
  20.                     differentNums++;
  21.                     if(sl > fl) {
  22.                         sIdx++;
  23.                         continue;
  24.                     }  
  25.                     if(sl < fl) {
  26.                         fIdx++;
  27.                         continue;
  28.                     } 
  29.                 }
  30.                 fIdx++;
  31.                 sIdx++; 
  32.             }
  33.             return differentNums <= 1; 
  34.         }
  35.     }
  36. }

面试题16.15.珠玑妙算 （简单）

  1. class Solution {
  2.     public int[] masterMind(String solution, String guess) {
  4.         int fake = 0, real = 0;
  6.         int[] map = new int[26];
  8.         for(int i = 0; i < 4; i++){
  9.             char sol = solution.charAt(i), gue = guess.charAt(i);
  11.             if(sol == gue) real++;
  12.             else{
  13.                 if(map[sol - 'A'] < 0) fake++;
  14.                 map[sol - 'A']++;
  16.                 if(map[gue - 'A'] > 0) fake++;
  17.                 map[gue - 'A']--;
  18.             }
  19.         }
  21.         int[] ans = {real, fake};
  23.         return ans;
  24.     }
  25. }

面试题16.04.井字游戏（中等）

  1. class Solution {
  2.     public String tictactoe(String[] board) {
  3.         int n = board.length;
  5.         // 检查行
  6.         for(int i = 0; i < n; i++) {
  7.             int j = 0;
  8.             for(; j < n - 1; j++) {
  9.                 if(board[i].charAt(j) == ' ' || board[i].charAt(j) != board[i].charAt(j + 1)) {
  10.                     break;
  11.                 }
  12.             }
  13.             if(j == n - 1) {
  14.                 return board[i].charAt(j) + "";
  15.             }
  16.         }
  18.         // 检查列
  19.         for(int i = 0; i < n; i++) {
  20.             int j = 0;
  21.             for(; j < n - 1; j++) {
  22.                 if(board[j].charAt(i) == ' ' || board[j].charAt(i) != board[j + 1].charAt(i)) {
  23.                     break;
  24.                 }
  25.             }
  26.             if(j == n - 1) {
  27.                 return board[j].charAt(i) + "";
  28.             }
  29.         }
  31.         // 检查从左上到右下
  32.         int i = 0, j = 0;
  33.         while(i < n - 1 && j < n - 1) {
  34.             if(board[i].charAt(j) == ' ' || board[i].charAt(j) != board[i + 1].charAt(j + 1)) {
  35.                 break;
  36.             }
  37.             i++;
  38.             j++;
  39.         }
  40.         if(i == n - 1 && j == n - 1) {
  41.             return board[i].charAt(j) + "";
  42.         }
  44.         i = n - 1;
  45.         j = 0;
  46.         // 检查从右上到左下
  47.         while(i > 0 && j < n - 1) {
  48.             if(board[i].charAt(j) == ' ' || board[i].charAt(j) != board[i - 1].charAt(j + 1)) {
  49.                 break;
  50.             }
  51.             i--;
  52.             j++;            
  53.         }
  54.         if(i == 0 && j == n - 1) {
  55.             return board[i].charAt(j) + "";
  56.         }
  58.         for(int p = 0; p < n; p++) {
  59.             for(int q = 0; q < n; q++) {
  60.                 if(board[p].charAt(q) == ' ') {
  61.                     return "Pending";
  62.                 }
  63.             }
  64.         }
  66.         return "Draw";
  67.     }
  68. }

55.跳跃游戏 （中等）

解题思路：
假设可达性 reachable = true，以最后一个元素的下标为目标值 targetIdx，往后遍历，判断后一个元素的值 + 该元素的下标值是否大于目标值 targetIdx。
如果小于，则 targetIdx 保持不变，reachable = false， 继续往后遍历。
反之，则 targetIdx 变为当前元素的下标值，reachable = true，继续往后遍历。
直至遍历完成。

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         // 倒序遍历排查
  4.         boolean res = true;
  5.         int n = nums.length;
  6.         int targetIdx = n - 1;
  7.         for(int i = n - 2; i >= 0; i--) {
  8.             if(nums[i] + i < targetIdx) {
  9.                 res = false;
  10.             } else {
  11.                 targetIdx = i;
  12.                 res = true;
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. }

贪心-0

解题思路：

如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新 如果可以一直跳到最后，就成功了

作者：ikaruga

链接：https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

  1. class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int k = 0;
  4.         for(int i = 0; i < nums.length; i++) {
  5.             if(k < i) {
  6.                 return false;
  7.             }
  8.             k = Math.max(k, i + nums[i]);
  9.         }
  10.         return true;
  11.     }
  12. }

贪心-优化写法

  1. public class Solution {
  2.     public boolean canJump(int[] nums) {
  3.         int n = nums.length;
  4.         int rightmost = 0;
  5.         for (int i = 0; i < n; ++i) {
  6.             if (i <= rightmost) {
  7.                 rightmost = Math.max(rightmost, i + nums[i]);
  8.                 if (rightmost >= n - 1) {
  9.                     return true;
  10.                 }
  11.             }
  12.         }
  13.         return false;
  14.     }
  15. }

48.旋转图像 （中等）经典

  1. class Solution {
  2.     public void rotate(int[][] matrix) {
  3.         // 水平线翻转
  4.         int s = 0, e = matrix.length - 1;
  5.         while(s < e) {
  6.             for(int i = 0; i < matrix.length; i++) {
  7.                 swap(s, i, e, i, matrix);
  8.             }
  9.             s++;
  10.             e--;
  11.         }
  12.         // 以左上角到右下角的对角线为标准进行翻转
  13.         int m = 0, n = 0;
  14.         while(m < matrix.length) {
  15.             for(int i = 0; i <= n; i++) {
  16.                 swap(m, i, i, m, matrix);
  17.             }
  18.             m++;
  19.             n++;
  20.         }
  21.     }
  23.     private void swap(int m1, int n1, int m2, int n2, int[][] matrix) {
  24.         int temp = matrix[m1][n1];
  25.         matrix[m1][n1] = matrix[m2][n2];
  26.         matrix[m2][n2] = temp;
  27.     }
  28. }

54.螺旋矩阵（中等）经典

  1. class Solution {
  2.     public List<Integer> spiralOrder(int[][] matrix) {
  3.         int m = matrix.length, n = matrix[0].length;
  4.         List<Integer> result = new ArrayList<>();
  5.         int top = 0, bottom = m - 1, left = 0, right = n - 1;
  6.         while(left <= right  && top <= bottom) {
  7.             // 左上到右上
  8.             for(int i = left; i <= right; i++) {
  9.                 result.add(matrix[top][i]);
  10.             }
  12.             // 从右上到右下
  13.             for(int i = top + 1; i <= bottom; i++) {
  14.                 result.add(matrix[i][right]);
  15.             }
  17.             // 右下到左下
  18.             if(top != bottom) {
  19.                 for(int i = right - 1; i >= left; i--) {
  20.                     result.add(matrix[bottom][i]);
  21.                 }
  22.             }
  25.             if(left != right) {
  26.                 // 左下到右上
  27.                 for(int i = bottom - 1; i > top; i--) {
  28.                     result.add(matrix[i][left]);
  29.                 }
  30.             }
  32.             left++;
  33.             right--;
  34.             top++;
  35.             bottom--;
  36.         }
  37.         return result;
  38.     }
  39. }

240.搜索二维矩阵II （中等）经典

二分搜索

  1. class Solution {
  2.     public boolean searchMatrix(int[][] matrix, int target) {
  3.         // 根据行来确定哪列
  4.         boolean res = false;
  5.         for(int[] nums : matrix) {
  6.             res = binarySearch(nums, target);
  7.             if(res){
  8.                 return res;
  9.             }
  10.         }
  11.         return res;
  12.     }
  14.     // 标准二分写法
  15.     private boolean binarySearch(int[] nums, int target) {
  16.         int s = 0, e = nums.length - 1; 
  17.         while(s <= e) {
  18.             int mid = (e + s) / 2;
  19.             if(nums[mid] == target) {
  20.                 return true;
  21.             } else if (target > nums[mid]) {
  22.                 s = mid + 1;
  23.             } else {
  24.                 e = mid - 1;
  25.             }
  26.         }
  27.         return false;
  28.     }
  29. }

优化写法

解题思路：

  • 从右上角的值开始倒推

  • 由于行、列的数据都是升序的，那么当前值大于目标值时，从右上角出发，只能 

    1. class Solution {
    2.   public boolean searchMatrix(int[][] matrix, int target) {
    3.       int hight = matrix.length, wide = matrix[0].length;
    4.       int row = 0, col = wide - 1;
    5.       while(row < hight && col >= 0) {
    6.           if(matrix[row][col] == target) {
    7.               return true;
    8.           }
    10.           if(matrix[row][col] > target) {
    11.               col--;
    12.               continue;
    13.           }
    15.           if(matrix[row][col] < target) {
    16.               row++;
    17.               continue;
    18.           }
    19.       }
    20.       return false;
    21.   }
    22. }