日韩不卡在线一本久道,这里只有精品视频8,综合精品激情九色一区

這是我最想寫的一篇文章之一了~ ~~因為這玩意真難......~~

目錄：
算法：附錄
 算法（1）：遞歸
 算法（2）：鏈表
 算法（3）：數(shù)組
 算法（4）：字符串
 算法（5）：二叉樹
 算法（6）：二叉查找樹
 算法（7）：隊列和堆棧（附贈BFS和DFS）
算法（8）：動態(tài)規(guī)劃
 算法（9）：哈希表
 算法（10）：排序
 算法（11）：回溯法
 算法（12）：位操作

例題1：求目標和（Target Sum，在算法（7）堆棧習題3中出現(xiàn)過，這里給出另一種解法）。給定一個數(shù)組以及一個目標數(shù)S，你可以給數(shù)組中每個數(shù)分配運算符‘+’ 或 ‘-’ 其中之一，使得數(shù)組之和為目標S。輸出共有多少種分配方式。
輸入: nums is [1, 1, 1, 1, 1], S is 3.
輸出: 5
解釋:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
代碼解析：使用備忘錄法。

class Solution:
    def findTargetSumWays(self, nums: list, S: int, ) -> int:
        if nums == []:
            return 0
        dic = {nums[0]: 1, -nums[0]: 1} if nums[0] != 0 else {0: 2}
        for i in range(1, len(nums)):
            tdic = {}
            for d in dic:
                tdic[d + nums[i]] = tdic.get(d + nums[i], 0) + dic.get(d, 0)
                tdic[d - nums[i]] = tdic.get(d - nums[i], 0) + dic.get(d, 0)
            dic = tdic
        return dic.get(S, 0)

if __name__ == '__main__':
    nums = [1, 1, 1, 1, 1]
    S = 3.
    solution = Solution()
    steps = solution.findTargetSumWays(nums,S)
    print(steps)

例題2：最大子數(shù)組（Maximum Subarray），給出一個數(shù)組，找到一個連續(xù)的子數(shù)組（至少一個元素），該子數(shù)組有最大和，返回該最大和。
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: [4,-1,2,1] 有最大和，為6.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curSum = maxSum = A[0]
        for num in A[1:]:
            # 這句代碼可以理解成：curSum = num if curSum < 0 else num + curSum
            curSum = max(num, curSum + num)
            maxSum = max(maxSum, curSum)

        return maxSum

例題3：解碼方法（Decode Ways）。
給A到Z編碼如下：

'A' -> 1
'B' -> 2
...
'Z' -> 26

現(xiàn)如今給一個非空字符串，里面由數(shù)字0到9組成，問有多少種解碼方式？
例題：
輸入: "226"
輸出: 3
解釋: "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

注意事項：我當時做這道題的時候忽略了0這個特殊的存在，因為0不對應任何一個字母。比如一個字符串中出現(xiàn)了‘00’，那么該字符串輸出就一定是0......下面給出了兩種代碼，供參考。

class Solution:
    def numDecodings(self, s: str) -> int:
        # v, w, p = 0, int(s>''), ''
        # for d in s:
        #     v, w, p = w, (d>'0')*w + (9<int(p+d)<27)*v, d
        # return w
        # w tells the number of ways
        # v tells the previous number of ways
        # d is the current digit
        # p is the previous digit
    
    
        #dp[i] = dp[i-1] if s[i] != "0"
        #       +dp[i-2] if "09" < s[i-1:i+1] < "27"
        if s == "": return 0
        dp = [0 for x in range(len(s)+1)]
        dp[0] = 1
        for i in range(1, len(s)+1):
            if s[i-1] != "0":
                dp[i] += dp[i-1]
            if i != 1 and "09" < s[i-2:i] < "27":  #"01"ways = 0
                dp[i] += dp[i-2]
        return dp[len(s)]

例題4：丑數(shù)，丑數(shù)為只能被2，3，5整除的數(shù)（1定義為第一個丑數(shù)），輸入一個整數(shù)n，輸出第n個丑數(shù)。
輸入：10
輸出：12（前十個丑數(shù)序列：1, 2, 3, 4, 5, 6, 8, 9, 10, 12）
代碼解釋：用了三指針技術(shù)，對每個丑數(shù)再乘以2，3或5就是新的丑數(shù)，但是為了使得輸出有序，需要三個指針來記錄位置。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1]
        i2, i3, i5 = 0, 0, 0
        while n > 1:
            u2, u3, u5 = 2 * ugly[i2], 3 * ugly[i3], 5 * ugly[i5]
            umin = min((u2, u3, u5))
            if umin == u2:
                i2 += 1
            if umin == u3:
                i3 += 1
            if umin == u5:
                i5 += 1
            ugly.append(umin)
            n -= 1
        return ugly[-1]

例題5：最長遞增子序列（Longest Increasing Subsequence），給出一個未排序的整型數(shù)組，返回其最長遞增子序列長度。
輸入: [10,9,2,5,3,7,101,18]
輸出: 4 （其中最長遞增子序列為[2,3,7,101]）
代碼解釋：(下文sub 數(shù)組里存放的元素可能不是實際的遞增子序列，但其長度是準確的)

leetcode（Longest Increasing Subsequence）

initial sub = [ ].
traversing the nums:
a) if val > sub's all elements, then subsequence length increased by 1, sub.append(val);
b) if sub[i-1] < val < sub[i], then we find a smaller value, update sub[i] = val. Some of the elements stored in the sub[ ] are known subsequences, and the other part is elements of other possible new subsequences. However, the length of the known subsequences is unchanged.
return the sub[ ]'s length.

Here is the solution's track, as we have nums = [8, 2, 5, 1, 6, 7, 9, 3],when we traversing the nums:

i = 0, sub = [8]
i = 1, sub = [2]
i = 2, sub = [2, 5]
i = 3, sub = [1, 5], # element has been changed, but the sub's length has not changed.
i = 4, sub = [1, 5, 6]
i = 5, sub = [1, 5, 6, 7]
i = 6, sub = [1, 5, 6, 7, 9]
i = 7, sub = [1, 3, 6, 7, 9] #done! Although the elements are not correct, but the length is correct.

Because of sub[ ] is incremental, we can use a binary search to find the correct insertion position.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # O(nlogn) solution with binary search
        def binarySearch(sub, val):
            lo, hi = 0, len(sub)-1
            while(lo <= hi):
                mid = lo + (hi - lo)//2
                if sub[mid] < val:
                    lo = mid + 1
                elif val < sub[mid]:
                    hi = mid - 1
                else:
                    return mid
            return lo

        sub = []
        for val in nums:
            pos = binarySearch(sub, val)
            if pos == len(sub):
                sub.append(val)
            else:
                sub[pos] = val
        return len(sub)

我先把常見問題寫在這，省的日后忘了：