来刷题啊 Top100 Liked Problems

LeetCode

617. Merge Two Binary Trees

Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.

Example 1:

Input:
Tree 1 Tree 2
1 2
/ \ / \
3 2 1 3
/ \ \
5 4 7
Output:
Merged tree:
3
/ \
4 5
/ \ \
5 4 7

Note: The merging process must start from the root nodes of both trees.

【题意】
二叉树合并，把相同位置的val加和

【思路】
根节点按要求加和，左右节点扔进递归

【代码】

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 or t2:
            new_root = TreeNode()
        else:
            return
        if t1:
            new_root.val += t1.val
        if t2:
            new_root.val += t2.val
        if t1 and t2:
            new_root.left = self.mergeTrees(t1.left, t2.left)
            new_root.right = self.mergeTrees(t1.right, t2.right)
        elif t1:
            new_root.left = self.mergeTrees(t1.left, None)
            new_root.right = self.mergeTrees(t1.right, None)
        elif t2:
            new_root.left = self.mergeTrees(None, t2.left)
            new_root.right = self.mergeTrees(None, t2.right)
        return new_root

【discussion】
简洁写法 啊呜呜呜突然觉得自己写的也太丑了

def mergeTrees(self, t1, t2):
    if t1 and t2:
            root = TreeNode(t1.val + t2.val)
            root.left = self.mergeTrees(t1.left, t2.left)
            root.right = self.mergeTrees(t1.right, t2.right)
            return root
    else:
        return t1 or t2

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.

【题意】
求二叉树的树深

【代码】

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root==None:
            return 0
        cnt = 0
        que = [root]
        while len(que):
            cnt += 1
            new_que = []
            for x in que:
                if x.left:
                    new_que.append(x.left)
                if x.right:
                    new_que.append(x.right)
            que = new_que[::]
        return cnt

【discussion】
One line solution

def maxDepth(self, root):
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right)) if root else 0

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

Example 1:
Input: nums = [2,2,1]
Output: 1
Example 2:
Input: nums = [4,1,2,1,2]
Output: 4
Example 3:
Input: nums = 1
Output: 1

Constraints:
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
Each element in the array appears twice except for one element which appears only once.

【题意】
只有一个数出现了一次 其他都出现了两次 找这个数

【代码】

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = nums[0]
        for x in nums[1:]:
            ans = ans^x
        return ans

【discussion】
其实还有多种做法

def singleNumber1(self, nums):
    dic = {}
    for num in nums:
        dic[num] = dic.get(num, 0)+1
    for key, val in dic.items():
        if val == 1:
            return key
def singleNumber2(self, nums):
    res = 0
    for num in nums:
        res ^= num
    return res
def singleNumber3(self, nums):
    return 2*sum(set(nums))-sum(nums)
def singleNumber4(self, nums):
    return reduce(lambda x, y: x ^ y, nums)
def singleNumber(self, nums):
    return reduce(operator.xor, nums)

226. Invert Binary Tree

Invert a binary tree.
Example:
Input:
4
/ \
2 7
/ \ / \
1 3 6 9
Output:
4
/ \
7 2
/ \ / \
9 6 3 1

【代码】

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root==None:
            return
        self.invertTree(root.left)
        self.invertTree(root.right)
        tmp = root.left
        root.left = root.right
        root.right = tmp
        return root

【discussion】
更Pythonic的写法

def invertTree(self, root):
    if root:
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

206. Reverse Linked List

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

【思路】
遍历每个节点，插到第一个的前面

【代码】

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre_head = ListNode(next=head)
        while head and head.next:
            now = head.next
            head.next, now.next, pre_head.next = now.next, pre_head.next, now
        return pre_head.next

【discussion】
递归的写法

class Solution(object):
    def reverseList(self, head, prev=None):
        if not head:
          return prev
        curr, head.next = head.next, prev
        return self.reverseList(curr, head)

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Input: [3,2,3]
Output: 3
Example 2:
Input: [2,2,1,1,1,2,2]
Output: 2

