1、剑指 Offer 10- I. 斐波那契数列（简单）

题目

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

思路

基本属于将题目翻译成代码，如果不加缓存逻辑会导致超时。

代码

  1. public class Offer10 {
  2.     /**
  3.      * 缓存
  4.      * */
  5.     public static final int[] MEMORY = new int[101];
  7.     public static int fib(int n) {
  8.         if (n==0) {
  9.             return 0;
  10.         }
  11.         if (n==1) {
  12.             return 1;
  13.         }
  15.         // 判断缓存
  16.         if (MEMORY[n] != 0) {
  17.             return MEMORY[n];
  18.         }
  20.         MEMORY[n] = (fib(n-1)+fib(n-2)) % 1000000007;
  21.         return MEMORY[n];
  22.     }
  24.     public static void main(String[] args) {
  25.         System.out.println(fib(50));
  26.     }
  27. }

2、剑指 Offer 10- II. 青蛙跳台阶问题（简单）

题目

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

思路

同上一题，主要区别在于阶梯为0的时候，要处理成1。

代码

  1. public class OfferTwo10 {
  2.     /**
  3.      * 缓存
  4.      * */
  5.     public static final int[] MEMORY = new int[101];
  7.     public static int numWays(int n) {
  8.         if (n == 0) return 1;
  9.         if (n == 1) return 1;
  10.         if (n == 2) return 2;
  11.         if (MEMORY[n] != 0) {
  12.             return MEMORY[n];
  13.         }
  14.         // 题目要求取模，不然算出来可能是负数的。
  15.         int mod = (numWays(n - 1) + numWays(n - 2)) % 1000000007;
  16.         MEMORY[n] = mod;
  17.         return MEMORY[n];
  18.     }
  20.     public static void main(String[] args) {
  21.         System.out.println(numWays(0));
  22.     }
  23. }

3、面试题 08.01. 三步问题（简单）

题目

https://leetcode-cn.com/problems/three-steps-problem-lcci/

思路

按正常两阶递归增加一阶逻辑。但是算出来一直是负数。原因是int越界了。

代码

  1. public class Interview0801 {
  2.     /**
  3.      * 缓存
  4.      * */
  5.     public static final int[] MEMORY = new int[1000001];
  7.     public static int waysToStep(int n) {
  8.         if (n==0) return 1;
  9.         if (n==1) return 1;
  10.         if (n==2) return 2;
  11.         if (MEMORY[n] != 0) {
  12.             return MEMORY[n];
  13.         }
  15.         // 第一次提交的时候 int mod = (waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3) % 1000000007)
  16.         // 发现结果成了负数了。
  17.         int mod = ((waysToStep(n - 1) + waysToStep(n - 2)) % 1000000007 + waysToStep(n - 3)) % 1000000007;
  18.         MEMORY[n] = mod;
  19.         return MEMORY[n];
  20.     }
  22.     public static void main(String[] args) {
  23.         System.out.println(waysToStep(1000));
  24.     }
  25. }

4、剑指 Offer 06. 从尾到头打印链表（简单）

题目

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

思路

每次都是打印当前节点+后续节点所有的值。
IMG_1785.jpg

注意点
本地跑main的时候因为方法和list都被加上了static 关键字。在提交的时候出现了这种情况：
测试用例:[]
测试结果:[2,3,1]
期望结果:[]

代码

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  5. public class Offer06 {
  6.     private List<Integer> resultList = new ArrayList<>();
  8.     public int[] reversePrint(ListNode head) {
  9.         // 当前为尾节点，返回空数组
  10.         if (head == null) {
  11.             return resultList.stream().mapToInt(Integer::intValue).toArray();
  12.         }
  13.         // 递归调用
  14.         reversePrint(head.next);
  15.         // 因为归的时候实际上就是相当于先进后出，所以将结果加到数组最后面即可。
  16.         resultList.add(head.val);
  17.         // 类型转换
  18.         return resultList.stream().mapToInt(Integer::intValue).toArray();
  19.     }
  21. //    public static void main(String[] args) {
  22. //        ListNode node1 = new ListNode(1);
  23. //        ListNode node2 = new ListNode(2, node1);
  24. //        ListNode node3 = new ListNode(3, node2);
  25. //        ListNode node4 = new ListNode(1, node3);
  26. //        int[] ints = reversePrint(node4);
  27. //        for (int anInt : ints) {
  28. //            System.out.println(anInt);
  29. //        }
  30. //    }
  32.     public static class ListNode {
  33.         int val;
  34.         ListNode next;
  35.         ListNode() {}
  36.         ListNode(int val) { this.val = val; }
  37.         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  38.     }
  39. }

