Leetcode 75 | Crystal’s Blog

type

Post

status

Published

date

Aug 18, 2023

slug

leecode75_01

summary

1768. 交替合并字符串

zip 是一个内置函数，在 Python 中用于同时迭代多个可迭代对象（例如列表、字符串等）。

zip 函数的基本语法是：

zip(*iterables)

其中，*iterables 表示可变数量的可迭代对象。

zip 函数将多个可迭代对象的元素按顺序打包成一个元组，然后返回一个由这些元组组成的迭代器。

python 代码


class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        combined=''
        for w1,w2 in zip(word1,word2):
           combined+=w1+w2
        combined+=word1[len(word2):]+word2[len(word1):]
        return combined

c++ 代码


class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int len1=word1.length();
        int len2=word2.length();
        int maxn=max(len1,len2);
        int i=0;
        string ans="";
        while(i<maxn){
            if(i<len1)
                ans+=word1[i];
            if(i<len2){
                ans+=word2[i];
            }
            i++;
        }
        return ans;
    }
};

1071. 字符串的最大公因子

思路1

类比数字的辗转相除法，来实现字符串之间的辗转相除法。

例如：str1=”ABABAB”,str2=”ABAB”

ABABAB=ABAB*1+AB

ABAB=AB*2+’’

c++代码


class Solution
{
public:
    string gcdOfStrings(string str1, string str2)
    {
        if (str2 == "")
        {
            return str1;
        }
        if (str1.length() < str2.length())
        {
            swap(str1, str2);
        }
        int i = 0;
        while (str1.substr(i, str2.length()) == str2)
        {
            cout<<str1.substr(i, str2.length())<<endl;
            i += str2.length();
        }
        if(i==0)
            return "";
        return gcdOfStrings(str2, str1.substr(i));
    }
};

思路2

如果存在一个最大字符串X满足条件，那么X一定是str1和str2的前缀。并且X的长度是str1长度和str2长度的公约数。进一步可以发现，X的长度就是str1长度和str2长度的最大公约数,记作gcd_len。因为如果存在一个字符串Y可以除尽str1和str2,那么一定存在长度为gcd_len的字符串X可以除尽str1和str2。

python 里//是整除，/是结果为浮点数的除。python里实现了str类型的*来实现字符串的自连接。

c++代码


class Solution
{
    // 判断字符串t是否能够通过自连接构成字符串s
    bool check(string s,string t){
        int len=s.length()/t.length();
        string tt="";
        while(len--){
            tt+=t;
        }
        if(tt==s){
            return true;
        }
        return false;

    }
public:
    string gcdOfStrings(string str1, string str2)
    {
        int len1 = str1.length(), len2 = str2.length();
        int gcd_len = __gcd(len1, len2);
        if (check(str1, str2.substr(0, gcd_len)) && check(str2, str1.substr(0, gcd_len)))
        {
            return str1.substr(0,gcd_len);
        }else{
            return "";
        }
    }
};

python代码


class Solution:
      
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        
        len1=len(str1)
        len2=len(str2)
        gcd_len=gcd(len1,len2)
        gcd_str=str1[:gcd_len]
        if gcd_str*(len1//gcd_len)==str1 and gcd_str*(len2//gcd_len)==str2:
            return gcd_str
        else:
            return ""

1431. 拥有最多糖果的孩子

python 代码


class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:
        max_value=max(candies)
        return [candy+extraCandies>=max_value for candy in candies]

c++ 代码


class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int max_value=*max_element(candies.begin(),candies.end());
        vector<bool>ans;
        for(auto x:candies){
            if(x+extraCandies>=max_value){
                ans.push_back(true);
            }else{
                ans.push_back(false);
            }
        }
        return ans;

    }
};

1. 两数之和

python代码


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mp={}
        for i,x in enumerate(nums):
            if target-x in mp:
                return [i,mp[target-x]]
            else:
                mp[x]=i
        return []

c++代码


#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        unordered_map<int, int> mp;
        for (int i = 0; i < nums.size(); i++)
        {
            if (mp.count(target-nums[i])==0){
                mp[nums[i]]=i;
            }else{
                return {i,mp[target-nums[i]]};
            }
        }
        return {};
    }
};

605. 种花问题

贪心。从头遍历到尾，遇到能种的的就种下。

c++代码


#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        rep(i,flowerbed.size()){
            if(flowerbed[i]==1)
                continue;
            if(((i-1<0)||flowerbed[i-1]==0)&&((i+1>=flowerbed.size())||flowerbed[i+1]==0)){
                n--;
                i++;
            }
        }
        if(n<=0){
            return true;
        }
        return false;
        
    }
};

python代码


