Leetcode刷题每日记录

Easy #69. Sqrt(x) 找到某个群间的值
Given a non-negative integer x, compute and return the square root of x.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.
Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.
Example 1:
Input: x = 4
Output: 2
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Solution:
很明显，判断某个区间的值，下意识，Divide and Conquer即二分算法。
1.每次找一半。 mid = (left + right) // 2 [直接除法，丢掉小数]
2.当x < mid 更新右边 right -1， mid < x 更新左边 left - 1，然后不断更新左或右的值，来控制mid的区间。
3.直到 mid < x < mid+1, 或者 left<=right break.

1. class Solution(object):
   
2.     def mySqrt(self, x):
   
3.         """
   
4.         :type x: int
   
5.         :rtype: int
   
6.         """
   
7.         
   
8.         # Binary Search
   
9.         left, right = 0, x
   
10.         
    
11.         # Logic mid
    
12.         while left <= right:
    
13.             
    
14.             # continully update mid
    
15.             mid = (left + right) // 2
    
16.             
    
17.             # Predict the mid** value
    
18.             if mid * mid <= x < (mid+1) * (mid+1):
    
19.                 return mid
    
20.             elif mid * mid < x:
    
21.                 left = mid + 1
    
22.             elif x < mid * mid:
    
23.                 right = mid -1
    
24.         

复制代码

Day3总结，刷了5道题，覆盖面主要在searching算法，后续总结：
1.DP，找到最大子组合，通过子问题状态下的子最优解，来叠加最后求得全局最优解。即找状态转移方程f(n) = f(n-1) + f(n-2)即n-2怎么转移到n-1然后最后不断叠加求到fn。
2.二分（DividendConquer），通过找到sqrt最近的数值这一题，来得出三个判断条件  x<mid: right-1; x> mid: left+1; mid<x<mid+1 return mid.
3.进位运算，用len_a, len_b, 【循环】carry 【%2 //2 进位，清空】, final =“”【append】加入自定义运算。
4.比较重要的形成做题思维，先考虑要用到什么数据结构，然后考虑到用什么主要算法，接着怎么控制循环和判断进行迭代，最后是否有edge case。即【Ideas（Algorithm/DA） -> Blue_Print（Iteration/Solution ）-> Edge_Case】

Day4 Easy #70. Climbing Stairs 爬楼梯问题，每次只能走1/2步
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution:
基本一看到是需要 【穷举】 + 【组合最佳etc】的题目，下意识就是Dynamic Programming，去找1) Base Case 2)状态转移方程和重叠子问题。
然后通过重叠子问题的关系嵌套，找到【聪明地穷举-记忆sub problem】，最后【状态压缩】，因此每次只需要保存两个状态，就可以压缩备忘录O(N)->O(1)，得到最优解。

思路：
可以倒着推导，比如每次只能走一步，两步。如果给定size10，正着有太多种组合，换成每次找子问题的最优解。则是0.找到base case，从2开始，dp = dp[1] * 2
1.要走到s(10)，只有可能是s(9)的排列组合，+size1， 或者走到s(8)的排列组合，+size2。
2.所以推导出状态转移方程就是 f(n) = f(n-1) + f(n-2) 所以求s(10)只需要知道s8和s9，同理递归。
3.再反着，就可以从s1 [s2 s3] -> dp[n-1] + dp[n-2] = dp[n] -> s[n] -> s(4) 推导任意size的可能性。
4. 通过这样的方式，就可以用一个记忆表Space O(n) 来记忆，将问题从O(2^n)简化到O(n).
5. Solution2，再接着，就可以发现其实记忆表也可以省略，因为只需要记忆两个状态。
dp[n], dp[n-1] = dp[n-1] + dp[n-2], dp[n] => dp[1], dp[0] = dp[0]+dp[1], dp[1]
Space->O(1), Time->O(n)

1. class Solution(object):
   
2.     def climbStairs(self, n):
   
3.         """
   
4.         :type n: int
   
5.         :rtype: int
   
6.         """
   
7.         # combination -> definitely DP
   
8.         # Brute_force 1, 1, 1 -> 3; 1+2 -> 3; 2+1 -> 3
   
9.         # 10 -> 1, 1, 1, 1, 1, 1, 1, 1, ,1 => 10 2 1 1 1 1 1 1 1 1 1 1 1
   
10.         
    
11.         # How to organize D(N) = D(N-1) + D(N-2)
    
12.         # FOR N=3 = [Posib 2 + 1 steps] + [Posib 1+ 2 steps]
    
13.         # so state_function => N(3) = N(2) + N(1)
    
14.         if n <= 3:
    
15.             return n
    
16.         
    
17.         # Solution 1 O(N) space
    
