剑指offer-1

剑指Offer day1

3、数组中重复的数字 https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

找出数组中重复的数字，题目中给定了一个长度为n的数组，并且所有数字都在0-n-1的范围内。

如果我们利用一个数组或者集合去记录每个数出现的频次，这样的空间复杂度是O(n)的，我们可以选择空间复杂度为O(1)的原地解法。

我们是一组刚好没有重复的数字,0~n-1，那么每个数都应该放在自己对应的位置上，比如0应该放在第一个位置，1应该放在第1个位置…..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findRepeatNumber(int[] nums) {
      //边界处理
        for(int num:nums){
            if(num<0||num>nums.length-1) return -1;
        }
        
            for(int i=0;i<nums.length;i++){
                while(i!=nums[i]){
                  //出现重复元素
                    if(nums[i]==nums[nums[i]]) return nums[i];
                    swap(nums,i,nums[i]);
                }
                
            }
         return -1;
    }
    private void swap(int []nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

4、二维数组中的查找 https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

题目的意思很简单，意思我们从一个n*m的二维数组中，寻找一个整数。该题目的性质就是从左到右都是递增，并且从上到下也都是递增的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
   public boolean findNumberIn2DArray(int[][] matrix, int target) { 
           if(matrix.length==0||matrix[0].length==0) return false;
         int m=matrix.length;
        int n=matrix[0].length;
        int i=0,j=n-1;
         
        while(i<=m-1&&j>=0){
          //从右上角开始寻找
             int x=matrix[i][j];
             if(target==x) return true;
          //如果当前值小于目标值，我们应该往下继续寻找
            else if(i<=m-1&&x<target) i++;
          //如果当前值大于目标值，我们应该往左继续寻找
            else if(j>=0&&x>target) j--;
        }
        return false;
    }
}

5、替换空格 https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

直接利用语法

1
2
3
4
5
6
7
8
9
10
class Solution{
   public String replaceSpace(String s) {
       StringBuilder sb=new StringBuilder();
     for(int i=0;i<s.length();i++){
        if(s.charAt(i)==' ') sb.append("%20");
       else sb.append(s.charAt(i));
     }
     return sb.toString();
    }
}

6、从头到尾打印链表 https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

实质上就是一个对于链表的遍历。我们可以采取对链表反转，然后直接遍历一遍得到结果的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] reversePrint(ListNode head) {
       ListNode node=  reverse(head);
        List<Integer>list=new ArrayList<>();
        ListNode cur=node;
        while(cur!=null){
            list.add(cur.val);
            cur=cur.next;
        }
        int res[]=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }
  //递归的对链表进行反转
    private ListNode reverse(ListNode head){
          if(head==null||head.next==null) return head;
         ListNode newNode=reverse(head.next);
        head.next.next=head;
        head.next=null;
          return newNode;
    }
}

同样的，一旦设计到反转，我们可以利用栈这个特殊的数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] reversePrint(ListNode head) {
           Stack<Integer>stack=new Stack<>();
         if(head==null) return new int[0];
          List<Integer>list=new ArrayList<>();
         ListNode cur=head;
        while(cur!=null){
            stack.push(cur.val);
            cur=cur.next;
        }
        while(!stack.isEmpty()){
            list.add(stack.pop());
        }
        int res[]=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }
}

7、重建二叉树

给定一个二叉树的前序遍历和中序遍历，让我们重建二叉树，这是一个经典的问题。

根据前序遍历的性质，前序遍历数组中第一个数即为根节点。 只要我们在中序遍历中找到这个数，那么就可以分为左右两部分，其中左边部分为该树对应的左子树，右边部分对应为该树的右子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
          return dfs(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        
    }
    private TreeNode dfs(int[]preorder,int[]inorder,int l,int r,int left,int right){
         if(l>=preorder.length||l>r||left>right||left>=inorder.length) return null;
        //根节点
        int value=preorder[l];
        TreeNode root=new TreeNode(value);
        //找到中序遍历中根节点的位置
        int k=left;
        while(inorder[k]!=value) k++;
         k-=left;
        root.left=dfs(preorder,inorder,l+1,l+k,left,left+k-1);
        root.right=dfs(preorder,inorder,l+k+1,r,left+k+1,right);
        return root;
        
    }
}

9、用两个栈实现队列

本题考察了栈和队列之间的关系，栈是后进先出的数据结构，而队列是先进先出的数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class CQueue {
        Stack<Integer>stack1;
        Stack<Integer>stack2;
    public CQueue() {
       stack1=new Stack<>();
       stack2=new Stack<>();
    }
    
    public void appendTail(int value) {
           stack1.push(value);       
    }
    
    public int deleteHead() {
      //将栈1的数据都放在栈2中
        if(stack2.isEmpty()){
             if(stack1.isEmpty()) return -1;
            while(!stack1.isEmpty()) stack2.push(stack1.pop());
    }
         return stack2.pop();
       
}
    
}

10-1、 斐波那契数列 https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

f(n)=f(n-1)+f(n-2) 如果我们采用自顶向下的递归方法。会出现很多重复的计算，即使我们利用一个哈希表存储结果，其时间复杂度也是不乐观的。此时我们采用自底向上的方法去实现。也即f(3)=f(1)+f(2)，依次往后递推。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution{
  public int fib(int n){
    if(n<=1) return n;
         int pre=0;
        int cur=1;
        for(int i=2;i<=n;i++){
             int sum=(pre+cur)%1000000007;
             pre=cur;
            cur=sum;
        }
        return cur;
  }
}

10-2、 青蛙跳台阶 https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

与上一题斐波那契基本上一样

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int numWays(int n) {
        if(n==0) return 1;
        int pre=1;
        int cur=1;
        for(int i=2;i<=n;i++){
            int sum=(pre+cur)%1000000007;
             pre=cur;
            cur=sum;
        }
        return cur;
    }
}

11、旋转数组的最小数字 https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

由于数组是两段有序的，我们可以直接利用二分法进行查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minArray(int[] nums) {
       if(nums.length==0) return -1;
        int n=nums.length-1;
        //对数组进行去重处理
        while(n>0&&nums[n]==nums[0]) n--;
        //如果直接是有序的，直接返回第一个元素
        if(nums[n]>=nums[0]) return nums[0];
        int l=0,r=n;
        while(l<r){
            int mid=(l+r)>>1;
            //即此时左边发生乱序了
            if(nums[mid]<nums[0]) r=mid;
            else l=mid+1;
        }
        return  nums[l];
    }
}

12、矩阵中的路径 https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

标准的dfs+回溯模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    private int m,n;
    private boolean[][]vis;
    public boolean exist(char[][] board, String word) {
          m=board.length;
         n=board[0].length;
         char c[]=word.toCharArray();
        vis=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(board[i][j]==c[0]){
                    if(dfs(board,i,j,0,c)) return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][]board,int i,int j,int index,char[]c){
        if(index==c.length) return true;
      
       if(i<0||i>=m||j<0||j>=n||board[i][j]!=c[index]||vis[i][j]==true) return false;
        vis[i][j]=true;
        boolean flag=dfs(board,i+1,j,index+1,c)||
                     dfs(board,i-1,j,index+1,c)||
                     dfs(board,i,j+1,index+1,c)||
                     dfs(board,i,j-1,index+1,c);
        vis[i][j]=false;
        return flag;
        
    }
}
赏

谢谢你请我喝奶茶

微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家