每日一题(1月)


1-10

605.种花问题

class Solution:
    def canPlaceFlowers(self, f: List[int], n: int) -> bool:
        f=[0]+f+[0,1]
        ans,tmp=0,0
        for i in f:
            if i:
                ans+=(tmp-1)//2  #整数除
                tmp=0
            else: tmp+=1
            #print(ans)
        return ans>=n

239.滑动窗口最大值⭐

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n=len(nums)
        q=collections.deque()
        for i in range(k):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)

        ans=[nums[q[0]]]
        for i in range(k,n):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
            if q[0]==i-k: q.popleft()
            ans.append(nums[q[0]])
        return ans

# q 用于存放大值的索引
# nums[q[0]]总是当前窗口最大值,并且后面对应的num递减

#单调双端队列
#deque: 类似list的容器,实现了在两端快速append和pop

86.分隔链表

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        small,large=ListNode(),ListNode()
        sp,lp,p=small,large,head
        while p:
            if p.val<x:
                sp.next=p
                sp=sp.next
            else:
                lp.next=p
                lp=lp.next
            p=p.next
        sp.next=large.next
        lp.next=None
        return small.next

# 熟悉一下python中的链表

509.斐波那契数

class Solution:
    #functools模块中的缓存
    @lru_cache(None)  
    def fib(self, n: int) -> int:
        if n<2: return n
        return self.fib(n-1)+self.fib(n-2)

830.较大分组的位置

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        left,right,n=0,0,len(s)
        ans=[]
        while right<n-1:
            while right<n and s[right]==s[left]:  #right<n的位置
            #解决了后面是末尾的问题
                right+=1
            if right-left>=3: ans.append([left,right-1])
            #print(left,right)
            left=right
        return ans

# 双指针

309.除法求值

# 一、dfs做法
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        dic=collections.defaultdict(dict)     #值也为字典
        for [a,b],val in zip(equations,values):
            dic[a][b]=val
            dic[b][a]=1/val

        def dfs(a,b,visited):
            if b in dic[a]: return dic[a][b]
            for c in dic[a]:                 #开始遍历寻找
                if c not in visited:
                    visited.add(c)
                    val=bt(c,b,visited)
                    if val!=-1: return dic[a][c]*val
            return -1
        ans=[]
        for [a,b] in queries:
            ans.append(dfs(a,b,set()))
        return ans
# 二、带权并查集作法
class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        f = {}  #记录每个结点的root
        d = {}  #记录每个结点到root的权

        def find(x):  #找到x的根节点并整理
            f.setdefault(x, x)
            d.setdefault(x,1)
            if x != f[x]:
                t = f[x]
                f[x] = find(t)
                d[x] *= d[t]
                return f[x]
            return x 

        def union(A, B, value):
            a, b = find(A), find(B)
            if a != b:
                f[a] = b   # a 的根结点是b
                d[a] = d[B] / d[A] * value  # a在b树上的权

        def check(x, y):
            if x not in f or y not in f:
                return -1.0
            a, b = find(x), find(y)
            if a != b: return -1.0 #ab不在一棵树
            return d[x] / d[y]

        for i,nums in enumerate(equations):
            union(nums[0],nums[1],values[i])
        ans=[]
        for x,y in queries:
            ans.append(check(x,y))
        return ans

#第一反应赋值,不行

#并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。

# dic.setdefault(key,default=None) 可类似于 dic.get()
# 如果键不存在于字典中,将会添加键并将值设为默认值。

# 并查集不懂

547.省份数量

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        dic=collections.defaultdict(set)
        n=len(isConnected)
        for i in range(n):                 #建立图
            for j in range(n):
                if i!=j and isConnected[i][j]==1:
                    dic[i].add(j)
                    dic[j].add(i)
        visited=[]
        ans=0
        def dfs(i):
            if i not in visited:
                visited.append(i)
                for j in dic[i]:
                    dfs(j)
        for i in range(n): #查找省份
            if i not in visited:
                dfs(i)
                ans+=1
        #print(visited)
        #print([i for i in dic.items()])
        return ans

# hh~

189.旋转数组

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k%=len(nums)
        k*=-1
        nums[:]=nums[k:]+nums[:k]

# nums[:]会指向新的内存空间,不能直接nums

