头像

在找工作の肖山




离线:2020-03-08 19:42



在找工作の肖山
2020-01-05 20:45

升序优先序列,优先pop出最小值

代码

from queue import PriorityQueue
n = int(input())
a = list(map(int,input().split()))

q = PriorityQueue()

for i in range(n):
    q.put(a[i])

sum = 0

while q.qsize()>1:
    a = q.get()
    b = q.get()
    q.put(a+b)
    sum += a+b

print(sum)



在找工作の肖山
2020-01-04 21:05

算法1

Set 和 List 的使用

考虑到set能够去掉所有重复元素,将nums的所有包含元素和原有数组一一对应,打了两个补丁,终于AC

代码

        if len(nums) == 2:#补丁一
            return nums
        nums = sorted(nums)
        res = []
        n = len(nums)
        j = 0
        s = set(nums)#得到不重复的数列
        s = list(s)
        for i in range(n-1):
            if nums[i] == nums[i+1] and nums[i] == s[j]:
                j += 1
                continue
            elif nums[i] != nums[i+1] and nums[i] == s[j]:
                res.append(s[j])
                j += 1
        if len(res) == 1:#补丁二
            res.append(nums[-1])
        return res

算法2

异或法

代码

        xor = 0
        for i in nums:
            xor ^= i
        num1, num2 = 0, 0
        mask = 1
        while xor & mask == 0:
            mask <<= 1
        for num in nums:
            if num & mask == 0:
                num1 ^= num
            else:
                num2 ^= num
        return [num1, num2]




在找工作の肖山
2019-08-15 08:56

算法1

python 代码

    if len(nums) == 0:return 0
        n = max(max(nums),len(nums))
        d = [0 for i in range(n+1)]
        for num in nums:
            d[num]+=1
        return(d[k])





在找工作の肖山
2019-08-15 08:37

题目描述

blablabla

样例

blablabla

对刷完剑指offer就改名老哥的题解的一点改动


算法1

python 代码

class Solution(object):
    def merge(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        cur = dummy
        while l1 and l2:
            if l1.val<=l2.val:
                cur.next = l1
                l1 = l1.next
            elif l2.val < l1.val:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        while l1:
            cur.next = l1
            l1 = l1.next
            cur = cur.next
        while l2:
            cur.next = l2
            l2 = l2.next
            cur = cur.next
        return dummy.next




在找工作の肖山
2019-07-31 09:35

题目描述

blablabla

样例

blablabla

算法1

代码

class Solution:
    def longestSubstringWithoutDuplication(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        l = 1
        sub = s[0]
        for i in s[1:]:
            if i in sub:
                index = sub.find(i)
                sub = sub[index+1:]
            sub = sub + i

            if l<len(sub):
                l = len(sub)
        return l





在找工作の肖山
2019-07-25 08:54

用最naive的方法,将多个同一物品转化成不同物品,再用01背包求解

代码

import sys

def bag(n, t, w, v, s):
ww = [0 for i in range(n * n + 1)]
vv = [0 for i in range(n * n + 1)]
k = 1
for i in range(1, n + 1):
for j in range(1, s[i] + 1):
ww[k] = w[i]
vv[k] = v[i]
k += 1
ans = [0 for i in range(t + 1)]

for i in range(1, k):
    for j in range(t, 0, -1):
        if j >= ww[i]:
            ans[j] = max(ans[j], ans[j - ww[i]] + vv[i])

return ans

if name == “main”:
n, t = map(int, input().strip().split())
w = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
s = [0 for i in range(n + 1)]
for i in range(1, n + 1):
w[i], v[i], s[i] = map(int, input().strip().split())
ans = bag(n, t, w, v, s)
print(ans[t])