剑指offer（java版）——基础知识篇

1.二维数组中的查找

题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array==null||array.length==0||array[0].length==0){
            return false;
        }
        int i=0;
        int j=array[0].length-1;
        while(i<array.length&&j>=0){
            if(target==array[i][j]){
                return true;
            }else if(target<array[i][j]){
                j--;
            }else{
                i++;
            }
        }
        return false;
    }
}

2.替换空格

题目描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路1：从头到尾扫描字符串，遇到空格，将后面的字符串后移2位，然后做替换
缺点：后面的字符串将被移动多次（多次赋值）。如果有O(n)个空格，字符串将移动O(n)次，每次需要移动O(n)个字符，所以时间复杂度是O（n^2）
思路2：从后往前开始字符串的替换和移动。首先遍历一次字符串，找到所有空格的数目。替换后字符串长度为 原来的字符串长度+空格个数*2。我们新建一个数组，从尾部开始向前遍历原数组，如果是空格，则新数组的位置替换成“%20”，新数组的下标逐个递减3格；如果不是空格，直接复制原数组的内容到新数组对应位置，下标都减1格。

注意：
1.空字符串
2.null输入
3.没有空格的情况
4.空格在头，中，尾的情况

知识点：
1.StringBuffer线程安全。内部char[]数组，方法前加synchronized关键字
2.StringBuffer中的capacity和length是不同的，capacity是容量，而length是实际字符串长度。当我们new StringBuffer(16)的时候，我们得到的是一个capacity=16，length=0的StringBuffer。
3.返回值是String，StringBuffer需要toString转化
4.从char[]到String，不能通过toString方式（没有重写这个方法，实际使用的是Object的toString，即返回了地址），而通过new String(char[] array)方式
5.StringBuffer的get和set:str.charAt(i)、str.setCharAt(int index,char newChar)
6.String的get和set:str.charAt(i)、String不可变，可以将String转化成StringBuilder/StringBuffer

public class Solution {
        public static String replaceSpace(StringBuffer str) {
        if(str==null||str.length()<=0){
            return str.toString();
        }
        int count=0;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' '){
                count++;
            }
        }
        char[] newStr = new char[str.length()+count*2];
        int i=str.length()-1;
        int j=newStr.length-1;
        while(i>=0){
            if(str.charAt(i)==' '){
                newStr[j--]='0';
                newStr[j--]='2';
                newStr[j--]='%';
            }else{
                newStr[j--]=str.charAt(i);
            }
            i--;
        }
        return new String(newStr);
    }
}

3.从尾到头打印链表

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
思路一：用栈。先进后出。
要点：
1.注意判断null值
2.stack的pop和peek方法可能会抛出EmptyStackException()，所以需要先调用empty()判断是否为空，然后再进行操作

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(listNode==null){
            return result;
        }
        Stack<Integer> stack = new Stack<Integer>();
        ListNode currentNode = listNode;
        while(currentNode!=null){
            stack.push(currentNode.val);
            currentNode = currentNode.next;
        }
        
        while(!stack.empty()){
            result.add(stack.pop());
        }
        return result;
    }
}

思路二：用递归的方式。递归的终止条件是下一个节点为空指针。
需要注意，如果是递归，需要把返回结果的list放在递归函数外，以免每次递归时被归0

public class Solution {
    ArrayList<Integer> result = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode==null){
            return result;
        }
        printListFromTailToHead(listNode.next);
        result.add(listNode.val);
        return result;
    }
}

4.重建二叉树

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：
前序遍历的首个节点是根节点，接下来是所有左子树节点，最后是所有右子树节点。利用中序遍历得到左子树节点个数和右子树节点个数；再对左右子树分别重复上述步骤，进行迭代。

1.前序遍历和层次遍历是不同的。前序遍历是根左右，深度优先，会遍历完左子树再遍历右子树；层次遍历是广度优先。同层从左到右遍历。
2.前序遍历的序列，首个节点是根节点。再之后是全部的左子树节点；再然后是全部的右子树节点。所以给出前序遍历序列之后，我们需要找到左子树截止的位置；
3.这里可以借助中序遍历的特点，根节点左边的是全部的左子树序列，根节点右边的是全部的右子树序列。
4.如果是后序遍历，则按照左右根的顺序，最后一个节点是根节点，根节点前面是右子树的全部节点，再往前是左子树的全部节点。也需要找到一个左右子树的分界点。

