vllbc02
所有文章 标签 分类 关于
vllbc02
/images/avatar.png

vllbc

至少有k个重复字符的最长字串

 发布于  收录于 算法题

至少有k个重复字符的最长字串

题目：

https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters/

思路：

利用递归，如果s中字符c的数目小于k,则以c作分割，分成的字串再次调用函数形成递归，然后从众多结果中找寻最大长度的。

代码：

class Solution(object):
    def longestSubstring(self, s, k):
        if len(s) < k:
            return 0
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)
阅读全文
 算法题, 至少有k个重复字符的最长字串

最长递增子序列

 发布于  收录于 算法题

最长递增子序列

题目：

https://leetcode-cn.com/problems/longest-increasing-subsequence/

思路：

动态规划 定义dp[i]为到nums[i]的最长递增子序列的长度，全部都初始化为1,因为本身就是长度为1的递增子序列

代码：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for _ in range(len(nums))]
        for i in range(1,len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)
阅读全文
 算法题, 最长递增子序列

外观数列

 发布于  收录于 算法题

外观数列

https://leetcode-cn.com/problems/count-and-say/

这题有意思

可以打表，不过打表的过程也相当于做出来了

class Solution:
    def countAndSay(self,n: int) -> str:
        if n == 1:
           return '1'
        s = self.countAndSay(n - 1)
        n,res = 0,''
        for ii,ss in enumerate(s):
            if ss != s[n]:
                res += str(ii-n) + s[n]
                n = ii
        res += str(len(s) - n) + s[-1]
        return res
print(Solution().countAndSay(3))

思路：

​ 递归，将上一层计算出来的东西作为迭代对象。

阅读全文
 算法题, 外观数列

NER

 发布于  收录于 NLP

NER(命名实体识别)

参考：https://www.jianshu.com/p/16e1f6a7aaef

命名实体识别（Named Entity Recognition，简称NER）是信息提取、问答系统、句法分析、机器翻译等应用领域的重要基础工具，在自然语言处理技术走向实用化的过程中占有重要地位。一般来说，命名实体识别的任务就是识别出待处理文本中三大类（实体类、时间类和数字类）、七小类（人名、机构名、地名、时间、日期、货币和百分比）命名实体。  举个简单的例子，在句子“小明早上8点去学校上课。”中，对其进行命名实体识别，应该能提取信息

阅读全文
 NLP, NER

打家劫舍

 发布于  收录于 算法题

打家劫舍

打家劫舍I

题目：

https://leetcode-cn.com/problems/house-robber/

思路:

一个简单题，不过踩了特例的坑。。可以暴力解决 也可以动态规划

代码:

暴力解决

class Solution:
    def rob(nums):
        if nums == []:
            return 0
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums[0],nums[1])
        maxs = [] #max[i]代表到i+1家的最大价钱
        maxs.append(nums[0])
        maxs.append(nums[1])
        for i in range(2,len(nums)):
            maxs.append(max(maxs[:i-1])+nums[i]) #从头到这家前面的第二家最大的价钱加上这一家的价钱
        return max(maxs)

动态规划

class Solution:

    def rob(self, nums: List[int]) -> int:

        if len(nums) <= 2:

            return max(nums)

        dp = [0] * len(nums)

        dp[0], dp[1] = nums[0], max(nums[0], nums[1])

        for i in range(2, len(nums)):

            dp[i] = max(dp[i-1], dp[i-2] + nums[i])

        return max(dp)

打家劫舍II

题目：

https://leetcode-cn.com/problems/house-robber-ii/

阅读全文
 算法题, 打家劫舍

thread

 发布于  收录于 Python
import threading
import time

简单的创建

def run(n):
    print("task", n)
    time.sleep(1)
    print('2s')
    time.sleep(1)
    print('1s')
    time.sleep(1)
    print('0s')
    time.sleep(1)

if __name__ == '__main__':
    t1 = threading.Thread(target=run, args=("t1",))
    t2 = threading.Thread(target=run, args=("t2",))
    t1.start()
    t2.start()

通过类创建

class MyThread(threading.Thread):
    def __init__(self, n):
        super(MyThread, self).__init__()  # 重构run函数必须要写
        self.n = n

    def run(self):
        print("task", self.n)
        time.sleep(1)
        print('2s')
        time.sleep(1)
        print('1s')
        time.sleep(1)
        print('0s')
        time.sleep(1)