【代码】
（1）

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        return nums[int(n/2)]

（2）

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        num, cnt = 0, 0
        for x in nums:
            if cnt==0:
                num = x
                cnt += 1
            elif num==x:
                cnt += 1
            elif num!=x:
                cnt -= 1
        return num

283. Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

【题意】
把数组中的0挪到最后面 要求是in-place操作

【思路】
先想到把0的pop掉然后在加上少掉的0，更好的是用双指针的做法把0和非0的直接交换（没前者好写就没写了orz）

【代码】

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        now = 0
        while now<len(nums):
            if nums[now]==0:
                nums.pop(now)
            else:
                now+=1
        zero_num = length-len(nums)
        nums += [0]*zero_num

【discussion】
比双指针做法更简单，因为其实不要想着是和0交换，而是直接按序排下去就好了，第一个非0的要放在数组第一个位置，第二个要放第二个位置，所以当不为0的时候idx++就是正确的位置，最后0都是会被交换到末尾的

def moveZeroes(self, nums):
    idx = 0 
    for i in xrange(len(nums)):
        if nums[i] != 0:
            nums[i], nums[idx] = nums[idx], nums[i]
            zero += 1

448. Find All Numbers Disappeared in an Array

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements of [1, n] inclusive that do not appear in this array.
Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[5,6]

【题意】
找到1~n中没有出现在数组里的数 n=len(nums)

【代码】
没想出来 还是用了额外空间OTL

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        all_nums = [0]*len(nums)
        for x in nums:
            all_nums[x-1]=1
        ans = []
        for i in range(len(nums)):
            if all_nums[i]==0:
                ans.append(i+1)
        return ans

【discussion】
超级机智！！
对nums中的每个数 如果这个数k出现了 就把index=k位置的置为负数，然后遍历一遍找到还是正数的，那这些位置的index就是答案

def findDisappearedNumbers(self, nums):
    for num in nums:
        index = abs(num) - 1
        nums[index] = -abs(nums[index])
    return [i + 1 for i, num in enumerate(nums) if num > 0]

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: l1 = [], l2 = []
Output: []
Example 3:
Input: l1 = [], l2 = [0]
Output: [0]
Constraints:
The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both l1 and l2 are sorted in non-decreasing order.

【题意】
合并两个递增的list

【思路】
先建个头，然后两个list的头看下取哪个就拿过来

【代码】

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        ans = ListNode()
        now = ans
        while l1 or l2:
            if l1 and l2:
                if l1.val < l2.val:
                    now.next, l1 = l1, l1.next
                else:
                    now.next, l2 = l2, l2.next
            else:
                now.next = l1 or l2
                l1, l2 = l1.next if l1 else l1, l2.next if l2 else l2
            now = now.next
        return ans.next

【discussion】
递归的写法

def mergeTwoLists2(self, l1, l2):
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

【题意】
给一list代表了每天的股价，问买一次卖一次最多能赚多少钱

【思路】
先算出每日价格的差 就相当于是最大连续子串和的问题了

【代码】

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        days = len(prices)
        if days<=1:
            return 0
        diff = [prices[i]-prices[i-1] for i in range(1,days)]
        ans, now = 0, 0
        for x in diff:
            now+=x
            if now<0:
                now=0
            ans = max(ans, now)
        return ans

【discussion】
只遍历一遍 在每个位置更新下当前见过的min_price，然后在这个点卖出的收益就是当前price-min_price

def maxProfit(prices):
    ans, min_price = 0, float('inf')
    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        ans = max(ans, profit)
    return ans

543. Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Given a binary tree
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.

【题意】
求二叉树的直径（一节点到另一节点的最长路径）