如果是前序+中序/后序+中序，可以唯一确定一棵二叉树。
如果是前序+后序，无法唯一确定一棵二叉树。
相关问题：
1.二叉树遍历（已知前序和后序遍历，求中序遍历的可能的序列数）
https://blog.csdn.net/qq_37437983/article/details/79613947
2.已知前序和中序，求后序遍历
递归。后序遍历 右子节点紧挨根节点（如果有的话）；左子节点位置在根节点前，右子树节点前的位置。
如果，i是后序遍历数组每次迭代的根节点位置，j是右子树长度；则i-j-1是左子树根节点的位置，i-1是右子树根节点的位置。
https://blog.csdn.net/qq_29375837/article/details/81160362

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode node=construct(pre,in,0,0,in.length-1);
        return node;
    }
    public TreeNode construct(int [] pre,int [] in,int preStart,int inStart,int inEnd){
        TreeNode node=null;
        if(pre==null||in==null||preStart<0||preStart>pre.length||inStart<0||
inEnd>in.length-1||inStart>inEnd){
            return null;
        }
        for(int i=inStart;i<=inEnd;i++){
            if(in[i]==pre[preStart]){
                node = new TreeNode(pre[preStart]);
                node.left = construct(pre,in,preStart+1,inStart,i-1);
                node.right = construct(pre,in,preStart+(i-inStart)+1,i+1,inEnd);
                break;
            }
        }
        return node;
    }
}

5.用两个栈实现一个队列

题目描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
思路：push不变
pop时先判断stack2是否为空，不为空直接pop stack2；为空则把stack1的元素逐一出栈再入栈stack2,最后pop stack2
遵循先进先出

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {
        stack1.push(node);
    }
    public int pop() {
        if(stack2.empty()){
            while(!stack1.empty()){
                int node = stack1.pop();
                stack2.push(node);
            }
        }
        return stack2.pop();
    }
}

附加：如果是用两个队列实现一个栈呢
思路1：queue1做进出队列，queue2做中转队列。push直接push到queue1，pop的时候，先把queue1的全部元素pop到queue2,然后queue2.pop，再把queue2中的所有元素pop回queue1（效率不高）
思路2： queue1和queue2都做进出队列。
push的时候，选择非空的队列进行push，如果都空，选择queue1
push。
pop的时候，把非空队列的元素全部pop到空队列，然后pop。

6.旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
关键点:
1.首先，“若干个元素搬到数组的末尾”中的若干个，可以为0个；即{1,2,3,4,5}也是{1,2,3,4,5}的一个旋转。
2.可以有相同元素。
10111是01111的一个旋转
11101也是01111的一个旋转
思路：
思路1.遍历得最小：O（n）复杂度
思路2.优化一点。发现后面的元素小于前面元素，则break。O(n)复杂度
思路3：利用二分法。O(logn)复杂度
利用二分法需要考虑缩小的条件。
考虑对于一个非递减数组有下面的情况：
（1）旋转0个元素。即旋转后的数组也非递减。返回数组第一个元素即可。这时只要判断出第一个元素小于最后一个元素，必定是这种情况
（2）如果旋转了，则必定是两个非递减数组的拼接。我们用low在第一个非递减数组中，high在第二个非递减数组中，不断缩小边界。mid是low和high的中间位置。
最小元素位于两个非递减数组的分界处。
如果low指向的值小于等于mid指向的值，说明low和mid都位于第一个非递减数组，low可以后移至mid的位置，依旧还是位于第一个非递减数组。
如果high指向的值大于等于mid指向的值，说明mid和high都位于第二个非递减数组，high可以前移至mid的位置，依旧还是位于第二个非递减数组。
最终，low将指向第一个非递减数组的最后一个元素，high将指向第二个非递减数组的第一个元素（即分界处）。这时，low和high将相邻，这就是循环结束的条件。high指向的位置就是最小元素的位置。
（3）在（2）中还包含着一个特殊情况。比如10111。它的low,high,mid指向的值相同，但是显然，low不能缩小到mid的边界。这说明，当low,high,mid指向值相同的时候，我们无法判断该如何移动指针。这个时候，应该改用遍历的方式。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array==null||array.length==0)
            return 0;
        int low = 0;
        int high = array.length-1;
        int mid = low;
        while(array[low]>=array[high]){
            if(high-low==1){
                mid = high;
                break;
            }
            mid = (low+high)/2;
            if(array[low]==array[mid]&&array[mid]==array[high]){
                return inOrder(array,low,high);
            }else if(array[low]<=array[mid]){
                low = mid;
            }else if(array[high]>=array[mid]){
                high = mid;
            }
        }
        return array[mid];
    }
    public int inOrder(int[] array,int low,int high){
        for(int i=low;i<high;i++){
            if(array[i]>array[i+1]){
                return array[i+1];
            }
        }
        return array[high];
    }
}

7.斐波那契数列

用循环，不要用递归
注意取值，是否超过int范围（一般10位）
39是63245986，没超。
保险起见，可以使用long