123.买卖股票的最佳时机 III

一份股票,两次交易,求最大利润

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/

class Solution(object):
    def maxProfit(self, prices):
        if not prices: return 0
        n=len(prices)
        dp=[[0]*n for _ in range(3)] #DP表为最大利润
        for k in range(1,3):
            pre_max=-prices[0]
            for i in range(1,n):
                pre_max=max(pre_max,dp[k-1][i-1]-prices[i])
                dp[k][i]=max(dp[k][i-1],pre_max+prices[i])
        return dp[-1][-1]

#这个DP的模板可以解决很多问题了
#pre_max=max(pre_max,dp[k-1][i-1]-prices[i])状态转移有些抽象啊

#[3,3,5,0,0,3,1,4]的DP表:
#[[0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 2, 2, 2, 3, 3, 4],
# [0, 0, 2, 2, 2, 5, 5, 6]]
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n1, y1 = 0, -float("INF")
        n2, y2 = 0, -float("INF")
        for p in prices:
            if y2 + p > n2:
                n2 = y2 + p 
            if n1 - p > y2:
                y2 = n1 - p 
            if y1 + p > n1:
                n1 = y1 + p 
            if -p > y1:
                y1 = -p
            # y1, n1, y2, n2 = max(y1, -p), max(n1, y1 + p), max(y2, n1 - p), max(n2, y2 + p)
        return max(n1, n2)

# copy

228.汇总区间

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        left,right,n=0,0,len(nums)
        ans=[]
        while right<n:
            while right<n-1 and nums[right+1]-nums[right]==1:  
                right+=1
            if right==left: 
                ans.append(str(nums[left]))
            else: 
                ans.append(str(nums[left])+'->'+str(nums[right]))
            right+=1
            left=right   
        return ans

# (两个while)+(right指针放区间内的右侧),解决了:后面读不出来,或者list访问越界

11-20

1202.交换字符串中的元素⭐

给你一个字符串 s,以及该字符串中的一些「索引对」数组 pairs,其中 pairs[i] = [a, b] 表示字符串中的两个索引(编号从 0 开始)。

你可以 任意多次交换 在 pairs 中任意一对索引处的字符。

返回在经过若干次交换后,s 可以变成的按字典序最小的字符串。

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        length=len(s)
        p=[i for i in range(length)] #初始化,只记录根节点

        def find(x):
            while x!=p[x]:
                p[x]=p[p[x]]
                x=p[x]
            return x

        for a_id,b_id in pairs:   #开始合并
            roota = find(a_id)
            rootb = find(b_id)
            if roota == rootb:
                continue
            p[rootb] = roota

        # tmp是相同根的容器
        tmp=collections.defaultdict(list)
        for i in range(length):
            root=find(i)
            tmp[root].append(i)

        ans=list(s)
        for same_idxs in tmp.values():
            same_idxs.sort()
            select_str=[s[i] for i in same_idxs]
            select_str.sort()
            for i,idx in enumerate(same_idxs):
                ans[idx]=select_str[i]

        return "".join(ans)

#关于本题:
#1.当成一个图问题
#2.索引对的交换具有传递性
#3.对于连通的索引直接排序,不连通的不能变动

#关于并查集:
#并查集解决一些元素分组问题,利用合并查询处理不相交的集合
#路径压缩:把节点的父节点设为根节点
#参考:https://zhuanlan.zhihu.com/p/93647900/
#暴力超时:
class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        q=deque([[i for i in s]])
        ans=[]
        while q:
            tmp=q.popleft()
            ans.append(tmp)
            for i,j in pairs:
                t=tmp.copy()
                t[i],t[j]=t[j],t[i]
                if t not in ans: 
                    q.append(t)
        return min([''.join(i) for i in ans])

684.冗余连接

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        dic=collections.defaultdict(set)
        for i in range(1,len(edges)+1):
            dic[i].add(i)           #并查集初始化
        for x,y in edges:
            if dic[x]!=dic[y]:
                dic[x]|=dic[y]      #合并集合
                for z in dic[y]:
                    dic[z]=dic[x]
            else:                   #x,y会形成闭环
                return [x,y]

#无向图

803.打砖块

#并查集,或DFS

1232.缀点成线

