剑指Offer题解（持续更新）

第2️⃣章

03 | 数组中重复的数字

问题描述

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

解题思路

• 把数字i放到num[i]上
• 如果num[i]上已经有i了，那么就是重复的数字了

代码

class Solution {
    public int findRepeatNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            while (i != nums[i]) {
                if (nums[nums[i]] != nums[i]) {
                    swap(nums,i,nums[i]);
                } else {
                    return nums[i];
                }
            }
        }
        return ans;
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

09 | 用两个栈实现队列

问题描述

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

解题思路

• 可以想象两个区域，排队区和进入区
• 入队的元素先进入排队区，出队的元素从进入区选择
• 当即将进如区为空时，将排队区的元素全部依次进入进入区（即先进去排队区的，先出进入区（将栈倒置即可））

代码

class CQueue {
    Stack<Integer> stact1 = new Stack<>();
    Stack<Integer> stact2 = new Stack<>();

    public CQueue() {

    }
    
    public void appendTail(int value) {
        stact1.push(value);
    }
    
    public int deleteHead() {
        if (stact1.isEmpty() && stact2.isEmpty()){
            return -1;
        }
        if (stact2.isEmpty()){
            while (!stact1.isEmpty()){
                stact2.push(stact1.pop());
            }
        }
        return stact2.pop();
        
    }
}

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

相关题目-225. 用两个队列实现栈

---

第3️⃣章

---

第4️⃣章

30 | 包含min函数的栈

问题描述

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

解题思路

• 栈顶元素为最小元素时，若进行出栈操作，则需要对栈内所有元素进行比较，复杂度：O(N)
• 使用辅助栈来存储各个时刻栈内的最小元素

代码

class MinStack {
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> auxStack = new Stack<>();
    int min = Integer.MAX_VALUE;
    /** initialize your data structure here. */
    public MinStack() {

    }
    
    public void push(int x) {
        min = Math.min(min,x);
        stack.push(x);
        auxStack.push(min);
    }
    
    public void pop() {
        stack.pop();
        auxStack.pop();
        if (auxStack.isEmpty()) {
            min = Integer.MAX_VALUE;
        } else {
            min = min();
        }
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int min() {
        return auxStack.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();
 */

---

第5️⃣章

---

第6️⃣章

---

第7️⃣章