public class Solution {
    public int Fibonacci(int n) {
        if(n==0)return 0;
        if(n==1)return 1;
        int[] fib = {0,1};
        int result =0;
        for(int i=2;i<=n;i++){
            result = fib[0]+fib[1];
            fib[0]=fib[1];
            fib[1]=result;
        }
        return result;
    }
}

变种1:跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级，求该青蛙跳上一个n级台阶总共有多少种跳法(先后次序不同算不同的结果)
解法：如果只有一级台阶，有1种跳法；如果有2级，有2种跳法。（初始）
如果有n级台阶（n>2），那么如果第一步跳1，有f(n-1)种跳法；如果第一步跳2，有f(n-2)种跳法。所以，f(n)=f(n-1)+f(n-2)
如果先后次序不同算相同的结果的话：n/2 +1种结果
变种2：变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路1：
如果只有一级台阶，有1种跳法；如果有2级，有2种跳法。（初始）
如果有n级台阶，那么第一步可以跳1，2，3，……，n。所以剩下的分别有f(n-1),f(n-2),f(n-3)……，f(1),1种跳法。
用一个长度为n的数组存储之前计算出来的值。
f(n)=f(n-1)+f(n-2)+……+f(1)+1

public class Solution {
    public int JumpFloorII(int target) {
        if(target==0)return 0;
        if(target==1)return 1;
        if(target==2)return 2;
        int[] pre = new int[target];
        pre[0]=1;
        pre[1]=2;
        int result=pre[0]+pre[1];
        for(int i=2;i<target;i++){
            pre[i]=result+1;
            result+=pre[i];
        }
        return pre[target-1];
    }
}

然而，这种方式仍然不是最简单的
由于
f(n)=f(n-1)+f(n-2)+……+f(1)+1
f(n-1)=f(n-2)+……+f(1)+1
所以f(n) = 2f(n-1)=22f(n-2)=22……f(2) = 2(n-2)*f(2)=2(n-1)
可以根据这个递推式去做。
pow(2,n-1)或者1<<n-1

变种3：矩形覆盖
题目描述
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
可以转化成变种1的思考方式

public class Solution {
    public int RectCover(int target) {
        if(target==0)return 0;
        if(target==1)return 1;
        if(target==2)return 2;
        int pre1= 1;
        int pre2= 2;
        int result =0;
        for(int i=2;i<target;i++){
            result=pre1+pre2;
            pre1=pre2;
            pre2 = result;
        }
        return result;
    }
}

8.二进制中1的个数

位运算是属于二进制数的运算
基本知识

  1. 代码中在数字前加前缀
    0x十六进制
    0b二进制
    0八进制
  2. 操作
    &
    ^
    |
    m<<n:最左边的n位将被丢弃，同时在右边补上n个0
    m=m>>n:最右边的n位将被丢弃。如果是有符号数，用数字的符号位填补
    左边的n位
    m>>>n:无符号右移，补0
  3. 原码、反码和补码
    https://blog.csdn.net/hittata/article/details/9108323
    计算机中的负数表示是补码
    以负数-5为例：
    1.先将-5的绝对值转换成二进制，即为0000 0101；
    2.然后求该二进制的反码，即为 1111 1010；
    3.最后将反码加1，即为：1111 1011
    所以Java中Integer.toBinaryString(-5)结果为11111111111111111111111111111011. Integer是32位(bit)的.

题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路1：整数右移，直到为0（负数会陷入死循环）。但是java提供无符号右移方式，此时是可行的

public class Solution {
    public int NumberOf1(int n) {
        int count=0;
        while(n!=0){
            if((n&1)!=0){
              count++;  
            }
            n=n>>>1;
        }
        return count;
    }
}

思路2：设置一个无符号整型的flag，然后每次flag左移，n&flag！=0时count数+1,直到flag为0(java语言中没有无符号整型这样的变量)

public class Solution {
    public int NumberOf1(int n) {
        int count=0;
        int flag=1;
        while(flag!=0){
            if((n&flag)!=0){
              count++;  
            }
            flag = flag<<1;
        }
        return count;
    }
}

思路3：n&(n-1)会将n的最右边一位1变成0。令n=n&(n-1),直到n为0

public class Solution {
    public int NumberOf1(int n) {
        int count=0;
        while(n!=0){
            n=n&(n-1);
            count++;
        }
        return count;
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 199,711评论 5赞 468
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 83,932评论 2赞 376
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 146,770评论 0赞 330
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,799评论 1赞 271
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,697评论 5赞 359
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,069评论 1赞 276
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,535评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,200评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,353评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,290评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,331评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,020评论 3赞 315
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,610评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,694评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,927评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,330评论 2赞 346
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 41,904评论 2赞 341