题解

[maiff]

动态规划

983. Minimum Cost For Tickets

• 考虑动态规划不能死板反向考虑，应该按照题目的方法，这题我在思考的时候在加天数的时候方向思考反了，好好审题
• @lru_cache(None) python这个是个好东西

935. Knight Dialer

• 求数求种类高清楚题目让求啥往那方面想，题目说求啥，你就求啥往那方面想
• 注意多维数组初始化
• 节省空间
• 递推式还是很重要

303. Range Sum Query - Immutable

这就是个数学题出的不好，但是以后记得求中间和可以用前面的和减后面和

1021. Best Sightseeing Pair

注意求解问题，可以先转化为部分问题求解，就像求数学题一样

1023.

 def camelMatch(self, qs, p):
        def u(s):
            return [c for c in s if c.isupper()]

        def issup(s, t):
            it = iter(t)
            return all(c in it for c in s)
        return [u(p) == u(q) and issup(p, q) for q in qs]

注意这里iter的迭代情况

873. Length of Longest Fibonacci Subsequence

 longest = collections.defaultdict(lambda: 2)
# dict's key can be tupe

动态规划双向考虑一下

300 最长递增子序列

我发现上题不用反过来也可以解。
这个可以用一个o(nlogn)的算法，维护一个数组，遍历原数组

1. 如果这个数比这个数组大，append
2. 如果这个数有比他大的就找到刚好比他大的那个替换
   2019.4.24日添加：
   这类题目是个特点
   寻找子数组，子数组满足一些关系就可以抽象成这种题目的思想，如果这种关系是可以传递的** 求长度 ** 比 求数组要简单的多 如果关系不是传递的求长度则要麻烦很多，也是一道典型的dp题，维护一个数组不断求解
   同理求解 369

def largestDivisibleSubset(self, nums):
    S = {-1: set()}
    for x in sorted(nums):
        S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
    return list(max(S.values(), key=len))

376. Wiggle Subsequence
     这题也可以归结为300题，不过这题只是其中一个性质才是对的，而且第二个循环正向遍历，不能反向遍历因为这个子序列其中一个一定包括第一个元素，正向一定是对的。并且每个dp元素持有最大的一定是对的。

304. Range Sum Query 2D - Immutable

对于有sqare的题目，使用数组缓存需要+1，一维数组可以用后缀数组求和
二维同样也可以

dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + matrix[i][j] - dp[i][j]

309. Best Time to Buy and Sell Stock with Cooldown

这题用动态规划是o(n^2)如果不加if条件就会超时，还有种n的方法用的广度优先搜索

357. Count Numbers with Unique Digits

遇到 这种题真的……就是个排列组合的问题

264. Ugly Number II

跟 309的思想差不多，在动态规划中维护了前几个好几个状态

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        k = [1] *n
        
        t2,t3,t5 = 0,0,0
        
        for i in range(1,n):
            k[i] = min(k[t2]*2, k[t3]*3, k[t5]*5)
             
            if k[i] == k[t2] * 2:
                t2+=1
            if k[i] == k[t3] * 3:
                t3+=1
            if k[i] == k[t5] * 5:
                t5+=1
            
        return k[-1]

416. Partition Equal Subset Sum
     注意转化问题，subsetSum为整个 array的一半
     然后最大的和的dp数组，dp[0]=1 遍历每个数，逆序遍历 dp如果存在 dp[sum+num]=1，为什么要逆序，就是防止这次更改了dp的影响

417. Can I Win
     就是搜索，加memo

418. Unique Substrings in Wraparound String

from functools import lru_cache
class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        res = {i: 1  for i in p}
        
        l = 1
        
        for i,j in zip(p,p[1:]):
            l = l + 1 if (ord(j) - ord(i))%26 == 1 else 1
            
            res[j] = max(res[j], l)
            
        return sum(res.values())
    
    
    # 想清楚 dp的状态是哪一个 这题是以什么字母为结尾
    # 最优子结构之间的关系这种
    # 只要得到最大的去重这步自然就解决了，因为对于相同字母结尾有相同顺序的一定有一样的结构按顺序的精妙！

像413. Arithmetic Slices
这种dp中安某种顺序序列增长的个数dp问题，一般都为O(n)解法，并且dp[i]= dp[i-1]+1 if some true else 1

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance
      
      所以k一定是在外层循环
      同时这是个多源的遍历一遍，把所有节点之间的最短路径都得到了，而diksj那种算法不行。

[maiff]

486. Predict the Winne
     注意题意，明白胜利条件，可以存着你想不到的状态，比如这题存的是两个分数的插值。

487. Target Sum
     典型的dp
     intuition:
     dp[n] = dp[n-1]组合nums[n]
     但是这样的复杂度是O(2^n)
     可以把问题抽象，把目的结果组合起来，根据题意得到dp过程中符合题意的结果可以把复杂度控制在O(n*l)上l为可能答案所有的可能