5、剑指 Offer 24. 反转链表（简单）

题目

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

思路

专项练习用递归实现，正常思路直接循环遍历节点之后采用头插法。
递的话主要就是传递下一个节点之后的链表。
归的话主要是假设有2个节点需要反转怎么弄。
然后发现3、4、5…个节点也能这样实现。
注意点在于遍历链表的时候定义一个指针会比较方便想明白。

代码

  1. import java.util.Arrays;
  3. /**
  4.  * 剑指 Offer 24. 反转链表（简单）
  5.  * 题目
  6.  * https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
  7.  *
  8.  * @author Altman
  9.  * @date 2022/4/23
  10.  */
  11. public class Offer24 {
  13.     public static ListNode reverseList(ListNode head) {
  14.         // 空节点
  15.         if (head == null) {
  16.             return null;
  17.         }
  19.         // 意味着只有一个节点，返回新的链表
  20.         if (head.next == null) {
  21.             return new ListNode(head.val);
  22.         }
  24.         ListNode newList = reverseList(head.next);
  25.         // 这里指定一个指针，靠指针的移动来表示当前指向哪一个节点。
  26.         ListNode p = newList;
  27.         // 遍历链表，将该节点的值按照尾插法。
  28.         while (newList != null) {
  29.             // 当前节点指向 null 就可以尾插节点了
  30.             if (p.next == null) {
  31.                 ListNode newNode = new ListNode(head.val);
  32.                 p.next = newNode;
  33.                 break;
  34.             }
  35.             p = p.next;
  36.         }
  38.         return newList;
  39.     }
  41.     public static void main(String[] args) {
  42.         ListNode node = ListNode.str2Node("5,4,3,2,1");
  43.         System.out.println(ListNode.toString(reverseList(node)));
  44.     }
  46.     public static class ListNode {
  47.         int val;
  48.         ListNode next;
  50.         ListNode() {
  51.         }
  53.         ListNode(int val) {
  54.             this.val = val;
  55.         }
  57.         ListNode(int val, ListNode next) {
  58.             this.val = val;
  59.             this.next = next;
  60.         }
  62.         /**
  63.          * 打印链表内容
  64.          * @date 2022/4/23
  65.          */
  66.         public static String toString(ListNode listNode) {
  67.             StringBuilder sb = new StringBuilder();
  68.             if (listNode == null) {
  69.                 return sb.toString();
  70.             }
  71.             sb.append(listNode.val);
  72.             while (true) {
  73.                 if (listNode.next == null) {
  74.                     break;
  75.                 }
  76.                 sb.append(",");
  77.                 sb.append(listNode.next.val);
  78.                 listNode = listNode.next;
  79.             }
  80.             return sb.toString();
  81.         }
  83.         /**
  84.          * string转链表(方便测试没有做过多校验)
  85.          * @param s 逗号分割节点
  86.          * @date 2022/4/23
  87.          */
  88.         public static ListNode str2Node(String s) {
  89.             String[] split = s.split(",");
  90.             ListNode listNode = new ListNode();
  91.             ListNode p = listNode;
  92.             for (String val : split) {
  93.                 if (val == null || val == "") {
  94.                     continue;
  95.                 }
  96.                 ListNode node = new ListNode(Integer.valueOf(val));
  97.                 p.next = node;
  98.                 p = p.next;
  99.             }
  101.             return listNode.next;
  102.         }
  103.     }
  104. }

6、剑指 Offer 25. 合并两个排序的链表（中等）

题目

[

](https://leetcode-cn.com/problems/three-steps-problem-lcci/)

思路

代码

7、剑指 Offer 16. 数值的整数次方（中等）

题目

[

](https://leetcode-cn.com/problems/three-steps-problem-lcci/)

思路

代码

8、面试题 08.05. 递归乘法（中等）

题目

[

](https://leetcode-cn.com/problems/three-steps-problem-lcci/)

思路

代码

[

](https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/)