头像

感谢信


访客:517

离线:2小时前


活动打卡代码 LeetCode 224. 基本计算器

class Solution {
public:
    stack<int> num;
    stack<char> op;
    void eval(){
        int b=num.top();num.pop();//这里注意反了反了a和b
        int a=num.top();num.pop();
        char c=op.top();op.pop();
        int r;
        if(c=='+') r=a+b;
        if(c=='-') r=a-b;
        if(c=='*') r=a*b;
        if(c=='/') r=a/b;
        num.push(r);
    }
    int calculate(string s) {
        int n=s.size();
        unordered_map<char,int> pr;
        pr['+']=pr['-']=1;
        pr['*']=pr['/']=2;
        for(int i=0;i<n;i++){
            char c=s[i];
            if(c==' ') continue;
            else if(isdigit(c)){
                int x=0,j=i;
                while(j<n && isdigit(s[j])) x=10*x+(s[j++]-'0');
                num.push(x);
                i=j-1;
            }
            else{
                while(op.size() && pr[op.top()]>=pr[c]) eval();//op.size()丢了
                op.push(c);
            }
        }
        while(op.size()) eval();
        return num.top();

    }
};


活动打卡代码 LeetCode 179. 最大数

class sort(str):
    def __lt__(x,y):  #富比较方法,lt是小于
        return x+y>y+x


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        res=sorted(map(str,nums),key=sort)
        ans="".join(res)
        if ans[0]=='0':
            return '0'
        else:
            return ans


活动打卡代码 LeetCode 216. 组合总和 III

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        def dfs(st,n,k,tmp):
            if not n:
                if not k:
                    res.append(tmp)
            else:
                for i in range(st,10):
                    if n>=i:
                        dfs(i+1,n-i,k-1,tmp+[i])#下一次从i+1开始选

        res=[]
        dfs(1,n,k,[])
        return res



class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def find(nums1,i,nums2,j,k):
            n1=len(nums1)
            n2=len(nums2)
            if n1-i>n2-j:# 这里不能用n1,n2,因为可能交换过了
                return find(nums2,j,nums1,i,k)
            if k==1:
                if i==n1: return nums2[j]#这里是j而不是0
                else: return min(nums1[i],nums2[j])#这里是i不是0
            if i==n1:
                return nums2[j+k-1]
            a=min(n1,i+k//2) # 第k//2的下一个位置,用于递归
            b=j+k-k//2 
            if nums1[a-1]<nums2[b-1]:
                return find(nums1,a,nums2,j,k-(a-i))#这边是a-i,而不是k-k//2,因为边界
            else:
                return find(nums1,i,nums2,b,k-(b-j))

        t=len(nums1)+len(nums2)
        if t&1:
            return find(nums1,0,nums2,0,t//2+1)
        else:
            l=find(nums1,0,nums2,0,t//2)
            r=find(nums1,0,nums2,0,t//2+1)
            return (l+r)/2



使用大根堆结构。假设arr1的长度是M,arr2的长度是N。因为是排序数组,arr1中最后一个数加上arr2中最后一个数一定就是最大的相加和。将这个数压入大根堆中。然后从大根堆中弹出一个堆顶,此时这个堆顶一定是(M-1, N-1)位置的和,表示获得一个最大相加和。然后,将两个相邻位置的和再放入堆中,即位置(M-1,N-2)和(M-2, N-1),因为除(M-1, N-1)位置的和外,最大的相加和一定在位置(M-1,N-2)和(m-2, N-1)中产生。重新调整大根堆,然后继续弹出,继续将弹出元素的两个相邻位置添加到堆中,直到弹出的元素达到K个。

import heapq

def topk(arr1, arr2,k):# 放进堆,出来一个,把最靠近他的两个再放进堆
    n1=len(arr1)
    n2=len(arr2)
    i=n1-1
    j=n2-1
    hp=[]
    res=[]
    heapq.heappush(hp,[-arr1[i]-arr2[j],i,j])
    for _ in range(k):
        t,i,j=heapq.heappop(hp)
        res.append(-t)
        a=[-arr1[i-1]-arr2[j],i-1,j]
        b=[-arr1[i]-arr2[j-1],i,j-1]
        heapq.heappush(hp,a)
        heapq.heappush(hp,b)
    return res

arr1=[1,3,4,5,7]
arr2=[1,2,5,8,9]
k=5
print(topk(arr1,arr2,k))


活动打卡代码 LeetCode 312. 戳气球

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n=len(nums)
        nums.insert(0,1)# 加了哨兵就不要考虑特殊情况了
        nums.append(1)
        f=[[0]*(n+2) for _ in range(n+2)]

        for le in range(1,n+1):
            for i in range(1,n+2-le):
                j=i+le-1
                for k in range(i,j+1):#k可以理解成[i,j][i,j]范围里最后戳破的一个气球。
                    f[i][j]=max(f[i][j],f[i][k-1]+nums[i-1]*nums[k]*nums[j+1] +f[k+1][j])
        return f[1][n]



class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        ans=0
        n=len(prices)
        if k>len(prices)//2:# 超过一半就要单独考虑了
            for i in range(1,n):
                ans+=max(0,prices[i]-prices[i-1])
            return ans 
        f=[[-1000]*(k+1) for i in range(n+1)]
        g=[[-1000]*(k+1) for i in range(n+1)]
        f[0][0]=0
        for i in range(1,n+1):
            for j in range(k+1):
                f[i][j]=max(f[i-1][j],g[i-1][j]+prices[i-1])# f[i][j]是不拥有股票的第i天,第j轮,g[i][j]是拥有股票
                g[i][j]=g[i-1][j]
                if j: g[i][j]=max(g[i][j],f[i-1][j-1]-prices[i-1])
        ans=max(map(max,f))
        return ans


活动打卡代码 LeetCode 475. Heaters

class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        heaters.append(float("-inf")) #这里的边界条件太帅了 
        heaters.append(float("inf"))
        heaters.sort()
        n=len(heaters)
        ans=float("-inf")
        for h in houses:
            l,r=0,n-1
            while l<r:
                m=l+r>>1
                if heaters[m]>=h:
                    r=m
                else:
                    l=m+1
            ans=max(ans,min(heaters[r]-h,h-heaters[r-1]))# 这边是r-1
        return (ans)




class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        ver1=list(map(int,version1.split('.')))
        ver2=list(map(int,version2.split('.')))
        l1=len(ver1)
        l2=len(ver2)
        i=0
        j=0
        while i<l1 or j<l2:# 要一起比
            a=ver1[i] if i<l1 else 0
            b=ver2[j] if j<l2 else 0
            if a<b:
                return -1
            elif a>b:
                return 1
            i+=1
            j+=1
        return 0



活动打卡代码 LeetCode 38. Count and Say

class Solution:
    def countAndSay(self, n: int) -> str:
        q='1'
        for i in range(n-1):
            l=len(q)
            j=0
            res=''
            while j<l:
                k=j
                cnt=0
                while k<l and q[k]==q[j]:
                    cnt+=1
                    k+=1
                res+=str(cnt)+q[j]
                j=k
            q=res
        return q