leetcode-357-Count Numbers with Unique Digits

lansheng228 发布于2019-07-30 17:36 / 909人阅读

摘要：此模型的特殊性相邻的三个值可以得到一个爆破值，相邻的两个值相当于没有值，赋予类比二分法求极值。通过二分确定具体的位置。此处二分法到极值是三个连续的数，从相邻三个数的固定值，逐次放宽范围，确定越来越宽的爆破值。

此题的总结：    
求解 最大爆破值， 是一个 倒序 二分法问题，最终的原子结构是连续的三个数。
连续的三个数，可以 往上递推 间隔一个数的三个数，间隔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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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