135 - 140

2023-10-20 23:10:52

135 分糖果

一开始用贪心算法

就很简单的从头到尾遍历，对于一个数如果他
比前面数大：就是前面那个糖果数加1
跟前面数相等：就是1
比前面数小：就是1
但是如果前面人的糖果也是1呢就会出现分数不同但是糖果相同的情况，此时需要把前面的严格递减（只差1）分数全部加1
比如前面人糖果数是 ...10，3,2,1 那么再来一个小的数就需要把 3,2,1全部加1 变成 10,4,3,2 后面添上当前的1
注意相等情况就不用往前看了。

举例： [0,1,2,3,2,1]
0位： 1颗糖
1位： 1比0大 2颗糖
2位： 2比1大 3颗糖
3位： 3比2大 4颗糖
4位： 2比3小 1颗糖
5位： 1比2小 1颗糖但是4位也是1颗糖找到一个严格递减的区间只有4位。所以4位加1变成2
得结果[1,2,3,4,2,1]

def candy(ratings):
    n = len(ratings)
    if n == 1:
        return 1
    num = [1]*n
    for i in range(n):
        if ratings[i] > ratings[i-1]:
            num[i] = num[i-1] +1
        elif ratings[i] < ratings[i-1]:
            if num[i-1] == 1:
                for index in range(i-1,-1,-1):
                    if num[index] == num [index+1] and ratings[index] != ratings[index+1]:
                        num[index] += 1
                    else:
                        break
    return sum(num)


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/candy/solution/liang-chong-fang-fa-xiang-xi-jie-xi-jia-x04aq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

思路2 ：

跟卖股票一样卖股票是找到每一个上升的区间这题是找到每一个上升的和每一个下降的区间每个区间结尾是下个区间开头。
对于一个数如果他
比后面数大：
存在一个递增的区间。找出这个区间从这个数字开始，这个区间赋予糖果 1，2，3,4,5
比后面数字小：
存在一个递减的区间。找出这个区间从这个数字开始，这个区间倒序赋予糖果 ...，3,2,1
但是此时需要注意一种特殊情况因为递减区间的开头是上一个递增区间的结尾。所以你不能让这个结尾变得更小，需要取一个MAX
跟后面数字一样：
跳过继续往后看就行。
因为代码会出现与i+1的比较所以把最后一位单独考虑了。

举例： [0,1,2,3,2,1]
0比1小找到一个递增区间 0,1,2,3
赋予糖果 1,2,3,4
3比2大找到一个递减区间 3,2,1
赋予糖果 3,2,1
但是第三个小朋友必须大于第二个小朋友的2个
所以取max[4,3]= 4
需要糖果就是[1,2,3,4,2,1]

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n == 1:
            return 1
        nums = [1]*n
        i = 0
        while i < n-1 :
            if ratings[i]> ratings[i+1]:
                index= i
                while  ratings[i]> ratings[i+1]:
                    i += 1
                    if i == n-1:
                        break
                for j in range(i-1,index,-1):
                    nums[j] = nums[j+1] +1
                nums[index] = max(nums[index],nums[index+1]+1)
            elif ratings[i] < ratings[i+1]:
                index= i
                while  ratings[i]< ratings[i+1]:
                    i += 1
                    if i == n-1:
                        break
                for j in range(index+1,i+1,1):
                    nums[j] = nums[j-1] +1
            elif ratings[i] == ratings[i+1]:
                i += 1
        if ratings[n-1] < ratings[n-2]:
            nums[n-1] = 1
        return sum(nums)

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/candy/solution/liang-chong-fang-fa-xiang-xi-jie-xi-jia-x04aq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

136 异或解法这两道都是抄的碰到进制就头痛

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x,y:x^y,nums)


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/single-number/solution/tong-yang-shi-ti-jie-wei-sha-wo-zhi-da-b-w0hz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

137：

出现1次的数字

答案都看不懂了

唉

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = b = 0
        for num in nums:
            a, b = (~a & b & num) | (a & ~b & ~num), ~a & (b ^ num)
        return b


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/single-number-ii/solution/kan-bu-dong-kan-bu-dong-kan-bu-dong-ai-b-5h01/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

138 再来克隆这次是奇怪的链表

p和r 一个代表原来一个代表复制一起往后遍历
next出现没见过的就建立
random出现没见过的先建立 next到他再说。
OK了

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return head
        nodedict = {}
        p = head
        chead = Node(x=p.val, next=None,random=None)
        nodedict[head] = chead
        r = chead
        while p.next != None:
            if p.next not in nodedict:
                chead = Node(x=p.next.val, next=None,random=None)
                nodedict[p.next] = chead
                r.next = chead
            else:
                r.next = nodedict[p.next]
            if p.random == None:
                r.random = None
            elif p.random not in nodedict:
                chead = Node(x=p.random.val, next=None,random=None)
                nodedict[p.random] = chead
                r.random = chead
            else:
                r.random = nodedict[p.random]
            p = p.next
            r = r.next
        if p.random:
            r.random = nodedict[p.random]
        return nodedict[head]

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/zhe-chong-ti-gan-jue-zhi-yao-na-ge-zi-di-yri6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

139：单词划分

回溯是我的爱，超时让我没法爱

我知道是DP 但我毫无思路

    n = len(s)
    dp = [False]*(n+1)
    dp[0] = True
    for i in range(n):
        for j in range(i+1):
            if dp[j] and (s[j:i+1] in wordset):
                dp[i+1] = True
                break
    return dp[n]

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/word-break/solution/hui-su-shi-wo-de-ai-chao-shi-rang-wo-mei-dytj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

140 单词划分2

算路径还得我回溯来！！！

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        wordset = set(wordDict)
        n = len(s)
        rel = []
        def dfs(start,path):
            for i in range(start+1,n+1):
                if s[start:i] in wordset:
                    path.append(s[start:i])
                    if i == n:
                        rel.append(' '.join(path[:]))
                    dfs(i,path)
                    path.pop()
        dfs(0,[])
        return rel

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/word-break-ii/solution/ha-ha-ha-ha-ha-suan-neng-bu-neng-ni-dpli-o7t0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

码农公寓

相关文章