9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element

1617-卿同学

发表文章数:84

热门标签

首页 » MySQL » 正文

9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element

 平衡二叉树专题 – 将二叉搜索树变平衡 – 力扣(LeetCode) (leetcode-cn.com)9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency elementhttps://leetcode-cn.com/problems/balance-a-binary-search-tree/solution/ping-heng-er-cha-shu-zhuan-ti-by-fe-lucifer-4/

# 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 balanceBST(self, root: TreeNode) -> TreeNode:
        order = []
        def inorder(node):
            if not node:
                return
            nonlocal order
            inorder(node.left)
            order += [node.val]
            inorder(node.right)
        
        inorder(root)
        print(order)
        def constructtree(nodelist):   #[1,2,3]
            if not nodelist:
                return
            if len(nodelist) == 1:
                return TreeNode(nodelist[0])
            mid = len(nodelist) // 2  #1
            node = TreeNode(nodelist[mid])
            print(nodelist[:mid])
            print(nodelist[mid:])
            node.left = constructtree(nodelist[:mid])    #[1]
            node.right = constructtree(nodelist[mid+1:])   #[2,3]
            return node
        return constructtree(order)
        

9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element

 倍增法

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        if dividend == 0:
            return 0
        if dividend == 2**31 and divisor == 1:
            return 2**31 - 1
        if dividend == -2**31 and divisor == -1:
            return 2**31 - 1
            
        flag = 0
        if (dividend >0 and divisor <0) or (dividend <0 and divisor >0):
            flag = 1
        ans = 0
        dividend = abs(dividend)
        divisor = abs(divisor)
        remain = dividend
        div = divisor
        while remain >= divisor:
            cur = 1
            div = divisor
            while div+div < remain:
                div += div
                cur += cur
            remain -= div
            ans += cur
        
        return ans if flag == 0 else -ans

9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        numdict = collections.Counter(nums)
        print(numdict)
        numlist = []
        for key,value in numdict.items():
            numlist.append([value,key])
        numlist.sort(reverse = True)
        print(numlist)
        ans = []
        for i in range(k):
            ans.append(numlist[i][1])
        return ans
            
            
            

动态规划:9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element

思路:

用一个dp数组记录到某一天花费最少的钱

那么每到达一个位置首先考虑当前天数是否在days 中,如果不在那花费的费用肯定和它前一天花费的最少费用相同

如果今天在days数组里的话,那么今天必须要花钱。3种方式买今天的票:

我们就要从三种购买方式中选择一种花费费用最少的,即你想到达第 i 天,你需要从 i 的前1或7或30天的后一位置花费对应cost[0]、cost[1]、cost[2]的钱才能到第 i 天。

dp[i] = min(dp[max(0,i-1)] + costs[0],
                dp[max(0,i-7)] + costs[1],
                dp[max(0,i-30)] + costs[2])
class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        dp = [0]*(days[-1]+1)
        days_index = 0
        for i in range(1,len(dp)):
            if days[days_index] != i:
                dp[i] = dp[i-1]
            else:
                dp[i] = min(dp[max(0,i-1)] + costs[0],
                dp[max(0,i-7)] + costs[1],
                dp[max(0,i-30)] + costs[2])
                days_index += 1
        return dp[-1]
            

9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element

括号题目:若是答案只要求数字,则只需要+1,-1操作

若是答案需要输入括号的字符串,则用stack来做

class Solution:
    def minAddToMakeValid(self, s: str) -> int:
        ans = 0
        count = 0
        for char in s:
            if char == '(':
                count += 1
            else:
                count -= 1
            print(count)
            if count < 0:
                ans -= count
                count = 0
        ans += count
        return ans

9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element

对角线相等题: 

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        for i in range(m):
            a,b = i,0
            num = matrix[a][b]
            a += 1
            b += 1
            while a
标签:

未经允许不得转载:作者:1617-卿同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《9/26:记得重做。平衡二叉树,两数相除,minimum cost ticket[dp], top k frequency element》 发布于2021-09-30

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
  • 去评论
  • QQ咨询
  • 去顶部

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录