class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        for i,x in enumerate(flowerbed):
            if x==1 :
                continue
            if (i-1<0 or flowerbed[i-1]==0) and (i+1>=len(flowerbed) or flowerbed[i+1]==0):
                n-=1
                flowerbed[i]=1
        if n<=0:
            return True
        return False

345. 反转字符串中的元音字母

双指针分别从头尾遍历，遇到元音就交换。

python里字符串是不可修改的，所以需要转换成列表

''.join(iterable)将可迭代对象拼接成字符串

python代码


class Solution:
       
    def reverseVowels(self, s: str) -> str:
        def check(ch:str)->bool:
            s="aeiouAEIOIU"
            return ch in s
        s=list(s)
        s_len=len(s)
        i,j=0,s_len-1
        while i<j:
            while i<j and not check(s[i]):
                i+=1
            while i<j and not check(s[j]):
                j-=1
            if i<j:
                s[i],s[j]=s[j],s[i]
                i+=1
                j-=1
        return ''.join(s)

c++代码


#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
class Solution {
    bool check(char ch){
        string s="aeiouAEIOU";
        rep(i,s.length()){
            if(ch==s[i]){
                return true;
            }
        }
        return false;
        
    }
public:
    string reverseVowels(string s) {
        int len=s.length();
        for(int i=0,j=len-1;i<j;){
          
            while(i<j&&!check(s[i])){
                i++;
            }
            while (j>i&&!check(s[j]))
            {
                j--;
            }   
            if(i<j){
                swap(s[i],s[j]);
                i++;
                j--;
            }
            
        }
        return s;
    }
};

151. 反转字符串中的单词

''.join()和' '.join() 注意区分。

c++代码


#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
class Solution {
public:
    string reverseWords(string s) {
        int i=0,len=s.length();
        vector<string>word_list;
        while(i<len){
            while(i<len&&s[i]==' ')
                i++;
            int j=i;
            while(j<len&&s[j]!=' ')
                j++;
            if(i!=j)
                word_list.push_back(s.substr(i,j-i));
            i=j+1;
            
        }
        string ss=word_list[word_list.size()-1];
        for(int i=word_list.size()-2;i>=0;i--){
            ss+=" ";
            ss+=word_list[i];
            
        }
        return ss;

    }
};

python代码


class Solution:
    def reverseWords(self, s: str) -> str:
        words=s.split()
        words.reverse()
        return ' '.join(words)

238. 除自身以外数组的乘积

ans=[1]*len(nums):定义一个长度为len(nums)，值全部为1的列表

c++代码


#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int len = nums.size();
        vector<int> ans;
        vector<int> lsum(len), rsum(len);
        rep(i, len)
        {
            if(i-1>=0)
                lsum[i] = lsum[i - 1] * nums[i];
            else    
                lsum[i]=nums[0];
        }
        for(int i=len-1;i>=0;i--){
            if(i+1<len){
                rsum[i]=rsum[i+1]*nums[i];
            }else{
                rsum[i]=nums[len-1];
            }
        }
        rep(i,len){
            int x=1;
            if(i>0)
                x*=lsum[i-1];
            if(i<len-1)
                x*=rsum[i+1];
            ans.push_back(x);
        }
        return ans;
    }
};

python代码


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans=[1]*len(nums)
        left,right=1,1
        for i in range(len(nums)):
            ans[i]*=left
            left*=nums[i]
            ans[len(nums)-1-i]*=right
            right*=nums[len(nums)-1-i]
        return ans

334. 递增的三元子序列

python代码


class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        inf=2e31+1
        n=len(nums)
        minn,maxn=[0]*n,[0]*n
        minn[0]=nums[0]
        maxn[n-1]=nums[n-1]
        for i in range(1,n,1):
            minn[i]=min(minn[i-1],nums[i])
            # print(minn[i])
        for i in range(n-2,-1,-1):
            maxn[i]=max(maxn[i+1],nums[i])
            # print(maxn[i])
        flag=False
        for i in range(1,n-1,1):
            print(nums[i],minn[i-1],maxn[i+1])
            if minn[i-1]<nums[i] and maxn[i+1]>nums[i]:
                flag=True
                break
        return flag

1657. 确定两个字符串是否接近

Counter()获取集合中每个元素的计数信息，并以字典的形式返回。

python


class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        cnt1,cnt2=Counter(word1),Counter(word2)
        return cnt1.keys()==cnt2.keys() and sorted(cnt2.values())==sorted(cnt1.values())

2390. 从字符串中移除星号

python 中用列表实现栈的功能

python


class Solution:
    def removeStars(self, s: str) -> str:
        slist=[]
        for x in s:
            if x!='*':
                slist.append(x)
            else:
                slist.pop()
        return ''.join(slist)