leetcode-357-Count Numbers with Unique Digits

lansheng228 發布于2019-07-30 17:36 / 941人閱讀

摘要：此模型的特殊性相鄰的三個值可以得到一個爆破值，相鄰的兩個值相當于沒有值，賦予類比二分法求極值。通過二分確定具體的位置。此處二分法到極值是三個連續的數，從相鄰三個數的固定值，逐次放寬范圍，確定越來越寬的爆破值。

此題的總結：    
求解 最大爆破值， 是一個 倒序 二分法問題，最終的原子結構是連續的三個數。
連續的三個數，可以 往上遞推 間隔一個數的三個數，間隔n個數的三個數
特點在于：每一次遞推，都有可能改變當前槽位值，因為，i，j不變，由于間隔變化，變得是取得間隔點。
局部最優公式：  dpi=max(dpi,nums[i]nums[center]nums[j]+dpi+dpcenter)
應用:  推理，后面的依賴于前面的，可以用二分法。  三個變量的dp，需要考慮迭代自身位置的值，只用兩個索引。

    此模型的特殊性： 相鄰的三個值可以得到一個爆破值， 相鄰的兩個值相當于沒有值，賦予0.
類比：二分法求極值。 通過二分確定具體的位置。 此處 二分確定確定之前的最大爆破值。
    二分法求極值的兩個值想等。  邊界值：長度不滿足要求，說明不在計量范圍內，可以賦予0.
    編輯距離：從前到后，遍歷，依次求最小的移動距離。   此處 二分法到極值是三個連續的數，從相鄰三個數的固定值，逐次放寬范圍，確定越來越寬的爆破值。
總結：dp的應用，相鄰作為局部，跳躍位置作為局部

class Solution(object):
    def maxCoins(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        assert isinstance(nums,list)
        nums.insert(0,1)
        nums.append(1)
        # row=[0]*len(nums)
        length=len(nums)
        max_coins=[[0]*length for _ in range(length)]
        # print(nums)
        # print(max_coins)
        for k in range(2,length):
            for index_i,i in enumerate(nums[:length-k]):
                index_j=index_i+k
                # print(index_i,index_j)
                for i in range(index_i+1,index_j):
                    elem1=max_coins[index_i][index_j]
                    print(index_i,i,index_j)
                    elem2=max_coins[index_i][i]+max_coins[i][index_j]+nums[index_i]*nums[i]*nums[index_j]
                    max_coins[index_i][index_j]=max(elem1,elem2)
        # print(max_coins)
        return max_coins[0][-1]


if __name__=="__main__":
    st=Solution()
    input_list=[3, 1, 5, 8]
    out=st.maxCoins(input_list)
    print(out)

GPU云服務器云服務器 Numbers Digits unique Mysql_unique

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/42306.html

357. Count Numbers with Unique Digits

摘要：題目鏈接和安卓解鎖那道題很想，那道題步數是到，這道題是到，表示數字的位數。，每次要記錄走到的位數作為，從開始。注意最后的情況，只有一位的時候算上，一位以上，首位都不可以是。滾動數組優化空間到 357. Count Numbers with Unique Digits 題目鏈接：https://leetcode.com/problems... 和安卓解鎖那道題很想，那道題步數是m到n，h...

liukai90 2019-08-14 17:25 評論0 收藏0
Sequelize Model

摘要：定義默認值和是否為空默認時間為創建時間設置為將會在數據表中添加列如果查詢時該列為數據庫會拋出錯誤如果你想在查詢前檢查該值是否為，看一下下面的驗證部分可以是或如果多個列是相同就會變成會創建索引也可以這么創建索引主鍵自動增量在可以有可以通過屬性定義Model import sequelize from sequelize var Foo = sequelize.define(foo, ...

andong777 2019-08-21 14:34 評論0 收藏0
30s js代碼片段翻譯

摘要：可否被整除使用模運算符來檢查余數是否等于。數值增加序號后綴使用模運算符來查找單位數和十位數的值。這是對 github 上30s代碼片段的翻譯整理，由于作者的文檔是通過腳本生成的，也就懶得去提pull了，整理了放到博客上供大家學習參考，后續會持續跟進翻譯。 Array Array concatenation (合并參數) 使用 Array.concat() 來連接參數中的任何數組或值。...

sevi_stuo 2019-08-22 13:46 評論0 收藏0
[LeetCode] 37. Sudoku Solver

Problem Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row.Each ...

alaege 2019-08-19 11:14 評論0 收藏0