《剑指offer》算法题整理

文章目录

• 〇、刷题建议
• 一、队、栈
• 二、双指针
• 三、树
• 四、数组

  力扣题库：跳转

〇、刷题建议

• 先花几天充分学习《数据结构》这门课程，再刷算法题，事半功倍。
• 按tag刷，这样有利于熟悉API。
• 同tag下，由简到难刷。
• 多看看官方解析或评论区优质答案，尤其是不熟练的题目。

一、队、栈

09. 用两个栈实现队列[简单]

  用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

• 原理

• 实现(Java)：

class CQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public CQueue() {
        stack1=new Stack<Integer>();
        stack2=new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(!stack2.empty())return stack2.pop();
        else if(!stack1.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
        else return -1;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

30. 包含min函数的栈[简单]

  定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数。在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

• 原理

• 实现(Java)：

class MinStack {
    //stack1存放原本的栈，stack2是辅助栈
    Stack<Integer> stack1,stack2;

    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    
    public void push(int x) {
        stack1.push(x);
        if(stack2.empty()||x<=stack2.peek())stack2.push(x);
    }
    
    //注意，这里用equals方法而不是==，因为元素是Integer类型的而不是int型的
    public void pop() {
        if(stack1.pop().equals(stack2.peek()))stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

59 - I. 滑动窗口的最大值[简单]？？

  给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

• 原理

• 实现(Java)：没调通，后期再改正优化

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //如果nums为空或k为0
        if(nums==null||nums.length==0||k==0)return new int[0];
        //deque为辅助双端队列
        Deque<Integer> deque=new ArrayDeque<Integer>();
        int[] max=new int[nums.length-k+1];
        //第一个滑动窗口，得到辅助队列
        for(int i=0;i<k-1;++i){
            //首先，当前元素得大于等于滑动窗口最右端的元素
            if(nums[i]>=nums[k-1]){
                //情况一二：队空，或队不空且小于等于队尾元素，直接入队
                if(deque.size()==0||nums[i]<=deque.getLast())deque.addLast(nums[i]);
                //情况三：队不空但大于队尾元素，则让队空，此元素入队
                else {
                    while(deque.size()!=0)deque.removeFirst();
                    deque.addLast(nums[i]);
                }
            }
        }
        deque.addLast(nums[k-1]);
        max[0]=deque.getFirst();
        System.out.println(max[0]);
        //从第二个滑动窗口开始
        for(int i=1;i<=nums.length-k;++i){
            //判断队头是否应该出队
            if(nums[i-1]==deque.getFirst())deque.removeFirst();
            //判断窗口中的新元素是否应该入队
            //情况一：队空，或该元素小于等于队尾元素，直接入队
            if(deque.size()==0||nums[k+i-1]<=deque.peekLast())deque.addLast(nums[k+i-1]);
            //情况二：该元素大于队头元素，全部出队，此元素再入队
            else if(nums[k+i-1]>deque.getFirst()){
                 while(deque.size()!=0)deque.removeFirst();
                 deque.addLast(nums[k+i-1]);
            }
            //情况三：该元素大于队尾元素但小于等于队头元素,将小于此元素的队中元素从右边出队，此元素再入队
            else{
                while(deque.getLast()<nums[k+i-1])deque.removeLast();
                deque.addLast(nums[k+i-1]);
            }
            max[i]=deque.getFirst();
            System.out.println(max[i]);
        }
        return max;
    }
}

二、双指针

22. 链表中倒数第k个节点[简单]

  输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode p1=head,p2=head;
        while((--k)!=0){
            p2=p2.next;
        }
        while(p2.next!=null){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }
}

三、树

27. 二叉树的镜像[简单]

  请完成一个函数，输入一个二叉树，该函数输出它的镜像。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //当根结点为空或为叶结点
        if(root==null||(root.left==null&&root.right==null)){}
        //当有左右子结点
        else if(root.left!=null&&root.right!=null){
            TreeNode temp=root.left;
            root.left=mirrorTree(root.right);
            root.right=mirrorTree(temp);
        }
        //当只有左子结点
        else if(root.left!=null){
            root.right=mirrorTree(root.left);
            root.left=null;
        }
        //当只有右子结点
        else{
            root.left=mirrorTree(root.right);
            root.right=null;
        }
        return root;
    }
}

55 - I. 二叉树的深度[简单]

  输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        int depth=0;
        //如果根结点为空
        if(root==null)depth=0;
        //如果根结点为叶结点
        else if(root.left==null&&root.right==null)depth=1;
        //如果只有左子树
        else if(root.right==null){
            depth=depth+1+maxDepth(root.left);
        }
        //如果只有右子树
        else if(root.left==null){
            depth=depth+1+maxDepth(root.right);
        }
        //如果左右子树都有
        else{
            depth=depth+1+Math.max(maxDepth(root.left),maxDepth(root.right));
        }
        return depth;
    }
}