[maiff]

516. Longest Palindromic Subsequence
     问题还是要把dp的式子写出来，然后考虑这次的状态是否只是依赖上几次的状态而不是所有之前的dp

[maiff]

740. Delete and Earn
     dp问题可能不是全局的考虑可能可以遍历每个元素，按个考虑清楚，就是每个dp的状态

[maiff]

787. Cheapest Flights Within K Stops

      f = collections.defaultdict(dict)
        for s, e, d in flights:
            f[s][e] = d
            
        heap = [(0, src, K+1)]
        while heap:
            d, s, k = heapq.heappop(heap)
            if s == dst:
                return d
            
            if k>0:
                for e in f[s]:
                    heapq.heappush(heap, (d+f[s][e], e, k-1))
        
        return -1

思路没有什么好说的就是最短路径算法加上边，
主要是python的语法：

1. collections.setdefaultdict(dic)
2. heapq 的元素可以为tuple，排序按第一个元素定

[maiff]

955. Delete Columns to Make Sorted II

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        res, m , n = 0, len(A[0]), len(A)
        so = [0]*n
        # 注意 m跟n
        # 注意so的代表着什么，代表着第i个字符，前一个字符串跟后一个字符串是否小于等于或者相等，因为只有小于等于的时候或者相等的时候要比下一个
        # 如果上一个不符合排序，当前比，如果也不符合就要删除
        
        for i in range(m):
            
            so2 = so[:]
            for j in range(n-1):
                
                if A[j][i] > A[j+1][i] and so[j] == 0:
                    res+=1
                    break
                
                so2[j] |= A[j][i] < A[j+1][i]
            else:
                so = so2
            
        return res

[maiff]

1130. Minimum Cost Tree From Leaf Values
      最开始写的时候没有搞清楚题意，但是在dp的递推式写出来的时候也能写出来代码，但是在看到别人的题解的时候发现我之前的直觉是对的，肯定有更简单的方法。

因为是中序序列，方法是只要加进来的比上一个大，就需要把上次小的pop出来因为他已经不参与之后的计算了，同理如果一直都大都不参与计算了，然后pop的时候要计算pop的cost是跟左边乘还是跟右边

    def mctFromLeafValues(self, A):
        res, n = 0, len(A)
        stack = [float('inf')]
        for a in A:
            while stack[-1] <= a:
                mid = stack.pop()
                res += mid * min(stack[-1], a)
            stack.append(a)
        while len(stack)  >2:
            res += stack.pop() * stack[-1]
        return res

来源

[maiff]

1234. Replace the Substring for Balanced String
      滑动窗口