18.         dp = [0 for i in range(n+1)]
    
19.         dp[0] = dp[1] = 1
    
20.         for index in range(2, n+1):
    
21.             # 3-> 2 | 1  4-> 3+1 | 2+2, so we only need to know how many possibilies could happend on 3 and 2, then sum them up.
    
22.             dp[index] = dp[index-1] + dp[index-2]
    
23.         return dp[index]
    
24.         
    
25.         # Solution2 O(1) space
    
26.         dp = [1]*2
    
27.         for index in range(2, n+1):
    
28.             # optimized dp[index], we could only need 0(1)
    
29.             # dp[1] newer one, updated by dp[0] + [1]
    
30.             # dp[0] older one, moved from old dp[1]
    
31.             dp[1], dp[0] = dp[0]+dp[1], dp[1]
    
32.         return dp[1]
    
33.                

复制代码

Day4 总结，刷了1道题，就是基本Dynamic Programming。

基本反思：动态规划算法做的就是【穷举 + 剪枝】，它俩天生一对儿。所以可以说只要涉及子序列，子组合最优化问题，十有八九都需要动态规划来解决，往这方面考虑就对了。

DP Note: 具体来说，动态规划的一般流程就是三步：【暴力的递归解法 -> 带备忘录的递归解法 -> 迭代的动态规划解法】。就思考流程来说，就分为一下几步：【找到状态和选择 -> 明确 dp 数组/函数的定义 -> 寻找状态之间的关系】。这就是思维模式的框架，按照以上的模式来解决问题，有了方向遇到问题就不会抓瞎，足以解决一般的动态规划问题。

通过爬楼梯这道题，可以看出规律最难的就是求出 【状态转移方程】推出状态 current(n) = previous(n-1) + previous(n-2)的关系。
之后就可以通过已经算过的答案，用一个【备忘录，或者变量存储】，进行剪支。
以及确定初始状态的【base case】 dp[0] = dp[1] = 1。
即找到 【如果通过子问题的不断叠加，最后推导出最优解。】

Day 5 Easy #83 Remove Duplicates from Sorted List 移走链表中的重复元素
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Example 1:
Input: head = [1,1,2]
Output: [1,2]
Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]


Solution：
其实考的主要就是怎么linkedList里面【pointer的地址连接】:比如 1->2->2 ==> 1 -> 2 即update下一个元素方式为
cur.next = cur.next.next
否则正常update:
cur = cur.next

考点:
【1】怎么存head位置(0)的头部pointer：
1）curr = head， 对curr 操作，最后return head；
2） init = head， 对head操作最后return init
3）新的head = listnode(0)，prev = head要return head.next
【2】是怎么循环linkedin list:
其实就是判断while head and head.next： 是否为null
结尾，head = head.next
【3】是怎么置换pointer位置：
直接【head.next = head.next.next】 or head.next=? (即当前的位置的下个连接连到哪，要跳过head.next，直接连接head.next.next)
否则，不改变，走循环【直接往下移head = head.next】

Code:

1. 
   
2. # Definition for singly-linked list.
   
3. # class ListNode(object):
   
4. #     def __init__(self, val=0, next=None):
   
5. #         self.val = val
   
6. #         self.next = next
   
7. class Solution(object):
   
8.     def deleteDuplicates(self, head):
   
9.         """
   
10.         :type head: ListNode
    
11.         :rtype: ListNode
    
12.         """
    
13.         # Data Structure: operate pointer & check .val eqaul or not
    
14.         # Get the pointer from head Node
    
15.         # Need to know How to loop for the node:
    
16.         # while pointer:
    
17.         #       pointer = pointer.next
    
18.         
    
19.         # head is "pointer"
    
20.         if head == None:
    
21.             return head
    
22. 
    
23.         # while head (head.next==null break):
    
24.         # Get to know whether head.val < head.next.val: head
    
25.         # head:curr_pointer, head.next: next_element; etc.
    
26.         # The operation that we want to do:
    
27.         #       1->1->2 => 1->2
    
28.         #       if current == current.next
    
29.         #          current.next = current.next.next
    
30. 
    
31.         # Begin
    
32.         # First pointer 0
    
33.         cur = head
    
34.         
    
35.         # Check whether we have head and head.next
    
36.         while cur and cur.next:
    
37.             # if we have, check current == current.next logic
    
38.             if cur.val == cur.next.val:
    
39.                 cur.next = cur.next.next
    
40.             else:
    
41.                 cur = cur.next
    
42.                
    
43.         return head

复制代码

Easy #88. Merge Sorted Array 两个排好序的list，进行merge

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Solution:
1.看到inplace操作，肯定双指针，一个控制list1的走法index1--，一个控制list2的走法index2--，如果是想要用while，还需要一个position的指针。
2.然后看到m,n为本身的长度，那么后面为0，基本就是倒序来判断。
3.最后看是否还有剩下的，直接append。

