开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 剑指Offer——简单 -> 正文阅读

[数据结构与算法]剑指Offer——简单

JZ3 从尾到头打印链表

在这里插入图片描述

错误

import java.util.ArrayList;
public class Solution {
   ArrayList<Integer> arrayList=new ArrayList<Integer>();

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
        if (listNode.next!= null) {
        
          printListFromTailToHead(listNode.next);
       
        }
        arrayList.add(listNode.val);
        return arrayList;
    }

}

解答：

ListNode  a =null;
 printListFromTailToHead(a);

调用时候：
由于：listNode.next!= null
得： null.next!= null
对空操作，空指针异常，报错

所以不能以listNode.next!= null作为判断条件

正确

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

思想

递归的时候：判断本身是否为null
调用的时候再：方法（本身.下一个）

JZ5 用两个栈实现队列

在这里插入图片描述

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.isEmpty()){
            while(stack1.size()!=0){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }else{
            return stack2.pop();
        }
        
    }
}

注意

pop的时候还要先判断stack2有没有值先

Stack<Integer> stack3 = new Stack<Integer>();
stack3.push(1);
stack3.push(2);

for(Integer i:stack3){
    System.out.println(i);
}

结果

1
2

用foreach不是先进后出了，只有pop才是先进后出

JZ6 旋转数组的最小数字

在这里插入图片描述

思路

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int left = 0;  //默认最小的
        int right = array.length - 1;
        while (left <= right) { // 说明继续查找
            int mid = (left + right) / 2;
           if(array[left]<array[right]){// 左边的数小于右边的数   因为从小到大排序的
                return array[left];
            }else if(array[mid]<array[right]){// 中间的数小于右边的数   刷新right
                right = mid;
            }else if(array[mid]>array[right]){// 中间的数大于右边的数   刷新left
                left = mid+1;
            }else{
                right--;
            }
        }
        return array[left];
    }
}

[3，4，5，1，2]
三种情况：
左边小于右边：由于是从小到大排序的，说明此时的数组是后面
的1，2了

中间的数小于右边的数：说明最小的在左边和中间，刷新right
例如【5，1，2，3，4】

中间的数大于右边的数：说明最小的在中间和右边，刷新left
例如[3，4，5，1，2] ，

当left=2，right=3时，mid=2
left = mid;时出来死循环所以要+1逼近
在这里插入图片描述

JZ8 跳台阶

在这里插入图片描述

解法一（递归：从上往下）

public class Solution {
    public int jumpFloor(int target) {
    if (target<=1) {
         return 1;
    }
       
    return jumpFloor(target-1) + jumpFloor(target-2);
    }
}

解法二（动态规划：从下往上）

public class Solution {
    public int jumpFloor(int target) {
    //斐波那契数列
    //计算f[5]的时候只用到了f[4]和f[3], 没有用到f[2]...f[0],所以保存f[2]..f[0]是浪费了空间。
    //只需要用3个变量即可。
    if (target == 0 || target == 1) {return target;}
    int a=1;
    int b=1;
    int c=0;
    for(int i=2;i<=target;i++){
        c=a+b;
        a=b;
        b=c;
    }
    return c;
    }
}

JZ9 跳台阶扩展问题

在这里插入图片描述
求的是种类所以f(n)=f(n-1)+f(n-2)+……f(1)

解答一

public class Solution {
    public int jumpFloorII(int target) {
        //易知 f(n)=f(n-1)+f(n-2)+……f(1)
        //f(n-1)=f(n-2)+……f(1)
         //两式相减得f(n)=2f(n-1)
 return (int) Math.pow(2, target-1);
        
    }
}

解法二

public class Solution {
    public int jumpFloorII(int target) {
        int res = 0;
        int sum = 0;
        int i = 1;
        while(i <= target) {
            res = sum + 1;  
            sum += res;   //f(n-1)之前的所有
            i++;
        }
        return res;
    }
}

一阶的时候 f(1) = 1 ；有两阶的时候可以
有 f(2) =1+f(1)=2；有三阶的时候可以有 f(3) = 1+f(2)+f(1)=4…依次内推，有n阶时f(n)=2^(n-1)。

