2021-09-29:单词缩写,数字交换得到最大值,滚动字符串归类,插入结点,接雨水,距离为K的点

1617-卿同学

发表文章数:84

热门标签

首页 » MySQL » 正文

2021-09-29:单词缩写,数字交换得到最大值,滚动字符串归类,插入结点,接雨水,距离为K的点

着重考虑边界情况:

例如数字读完 index 应该等于 len(word)

或者是num第一个是0

或者是读到某一时候 index都必须是小于n的,大于n就return False

class Solution:
    def validWordAbbreviation(self, word: str, abbr: str) -> bool:
        index = 0
        m = len(abbr)
        n = len(word)
        num = 0
        for i in range(m):
            
            if abbr[i].isdigit():
                if num==0 and int(abbr[i]) == 0:
                    return False
                num = num*10 +int(abbr[i])
                if num > n-index:
                    return False
            else:
                print(abbr[i])
                index += num
                if index >= n:
                    return False
                if abbr[i] != word[index]:
                    return False
                index +=1
                num =0
        index += num
        if index < n:
            return False
        return True
                
                

maximum swap:

class Solution:
    def maximumSwap(self, num: int) -> int:
        numstring = list(str(num))
        numstring = list(map(int,numstring))
        print(numstring)
        n = len(numstring)
        if n == 1:
            return num
        maxval = [[numstring[-1],n-1]]
        prev = [numstring[-1],n-1]
        ans = ""
        for i in range(n-2,-1,-1):
            if numstring[i] > maxval[-1][0]:
                maxval.append([numstring[i],i])
                prev = [numstring[i],i]
            else:
                maxval.append(prev)
        print(maxval)
        maxval = maxval[::-1]
        print(maxval)
        for i in range(n):
            if numstring[i] != maxval[i][0]:
                print (i)
                numstring[i],numstring[maxval[i][1]] = numstring[maxval[i][1]],numstring[i]
                break
        for i in range(n):
            ans += str(numstring[i])
        return int(ans)
        

2021-09-29:单词缩写,数字交换得到最大值,滚动字符串归类,插入结点,接雨水,距离为K的点

思路:

求字母间的差值,然后用字典key,val存起来。val是一个list,后面加的是此类的字符串

需要注意的问题!!    在每个差值后面加空格,以免出现 1 1  = 11的情况 

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        ans = []
        groupdict = defaultdict(list)
        for word in strings:
            n = len(word)
            if n == 1:
                groupdict["a"] += [word]
            else:
                index = ""
                for i in range(1,n):
                    diff = ord(word[i])-ord(word[i-1])
                    diff = diff % 26
                    index += " " +str(diff)
                print(index,word)
                groupdict[index] += [word]
        for key,val in groupdict.items():
            ans += [val]
        return ans
                
        

思路:3种情况

1:中间点, 升序中间

2:开始结束点中间,唯一降序,如果比这些都大或者都小就插入

3:所有点值都一样,遍历一遍到开头结尾判断头尾是不是一样的

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

class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if not head:
            newNode = Node(insertVal,None)
            newNode.next = newNode
            return newNode
        prev, cur = head,head.next
        while True:
            if prev.val <= insertVal <= cur.val:
                prev.next = Node(insertVal,cur)
                break
            elif prev.val > cur.val:
                if insertVal > prev.val or insertVal < cur.val:
                    prev.next = Node(insertVal,cur)
                    break
            prev,cur = cur,cur.next
            if prev == head and prev.val == cur.val:
                prev.next = Node(insertVal,cur)
                break
        return head
            
            
        
        

 2021-09-29:单词缩写,数字交换得到最大值,滚动字符串归类,插入结点,接雨水,距离为K的点

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        maxleft = [0]*n
        maxleftval = 0
        for i in range(1,n):
            if height[i-1] > maxleftval:
                maxleft[i] = height[i-1]
                maxleftval = height[i-1]
            else:
                maxleft[i] = maxleftval
        maxright = [0]*n
        maxrightval = 0
        print(maxleft)
        for i in range(n-2,-1,-1):
            if height[i+1] > maxrightval:
                maxright[i] = height[i+1]
                maxrightval = height[i+1]
            else:
                maxright[i] = maxrightval
        print(maxright)
        trapwater = 0
        for i in range(n):
            val = min(maxright[i],maxleft[i])
            print(val - height[i])
            if (val - height[i])>0:
                trapwater += val - height[i]
        return trapwater

2021-09-29:单词缩写,数字交换得到最大值,滚动字符串归类,插入结点,接雨水,距离为K的点

2021-09-29:单词缩写,数字交换得到最大值,滚动字符串归类,插入结点,接雨水,距离为K的点

 先建立一个parent节点,

再通过parent节点去找

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
        def dfs(node,par):
            if node:
                node.par = par
                dfs(node.left,node)
                dfs(node.right,node)
                
        dfs(root,None)
        queue = [[target,0]]
        seen = [target]
        ll = []
        while queue:
            ll =[]
            if queue[0][1] == k:
                return [node.val for node,d in queue]
            for curnode,d in queue:
                if curnode.par and curnode.par not in seen:
                    ll.append([curnode.par,d+1])
                    seen.append(curnode.par)
                if curnode.left and curnode.left not in seen:
                    ll.append([curnode.left,d+1])
                    seen.append(curnode.left)
                if curnode.right and curnode.right not in seen:
                    ll.append([curnode.right,d+1])
                    seen.append(curnode.right)
            queue = ll
        return []
        
            
        
标签:
分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

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

支付宝扫一扫打赏

微信扫一扫打赏

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

登录

忘记密码 ?

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

Q Q 登 录
微 博 登 录