思路即为，倒着来 pos = m+n, list1 = m, list2 = n.
当list1, list2还有元素的时候，即list1>0; list2>0: 做判断的比较，谁大把谁填到最后一位去
x = list1[index_1] >? list2[index_2], list1[pos] = x

1. class Solution(object):
   
2.     def merge(self, nums1, m, nums2, n):
   
3.         """
   
4.         :type nums1: List[int]
   
5.         :type m: int
   
6.         :type nums2: List[int]
   
7.         :type n: int
   
8.         :rtype: None Do not return anything, modify nums1 in-place instead.
   
9.         """
   
10.         # in-place: 2 pointers as index
    
11.         fast_p = m
    
12.         slow_p = n
    
13.         pos = m+n
    
14.         # Core Algorithm: |1 2 3 | 2 5 6|
    
15.         #      Judgement: fast_index vs slow_index;
    
16.         #                  if fast_index < slow_index, kept it
    
17.         #                  elif fast > slow: x[fast_index], y[slow_index] =
    
18.         #                        y[slow_index] = x[fast_iondex], swap it, slow+1
    
19.         
    
20.         # 0 ,0, 0 is acatually a inital_storage
    
21.         
    
22.         # Core algorithm, get the max, and pop the array that we used
    
23.         while fast_p > 0 and slow_p > 0:
    
24.             # from end to start
    
25.             if nums1[fast_p-1] < nums2[slow_p-1]:
    
26.                 # put max_value into pos
    
27.                 nums1[pos-1] = nums2[slow_p-1]
    
28.                 slow_p -= 1
    
29.             else:
    
30.                 nums1[pos-1] = nums1[fast_p-1]
    
31.                 fast_p -= 1
    
32.             # iteration
    
33.             pos = pos - 1
    
34.             print slow_p, fast_p, pos
    
35.             
    
36.         # judge the rest of the array, can directly put it into that
    
37.         if fast_p > 0:
    
38.             nums1[:pos] = nums1[:fast_p]
    
39.         else:
    
40.             nums1[:pos] = nums2[:slow_p]
    
41.             
    
42.         return nums1

复制代码

Easy #94. Binary Tree Inorder Traversal 树的中序遍历
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]

Solution:
树的遍历，两种解法。
递归：
模版

1. # recursive
   
2. class Solution(object):
   
3.     def inorderTraversal(self, root):
   
4.         """
   
5.         :type root: TreeNode
   
6.         :rtype: List[int]
   
7.         """
   
8.         res = []
   
9.         self.helper(root, res)
   
10.         return res
    
11.    
    
12.     def helper(self, root, res):
    
13.         if root:
    
14.             self.helper(root.left, res)
    
15.             res.append(root.val)
    
16.             self.helper(root.right, res)
    
17. 
    
18. # # iterative
    
19. # def inorderTraversal(self, root):
    
20. #     res, stack = [], []
    
21. #     while True:
    
22. #         while root:
    
23. #             stack.append(root)
    
24. #             root = root.left
    
25. #         if not stack:
    
26. #             return res
    
27. #         node = stack.pop()
    
28. #         res.append(node.val)
    
29. #         root = node.right

复制代码

非递归:
非递归使用栈的解法，也是符合本题要求使用的解法之一，需要用栈来做，思路是从根节点开始，
1.先将根节点压入栈:
tree_stack.append(root)
2.然后再将其所有左子结点压入栈:
root = root.left
3.然后取出栈顶节点，保存节点值，再将当前指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子结点压入栈中。这样就保证了访问顺序为左-根-右
                # get the left tree firstly, then pop
                node = tree_stack.pop()
                # get left tree vale
                trav_inorder.append(node.val)
                # update root index, go back to parent
                root = node.right

1. # Definition for a binary tree node.
   
2. # class TreeNode(object):
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution(object):
   
8.     def inorderTraversal(self, root):
   
9.         """
   
10.         :type root: TreeNode
    
11.         :rtype: List[int]
    
12.         """
    
13.         tree_stack = []
    
14.         trav_inorder = []
    
15.         
    
16.         while root or tree_stack:
    
17.             if root:
    
18.                 tree_stack.append(root)
    
19.                 root = root.left
    
20.             else:
    
21.                 # get the left tree firstly, then pop
    
22.                 node = tree_stack.pop()
    
23.                 # get left tree vale
    
24.                 trav_inorder.append(node.val)
    
25.                 # update root index, go back to parent
    
26.                 root = node.right
    
27.         return trav_inorder

复制代码