class Solution:
    def checkStraightLine(self, coordinates: List[List[int]]) -> bool:
        x1,y1=coordinates[0][0],coordinates[0][1]
        x2,y2=coordinates[1][0], coordinates[1][1]
        for xi,yi in coordinates[2:]:
            if (yi-y1)*(x2-x1)!=(y2-y1)*(xi-x1):
                return False
        return True

721.账户合并

#思路:建立并查集,将可以连接的account合并。
class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        f={}
        def find(x):
            f.setdefault(x,x) #不存在 key=x 就初始化
            while f[x]!=x:
                f[x]=f[f[x]]
                x=f[x]
            return x

        def union(x,y):
            f[find(x)]=find(y) #将x连到y的根上

        visited={}
        n=len(accounts)
        for i,account in enumerate(accounts):  #进行连接
            name,email=account[0],account[1:]
            for e in email:
                if e in visited:
                    union(i,visited[e])
                else:
                    visited[e]=i

        disjointSet=collections.defaultdict(set)
        for i in range(n):
            root=find(i)
            for es in accounts[i][1:]:
                disjointSet[root].add(es)
        #print(disjointSet)
        return [[accounts[key][0]]+list(sorted(val)) for key,val in disjointSet.items()]

1584.连接所有点的最小费用

给你一个 points 数组,表示 2D 平面上的一些点,其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 :|xi - xj| + |yi - yj| ,其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时,才认为所有点都已连接。

#方法一:最小生成树prim算法

#每次迭代选择代价最小的边对应的点,加入到树中。
#算法从某一个顶点s开始,逐渐覆盖整个连通网的所有顶点。

class Solution:
    def get_dist(self,a,b):
        return abs(a[0]-b[0])+abs(a[1]-b[1])
    def prim(self,points):
        n=len(points)
        dist=[float('inf')]*n
        dist[0]=0
        visited=[]
        ans=0
        for _ in range(n):
            # 离集合最近的点
            t = min([i for i in range(n) if not vis[i]], key = lambda x:(dist[x], x))
            vis[t] = 1
            ans += dist[t]

            # 用离集合最近的点更新其他的点到集合的距离
            for i in range(n):
                if not vis[i]:
                    dist[i] = min(dist[i], self.get_dist(points[i], points[t]))
        return ans
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        return self.prim(points)

#完全图:每对顶点都有边连接。
#方法二:最小生成树kruskal算法

#每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        def dist(a,b):    #math中也有个dist函数
            return abs(a[0]-b[0])+abs(a[1]-b[1])
        n=len(points)
        cost_list=[(dist(points[i],points[j]),i,j) for i in range(n-1) for j in range(i,n)]
        cost_list.sort(key=lambda x:x[0])

        f={}   #记录每个点的根节点
        def find(x): #仅find和初始化功能
            f.setdefault(x,x)
            while x!=f[x]:
                f[x]=f[f[x]]
                x=f[x]
            return x
        def union(x,y):
            f[find(x)]=find(y)

        ans=0
        for cost,x,y in cost_list:
            if find(x)==find(y): continue   #两个点在树中
            union(x,y)
            ans+=cost
        return ans

#会默写这段代码了,hh

628.三个数的最大乘积

class Solution(object):
    def maximumProduct(self, nums):
        nums.sort()
        return max(nums[-1]*nums[-2]*nums[-3],nums[0]*nums[1]*nums[-1])

21-31

1489.关键边和伪关键边

给定n个点的带权无向连通图。
求关键边(每种最小生成树都有的边)
伪关键边(出现在最小生成树中,但不必全部出现)