【思路】
如果知道直径的根是哪个点，那直径就等于以这个点为根的左边最长+右边最长，所以要遍历到每个点上求一下；因为递归求树高的时候就会遍历到所有点，所以直接在求树高的时候顺带更新一下ans

【代码】

class Solution:
    def __init__(self):
        self.ans = 0
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0
        def length(root):
            if not root:
                return 0
            l, r = length(root.left), length(root.right)
            self.ans = max(self.ans, l+r)
            return max(l, r)+1
        length(root)
        return self.ans

（顺带发现 写成内嵌函数会比写成类函数更快）

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to 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: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 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
Constraints:
1 <= n <= 45

【题意】
一次可以跨一级台阶或两级台阶，问要上n级台阶有几种走法

【思路】
经典DP，原问题P(N) = P(N-1)+P(N-2)，但因为觉得简单写的太随意还错了3次 555。错的点：一定要开数组存memory不然会T，提前判n小于3就返回是因为后面dp[0],1,2的赋值需要保证n>3

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<3:
            return n
        dp = [-1]*(n+1)
        dp[0], dp[1], dp[2] = 0, 1, 2
        def dfs(n):
            if dp[n]!=-1:
                return dp[n]
            else:
                dp[n] = dfs(n-1)+dfs(n-2)
                return dp[n]
        return dfs(n)

【discussion】
非递归的写法

# Bottom up, O(n) space
def climbStairs2(self, n):
    if n == 1:
        return 1
    res = [0 for i in xrange(n)]
    res[0], res[1] = 1, 2
    for i in xrange(2, n):
        res[i] = res[i-1] + res[i-2]
    return res[-1]

101. Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3

【题意】
判断二叉树是否左右对称

【思路】
递归

【代码】

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def issym(left, right):
            if left==None and right==None:
                return True
            elif left==None or right==None:
                return False
            elif left.val==right.val and issym(left.left, right.right) and issym(left.right, right.left):
                return True
            else:
                return False
        if root==None:
            return True
        return issym(root.left, root.right)

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2:
Input: nums = 1
Output: 1
Example 3:
Input: nums = [0]
Output: 0
Example 4:
Input: nums = [-1]
Output: -1

【题意】
求最大连续子序列的最大值（子序列至少要有一个数）

【思路】
最大连续子序列常规操作闭眼写，但那个是默认全为负就取0个数，所以特判一下如果全为负就直接返回最大

【代码】

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans, now = 0, 0
        flag = False
        for x in nums:
            if x>0:
                flag = True
            now += x
            if now < 0:
                now = 0
            ans = max(ans, now)
        if flag == False:
            return max(nums)
        else:
            return ans

【discussion】
超级简单的写法，直观的解释就是，num存的是从头开始到我这的最大连续子序列。那么对于每个位置，如果前面的大于0，就对我这有利可以加过来，如果小于0，就放弃掉。
本质是和常规操作一样的想法，但就可以存下每个位置为结尾且至少有一个数的最大连续子序列，然后取max。

for i in range(1, len(nums)):
        if nums[i-1] > 0:
            nums[i] += nums[i-1]
    return max(nums)

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums1 == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Constraints:
2 <= nums.length <= 105
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

【题意】
返回数组中的两个不同的数位置，使得它们的和是target

【思路】
遍历数组中每个数，查target-nums[i]有没有在nums里，这样是O(N^2)

【代码】

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, x in enumerate(nums):
            if target-x in nums:
                idx = nums.index(target-x)
                if idx==i:
                    continue
                else:
                    return([i, idx])

【discussion】
O(N)的做法，一边遍历一边用dict记录这个值出现的位置，不同时存d[m]是因为不允许重复，所以就只记录在遍历到此处之前的数

    def twoSum(self, nums, target):
        d = {}
        for i, n in enumerate(nums):
            m = target - n
            if m in d:
                return [d[m], i]
            else:
                d[n] = i

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

【题意】
实现一个能getMin的栈