Easy #100. Same Tree
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Input: p = [1,2,3], q = [1,2,3]
Output: true
Input: p = [1,2], q = [1,null,2]
Output: false

Solution:
递归或者Stack来解决，不断check p and q 是否为None, 以及是否都是相等的，如果是 return True，不是return False。
Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.

1. 
   
2. # Definition for a binary tree node.
   
3. # class TreeNode(object):
   
4. #     def __init__(self, val=0, left=None, right=None):
   
5. #         self.val = val
   
6. #         self.left = left
   
7. #         self.right = right
   
8. class Solution(object):
   
9.     def isSameTree(self, p, q):
   
10.         """
    
11.         :type p: TreeNode
    
12.         :type q: TreeNode
    
13.         :rtype: bool
    
14.         """
    
15.         
    
16.         # DFS
    
17.         stack = [(p , q)]
    
18.         while stack:
    
19.             (node1, node2) = stack.pop()
    
20.             
    
21.             if not node1 and not node2:
    
22.                 continue
    
23.             elif None in [node1, node2]:
    
24.                 return False
    
25.             else:
    
26.                 if node1.val != node2.val:
    
27.                     return False
    
28.                 stack.append([node1.right, node2.right])
    
29.                 stack.append([node1.left, node2.left])
    
30.             
    
31.         return True
    
32.    
    
33.         # Recurrent
    
34.         if not p and not q:
    
35.             return True
    
36.         # one of p and q is None
    
37.         if not q or not p:
    
38.             return False
    
39.         if p.val != q.val:
    
40.             return False
    
41.         return self.isSameTree(p.right, q.right) and \
    
42.                self.isSameTree(p.left, q.left)
    
43. 
    
44.         
    
45.         
    
46.         

复制代码

Easy #100. Same Tree
Input: p = [1,2,3], q = [1,2,3]
Output: true

Solution:
Check if p and q nodes are not None, and their values are equal. If all checks are OK, do the same for the child nodes recursively.
递归判断是否1.不为None 2.相等 否则为False

1. # Definition for a binary tree node.
   
2. # class TreeNode(object):
   
3. #     def __init__(self, val=0, left=None, right=None):
   
4. #         self.val = val
   
5. #         self.left = left
   
6. #         self.right = right
   
7. class Solution(object):
   
8.     def isSameTree(self, p, q):
   
9.         """
   
10.         :type p: TreeNode
    
11.         :type q: TreeNode
    
12.         :rtype: bool
    
13.         """
    
14.         
    
15.         # DFS
    
16.         stack = [(p , q)]
    
17.         while stack:
    
18.             (node1, node2) = stack.pop()
    
19.             
    
20.             if not node1 and not node2:
    
21.                 continue
    
22.             elif None in [node1, node2]:
    
23.                 return False
    
24.             else:
    
25.                 if node1.val != node2.val:
    
26.                     return False
    
27.                 stack.append([node1.right, node2.right])
    
28.                 stack.append([node1.left, node2.left])
    
29.             
    
30.         return True
    
31.    
    
32.         # Recurrent
    
33.         if not p and not q:
    
34.             return True
    
35.         # one of p and q is None
    
36.         if not q or not p:
    
37.             return False
    
38.         if p.val != q.val:
    
39.             return False
    
40.         return self.isSameTree(p.right, q.right) and \
    
41.                self.isSameTree(p.left, q.left)
    
42. 
    
43.         
    
44.         
    
45.         

复制代码

Day5 总结，刷了四道题，主要是链表的遍历，array双指针，以及树的遍历和比较

1. linked List怎么操作pointer移除重复元素, 1.需要存储pointer0的头部指针用于return. 2.循环为head=head.next 3.置换位置下个连接的位置和update head head.next = head.?
2. array inplace merge两个list，双指针，和+global指针用于指定倒序的赋值
3. 树的中序遍历，模版。
4. 树的左右节点判断，不断的对比两个树的左右节点，recurrsive循环。

基本前100题的easy题目都结束了，也熟悉了 Array, String, Hash_table, LinkedList, Tree的操作，和基本算法: Divide&Conquer, DP, Recursive, Iteration, 二分。
后面就可以开始具体一天刷一个类型的题目，然后再进行总结。

【Schedule】
后续安排按照这几个类型来刷
https://github.com/azl397985856/leetcode/tree/master/thinkings
0.链表
1.树 <- 递归+BFS+DFS
2.二叉树 <- 回溯
3.数组 <- 二分/滑动窗口
4.动态规划

【Tips 时间规划】
每天其实最好是晚上睡前总结和规划第二天早的任务
第二天白天早上起来先刷好这一天最难的题，下午继续刷和总结，晚上review all。
这样不容易疲惫。