if __name__ == "__main__":
    t1 = MyThread("t1")
    t2 = MyThread("t2")
    t1.start()
    t2.start()

对比没有join()和join()的区别

def run(n):
    print("task", n)
    time.sleep(1)       #此时子线程停1s
    print('3')
    time.sleep(1)
    print('2')
    time.sleep(1)
    print('1')

if __name__ == '__main__':
    t = threading.Thread(target=run, args=("t1",))
    t.setDaemon(True)   #把子进程设置为守护线程，必须在start()之前设置
    t.start()
    print("end")
def run(n):
    print("task", n)
    time.sleep(1)       #此时子线程停1s
    print('3')
    time.sleep(1)
    print('2')
    time.sleep(1)
    print('1')

if __name__ == '__main__':
    t = threading.Thread(target=run, args=("t1",))
    t.setDaemon(True)   #把子进程设置为守护线程，必须在start()之前设置
    t.start()
    t.join() # 设置主线程等待子线程结束
    print("end")

锁的应用

def run(n, semaphore):
    semaphore.acquire()   #加锁
    time.sleep(1)
    print("run the thread:%s\n" % n)
    semaphore.release()     #释放

if __name__ == '__main__':
    num = 0
    semaphore = threading.BoundedSemaphore(5)  # 最多允许5个线程同时运行
    for i in range(22):
        t = threading.Thread(target=run, args=("t-%s" % i, semaphore))
        t.start()
    while threading.active_count() != 1:
        pass  # print threading.active_count()
    else:
        print('--')

事件类

event = threading.Event()


def lighter():
    count = 0
    event.set()     #初始值为绿灯
    while True:
        if 5 < count <=10 :
            event.clear()  # 红灯，清除标志位
            print("\33[41;1mred light is on...\033[0m")
        elif count > 10:
            event.set()  # 绿灯，设置标志位
            count = 0
        else:
            print("\33[42;1mgreen light is on...\033[0m")

        time.sleep(1)
        count += 1

def car(name):
    while True:
        if event.is_set():      #判断是否设置了标志位（绿灯）
            print("[%s] running..."%name)
            time.sleep(1)
        else:
            print("[%s] sees red light,waiting..."%name)
            event.wait()#如果变为绿灯
            print("[%s] green light is on,start going..."%name)

light = threading.Thread(target=lighter,)
light.start()

car = threading.Thread(target=car,args=("MINI",))
car.start()

queue队列

import threading
import queue,time

q=queue.Queue(maxsize=10)
def Producer(name):
    count=1
    while True:
        q.put("骨头 %s"%count)
        print("{}生产了骨头".format(name),count)
        count+=1
        time.sleep(1)      
def Consumer(name):
    while True:
        print("[%s] 取到  [%s] 并且吃了它。。。"%(name,q.get()))
        time.sleep(1)
p=threading.Thread(target=Producer,args=('wlb',))
c=threading.Thread(target=Consumer,args=("dog",))
c1=threading.Thread(target=Consumer,args=("cat",))

p.start()
c.start()
c1.start()

互斥锁

由于线程之间是进行随机调度，并且每个线程可能只执行n条执行之后，当多个线程同时修改同一条数据时可能会出现脏数据，所以，出现了线程锁，即同一时刻允许一个线程执行操作。线程锁用于锁定资源，你可以定义多个锁, 像下面的代码, 当你需要独占某一资源时，任何一个锁都可以锁这个资源，就好比你用不同的锁都可以把相同的一个门锁住是一个道理。

阅读全文
 Python, Thread

丑数系列

 发布于  收录于 算法题

丑数系列

1.丑数

题目：

https://leetcode-cn.com/problems/ugly-number/

思路：

就是让这个数字不断地除以2.3.5 如果最后变成了1 就说明是个丑数

代码：

class Solution:
    def isUgly(self, num: int) -> bool:
        if num<=-231 or num>=231-1:
            return False
        while num >1:
            if num %2 == 0:
                num=int(num/2)
            elif num %3 ==0:
                num =int(num/3)
            elif num %5 ==0:
                num=int(num/5)
            else:
                break
        if num == 1:
            return True
        else:
            return False

丑数II

题目：

https://leetcode-cn.com/problems/ugly-number-ii/

阅读全文
 算法题, 丑数系列

GBDT

 发布于  收录于 Machine Learning 集成学习 Boosting

梯度提升决策树(GBDT)

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

回归树

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

阅读全文
 Machine Learning, 集成学习, Boosting, GBDT