剑指offer刷题（简单等级）

(1)斐波那契数列

(2)数组中重复的数字

描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1

数据范围：0≤n≤10000 0≤n≤10000

进阶：时间复杂度O(n) O(n) ，空间复杂度O(n) O(n)

思路的突破点：数据都在0～n-1的范围内，即若不重复可做到每个位置对应的值是其下标

从0下标开始找index = 0

        1、若下标与当前存储的值不同时，将该值换到对应的位置。

                若此位置已有匹配的值则有重复数，返回；否则交换

        2、若下标与当前存储的值相同，则index++

(3)替换空格

(4)从尾到头打印链表

有要求顺序的输出往往可以考虑与栈队列结合

注意对象为null是要返回的是null，或某个无内容的对象。

(5)用两个栈实现队列

(6)旋转数组的最小数字

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤100001≤n≤10000，数组中任意元素的值: 0≤val≤100000≤val≤10000

要求：空间复杂度：O(1)O(1) ，时间复杂度：O(logn)O(logn)

充分理解这几个词的区别：

若符合a(n+1)>an，则数列的递增的，也是升序的
若符合a(n+1)<an，则数列的递减的，也是降序的
若符合a(n+1)≤an，则数列是非升序的
若符合a(n+1)≥an，则数列是非降序的

故数组AB的旋转数组BA有如下特点：B是非降序的，A是非降序的。最小值为A的第一个数字。

利用二分，确定min在mid的左还是右

只与right或left比较即可确认min的大概位置

注意处理两种情况的处理：1、mid值小于right或left，此时min可能在mid左边或mid处，应right=mid

2、mid值等于right值，right减一

(7)二进制中1的个数

这里主要牵扯两种简便方法

1、n&（1<<i）eg用n与001与得到第一位是否为1

                             用n与010与得到第二位是否为1

                            ......

                             用n与1000 0000 0000 0000 ... 0000得到第32位是否为1

2 n&=（n-1）每次将n的最低位1反转成0与n进行与。记一次1

                        若n变为了0说明无0，可以结束。

(8)打印从1到最大的n位数​​​​​​​

(9)删除链表的节点

(10)链表中倒数最后k个结点

(11)反转链表

注意链表为空的情况，直接返回链表。

(12)合并两个排序的链表

(13)二叉树的镜像

这里本质是交换每一个节点的左右子树

1、若使用递归，注意不要提前将被更改的节点进行存储

2、若使用栈，则只需将左右节点依次进栈，弹栈时交换其左右节点。

(14)对称的二叉树​​​​​​​(思路)

注意比较哪些位置，如何比较。

1.递归实现：两指针从同一起点开始。

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        return isSym(pRoot,pRoot);
    }
    boolean isSym(TreeNode root1,TreeNode root2){
        if(root1==null&&root2==null)
            return true;
        if(root1==null||root2==null||root1.val!=root2.val)
            return false;
        return isSym(root1.left,root2.right)&&isSym(root1.right,root2.left);
    }
    
}

2、思想：使用中序遍历，若为对称左中右与右中左结果一样。

import java.util.*;
public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot==null)
            return true;
        Queue<TreeNode> queue1 = new LinkedList<TreeNode>();
        Queue<TreeNode> queue2 = new LinkedList<TreeNode>();
        queue1.add(pRoot);
        queue2.add(pRoot);
        while(!queue1.isEmpty()&&!queue2.isEmpty()){
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            //注意这里两个条件的处理
            if(node1==null&&node2==null)
                continue;
            if(node1==null||node2==null||node1.val!=node2.val)
                return false;
         
            queue1.add(node1.left);
            queue1.add(node1.right);

            queue2.add(node2.right);
            queue2.add(node2.left);

        }
        return true;
    }
}

（15）顺时针打印矩阵 

 注意上和下，左和右有可能重复记录。故要对判断是否已经记录过。

 public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> array = new ArrayList<Integer>();
        int r = matrix.length;
        int c = matrix[0].length;
        int ccount = (r<c)?r:c;
        ccount = ccount/2+ccount%2;
        for(int i=0;i<ccount;i++){
            int r1 = i,r2 = r - i -1;
            int c1 = c-i-1,c2 = i;
            for(int l1 = i;l1 < c-i;l1++)
                array.add(matrix[r1][l1]);
            for(int l2 = i+1;l2<r-i-1;l2++)
                array.add(matrix[l2][c1]);
            if(r2!=r1)
                for(int l3 = c-i-1;l3 >= i;l3--)
                    array.add(matrix[r2][l3]);
            if(c2!=c1)
                for(int l4 = r-i-2;l4>i;l4--)
                    array.add(matrix[l4][c2]);
            
        }
        return array;
    
    }

（16）包含min函数的栈 

思想：又一个另外的栈来存储当前已存入栈中的最小值。

(17)从上往下打印二叉树

递归方式未完成

(18)数组中出现次数超过一半的数字

(19)连续子数组的最大和

自己的思路：可能存在最大值为负的情况。

                        初始化：sum = 0 ，max = Integer.MIN_VALUE

