剑指offer：8-11记录

向右看齐 2023-07-12 14:47 11阅读 0赞

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

示例 1：

输入：  
\["CQueue","appendTail","deleteHead","deleteHead"\]  
\[\[\],\[3\],\[\],\[\]\]  
输出：\[null,null,3,-1\]  
示例 2：

输入：  
\["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"\]  
\[\[\],\[\],\[5\],\[2\],\[\],\[\]\]  
输出：\[null,-1,null,null,5,2\]  
提示：

1 <= values <= 10000  
最多会对 appendTail、deleteHead 进行 10000 次调用

思路：辅助栈，弹出操作之前，当栈2为空时将栈1的元素全部倒入栈2，然后弹出栈2顶。

class CQueue {
        Stack<Integer> stack1;
        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()){
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            if(stack2.empty()){
                return -1;
            }
            return stack2.pop();
        }
    }
    
    /**
     * Your CQueue object will be instantiated and called as such:
     * CQueue obj = new CQueue();
     * obj.appendTail(value);
     * int param_2 = obj.deleteHead();
     */

--------------------

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1  
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.  
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2  
输出：1  
示例 2：

输入：n = 5  
输出：5

提示：

0 <= n <= 100

思路：按照式子优化空间，用几个变量即可。

class Solution {
        public int fib(int n) {
            int a = 0, b = 1, sum;
            for(int i = 0; i < n; i++){
                sum = (a + b) % 1000000007;
                a = b;
                b = sum;
            }
            return a;
        }
    }

--------------------

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2  
输出：2  
示例 2：

输入：n = 7  
输出：21  
提示：

0 <= n <= 100

式子和上题一样。

class Solution {
        public int numWays(int n) {
            int a = 1, b = 1, sum;
            for(int i = 0; i < n; i++){
                sum = (a + b) % 1000000007;
                a = b;
                b = sum;
            }
            return a;
        }
    }

--------------------

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 \[3,4,5,1,2\] 为 \[1,2,3,4,5\] 的一个旋转，该数组的最小值为1。

示例 1：

输入：\[3,4,5,1,2\]  
输出：1  
示例 2：

输入：\[2,2,2,0,1\]  
输出：0

思路：二分，注意和右端点比，不要左端点。

灵魂是如何操作相等情况。

class Solution {
        public int minArray(int[] numbers) {
            int i = 0, j = numbers.length - 1;
            while (i < j) {
                int mid = (i + j) / 2;
                if (numbers[mid] > numbers[j]) i = mid + 1;
                else if (numbers[mid] < numbers[j]) j = mid;
                //这一句是细节灵魂所在
                else j--;
            }
            return numbers[i];
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70][]

--------------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309135220824.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hlYnR1NjY2,size_16,color_FFFFFF,t_70