# 并查集模板
class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.size = [1] * n
        self.n = n
        # 当前连通分量数目
        self.setCount = n

    def findset(self, x: int) -> int:
        if self.parent[x] == x:
            return x
        self.parent[x] = self.findset(self.parent[x])
        return self.parent[x]

    def unite(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        if x == y:
            return False
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.parent[y] = x
        self.size[x] += self.size[y]
        self.setCount -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        x, y = self.findset(x), self.findset(y)
        return x == y

# Tarjan 算法求桥边模版
class TarjanSCC:
    def __init__(self, n: int, edges: List[List[int]], edgesId: List[List[int]]):
        self.n = n
        self.edges = edges
        self.edgesId = edgesId
        self.low = [-1] * n
        self.dfn = [-1] * n
        self.ans = list()
        self.ts = -1

    def getCuttingEdge(self) -> List[int]:
        for i in range(self.n):
            if self.dfn[i] == -1:
                self.pGetCuttingEdge(i, -1)
        return self.ans

    def pGetCuttingEdge(self, u: int, parentEdgeId: int):
        self.ts += 1
        self.low[u] = self.dfn[u] = self.ts
        for v, iden in zip(self.edges[u], self.edgesId[u]):
            if self.dfn[v] == -1:
                self.pGetCuttingEdge(v, iden)
                self.low[u] = min(self.low[u], self.low[v])
                if self.low[v] > self.dfn[u]:
                    self.ans.append(iden)
            elif iden != parentEdgeId:
                self.low[u] = min(self.low[u], self.dfn[v])

class Solution:
    def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
        m = len(edges)
        for i, edge in enumerate(edges):
            edge.append(i)
        edges.sort(key=lambda x: x[2])

        uf = UnionFind(n)
        ans0 = list()
        label = [0] * m

        i = 0
        while i < m:
            # 找出所有权值为 w 的边,下标范围为 [i, j)
            w = edges[i][2]
            j = i
            while j < m and edges[j][2] == edges[i][2]:
                j += 1

            # 存储每个连通分量在图 G 中的编号
            compToId = dict()
            # 图 G 的节点数
            gn = 0

            for k in range(i, j):
                x = uf.findset(edges[k][0])
                y = uf.findset(edges[k][1])
                if x != y:
                    if x not in compToId:
                        compToId[x] = gn
                        gn += 1
                    if y not in compToId:
                        compToId[y] = gn
                        gn += 1
                else:
                    # 将自环边标记为 -1
                    label[edges[k][3]] = -1

            # 图 G 的边
            gm = collections.defaultdict(list)
            gmid = collections.defaultdict(list)

            for k in range(i, j):
                x = uf.findset(edges[k][0])
                y = uf.findset(edges[k][1])
                if x != y:
                    idx, idy = compToId[x], compToId[y]
                    gm[idx].append(idy)
                    gmid[idx].append(edges[k][3])
                    gm[idy].append(idx)
                    gmid[idy].append(edges[k][3])

            bridges = TarjanSCC(gn, gm, gmid).getCuttingEdge()
            # 将桥边(关键边)标记为 1
            ans0.extend(bridges)
            for iden in bridges:
                label[iden] = 1

            for k in range(i, j):
                uf.unite(edges[k][0], edges[k][1])

            i = j

        # 未标记的边即为非桥边(伪关键边)
        ans1 = [i for i in range(m) if label[i] == 0]

        return [ans0, ans1]

#copy,溜了溜了

989. 数组形式的整数加法

class Solution:
    def addToArrayForm(self, A: List[int], K: int) -> List[int]:
        sum=0
        for num in A:
            sum=sum*10+num
        sum+=K
        return [int(i) for i in str(sum)]

1319.连通网络的操作次数

class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        if len(connections)<n-1: return -1

        f={}
        def find(x):
            f.setdefault(x,x)
            while x!=f[x]:
                f[x]=f[f[x]]
                x=f[x]
            return x
        def union(x,y):
            f[find(x)]=f[y]

        n-=1   #需要n-1条边才能连通网络
        for x,y in connections:
            if find(x)==find(y):
                continue
            union(x,y)
            n-=1  #需要的边减少了
        return n

674.最长连续递增序列

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans=0
        start=0
        for i in range(len(nums)):
            if i and nums[i]<=nums[i-1]:
                start=i
            ans=max(ans,i-start+1)
        return ans

959.由斜杠划分区域

class uf:
    def __init__(self,n):
        self.f={}
        self.cnt=n
        for i in range(n):
            self.f[i]=i

    def find(self,x):
        while x!=self.f[x]:
            self.f[x]=self.f[self.f[x]]
            x=self.f[x]
        return x

    def union(self,x,y):
        if not self.connect(x,y):
            self.f[self.find(x)]=self.find(y)  #将x根连到y的根节点
            self.cnt-=1

    def connect(self,x,y):
        return self.find(x)==self.find(y)

class Solution:
    def regionsBySlashes(self, grid: List[str]) -> int:
        n=len(grid)
        u=uf(n*n*4)
        def get_pos(row,col,i):
            return (row*n+col)*4+i
        for row in range(n):
            for col in range(n):
                v=grid[row][col]
                if col>0:
                    u.union(get_pos(row,col-1,1),get_pos(row,col,3))
                if row>0:
                    u.union(get_pos(row-1,col,2),get_pos(row,col,0))
                if v=='/':
                    u.union(get_pos(row,col,0),get_pos(row,col,3))
                    u.union(get_pos(row,col,1),get_pos(row,col,2))
                elif v=='\\':
                    u.union(get_pos(row,col,0),get_pos(row,col,1))
                    u.union(get_pos(row,col,2),get_pos(row,col,3))
                else:  
                    u.union(get_pos(row,col,0),get_pos(row,col,1))
                    u.union(get_pos(row,col,2),get_pos(row,col,3))
                    u.union(get_pos(row,col,1),get_pos(row,col,2))
        return u.cnt

# 万能的并查集...

1128.等价多米诺骨牌对的数量

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        tmp=Counter([a*10+b if a>=b else b*10+a for a,b in dominoes])
        return sum(comb(k,2) for k in tmp.values())

#特定情况下,选取特征哈希键

1579.保证图的可完全遍历⭐

Alice 和 Bob 共有一个无向图,其中包含 n 个节点和 3 种类型的边,返回可以删除的最大边数,如果 Alice 和 Bob 无法完全遍历图,则返回 -1

class uf:
    def __init__(self,n):
        self.f={}
        self.cnt=n
        for i in range(n):
            self.f[i]=i
    def find(self,x):
        while x!=self.f[x]:
            self.f[x]=self.f[self.f[x]]
            x=self.f[x]
        return x
    def union(self,x,y):
        if not self.connect(x,y):
            self.f[self.find(x)]=self.find(y)
            self.cnt-=1
    def connect(self,x,y):
        return self.find(x)==self.find(y)

class Solution:
    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
        edges.sort(key=lambda x:x[0],reverse=True)
        ua,ub=uf(n),uf(n)
        ans=0
        for t,x,y in edges:
            x,y=x-1,y-1   #对上序号
            if t==3:
                if ua.connect(x,y): ans+=1
                else: 
                    ua.union(x,y)
                    ub.union(x,y)
            elif t==2:
                if ub.connect(x,y): ans+=1
                else: ub.union(x,y)
            else:
                if ua.connect(x,y): ans+=1
                else: ua.union(x,y)
        if ua.cnt!=1 or ub.cnt!=1: return -1
        return ans

# uf 666

724.寻找数组的中心索引

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total=sum(nums)
        tmp=0
        for i,num in enumerate(nums):
            if tmp*2+num==total: return i
            tmp+=num
        return -1

1631.最小体力消耗路径⭐

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows,cols=len(heights),len(heights[0])
        edges=[]
        for i in range(rows):
            for j in range(cols):
                idx=i*cols+j
                if i: edges.append([idx,idx-cols,abs(heights[i][j]-heights[i-1][j])])
                if j: edges.append([idx,idx-1,abs(heights[i][j]-heights[i][j-1])])
        edges.sort(key=lambda x:x[2])
        #print(edges)

        f={}
        def find(x):
            f.setdefault(x,x)
            while x!=f[x]:
                f[x]=f[f[x]]
                x=f[x]
            return x
        def union(x,y):
            f[find(x)]=f[y]

        ans=0
        for x,y,w in edges:
            if find(x)==find(y):
                continue
            union(x,y)
            ans=max(ans,w)
            if find(0)==find(rows*cols-1): 
                break
        return ans

#并查集,连通

778.水位上升的泳池中游泳

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        f={}
        def find(x):
            f.setdefault(x,x)
            while x!=f[x]:
                f[x]=f[f[x]]
                x=f[x]
            return x
        def union(x,y):
            f[find(x)]=find(y)

        rows,cols=len(grid),len(grid[0])
        edges=[]
        for i in range(rows):
            for j in range(cols):
                idx=i*cols+j
                if i: edges.append([idx,idx-cols,max(grid[i][j],grid[i-1][j])])
                if j: edges.append([idx,idx-1,max(grid[i][j],grid[i][j-1])])
        edges.sort(key=lambda x:x[2])

        ans=0
        for x,y,w in edges:
            if find(x)==find(y): continue
            union(x,y)
            ans=max(ans,w)
            if find(0)==find(rows*cols-1): break
        return ans 

# 激动,和昨天一个题。

839. 相似字符串组

class Solution:
    def numSimilarGroups(self, strs: List[str]) -> int:
        def check(x,y):
            cnt=0
            for a,b in zip(x,y):
                if a!=b: cnt+=1
                if cnt>2: return False #strs中所有单词长度相同
            return True

        f={}
        def find(x):
            f.setdefault(x,x)
            while x!=f[x]:
                f[x]=f[f[x]]
                x=f[x]
            return x
        def union(x,y):
            f[find(x)]=find(y)

        n=len(strs)
        for i in range(n):
            for j in range(i+1,n):
                if find(i)==find(j): continue
                if check(strs[i],strs[j]):
                    #print(strs[i],strs[j])
                    union(i,j)
        return sum(f[i]==i for i in range(n)) #连通分量个数

# 1月打卡完成

wuliao

3.无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n=len(s)
        q=collections.deque()
        ans=0
        for i in range(n):
            if s[i] not in q:
                q.append(s[i])
            else:
                while q[0]!=s[i]:
                    q.popleft()
                q.popleft()
                q.append(s[i])
            ans=max(ans,len(q))
        return ans

#参照239滑动窗口问题

29.整数相除

不用乘除,mod

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        flag=dividend*divisor<0
        dividend=abs(dividend)
        divisor=abs(divisor)

        def div(dividend, divisor):
            if dividend<divisor: return 0
            tmp=divisor
            cnt=1
            while tmp+tmp<dividend:  #2倍法找邻值
                tmp+=tmp
                cnt+=cnt
            return cnt+div(dividend-tmp,divisor)

        ans=div(dividend,divisor)
        if flag: ans*=-1
        return ans if -(1<<31)<=ans<=(1<<31)-1 else (1<<31)-1 #题意溢出更改

删除链表中的结点

class Solution:
    def deleteNode(self, node):
        node.val=node.next.val
        node.next=node.next.next

# 等效地删除了

链表倒数第k个结点

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        slow,fast=head,head
        for i in range(k-1):
            fast=fast.next
        while fast.next:
            slow=slow.next
            fast=fast.next
        return slow.val

二叉树的直径

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans=1
        def depth(node):         #从下往上的计算
            if not node: return 0
            l=depth(node.left)
            r=depth(node.right)
            self.ans=max(self.ans,l+r+1)
            return max(l,r)+1   #当前结点最大深度
        depth(root)
        return self.ans-1

二叉树镜像

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return 
        tmp=root.left
        root.left=self.mirrorTree(root.right)
        root.right=self.mirrorTree(tmp)
        return root

混一下

class ParkingSystem:
    def __init__(self, big: int, medium: int, small: int):
        self.big=big
        self.medium=medium
        self.small=small
    def addCar(self, carType: int) -> bool:
        if carType==1:
            self.big-=1
            return self.big>=0
        elif carType==2:
            self.medium-=1
            return self.medium>=0
        else:
            self.small-=1
            return self.small>=0

#1.复习一下类...
#2.python str 还有replace()
#3.zip打包,一个for里多做点事
#4.col = [max(i) for i in zip(*matrix)]

75.颜色分类

一趟扫描,排序012

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        p0, p2 = 0, len(nums) - 1
        i = 0
        while i <= p2:
            while i <= p2 and nums[i] == 2:
                nums[i], nums[p2] = nums[p2], nums[i]
                p2 -= 1
            if nums[i] == 0:
                nums[i], nums[p0] = nums[p0], nums[i]
                p0 += 1
            i += 1
#快速排序

416.分割等和子集

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n=len(nums)
        if n<2: return False
        total=sum(nums)
        if total%2: return False

        k=total//2
        dp=[1]+[0]*k
        for i, num in enumerate(nums):
            for j in range(k, num - 1, -1):
                if dp[j - num]: dp[j]=1

        return True if dp[k] else False
#0-1背包

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录