每次进行sum+操作后：1、比较是否大于max，是更新max。

                                        2、sum是否小于0，小于0则将sum重新置0。因为此时sum为负，应重新开始，不然负加之后的值必使其变小。                                        

（20）数字序列中某一位的数字

 public int findNthDigit (int n) {
        if(n==0)
            return 0;
        int digit = 1;
        //注意：计算过程中会出现超过int现象故此两个数为long
        long start = 1;
        long sum = 9;
        /*
        计算当前位数范围一共有多少位
        大于则减去当前位数的总位数个数，继续寻找
        小于则先算出，数字
        将数字转化为字符串
        再计算是其中的哪一位
        */
        while(n>sum){
            n -= sum;
            digit++;
            start*=10;
            sum = digit*(start*10-start);
        }
        int num = (int)start+(n/digit)-1;
        String numStr = Integer.toString(num);
        int index = (n+digit-1)%digit;
        return numStr.charAt(index)-'0';//注意最终目标为整数
        
    }

(21)第一个只出现一次的字符

问题：如何在字典中找到第一个出现的不重复字符。只要顺着输入字符串遍历一遍遇到的第一个出现一次的即为首次非重复字符。

(22)两个链表的第一个公共结点

有一个简便方法：

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if( pHead1==null || pHead2 == null)
            return null;
        ListNode p1=pHead1;
        ListNode p2=pHead2;
        while(p1!=p2){
            p1 = (p1==null)?pHead2:p1.next;
            p2 = (p2==null)?pHead1:p2.next;
        }
        return p1;
    }

（23） 数字在升序数组中出现的次数

这里有两点需要注意

特殊情况[3]4

[3,3,3,3]4

 public int GetNumberOfK(int [] array , int k) {
        
        int start = 0;
        int end = array.length-1;
        while(start<end&&(array[start]!=k||array[end]!=k)){
            int mid = (start+end)/2;
            if(array[mid]<k){
                //一种mid复制时注意mid值已排除要用mid+1或mid-1不然可能陷入无限循环
                start = mid+1;
            }
            else if(array[mid]>k)
                end=mid-1;
            else{
                if(array[start]!=k)
                    start++;
                if(array[end]!=k)
                    end--;
            }
        }
        //可能存在[2]4 start=0 end=0 结果应为0的情况
        if(start<=end&&array[start]==k&&array[end]==k)
            return end-start+1;
        else
            return 0;
    }

(24) 二叉树的深度

使用递归，我所完成的代码没有如下的简便：

public int TreeDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
    }

使用队列辅助完成

 public int TreeDepth(TreeNode root) {
        if(root==null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int depth = 0;
        while(!queue.isEmpty()){
            //可以用size()来获取当前队列中有多少个元素
            int levesum = queue.size();
            while(levesum>0){
                TreeNode node = queue.poll();
                if(node.left!=null)
                    queue.add(node.left);
                if(node.right!=null)
                    queue.add(node.right);
                levesum--;
            }
            depth++;
        }
        return depth;
    }

（25）扑克牌顺子 

考虑问题时忽略了有相等值的情况。如有相等值直接失败。

简便思虑，类似于数组中重复的数字。

有相等值直接false，排除掉0记录下最大值和最小值。如果两者差小于5说明是顺子（即不连贯的地方一定会被0填充，因为其他数均在这两个数之间，若不是这之间的，也只能为0）。

 public boolean IsContinuous(int [] numbers) {
        Set<Integer> set = new HashSet();
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<numbers.length;i++){
            if(numbers[i] == 0)
                continue;
            else{
                if(set.contains(numbers[i]))
                    return false;
                else{
                    set.add(numbers[i]);
                    if(numbers[i]>max)
                        max=numbers[i];
                    if(numbers[i]<min)
                        min=numbers[i];
                }
            }
        }
        return max-min<5;
    }

(26)买卖股票的最好时机(一)

换一种思路，不要去找改点之后的最大值，不然每次都要重新计算。

转而寻找，记录改点之前的最小值，此点减去之前的最小价格，即为该处卖出的最大收入（最小值，从左到右便利的过程中就可以及时更新，耗时最短）

public int maxProfit (int[] prices) {
        // write code here
        if(prices.length==0)
            return 0;
        int min = prices[0];
        int max = 0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]<min)
                min = prices[i];
            if(prices[i]-min>max)
                max = prices[i]-min;
        }
        return max;
    }

（27）不用加减乘除做加法​​​​​​​

一个位运算的小技巧：num1异或num2（num1^num2）为进行进位前每一位上的数字。

                                       num1与num2（num1&num2）为每一位是否应该向上进位，故向左移一位后（<<）则或得每一位上的进位

1、当进位不为0时要一直循环计算

2、当进位为0时则停止计算。

 public int Add(int num1,int num2) {
        int add = num2;
        while(add!=0){
            int sum = num1^add;
            add = (num1&add)<<1;
            num1 = sum;
        }
        return num1;
        
    }

