2020年8月3日
18:55

1.爬梯子

https://leetcode-cn.com/problems/climbing-stairs/
这题稍加分析就会发现其实是一个斐波那契数列，可以用动态规划的方法来解决，也可以直接用公式计算

题解一：
Python:

  1. class Solution:
  2.     def climbStairs(self, n: int) -> int:
  3.         climb = {}
  4.         climb[1]=1
  5.         climb[2]=2
  6.         for i in range(3,n+1):
  7.             climb[i] = climb[i-1] + climb[i-2]
  8.         return climb[n]

Java:

  1. class Soulution{
  2.     public int climbStairs(int n) {
  3.         if (n<=2){
  4.             return n;
  5.         }
  6.         /*给定n是一个正整数*/
  7.         int[] climb = new int [n+1];
  8.         climb[1]=1;
  9.         climb[2]=2;
  10.         for(int i=3,i<=n+1,i++){
  11.             climb[i]=climb[i-2]+climb[i-1]
  12.             }
  13.         return climb[n];
  14.     }
  15. }

题解二:

  1. class Solution {
  2.    public int climbStairs(int n) {
  3.        double sqrt_5 = Math.sqrt(5);
  4.        double fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
  5.        return (int)(fib_n / sqrt_5);
  6.    }
  7. }

2. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
https://leetcode-cn.com/problems/merge-two-sorted-lists/
链表题我是按照这个题解的方法做的
https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/xin-shou-you-hao-xue-hui-tao-lu-bu-fan-cuo-4nian-l/
https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/merge-two-sorted-lists-by-ikaruga/

也就是迭代的方法

Python:

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
  9.         # 创建哑节点作为 结果链表 的开头
  10.         dummy = ListNode(0)
  11.         # 有个游标，标识 结果链表 的结尾
  12.         move = dummy
  13.         # l1 和 l2 都未遍历结束
  14.         while l1 and l2:
  15.             # 如果 l1 的数值比较小
  16.             if l1.val <= l2.val:
  17.                 # 把 l1 头部节点拼接到 结果链表 的结尾
  18.                 move.next = l1
  19.                 # l1 指向下一个节点
  20.                 l1 = l1.next
  21.             else:
  22.                 # 把 l2 头部节点拼接到 结果链表 的结尾
  23.                 move.next = l2
  24.                 # l2 指向下一个节点
  25.                 l2 = l2.next
  26.             # 移动 结果链表 的结尾指针
  27.             move = move.next
  28.         # l1 或者 l2 尚未使用完，拼接到 结果链表 的最后
  29.         move.next = l1 if l1 else l2
  30.         # 返回哑节点的下一个位置
  31.         return dummy.next

Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;//当前节点的值
 *     ListNode next;//下一个节点的引用值
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode temp=new ListNode(0);
        ListNode head=temp;
        while(l1!=null&&l2!=null){
           if(l1.val<l2.val) 
           {
               temp.next=l1;
               l1=l1.next;
           }   
           else
           {
               temp.next=l2;
               l2=l2.next;
           }
           temp=temp.next;
        }
        if(l1==null)  temp.next=l2;
        if(l2==null)  temp.next=l1;
        return head.next;//返回头节点指向的序列
    }
}