剑指offer

03 数组中重复的数字

public int findRepeatNumber(int[] nums){
    //排序后的数组，重复元素必然相邻
    Arrays.sort(nums);
    //结果集
    int res=0;
    for(int i=0;i<nums.length-1;i  ){
        //找到重复元素
        if(nums[i]==nums[i 1]){
            res=nums[i 1];
            break;
        }
    }
    return res;
}

一个萝卜一个坑

如果没有重复数字，那么正常排序后，数字i应该在下标为i的位置，所以思路是重头扫描数组，遇到下标为i的数字如果不是i的话，（假设为m),那么我们就拿与下标m的数字交换。在交换过程中，如果有重复的数字发生，那么终止返回ture

 public int findRepeatNumber(int[] nums){
        int temp;
        for(int i=0;i<nums.length;i  ){
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]])
                    return nums[i];
                temp=nums[i];
                nums[i]=nums[temp];
                nums[temp]=temp;
            }
        }
        return -1;
    }

04 二维数组中的查找

右上角

public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix==null||matrix.length==0||(matrix.length==1&&matrix[0].length==0)) return false;
        int xl = matrix.length;
        int yl = matrix[0].length;
        int i=0,j=yl-1;
        while(i<xl&&j>=0){
            if(matrix[i][j]==target){
                 return true;
            }else if(matrix[i][j]<target){
                i  ;
            }else{
                j--;
            }
        }
        return false;
    }

05 替换空格

public String replaceSpace(String s) {
    StringBuilder res = new StringBuilder();
    for(int i=0;i<s.length();i  ){
        if(s.charAt(i)==' '){
            res.append(" ");
        }else{
            res.append(s.charAt(i));
        }
    }
    return res.toString();
}

06 从尾到头打印链表

public int[] reversePrint(ListNode head) {
    LinkedList<Integer> stack = new LinkedList<Integer>();
    while(head!=null){
        stack.addLast(head.val);
        head=head.next;
    }
    
    int[] res = new int[stack.size()];
    for(int i=0;i<res.length;i  ){
        res[i]=stack.removeLast();
    }
    return res;
}

07 重建二叉树

    Map<Integer,Integer> hash = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int np=preorder.length,n=inorder.length;
        for(int i=0;i<n;i  ){
            hash.put(inorder[i],i);
        }
        return dfs(preorder,inorder,0,np-1,0,n-1);
    }
    public TreeNode dfs(int[] pre,int[] in,int pl,int pr,int il,int ir){
        if(pl>pr){return null;}
        TreeNode root = new TreeNode(pre[pl]);
        int k = hash.get(root.val)-il;
        //left    前序中的下标区间，中序中的下标区间
        root.left=dfs(pre,in,pl 1,pl k,il,il k-1);
        //right
        root.right=dfs(pre,in,pl k 1,pr,il k 1,ir);
        return root;
    }

09 用两个栈实现队列

class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    public CQueue() {
        stack1=new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    
    //添加元素
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    //删除头元素
    public int deleteHead() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty())
                stack2.push(stack1.pop());
        }
        if(stack2.isEmpty()){
            return -1;
        }else{
            return stack2.pop();
        }
    }
}

10-1 斐波那契

public int fib(int n){
    int a=0,b=1,sum;
    for(int i=0;i<n;i  ){
        sum=(a b)00000007;
        a=b;
        b=sum;
    }
    return a;
}

10-2 青蛙跳台阶

class Solution {
    public int numWays(int n) {
        int a=1,b=1,sum;
        for(int i=0;i<n;i  ){
            sum=(a b)00000007;
            a=b;
            b=sum;
        }
        return a;
    }
}

11 旋转数组的最小数字

class Solution {
    public int minArray(int[] numbers) {
        int l=0,r=numbers.length-1;
        while(l<r){
            int m=(l r)/2;
            if(numbers[m]>numbers[r])   l=m 1;
            else if(numbers[m]<numbers[r]) r=m;
            else{
                int x=l;
                for(int k=l 1;k<r;k  ){
                    if(numbers[k]<numbers[x])
                        x=k;
                }
                return numbers[x];
            }
        }
        return numbers[l];
    }
}

12 矩阵中的路径

class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i=0;i<board.length;i  ){
            for(int j=0;j<board[0].length;j  ){
                if(dfs(board,words,i,j,0))
                    return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,char[] words,int i,int j,int k){
        //超出范围或者不相等
        if(i<0||i>board.length-1||j<0||j>board[0].length-1||board[i][j]!=words[k])  return false;
        //base case k长度==word长度
        if(k==words.length-1) return true;
        //做选择
        board[i][j]='\0';
        //递归
        boolean res=dfs(board,words,i 1,j,k 1)||dfs(board,words,i-1,j,k 1)
            ||dfs(board,words,i,j 1,k 1)||dfs(board,words,i,j-1,k 1);
        //撤销选择
        board[i][j]=words[k];
        return res;
    }
}

13 机器人的运动范围

class Solution {
    int count;
    public int movingCount(int m, int n, int k) {
        int[][] visited=new int[m][n];
        count=0;
        dfs(m,n,k,visited,0,0);
        return count;
    }
    public void dfs(int m,int n,int k,int[][] visited,int i,int j){
        //1.索引越界2.大于数位之和3.走过
        if(i>m-1||i<0||j>n-1||j<0||visited[i][j]==1||(k<sums(i) sums(j))) return;
        //当前已经走过
        visited[i][j]=1;
        count  ;
        //递归
        int[] dx=new int[]{-1,0,1,0};int[] dy=new int[]{0,1,0,-1};
        for(int s=0;s<4;s  ){
            dfs(m,n,k,visited,i dx[s],j dy[s]);
        }
        //不需要撤销选择
    }
    //数位之和
    int sums(int x){
        int s=0;
        while(x!=0){
            s =x;
            x=x/10;
        }
        return s;
    }
}

 

来源：https://www./content-4-881301.html