54. 二叉搜索树的第k大节点[简单]？？

  给定一棵二叉搜索树，请找出其中第k大的节点。

• 原理

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int k,res;
    public int kthLargest(TreeNode root, int k) {
        this.k=k;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.right);
        if(--k==0)res=root.val;
        dfs(root.left); 
    }
}

68 - II. 二叉树的最近公共祖先[简单]

  给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //结点不存在
        if(root==null||p==null||q==null)return null;
        //有一个为根结点
        if(root==p||root==q)return root;
        
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //一左一右
        if(left!=null&&right!=null)return root;
        //在同一侧
        else if(left!=null)return left;
        else if(right!=null)return right;
        else return null;
    }
}

68 - I. 二叉搜索树的最近公共祖先[简单]

  给定一个搜索二叉树, 找到该树中两个指定节点的最近公共祖先。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||p==null||q==null)return null;
        if(root==p||root==q)return root;
        //如果都比根结点大
        if(p.val>root.val&&q.val>root.val)return lowestCommonAncestor(root.right,p,q);
        //如果都比根结点小
        else if(p.val<root.val&&q.val<root.val)return lowestCommonAncestor(root.left,p,q);
        //如果一个比根大，一个比根小
        else return root;
    }
}

32 - II. 从上到下打印二叉树 II[简单]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null)return new ArrayList<List<Integer>>(0);
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        //如果为叶结点
        if(root.left==null&&root.right==null){
            List<Integer> item=new ArrayList<Integer>(1);
            item.add(root.val);
            list.add(item);
        }
        //如果有左右子树
        else {
            LinkedList<TreeNode> que=new LinkedList<TreeNode>();
            que.add(root);
            //循环打印
            while(que.size()!=0){
                List<Integer> item=new ArrayList<Integer>(que.size());
                int length=que.size();
                for(int i=0;i<length;++i){
                    TreeNode node=que.remove();
                    item.add(node.val);
                    if(node.left!=null)que.addLast(node.left);
                    if(node.right!=null)que.addLast(node.right);
                }
                list.add(item);
            }
        }
        return list;
    }
}

55 - II. 平衡二叉树[简单]

  输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        //结点为空
        if(root==null)return true;
        //结点为叶结点
        else if(root.left==null&&root.right==null)return true;
        //其他
        else {
            boolean result=(depth(root.left)-depth(root.right))<=1&&(depth(root.left)-depth(root.right))>=-1;
            return result&&isBalanced(root.left)&&isBalanced(root.right);
        }
    }
    public int depth(TreeNode root){
        //如果结点为空
        if(root==null)return 0;
        //如果结点为叶结点
        else if(root.left==null&&root.right==null)return 1;
        else return 1+Math.max(depth(root.left),depth(root.right));
    } 
}

28. 对称的二叉树[简单]

  请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        //如果结点为空或为叶结点
        if(root==null||(root.left==null&&root.right==null))return true;
        //如果只有一个左/右子树
        else if(root.left==null||root.right==null)return false;
        //左右子树都存在
        else return symmetric(root.left,root.right);
            
    }
    public boolean symmetric(TreeNode node1,TreeNode node2){
        //先判断两结点值是否相等
        if(node1.val!=node2.val)return false;
        //result1和2分别用来记录node1.left和node2.right、node1.right和node2.left的对称情况
        boolean result1=false;boolean result2=false;
        if(node1.left==null&&node2.right==null)result1=true;
        else if(node1.left==null||node2.right==null)return false;
        else result1=symmetric(node1.left,node2.right);

        if(node1.right==null&&node2.left==null)result2=true;
        else if(node1.right==null||node2.left==null)return false;
        else result2=symmetric(node1.right,node2.left);

        return result1&&result2;
    }
}

四、数组

03. 数组中重复的数字[简单]

  找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
    public int findRepeatNumber(int[] nums) {
        //辅助空间，用来记录数值是否重复出现，元素默认值都是false
        boolean[] count=new boolean[nums.length];
        //遍历nums
        for(int i=0;i<nums.length;++i){
            //先检查是否已经出现过了
            if(count[nums[i]])return nums[i];
            //如果没出现过，记录此次出现并进行下一步
            else count[nums[i]]=true;
        }
        return -1;
    }
}

53 - I. 在排序数组中查找数字 I[简单]

  统计一个数字在排序数组中出现的次数。

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length==0||target<nums[0]||target>nums[nums.length-1])return 0;

        int count=0;
        for(int i=0;i<nums.length&&nums[i]<=target;++i){
            if(nums[i]==target)++count;
        }
        return count;
    }
}

本文地址：https://blog.csdn.net/Tracycoder/article/details/112217258