剑指 Offer（第 2 版）7/5 5-8

1.剑指 Offer 06. 从尾到头打印链表 简单

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
        public int[] reversePrint(ListNode head) {
    
            int n = 0;
            ListNode temp = head;
            //统计链表节点个数
            while (temp != null){
    
                n++;
                temp = temp.next;
            }
            int[] res = new int[n];
            while (head != null){
    
                res[--n] = head.val;
                head = head.next;
            }
            return res;
        }
    }

2.剑指 Offer 09. 用两个栈实现队列 简单

 //两个栈实现队列
    class CQueue {
    
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        public CQueue() {
    

        }

        public void appendTail(int value) {
    
            stack.push(value);
        }

        public int deleteHead() {
    
            //两个栈都空，表示此时队列中元素个数为0
            if (stack.isEmpty() && stack2.isEmpty())return -1;
            if (!stack2.isEmpty())return stack2.pop();//栈2有元素则直接返回
            while (!stack.isEmpty())stack2.push(stack.pop());//转移
            if (!stack2.isEmpty())return stack2.pop();//栈2有元素则返回
            return -1;
        }
    }

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

3.剑指 Offer 10- I. 斐波那契数列 简单

注意，要在循环中取模，不能等到循环结束再取模，防止越界错误
斐波那契数列

  class Solution {
    
        public int fib(int n) {
    
            if (n < 2)return n;
            int a = 0;
            int b = 1;
            int c = 0;
            for (int i = 2; i <= n; i++) {
    
                //必须在这里提前取模
                c = a + b > 1000000007 ? (a + b) % 1000000007 : a + b;
                a = b;
                b = c;
            }
            //不能前面没有取模，直接在这里取模，否则前面循环中可能越界
            return c;
        }
    }

4.剑指 Offer 10- II. 青蛙跳台阶问题 简单

注意，要在循环中取模，不能等到循环结束再取模，防止越界错误
斐波那契数列

class Solution {
    
        public int numWays(int n) {
    
            if (n == 0)return 1;//第0阶有1种方案
            if (n < 3)return n;
            //dp[i] = 跳到第i阶台阶的方案数
            int[] dp = new int[n + 1];
            dp[0] = dp[1] = 1;
            for (int i = 2; i <= n; i++) {
    
                dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
            }
            return dp[n];
        }
    }