JZ16 合并两个排序的链表

在这里插入图片描述

JZ16 合并两个排序的链表

在这里插入图片描述

解法一(迭代版本)

public class Solution {
    ListNode head=new ListNode(-1);
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode temp=head;
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                temp.next=list1;
                list1=list1.next;
            }
            else{
                temp.next=list2;
                list2=list2.next;
            }
            temp=temp.next;
        }
        if(list1==null){
            temp.next=list2;
        }
        if(list2==null){
            temp.next=list1;
        }
        
        return head.next;
    }
}

创建哑节点: 弄个虚拟头节点（哨兵节点）

HeroNode temp = head;：temp是指针，指向的是head的地址

解法二（递归版本）

public ListNode Merge(ListNode list1,ListNode list2) {
    if(list1 == null){
        return list2;
    }
    if(list2 == null){
        return list1;
    }
    if(list1.val <= list2.val){
        list1.next = Merge(list1.next, list2);
        return list1;
    }else{
        list2.next = Merge(list1, list2.next);
        return list2;
    }       
}

解法三

运用栈

JZ20 包含min函数的栈

在这里插入图片描述

错误

import java.util.Stack;

public class Solution {

    Stack<Integer> stack = new Stack<>();
     Integer min=null;
    public void push(int node) {
        if(min == null || min>node){//
        min=node;
    }
        stack.push(node);
    }
    
    public void pop() {
        
        stack.pop();
        
    }
    
    public int top() {
        
       int a= stack.peek();
        return a;
    }
    
    public int min() {
    
        return min;
    }

}

因为 min是为变的，当pop出min时，min就变了

正确

private Stack<Integer> main = new Stack<>();
    private Stack<Integer> min = new Stack<>();
      
    public void push(int node) {
        if(min.isEmpty() || min.peek()>=node){
            min.push(node);
        }
        main.push(node);
    }
      
    public void pop() {
        if(min.peek() == main.peek())
            min.pop();
        main.pop();
    }
      
    public int top() {
        return main.peek();
    }
      
    public int min() {
        return min.peek();
    }

当遇到小点的就压进去，一样的也要压进去。
取的时候和min栈一样，也要弹出来

JZ39 平衡二叉树

在这里插入图片描述

解答

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root==null){
            return true;
        }else if(Math.abs(height(root.left)-height(root.right))>1 ){
            return false;
        }else{
         return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);  
         // return true;//递归每个节点判断
        }
    }
    public int  height(TreeNode root){
        if (root==null){
            return 0;
        }
        return Math.max( root.left==null? 0 :height(root.left) ,root.right==null? 0 :height(root.right) )+1;
    }

}

//要递归每个节点判断
//return true; 是错误的
return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);

JZ36 两个链表的第一个公共结点

在这里插入图片描述

思路

在这里插入图片描述

a+b == b+a
其实该方法主要就是用链表循环的方式替代了长链表指针先走k步这一步骤。

代码

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

JZ30 连续子数组的最大和

在这里插入图片描述

方法一：动态规划

状态定义：dp[i]表示以i结尾的连续子数组的最大和。所以最终要求dp[n-1]

状态转移方程：dp[i] = max(array[i], dp[i-1]+array[i])

解释：如果当前元素为整数，并且dp[i-1]为负数，那么当然结果就是只选当前元素

技巧：这里为了统一代码的书写，定义dp[i]表示前i个元素的连续子数组的最大和，结尾元素为array[i-1]

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        
    if (array == null || array.length <= 0){
        return 0;
    }

    int Sum = array[0];   //临时最大值
    int MAX = array[0];   //比较之后的最大值

    for (int i = 1; i < array.length; i++)
    {
        Sum = Math.max(Sum + array[i], array[i]);   //状态方程

        if (Sum >= MAX){
            MAX = Sum;
        }
            
    }
    return MAX;
    }
}

方法二：空间复杂度O(1)解法