【思路】
除了另外开一个minval数组，专门存从开始到每个位置的最小值，其他就没啥了

【代码】

class MinStack:
    def __init__(self):
        self.nums = []
        self.minval = []
    def push(self, x: int) -> None:
        self.nums.append(x)
        if len(self.minval)==0:
            self.minval = [x]
        else:
            self.minval.append(min(x,self.minval[-1]))
    def pop(self) -> None:
        self.nums.pop()
        self.minval.pop()
    def top(self) -> int:
        return self.nums[-1]
    def getMin(self) -> int:
        return self.minval[-1]

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

【题意】
只能抢劫不相邻位置的房子，问最多能得多少

【思路】
DP

【代码】

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums)==0:
            return 0
        dp = nums[::]
        for i, x in enumerate(nums):
            if i-2>=0:
                dp[i] = max(dp[i], dp[i-2]+nums[i])
            if i-1>=0:
                dp[i] = max(dp[i], dp[i-1])
        return dp[-1]

【discussion】
更节省空间的做法

    # Approach 2:- Constant space use two variables and compute the max respectively
    prev = curr = 0
    for num in nums:
      temp = prev # This represents the nums[i-2]th value
      prev = curr # This represents the nums[i-1]th value
      curr = max(num + temp, prev) # Here we just plug into the formula
    return curr

160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

【题意】
给两个链表，他们可能会在最后一部分有交叉（两个轨道汇入一个轨道），返回汇入的这个节点的value，如果没有交叉就返回None，要求时间O(N)空间O(1)

【思路】
第一想法就是遍历一遍把前序节点都找出来，然后反着找最后的交汇点，但是这样空间要多占O(N)。然后想着拆成两条链，先遍历一条扔进set，再看第二条时会遇到set中的值，但发现值不是唯一的，只能判断节点是不是相同而不能判断值。
扫了眼discussion，先把两条链的长度算出来，然后就能知道长的那条要从哪里开始能两条同步找，然后用节点判断。

【代码】

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        def getLen(head):
            cnt = 0
            while head:
                cnt+=1
                head = head.next
            return cnt
        alen = getLen(headA)
        blen = getLen(headB)
        if blen>alen:
            headA, headB = headB, headA
            alen, blen = blen, alen
        diff = alen-blen
        for _ in range(diff):
            headA = headA.next
        while headA:
            if headA==headB:
                return headA
            headA, headB = headA.next, headB.next
        return None

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?

【思路】
没想到O(1)空间的解法
思路就是先遍历一遍得到整条链的长度，然后第二遍搜到一半长度的位置，一边存下前一半的values，然后在后一半和前面的对比。这样是时间O(2N)空间O(N/2)。

