• Offer刷题——1

    目录

    剑指 Offer 03. 数组中重复的数字

     剑指 Offer 04. 二维数组中的查找​编辑

    剑指 Offer 05. 替换空格

    剑指 Offer 06. 从尾到头打印链表 

    剑指 Offer 03. 数组中重复的数字

    1. class Solution {
    2.          public int findRepeatNumber(int[] nums) {
    3.         Map map=new HashMap<>();
    4.         for (int i = 0; i 
    5.             if (!map.containsKey(nums[i])){
    6.                 map.put(nums[i],1);
    7.             }else {
    8.                 map.put(nums[i],map.get(nums[i])+1);
    9.             }
    10.         }
    11.         for (Map.Entry entry:map.entrySet()) {
    12.             if (entry.getValue()>1){
    13.                 return entry.getKey();
    14.             }
    15.         }
    16.         return -1;
    17.     }
    18.  
    19.  
    20. }
    • 我的思路就是用一个hashmap来存储
    • 一个注意点就是其map的遍历方式，用Entry的这种形式来遍历Map的元素
    • 也可以用Set，因为其Set的唯一性，如果遇到了就直接返回这个指

     剑指 Offer 04. 二维数组中的查找

    1. class Solution {
    2.    public boolean findNumberIn2DArray(int[][] matrix, int target) {
    3.         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    4.             return false;
    5.         }
    6.         int rows=0;
    7.         int columns=matrix[0].length-1;
    8.         if (target>matrix[matrix.length-1][columns]||target0][0]){
    9.             return false;
    10.         }else {
    11.             return helper(matrix,rows,columns,target);//从左上角开始递归
    12.         }
    13.     }
    14.  
    15.     private boolean helper(int[][] matrix, int rows, int columns,int target) {
    16.         if (rows<0||rows>matrix.length-1||columns<0||columns>matrix[0].length){
    17.             return false;
    18.         }
    19.         if (matrix[rows][columns]==target){
    20.             return true;
    21.         }else if(matrix[rows][columns]>target){
    22.             return helper(matrix,rows,columns-1,target);
    23.         }else {
    24.             return helper(matrix,rows+1,columns,target);
    25.         }
    26.     }
    27. }

    剑指 Offer 05. 替换空格

    1. class Solution {
    2.     public String replaceSpace(String s) {
    3.         return s.replace(" ", "%20") ;
    4.     }
    5. }
    •  大概思路，创建一个新字符串，遇到空格就加%20，如果遇到别的字符，就直接添加

    剑指 Offer 06. 从尾到头打印链表 

    栈的解法 

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. class Solution {
    10.       public int[] reversePrint(ListNode head) {
    11.         LinkedList stack=new LinkedList<>();
    12.         while (head!=null){
    13.             stack.addLast(head.val);
    14.             head=head.next;
    15.         }
    16.         int arr[]=new int[stack.size()];
    17.         for (int i = 0; i < arr.length; i++) {
    18.             arr[i]=stack.removeLast();
    19.         }
    20.         return arr;
    21.     }
    22.  
    23. }

    递归解法

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. class Solution {
    10.    LinkedList list=new LinkedList<>();
    11.     public int[] reversePrint(ListNode head) {
    12.        helper(head);
    13.        int arr[]=new int[list.size()];
    14.         for (int i = 0; i 
    15.             arr[i]=list.get(i);
    16.         }
    17.         return arr;
    18.     }
    19.  
    20.     private void helper(ListNode head) {
    21.         if (head==null) return;
    22.         helper(head.next);
    23.         list.add(head.val);
    24.     }
    25. }
    • 从这道题我们就可以目标，其实递归可以用栈实现，递归本质就是一个栈

    剑指 Offer 07. 重建二叉树 LCOF

    1. class Solution {
    2.     public TreeNode buildTree(int[] preorder, int[] inorder) {
    3.         int n=preorder.length-1;
    4.         int m=inorder.length-1;
    5.         return helper(preorder,0,n,inorder,0,m);
    6.         //以pre[0,n]和ino[0,m]来创建树 pre[0]是根节点 ，通过ino来确定左右子树的范围
    7.     }
    8.  
    9.     private TreeNode helper(int[] preorder, int preStart, int n, int[] inorder, int inoStart, int m) {
    10.         if(preStart>n){
    11.             //说明要构建的节点已经没有了
    12.             return null;
    13.         }
    14.         int rootVal=preorder[preStart];//要构造的根节点
    15.         int index=findNum(inorder,rootVal);
    16.         int leftSize=index-inoStart;
    17.         TreeNode root=new TreeNode(rootVal);
    18.         root.left=helper(preorder,preStart+1,preStart+leftSize,
    19.                 inorder,inoStart,index-1);
    20.         root.right=helper(preorder,preStart+leftSize+1,n,
    21.                         inorder,index+1,m);
    22.         return root;
    23.     }
    24.  
    25.     private int findNum(int[] inorder, int rootVal) {
    26.         for (int i = 0; i < inorder.length; i++) {
    27.             if (inorder[i]==rootVal){
    28.                 return i;
    29.             }
    30.         }
    31.         return -1;
    32.     }
    33. }

    剑指 Offer 09. 用两个栈实现队列

     

    1. class CQueue {
    2.  LinkedList A;
    3.     LinkedList B;
    4.     public CQueue() {
    5.         A=new LinkedList<>();
    6.         B=new LinkedList<>();
    7.         //用B来存储数据,A来辅助
    8.     }
    9.  
    10.     public void appendTail(int value) {
    11.         while (!B.isEmpty()){
    12.            int val=B.removeLast();
    13.            A.addLast(val);
    14.         }
    15.         A.addLast(value);
    16.         while (!A.isEmpty()){
    17.             int val=A.removeLast();
    18.             B.addLast(val);
    19.         }
    20.     }
    21.  
    22.     public int deleteHead() {
    23.         if (B.isEmpty()){
    24.             return -1;
    25.         }else {
    26.             return B.removeLast();
    27.         }
    28.     }
    29. }
    30.  
    31. /**
    32.  * Your CQueue object will be instantiated and called as such:
    33.  * CQueue obj = new CQueue();
    34.  * obj.appendTail(value);
    35.  * int param_2 = obj.deleteHead();
    36.  */

    剑指 Offer 11. 旋转数组的最小数字

    1. class Solution {
    2.     public int minArray(int[] numbers) {
    3.         int right=numbers.length-1;
    4.         int left=0;
    5.         while (left
    6.             int mid=left+(right-left)/2;
    7.             if (numbers[mid]>numbers[right]){
    8.                 left=mid+1;
    9.             }else if(numbers[mid]
    10.                 right=mid;
    11.             }else {
    12.                 //当两个值相同,不能判断这个值到底在左边还是在右边
    13.                 //就将right--
    14.                 //如果减去的这个值不是我们要找的，无所谓
    15.                 //如果减去的值是我们要找的，那么数组中还是存在一个，不用担心
    16.                 right--;
    17.             }
    18.         }
    19.         return numbers[left];
    20.     }
    21. }

    剑指 Offer 12. 矩阵中的路径

     

    1. class Solution {
    2.    public boolean exist(char[][] board, String word) {
    3.         for (int i = 0; i < board.length; i++) {
    4.             for (int j = 0; j < board[0].length; j++) {
    5.                 if (backtrack(board,i,j,word,0)){
    6.                     return true;
    7.                 }
    8.             }
    9.         }
    10.         return false;
    11.     }
    12.  
    13.     /**
    14.      * 表示从k到字符串结束，是否有字符串匹配
    15.      * @param board
    16.      * @param i
    17.      * @param j
    18.      * @param word
    19.      * @param k
    20.      * @return
    21.      */
    22.     private boolean backtrack(char[][] board, int i, int j, String word,int k ) {
    23.         if (i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!=word.charAt(k)){
    24.             return false;
    25.             //不满足条件 就不要再去往上下左右去走了
    26.         }
    27.         if(k==word.length()-1){
    28.             //因为在前面这个判断,我们都会去判断响应的字符是否匹配上，如果都匹配上了k个字符，肯定就是可以的
    29.             return true;
    30.         }
    31.         board[i][j]='\0';//为什么这样做，这样就是相当于做选择，为什么，因为这样换，在下次肯定是匹配不上的
    32.         //这样也为了防止重复去利用了一个格子 走到这一步，也说明第k个的字符跟这个字符是匹配上的
    33.         //做出选择，让这个字符跟字符串中对应的字符去匹配
    34.         boolean res= backtrack(board,i+1,j,word,k+1)||backtrack(board,i,j+1,word,k+1)||
    35.         backtrack(board,i-1,j,word,k+1)||backtrack(board,i,j-1,word,k+1);
    36.         board[i][j]=word.charAt(k);
    37.         return res;
    38.     }
    39. }

    剑指 Offer 13. 机器人的运动范围

     

    1. class Solution {
    2.     boolean visited[][];
    3.     public int movingCount(int m, int n, int k) {
    4.         this.visited = new boolean[m][n];
    5.          return backTrack(0,0,k,m,n);
    6.     }
    7.  
    8.     private int backTrack(int row, int col, int k, int m, int n) {
    9.         if (row<0||row>=m||col<0||col>=n||countNum(row,col)>k||visited[row][col]){
    10.                 return 0;
    11.         }
    12.         //走到这里，说明这是一个还没有统计的格子
    13.         visited[row][col]=true;
    14.         return 1+backTrack(row-1,col,k,m,n)+backTrack(row+1,col,k,m,n)+
    15.                 backTrack(row,col-1,k,m,n)+backTrack(row,col+1,k,m,n);
    16.     }
    17.  
    18.     public int countNum(int m,int n){
    19.         int sum=0;
    20.         while (m>0){
    21.             sum+=m%10;
    22.             m=m/10;
    23.         }
    24.         while (n>0){
    25.             sum+=n%10;
    26.             n=n/10;
    27.         }
    28.         return sum;
    29.     }
    30. }

    剑指 Offer 14- I. 剪绳子

     

    1.  public int cuttingRope(int n) {
    2.         int dp[]=new int[n+1];
    3.         dp[1]=1;
    4.         dp[2]=1;
    5.         for (int i = 3; i <=n; i++) {
    6.             for (int j = 2; j 
    7.                 dp[i]= Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
    8.             }
    9.         }
    10.         return dp[n];
    11.     }

    剑指 Offer 15. 二进制中1的个数

    正常思路

    1. package Offer;
    2.  
    3. public class offer15 {
    4.     public int hammingWeight(int n) {
    5.         int count=0;
    6.         while (n!=0){
    7.             if ((n&1)==1){
    8.                 count++;
    9.             }
    10.             n= n>>>1;
    11.         }
    12.         return count;
    13.     }
    14. }

     n&(n-1)操作

    • n-1相当将n的二进制最后一位的给消除（但是不能保证其他位的变为），n&(n-1)就是将除了将最后一位1变成0，其他不变

     

    剑指 Offer 16. 数值的整数次方 快速幂问题

    背后原理

     二分实现

     

    1. class Solution {
    2.     public double myPow(double x, int n) {
    3.         if (n==0){
    4.             return 1.0;
    5.         }
    6.         if(x==0){
    7.             return 0;
    8.         }
    9.         long n1=n;
    10.         if (n<0){
    11.             x=1/x;
    12.             n1=-n;
    13.         }
    14.        return helper(x, n1);
    15.     }
    16.  
    17.     private double helper(double x, long n1) {
    18.         if (n1==1){
    19.             return x;
    20.         }
    21.         if ((n1&1)==0){
    22.             //为偶数
    23.             return helper(x*x,n1>>>1);
    24.         }else {
    25.             return helper(x,n1-1)*x;
    26.         }
    27.     }
    28. }

    剑指 Offer 17. 打印从1到最大的n位数 

    这道题，应该去考关于大数的处理

    什么是大数

     用回溯来完成所有的全排列

    1. package Offer;
    2.  
    3. import java.util.LinkedList;
    4. import java.util.List;
    5.  
    6. public class Offer17 {
    7.     //用于存储最终的结果
    8.     private List list=new LinkedList<>();
    9.     //用于存储每个符合要求的字符串
    10.     private StringBuilder track=new StringBuilder();
    11.     public void printNumbers(int n) {
    12.         backtrack(n,0);
    13.         System.out.println(list);
    14.     }
    15.  
    16.     private void backtrack(int n, int cur) {
    17.         if (cur==n){
    18.             //说明n位都有对应的数字了
    19.             list.add(track.toString());
    20.             return;
    21.         }
    22.         for (int i = 0; i <=n; i++) {
    23.             //做选择
    24.             track.append(i);
    25.             //进行下一个数字的选择
    26.             backtrack(n,cur+1);
    27.             //回溯
    28.             track.deleteCharAt(track.length()-1);
    29.         }
    30.     }
    31.  
    32.     public static void main(String[] args) {
    33.         Offer17 test=new Offer17();
    34.         test.printNumbers(5);
    35.     }
    36. }

    •  会出现这种高位为0的情况，如何避免呢？我们当track长度为0的时候，如果添加的数字是0，我们就跳过这次插入，这样就可以避免高位为0这种情况，比如我第一次要插入0，发现track为0，我们就插入第二位，发现track还是为0 ，也就会跳过
    1. class Solution {
    2.      //用于存储最终的结果
    3.     private List list=new LinkedList<>();
    4.     //用于存储每个符合要求的字符串
    5.     private StringBuilder track=new StringBuilder();
    6.     int []res;
    7.     int count=0;
    8.     public int[] printNumbers(int n) {
    9.         res=new int[(int)(Math.pow(10,n)-1)];
    10.         backtrack(n,0);
    11.         return res;
    12.     }
    13.  
    14.     private void backtrack(int n, int cur) {
    15.         if (cur==n){
    16.             //说明n位都有对应的数字了
    17.             if (track.length()!=0){
    18.                 list.add(track.toString());
    19.                 res[count]=Integer.parseInt(track.toString());
    20.                 count++;
    21.             }
    22.             return;
    23.         }
    24.         for (int i = 0; i <=9; i++) {
    25.             if (!(i==0&&track.length()==0)){
    26.                 track.append(i);
    27.             }
    28.             //做选择
    29.             //进行下一个数字的选择
    30.             backtrack(n,cur+1);
    31.             //回溯
    32.             if (!(i==0&&track.length()==0)){
    33.                 track.deleteCharAt(track.length()-1);
    34.             }
    35.         }
    36.     }
    37. }

    剑指 Offer 18. 删除链表的节点 

    1. /**
    2.  * Definition for singly-linked list.
    3.  * public class ListNode {
    4.  *     int val;
    5.  *     ListNode next;
    6.  *     ListNode(int x) { val = x; }
    7.  * }
    8.  */
    9. class Solution {
    10.  public ListNode deleteNode(ListNode head, int val) {
    11.         ListNode dummyHead=new ListNode(-1);
    12.         dummyHead.next=head;
    13.         ListNode prev=dummyHead;
    14.         while (prev.next!=null){
    15.             ListNode node=prev.next;
    16.             if (node.val==val){
    17.                 prev.next=node.next;
    18.                 node=node.next=null;
    19.                 break;
    20.             }else {
    21.                 prev=prev.next;
    22.             }
    23.         }
    24.         return dummyHead.next;
    25.     }
    26. }
    •  这个题唯一的难点就是，删除头节点和非头节点的处理方式是一样的，这里我引入了虚拟头节点，就不用担心第一个是我们要删除的头节点，让虚拟头节点作为删除节点的前驱节点（删除节点最重要的就是要找到前驱节点）
  • 相关阅读:
    Linux 系统时间同步 ​使用 NTP 服务时间同步​
    Postman如何做接口测试6：如何使用外部 json 文件数据
    Jackson自定义序列化
    车牌自动识别-matlab
    IAM、EIAM、CIAM、RAM、IDaaS 都是什么？
    【PAT甲级】1127 ZigZagging on a Tree
    编解码持续升级，「硬」实力铸就视频云最优解
    C++ 使用栈求解中缀、后缀表达式的值
    微信小程序| 打造ChatGPT英语四六级背单词小程序
    dubbo入门小案例
  • 原文地址：https://blog.csdn.net/qq_50985215/article/details/126092384