class Solution:
    def balancedString(self, s: str) -> int:
        count = collections.Counter(s)
        
        res = n = len(s)
        i = 0
        
        for j, v in enumerate(s):
            count[v] -= 1
            
            while i < n and  all(count[c] <= (n // 4) for c in 'QWER'):
                res = min(res, j-i+1)         
                
                count[s[i]] += 1
                #print(i,j,count,n//4)
                i+=1
                
        return res

https://docs.python.org/zh-cn/3/library/collections.html

1248. Count Number of Nice Subarrays
1249. Subarrays with K Different Integers
1250. 滑动窗口一般动前面的游标，每次的结果可以根据当前情况下直接推出。不依赖之前结果。
1251. 注意问题转化

[maiff]

287. Find the Duplicate Number
     bit map
     移位操作可以当成O(1)

def findDuplicate(self, nums: List[int]) -> int:
        mask = 0
        for i in nums :
            bit = 1<<i
            if bit & mask :
                return i
            mask |= bit

快慢指针

class Solution:
    def findDuplicate(self, nums):
        # Find the intersection point of the two runners.
        tortoise = nums[0]
        hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            print(tortoise, hare)
            if tortoise == hare:
                break
        
        ptr1 = nums[0]
        ptr2 = tortoise
        while ptr1 != ptr2:
            ptr1 = nums[ptr1]
            ptr2 = nums[ptr2]
        
        return ptr1

最后一次循环

才理解这个intersection point。 相交点一定是环上的点，但不一定是入口。假设链表从头部到环入口前一个点一共a个点，环上一共b个点，那么每一步龟兔的距离都会加一，相交点一定是入口点向后(b-a)个的点。 然后从起点前进a步到达入口，相交点前进a步正好也回到入口。

设在环上走了x
慢走了a+x
快走了2a+2x
环上快走了a+2x
a+2x-b=x
x=b-a
所以再来一次刚好在入口相遇

[maiff]

39 -> 40 -> 77 -> 78 -> 90 -> 216,
you can basically solve every single Combination problem.
39.Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.

res = []
        self.dfs(candidates, target, [], res)
        return res


    def dfs(self, nums, n, path, res):
        if n < 0:  # backtracking
            return
        if n == 0:
            res.append(path)
        for i in range( len(nums)):
            self.dfs(nums[i:], n-nums[i], path+[nums[i]], res) # 注意nums[i:]避免重复的集合，以后的序列不能选择之前的

40. 每个只能用一次，但是会有重复的元素，保证set不能重复，这里的重复来自与同样的元素

        candidates = sorted(candidates)
        res  = []
        self.dfs(candidates, target, [], res,0)
        return res
    
    def dfs(self, nums, n, path, res,index):
        if n < 0:
            return
        elif n == 0:
            res.append(path)

        for i in range(len(nums)):
            if i >0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[i+1:], n-nums[i], path+[nums[i]], res,index+1)        

77 Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

def combine(self, n: int, k: int) -> List[List[int]]:

        res = []
        self.dfs(list(range(1,n+1)), k, [], res)
        return res

    def dfs(self, nums, k, path, res):
        if k == 0:
            res.append(path)
        
        for i in range(len(nums)):
            self.dfs(nums[i+1:], k-1, path+[nums[i]], res)

78.Given a set of distinct integers, nums, return all possible subsets (the power set).

    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        res.append(path)
        if len(nums) == 0:
            return
        # print(nums, path, res)
        for i in range(len(nums)):
            print(i)
            self.dfs(nums[i+1:], path+[nums[i]], res)
     

90. Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums = sorted(nums)
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        res.append(path)
        if len(nums) == 0:
            return
        # print(nums, path, res)
        for i in range(len(nums)):
            if i>0 and nums[i] == nums[i-1]:
                continue
            self.dfs(nums[i+1:], path+[nums[i]], res)

216.dfs

def combinationSum3(self, k, n):
    res = []
    self.dfs(xrange(1,10), k, n, 0, [], res)
    return res
    
def dfs(self, nums, k, n, index, path, res):
    if k < 0 or n < 0: # backtracking 
        return 
    if k == 0 and n == 0: 
        res.append(path)
    for i in xrange(index, len(nums)):
        self.dfs(nums, k-1, n-nums[i], i+1, path+[nums[i]], res)

[maiff]

def daysBetweenDates(year1, month1, day1, year2, month2, day2):
	# 判断日期是否大于3月并且记录到3月的间隔天数
    m1 = (month1 + 9) % 12
    # 如果月份为1月或2月，则不包括当前年
    y1 = year1 - m1/10
    #  y1/4 - y1/100 + y1/400是加所有闰年多出的那一天
    # (m2*306 + 5)/10用于计算到当前月到3月1日间的天数,306=365-31-28(1月和2月的总天数)
    d1 = 365*y1 + y1/4 - y1/100 + y1/400 + (306*m1 + 5)/10 + day1 - 1
    
    m2 = (month2 + 9) % 12
    y2 = year2 - m2/10
    d2 = 365*y2 + y2/4 - y2/100 + y2/400 + (306*m2 + 5)/10 + day2 - 1
    
    return d2 - d1

[maiff]

树形数组:
ask操作：

[maiff]

https://blog.csdn.net/zhengjihao/article/details/73610609
这是坐凳子所以是排列问题

[maiff]

0-1背包问题
由f(i,j)=max{f(i-1,j),f(i-1,j-v[i]+w[i]}
因为fi只依赖fi-1
所以可以优化成一维数组，
但是要逆序求解，因为 j如果从小到大会覆盖之前的j，必须从大到小
另一道滚动数组的题
https://blog.csdn.net/a909301740/article/details/79940697

[maiff]

In [14]: def a(s, arr):
    ...:     q,k = 1,0
    ...:     m = len(s)
    ...:     arr[0] = 0
    ...:     for q in range(1, m):
    ...:         while k>0 and s[q] != s[k]:
    ...:             print(k,q, arr)
    ...:             k = arr[k-1]
    ...:         if s[q] == s[k]:
    ...:             k+=1
    ...:         arr[q] = k
    ...:

In [15]: a(s,arr)
2 4 [0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0]
4 10 [0, 0, 1, 2, 0, 0, 1, 2, 3, 4, 0]

In [16]: s
Out[16]: 'sasapqsasas'

In [17]: arr
Out[17]: [0, 0, 1, 2, 0, 0, 1, 2, 3, 4, 3]

　　已知前一步计算时最大相同的前后缀长度为k（k>0），即P[0]···P[k-1]；
　　此时比较第k项P[k]与P[q],如图1所示
　　如果P[K]等于P[q]，那么很简单跳出while循环;
　　关键！关键有木有！关键如果不等呢？？？
因为0-k-1 和 q-k q-k-1相同 因为最后一位不同我们要缩小范围，就是在 0-k-1中找到与前缀相同的匹配就可以完成匹配了，
'sasapqsasas'
最后一位s与p不相等
又因为sasa sasa是相等的，但是 我们不能要全部只能要一部分，怎么要这一部分，因为我们之前已经找到了前缀字符，所以找这一部分与前缀相同的就好如果还不相同继续递归