【代码】

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        lenth = 0
        now = head
        while now:
            lenth += 1
            now = now.next
        now = head
        vals = []
        for i in range(lenth//2):
            vals.append(now.val)
            now = now.next
        if lenth%2:
            now = now.next
        # print(vals, now.val)
        for i in range(lenth//2):
            if not now.val==vals[-1]:
                return False
            else:
                vals.pop()
                now = now.next
        return True

【discussion】
用walk和run指针的想法走到一半的位置（一个一次走两步一个一次走一步），然后把后一半reverse，就可以比较两条链了。不用担心奇数个的问题，因为后一半这样做完reverse之后相当于是两个不同head的链交汇到mid节点的位置。

def isPalindrome(self, head):
    fast = slow = head
    # find the mid node
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    # reverse the second half
    node = None
    while slow:
        nxt = slow.next
        slow.next = node
        node = slow
        slow = nxt
    # compare the first and second half nodes
    while node: # while node and head:
        if node.val != head.val:
            return False
        node = node.next
        head = head.next
    return True

20. Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
Example 4:
Input: s = "([)]"
Output: false
Example 5:
Input: s = "{[]}"
Output: true
Constraints:
1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

【思路】
经典栈题
觉得简单写的太草率还wa了两次orz 没有判最后栈非空、没有判遍历时遇到栈是空的情况

【代码】

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        dic = {'(':')', '{':'}', '[':']'}
        for x in s:
            if x in dic:
                stack.append(x)
            elif len(stack)==0:
                return False
            elif x==dic[stack[-1]]:
                stack.pop()
            else:
                return False
        if len(stack)!=0:
            return False
        return True

763. Partition Labels

A string S of lowercase English letters is given. We want to partition this string into as many parts as possible so that each
letter appears in at most one part, and return a list of integers
representing the size of these parts.

Example 1:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation: The partition is "ababcbaca", "defegde", "hijhklij". This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

Note:
S will have length in range [1, 500]. S will consist of lowercase
English letters ('a' to 'z') only.

【题意】
给一字符串，要切成尽量多个片段，并使得同个字母只出现在一个片段

【思路】
记录下每个字母第一次出现的位置和最后一次出现的位置，那么他们中间这一段就必然要连在一起了，再进行片段之间的合并

【代码】

class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        dic = {}
        for i in range(len(S)):
            x = S[i]
            if x not in dic:
                dic[x] = [i,i]
            else:
                dic[x][1] = i
        frag = list(dic.values())
        frag.sort()
        # print(frag)
        ans = []
        l, r = frag[0][0], frag[0][2]
        for x in frag[1:]:
            ll, rr = x[0], x[1]
            if ll < r:
                r = max(r, rr)
            else:
                ans.append(r-l+1)
                l, r = ll, rr
        return ans+[len(S)-sum(ans)]

【discussion】

复杂度更低的解法O(N)：遍历两遍，第一遍记录每个字母最后出现的位置，第二遍开始，对于每个看到的字母去查它的最后位置，维护right=max(right,rightmost[now])，直到当前遍历到的就是之前扫过的所有字母的最后位置，说明当前这一段结束了，result+=[...]。

def partition_labels(S):
    rightmost = {c:i for i, c in enumerate(S)}
    left, right = 0, 0
    result = []
    for i, letter in enumerate(S):
        right = max(right,rightmost[letter])
        if i == right:
            result += [right-left + 1]
            left = i+1
    return result

338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
Follow up:
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

【题意】
输出从0到num每个数的二进制表示中1的个数

【思路】
只要这个二进制数去掉一个1，就会得到一个更小的数，而这个更小的数是我们算过的，知道答案，就可以写成 1+ans[更小的数]。还记得 -x&x 可以把x二进制变成只剩最后一个1其他都是0，所以就把这个位置的值去掉，得到 ans[x-(-x&x)]+1。

【代码】

class Solution:
    def countBits(self, num: int) -> List[int]:
        ans = [0 for _ in range(num+1)]
        for x in range(1, num+1):
            if x<=2:
                ans[x]=1
            else:
                ans[x] = ans[x-(-x&x)]+1
        return ans

【discussion】

x & (x-1) 就是给 x 删去最后一个1，所以其实可以直接写作 ans[i] = ans[x & (x-1)] + 1

还有一个挺有趣的做法，就是直接按照1,2,4,8..这样一段一段增加下去，每一段都相当于在前面得到的所有数加上最高位的1，但这样不好的地方就是最坏会到O(2N)

def countBits(self, num):
        iniArr = [0]
        if num > 0:
            amountToAdd = 1
            while len(iniArr) < num + 1:
                iniArr.extend([x+1 for x in iniArr])
        return iniArr[0:num+1]

406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note:
The number of people is less than 1,100.
Example
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

【题意】
在一个队伍中知道每个人的身高和排在他前面的更高或和他一样高的人数，还原出这个队伍

【思路】
按照x[0]降序、x1升序，这样先安排个子高的，然后再排矮的，同样个高的站前面的先安排，此时x1位置的值就是他应该插入的位置

【代码】

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        people = sorted(people, key=lambda x:x[1])
        people = sorted(people, key=lambda x:x[0], reverse=True)
        ans = []
        for x in people:
            idx = x[1]
            if len(ans) < idx+1:
                ans.append(x)
            else:
                ans = ans[:idx]+[x]+ans[idx:]
        return ans

【discussion】
更简洁的写法

def reconstructQueue(self, people):
    people.sort(key=lambda (h, k): (-h, k))
    queue = []
    for p in people:
        queue.insert(p[1], p)
    return queue

46. Permutations

Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

【题意】
给一串数组，输出全排列

【思路】
练习dfs

【代码】

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        length = len(nums)
        def dfs(tmp_l, dic):
            if len(tmp_l)==length:
                ans.append(tmp_l)
                return
            for i in nums:
                if i not in dic:
                    dic[i]=1
                    dfs(tmp_l+[i], dic)
                    dic.pop(i)
        dfs([],{})
        return ans

【discussion】
不用dfs，对于num中每个元素一个个插：每拿到一个新的元素，就把之前已经排好的拎出来插在所有可以插入的位置

def permute(self, nums):
    perms = [[]]   
    for n in nums:
        new_perms = []
        for perm in perms:
            for i in xrange(len(perm)+1):   
                new_perms.append(perm[:i] + [n] + perm[i:])   #insert n
        perms = new_perms
    return perms

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]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = 1
Output: 1
Example 4:
Input: root = [1,2]
Output: [2,1]

【题意】
给一个树 输出中序遍历

【思路】
中序是[左根右] 直接dfs就vans了

【代码】

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if root==None:
            return []
        return self.inorderTraversal(root.left) + [root.val] +  self.inorderTraversal(root.right)

【discussion】
非递归的写法 自己压栈

def inorderTraversal(self, root):
    res, stack = [], []
    while True:
        while root:
            stack.append(root)
            root = root.left
        if not stack:
            return res
        node = stack.pop()
        res.append(node.val)
        root = node.right

739. Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

【题意】
给一个每日温度的列表 输出对于这个列表中的每一天 要等几天会温度变暖

【思路】
最后一天的日子好算就是0 所以从后往前遍历比较好求
维护一个单调栈 从后往前的压栈 如果遇到栈里的数比它小 就可以直接踹掉 因为对于靠前面的日子来说 是不可能指到一个更小还更靠后的数的（后来这个地方wa了 因为题意是需要小于等于都踹掉）
然后这时候栈首-现在这个idx就是所求值，如果栈空就是0

【代码】

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        idx = len(T)-1
        stack = [(T[-1],idx)]
        ans = [0]
        for x in T[-2::-1]:
            idx -= 1
            while len(stack) and x >= stack[-1][0]:
                stack.pop()
            if len(stack)==0:
                ans.append(0)
            else:
                ans.append(stack[-1][3]-idx)
            stack.append((x, idx))
        return ans[::-1]

【discussion】
更简洁的写法 而且其实栈里不需要存value只存idx就好了

  def dailyTemperatures(self, T):
    ans = [0] * len(T)
    stack = []
    for i, t in enumerate(T):
      while stack and T[stack[-1]] < t:
        cur = stack.pop()
        ans[cur] = i - cur
      stack.append(i)
    return ans

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1
Output: ["()"]
Constraints:
1 <= n <= 8

【题意】
输出n对括号能组成的所有valid的字符串

【思路】
dfs 记录现在有多少左括号了 如果 > 0 就能放右括号 如果 < n 就还能放左括号 到最后如果left=0说明是合法的 加入ans

【代码】

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(tmp_s, left):
            if len(tmp_s)==2*n:
                if left==0:
                    ans.append(tmp_s)
                return
            if left>0:
                dfs(tmp_s+")", left-1)
            if left<n:
                dfs(tmp_s+"(", left+1)
        dfs("",0)
        return ans

【discussion】
这样dfs虽然好写 但会有很多重复计算 比如n=3的时候就会重复算n=1+2和n=2+1 好在n不大就没超时
所以这个DP的思路确实很赞 十分奇妙

To generate all n-pair parentheses, we can do the following:

Generate one pair: ()
Generate 0 pair inside, n - 1 afterward: () (...)...
Generate 1 pair inside, n - 2 afterward: (()) (...)...
...
Generate n - 1 pair inside, 0 afterward: ((...))

I bet you see the overlapping subproblems here. Here is the code:
(you could see in the code that x represents one j-pair solution and y represents one (i - j - 1) pair solution, and we are taking into account all possible of combinations of them)

class Solution(object):
    def generateParenthesis(self, n):
        dp = [[] for i in range(n + 1)]
        dp[0].append('')
        for i in range(n + 1):
            for j in range(i):
                dp[i] += ['(' + x + ')' + y for x in dp[j] for y in dp[i - j - 1]]
        return dp[n]

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
3,
1,
2,
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

【题意】
给一个列表 输出所有的子集

【思路】
遍历nums 对于每一个元素都把之前得到的所有子集拿出来把它塞进去

【代码】

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = [[]]
        for x in nums:
            ans += [ a+[x] for a in ans]
        return ans

【discussion】
除了dfs外 还看到一个思路 是把取子集当做是Bit Manipulation
给nums的每个位置赋予0/1 0代表不取1代表取 那么比如当n=3的时候 就相当于i从000遍历到111 (1 << len(nums)）对于0~len(num)-1的这j个位置上 如果是1就把nums[j] append进来

    def subsets(self, nums):
        res = []
        for i in xrange(1<<len(nums)):
            tmp = []
            for j in xrange(len(nums)):
                if i & 1 << j:  # if i >> j & 1:
                    tmp.append(nums[j])
            res.append(tmp)
        return res

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = 1, k = 1
Output: 1
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
You can return the answer in any order.

【题意】
输出列表中出现最多次的前K个元素

【思路】
先遍历一遍把元素个数记下来 然后按照次数sort一下

【代码】

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        for x in nums:
            if x in dic:
                dic[x]+=1
            else:
                dic[x]=1
        dic = sorted(dic.items(), key=lambda x: -x[1])
        ans = []
        for i in range(k):
            ans.append(dic[i][0])
        return ans

【discussion】

最后一步更好的写法

    arr = sorted(dic, key = dic.get,reverse = True)
    return([arr[:k])

另一种思路，为避免sort的O(NlogN)，可以把dict的key和value换一下，key换成次数后就是有范围的，从nums的长度到1，去找前K个，这样就O(N)了

    def topKFrequent(self, nums, k):
        frq = defaultdict(list)
        for key, cnt in Counter(nums).items():
            frq[cnt].append(key)
        res = []
        for times in reversed(range(len(nums) + 1)):
            res.extend(frq[times])
            if len(res) >= k: return res[:k]
        return res[:k]

230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

【题意】
找出二叉搜索树上的第K大元素

【思路】
如果知道左子树的节点个数M，root就是第M+1大。如果K < M，就在左子树继续找，否则就在右子树找第K-(M+1)大。

【代码】

class Solution:
    def cul(self, root):
        if root==None:
            return 0
        return self.cul(root.left)+self.cul(root.right)+1
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        left_num = self.cul(root.left)
        if left_num == k-1:
            return root.val
        elif left_num > k-1:
                return self.kthSmallest(root.left, k)
        else:
            return self.kthSmallest(root.right, k-(left_num+1))

【discussion】
上面那种做法最坏复杂度可能到O(N^2)
其实不用那么复杂，BST按照中序遍历得到的就是从小到大的序列，然后返回列表中的第k个就行了，这样是O(N)

class Solution(object):
    def kthSmallest(self, root, k):
        count = []
        self.helper(root, count)
        return count[k-1]
    def helper(self, node, count):
        if not node:
            return
        self.helper(node.left, count)
        count.append(node.val)
        self.helper(node.right, count)

或者不用存下来，直接在遍历左子树的时候k-=1，当k为0时就得到ans了

def kthSmallest(self, root, k):
    self.k = k
    self.res = None
    self.helper(root)
    return self.res
def helper(self, node):
    if not node:
        return
    self.helper(node.left)
    self.k -= 1
    if self.k == 0:
        self.res = node.val
        return
    self.helper(node.right)

647. Palindromic Substrings

Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Example 2:
Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Note:
The input string length won't exceed 1000.

【题意】
给一字符串 输出所有子串中是回文串的个数

【思路】
遍历，把每个当做中心，然后往周围找，这样是O(N^2)，除了这种奇数个的情况，还得再处理一下偶数

【代码】

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = len(s)
        for i, x in enumerate(s):
            k = min(i, len(s)-i-1)
            for j in range(1, k+1):
                if s[i-j]==s[i+j]:
                    ans += 1
                else:
                    break
        for i, x in enumerate(s):
            if i+1<len(s) and s[i]==s[i+1]:
                ans += 1
                k = min(i, len(s)-i-2)
                for j in range(1, k+1):
                    if s[i-j]==s[i+1+j]:
                        ans += 1
                    else:
                        break
        return ans

【discussion】
DP的写法，dp[i][j]代表这一段是回文

def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        res = 0
        for i in range(n-1, -1, -1):
            for j in range(i, n):
                dp[i][j] = s[i] == s[j] and ((j-i+1) < 3 or dp[i+1][j-1])
                res += dp[i][j]
        return res

有个超级机智的统一奇偶长度的方法，就是在每个字符中间插空加上任意一个符号，对结果没有影响，比如加上“#”，奇偶的情况就是#a#b#a#和#a#b#b#a#，这样统一都变成奇数个了

O(N)的做法，Manacher算法: （知乎的讲解）

    def ManacherAlgm(self, s):
        # Transform S into T.
        # For example, S = "abba", T = "^#a#b#b#a#$".
        # ^ and $ signs are sentinels appended to each end to avoid bounds checking
        T = '#'.join('^{}$'.format(s))
        n = len(T)
        P = [0] * n
        C = R = 0
        for i in range (1, n-1):
            # (R > i) and min(R - i, P[2*C - i]) considering Case1 and Case2
            P[i] = (R > i) and min(R - i, P[2*C - i])
            # Attempt to expand palindrome centered at i
            while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                P[i] += 1
            # If palindrome centered at i expand past R,
            # adjust center based on expanded palindrome.
            if i + P[i] > R:
                C, R = i, i + P[i]
        return (sum(P) + len(s)) // 2

238. Product of Array Except Self

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

【题意】
对于列表中的每个位置，输出整个列表除了该位置的数的乘积，限制是不让用除法

【思路】
算个前缀积和后缀积

【代码】

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        pre = [1]
        suf = [1]
        for x in nums:
            pre.append(pre[-1]*x)
        for x in nums[::-1]:
            suf.append(suf[-1]*x)
        suf.reverse()
        ans = []
        for i in range(len(nums)):
            ans.append(pre[i]*suf[i+1])
        return ans

【discussion】
只用O(1)空间的做法
也是正反两次遍历，维护一个在这个位置需要乘下去的p，比如n=4的时候：
第一遍遍历nums 得到output[-, 0, 01, 012]
第二遍反过来遍历nums 得到output[123, 0 23, 01 3, 012]

    def productExceptSelf(self, nums):
        p = 1
        n = len(nums)
        output = []
        for i in range(0,n):
            output.append(p)
            p = p * nums[i]
        p = 1
        for i in range(n-1,-1,-1):
            output[i] = output[i] * p
            p = p * nums[i]
        return output