(28)构建乘积数组

一种简便思路

用两个循环完成

一次算下三角，从上往下，由左至右。每次比上一次多一个数

一次算上三角，从下往上，由右至左。每次比上一次多一个数

public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        B[0] = 1;
        for(int i = 1;i<A.length;i++){
            B[i] = B[i-1]*A[i-1];
        }
        int sum = 1;
        for(int i=A.length-2;i>=0;i--){
            sum*=A[i+1];
            B[i]*=sum;
        }
        return B;
    }

(29) 二叉搜索树的最近公共祖先

思路：

1、非递归：

public int lowestCommonAncestor (TreeNode root, int p, int q) {
       if(root == null)
            return -1;
        ArrayList<Integer> route1 = new ArrayList();
        ArrayList<Integer> route2 = new ArrayList();
        TreeNode t1 = root;
        TreeNode t2 = root;
        while(t1!=null&&t1.val!=p){
            route1.add(t1.val);
            if(t1.val<p)
                t1 = t1.right;
            else
                t1 = t1.left;
        }
        if(t1==null)
            return -1;
        else
            route1.add(t1.val);
        while(t2!=null&&t2.val!=q){
            route2.add(t2.val);
            if(t2.val<q)
                t2 = t2.right;
            else
                t2 = t2.left;
        }
        if(t2==null)
            return -1;
        else
            route2.add(t2.val);
        int conroot = -1;
        for(int i = 0;i<route1.size()&&i<route2.size();i++){
            int x = route1.get(i);
            int y = route2.get(i);
            if(x == y)
            conroot = route1.get(i);
        }
        return conroot;
    }

 2、递归版本

若p，q在当前节点的两侧（包含在此节点上），则此节点为最近公共跟。

若p，q在同一侧，则向这一侧递归

public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if(root==null)
           return -1;
        if(root.val>=p&&root.val<=q||root.val<=p&&root.val>=q)
            return root.val;
        if(root.val<p&&root.val<q)
            return lowestCommonAncestor(root.right,p,q);
        return lowestCommonAncestor(root.left,p,q);
    }

(30)跳台阶 

(31)跳台阶扩展问题

化简方式的思路：

(n)=f(n−1)+f(n−2)+...+f(n−(n−1))+f(n−n)=f(0)+f(1)+f(2)+...+f(n−1)，因为f(n−1)=f(n−2)+f(n−3)+...+f((n−1)−(n−2))+f((n−1)−(n−1))f(n−1)=f(n−2)+f(n−3)+...+f((n−1)−(n−2))+f((n−1)−(n−1))，经整理得f(n)=f(n−1)+f(n−1)=2∗f(n−1)f(n)=f(n−1)+f(n−1)=2∗f(n−1)

(32) 翻转单词序列

分割+倒序

倒序重新组成字符串时别忘记添加空格。

(34)判断是不是平衡二叉树

1.一个函数完成

思路初期易错点：左右字数都为空的节点为1层，而不是即位0

  public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null)
            return true;
        if(root.left==null&&root.right==null)
        {
            //此处应算作一层，什么都没有的空节点才是0
            root.val = 1;
            return true;
        }
        boolean left=true,right=true;
        int dleft=0,dright=0;
        if(root.left!=null){
            left = IsBalanced_Solution(root.left);
            dleft = root.left.val;
        }
        else
            dleft = 0;
            
        if(root.right!=null){
            right = IsBalanced_Solution(root.right);
            dright = root.right.val;
        }
        else
            dright = 0;
        root.val = ((dright<dleft)?dleft:dright)+1;
        if(left&&right){
            if(Math.abs(dleft-dright)<=1)
                return true;
            return false;
        }
        return false;
    }

2、可利用两个函数完成

用-1代表此节点不平衡。

故若返回为-1，直接传递-1表明此分支不平衡

public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null)
            return true;
        return DeepPath(root)!= -1;
       
    }
    public int DeepPath(TreeNode root){
        if(root == null)
            return 0;
        int left = DeepPath(root.left);
        if(left == -1)
            return -1;
        int right = DeepPath(root.right);
        if(right == -1)
            return -1; 
        return Math.abs(left-right) > 1 ? -1:1+Math.max(left,right);
    }

(35)调整数组顺序使奇数位于偶数前面(二)​​​​​​​

(36)二叉树中和为某一值的路径(一)

递归实现的更简便思路：每次用sum的剩余值与叶子结点中值比较

public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null)
            return false;
        if(root.left==null&&root.right==null&&sum==root.val)
            return true;
        sum -= root.val;
        return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
    }

非递归：每个节点的值更改为从根节点走到此节点的长度（只需要先序遍历就可以）

     if(root==null)
            return false;
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.pop();
            if(node.left==null&&node.right==null&&node.val == sum)
                return true;
            if(node.left!=null)
            {
                node.left.val += node.val;
                stack.push(node.left);
            }
            if(node.right!=null){
                node.right.val += node.val;
                stack.push(node.right);
            }
        }
        return false;
    }