GBDT

vllbc 发布于 2021-01-06 收录于 Machine Learning 集成学习 Boosting

梯度提升决策树(GBDT)

GBDT(Gradient Boosting Decision Tree)是一种迭代的决策树算法，由多棵决策树组成，所有树的结论累加起来作为最终答案。

回归树

选择最优切分变量j与切分点s：遍历变量j，对规定的切分变量j扫描切分点s，选择使下式得到最小值时的(j,s)对。其中Rm是被划分的输入空间， \(\mathrm{cm}\) 是空间Rm对应的固定输出值。

两两交换链表中的节点

vllbc 发布于 2021-01-03 收录于算法题

两两交换链表中的节点

题目：

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

思路:

先把第二位储存起来，然后将后面的递归操作后，再把第二位指向第一位，完成换位

代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution: #假设为[1,2,3,4]
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next: #递归出口
            return head
        newnode = head.next #储存第二位2
        head.next = self.swapPairs(head.next.next) #此时为[1,4,3]
        newnode.next = head #[2,1,4,3]
        return newnode

种花问题（新年快乐!2021第一题）

vllbc 发布于 2021-01-01 收录于算法题

种花问题（新年快乐!2021第一题）

新年快乐！2021年第一题，每日一题！希望2021年LC和github可以全绿！加油！

https://leetcode-cn.com/problems/can-place-flowers/

代码如下：

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        flowerbed = [0] + flowerbed + [0]
        for i in range(1,len(flowerbed)-1):
            if flowerbed[i-1] == 0 and flowerbed[i] == 0 and flowerbed[i+1] == 0:
                n -= 1
                flowerbed[i] = 1
        return n <= 0

思路很暴力，就是三个0在一起就可以插进去。。

零钱兑换

vllbc 发布于 2020-10-10 收录于算法题

零钱兑换

https://leetcode-cn.com/problems/coin-change/

以我目前的水平做出来有点吃力，看了思路才做出来

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(amount+1):
           for coin in coins: #
               if i >= coin:
                   dp[i] = min(dp[i],dp[i-coin]+1)
        
        return -1 if (dp[-1] == float("inf")) else dp[-1]

伪代码如下

# 伪码框架
def coinChange(coins: List[int], amount: int):

    # 定义：要凑出金额 n，至少要 dp(n) 个硬币
    def dp(n):
        # 做选择，选择需要硬币最少的那个结果
        for coin in coins:
            res = min(res, 1 + dp(n - coin))
        return res

    # 题目要求的最终结果是 dp(amount)
    return dp(amount)

去除重复字母

vllbc 发布于 2020-09-02 收录于算法题

去除重复字母

一开始看到题目感觉挺简单的，没想到对现在的我挺有难度。。

https://leetcode-cn.com/problems/remove-duplicate-letters/

#1
class Solution:
    def removeDuplicateLetters(s: str):
        res = ""
        while s: #用递归也可以
            loc = min(map(s.rindex,s)) #s.rindex是返回列表各值最后出现的索引 求这个最小的索引
            a = min(s[:loc+1]) #求字典序最小的
            res += a
            s = s[s.index(a):].replace(a,"") #把已经加入的和与其重复的都去掉了
        return res



#2
#遍历字符串，压入栈，如果遇到比栈顶小的元素且当前字符后面还有与栈顶相同的元素时，移除栈顶元素
class Solution:
    def removeDuplicateLetters(s: str) -> str:
        stack = []
        for i, t in enumerate(s):
            if t in stack:
                continue
            while stack !=[] and t < stack[-1] and s[i:].find(stack[-1]) != -1:
                stack.pop()
            stack.append(t)
        return "".join(stack)

两个方法，第二个方法更好想点。第一个方法是copy的

作者发布于 0001-01-01

        
Table file.mtime as "最后修改时间"
WHERE tags[0] = "Reading" and date(today) - file.mtime <= dur(7 days)
Sort file.mtime desc

作者发布于 0001-01-01

        
Table rows.file.link as filename
WHERE todo and title != "<% tp.file.title %>"
Sort file.ctime desc
GROUP BY tags[1] as "category"

作者发布于 0001-01-01

        
Table file.mtime as "最后修改时间"
WHERE !todo and date(today) - file.mtime <= dur(7 days) and tags[0] != "Reading" and title
Sort file.mtime desc