思想很简单，就是对下标为i的元素array[i]，先试探的加上array[i], 如果和为负数，显然，以i结尾的元素对整个结果不作贡献。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
   
    int MaxSum = array[0];  
    int ThisSum= 0; 
    for(int i=0;i<array.length;i++)  
    {  
        ThisSum+= array[i];  
        if(ThisSum > MaxSum)  {
            MaxSum = ThisSum;
        }
              
        /*如果累加和出现小于0的情况，  
           则和最大的子序列肯定不可能包含前面的元素，  
           这时将累加和置0，从下个元素重新开始累加  */
       if(ThisSum< 0)  {
            ThisSum= 0;  
         }  
    }
    return MaxSum; 
    }
}

注意

max = array[0] 之所以不定义0，是为了避免所有值都小于0的情况，如果定义array[0],一定能得到最大值

JZ45 扑克牌顺子

描述
现在有2副扑克牌，从扑克牌中随机五张扑克牌，我们需要来判断一下是不是顺子。
有如下规则：

A为1，J为11，Q为12，K为13，A不能视为14
大、小王为 0，0可以看作任意牌
如果给出的五张牌能组成顺子（即这五张牌是连续的）就输出true，否则就输出false。

例如：给出数据[6,0,2,0,4]
中间的两个0一个看作3，一个看作5 。即：[6,3,2,5,4]
这样这五张牌在[2,6]区间连续，输出true
数据保证每组5个数字，每组最多含有4个零，数组的数取值为 [0, 13]
在这里插入图片描述

代码思路

最大和最小差值应该小于5，因为只有五个数字，加了0也不可能变出花来。

还有一点是，

如果数字重复，那么返回错误即可。
最后就需要判断0的个数，去除0以后的数组，进行排序，最大和最小的差值必须小于5即可（因为0可能充当头尾数）。

import java.util.Arrays;
public class Solution {
    public boolean IsContinuous(int [] numbers) {
        int numOfZero=0;
        Arrays.sort(numbers);
        for(int i=0;i<4;i++){
            if(numbers[i]==0){
                numOfZero++;
            }else if(numbers[i]==numbers[i+1]){//重复值
                return false;
            }
        }
        return numbers[4]-numbers[numOfZero]<5;//[6,0,2,0,4]    最大的减去不是0的最小数
        
    }
}

JZ59 按之字形顺序打印二叉树

描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
例如：
给定的二叉树是{1,2,3,#,#,4,5}
在这里插入图片描述

解法一（递归）

//思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
//     所以，按照中序遍历顺序找到第k个结点就是结果。
public class Solution {
   int index = 0; //计数器
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root != null){ //中序遍历寻找第k个
            TreeNode node = KthNode(root.left,k);
            if(node != null)
                return node;
            index ++;
            if(index == k)
                return root;
            node = KthNode(root.right,k);
            if(node != null)
                return node;
        }
        return null;
    }
}

JZ62 二叉搜索树的第k个结点

描述
给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。

示例1

输入：{5,3,7,2,4,6,8},3
返回值：4
说明：按结点数值大小顺序第三小结点的值为4

解法一（递归）

//思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
// 所以，按照中序遍历顺序找到第k个结点就是结果。

public class Solution {
   int index = 0; //计数器
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root != null){ //中序遍历寻找第k个
            TreeNode node = KthNode(root.left,k);
            if(node != null)
                return node;
            index ++;
            if(index == k)
                return root;
            node = KthNode(root.right,k);
            if(node != null)
                return node;
        }
        return null;
    }
}

解法二（非递归）

用栈

import java.util.Stack;
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot == null || k <= 0){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>(); //建立栈
        TreeNode cur = pRoot;
        //while 部分为中序遍历
        while(!stack.isEmpty() || cur != null){ 
            if(cur != null){
                stack.push(cur); //当前节点不为null，应该寻找左儿子
                cur = cur.left;
            }else{
                cur = stack.pop();//当前节点null则弹出栈内元素，相当于按顺序输出最小值。
                if(--k == 0){ //计数器功能
                    return cur;
                }
                cur = cur.right;
            }
        }
        return null;
    }
}