哈希

1.两数之和

快速查找需求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
public:
    vector<int> twoSum(vector<int>& nums,int target){
        unordered_map<int,int> hashtable;
        for(int i=0;i<nums.size();i++){
            auto it = hashtable.find(target-nums[i]);
            if(it !=hashtable.end()){
                return {i,it->second};
            }
            hashtable[nums[i]]=i;
        }
        return {};
    }
};
1
2
3
4
5
6
7
8
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable={}
        for i in range(len(nums)):
            if target-nums[i] in hashtable:
                return [i,hashtable[target-nums[i]]]
            hashtable[nums[i]] =i
        return []

面试题 16.15 珠玑妙算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> masterMind(string solution, string guess) {
        int ri= 0,fr=0;
        int dic[4][2] = {0};
        unordered_map<char,int> char_to_index = {{'R',0},{'Y',1},{'G',2},{'B',3}};
        for(int i=0;i<4;i++){
            char s=solution[i],g = guess[i];
            if(s==g)
                ri++;
            else{
                dic[char_to_index[s]][0]++;
                dic[char_to_index[g]][1]++;
            }
        }
        for(int i=0;i<4;i++)
            fr+=min(dic[i][0],dic[i][1]);
        return {ri,fr};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 低效
class Solution:
    def masterMind(self, solution: str, guess: str) -> List[int]:
        hash_sol,hash_gue = defaultdict(int),defaultdict(int)
        right,fr=0,0
        for i in range(4):
            if solution[i]==guess[i]:
                right += 1
            else:
                hash_gue[guess[i]]+=1
                hash_sol[solution[i]]+=1
        for key in hash_gue:
            if key in hash_sol:
                fr += min (hash_sol[key],hash_gue[key])
        return [right,fr]
# 优化
from typing import List

class Solution:
    def masterMind(self, solution: str, guess: str) -> List[int]:
        # 初始化猜中次数和伪猜中次数
        corr, err = 0, 0
        
        # 使用列表代替字典，索引对应字符：
        # 0: 'R', 1: 'Y', 2: 'G', 3: 'B'
        # dic[char][0]: solution 中未匹配的字符数量
        # dic[char][1]: guess 中未匹配的字符数量
        dic = [[0, 0] for _ in range(4)]
        
        # 字符到索引的映射
        char_to_index = {'R': 0, 'Y': 1, 'G': 2, 'B': 3}
        
        # 遍历字符串，统计猜中次数和未匹配字符
        for i in range(4):
            s, g = solution[i], guess[i]
            if s == g:
                corr += 1
            else:
                # 更新 solution 中未匹配字符的数量
                dic[char_to_index[s]][0] += 1
                # 更新 guess 中未匹配字符的数量
                dic[char_to_index[g]][1] += 1
        
        # 计算伪猜中次数
        for count_sol, count_gue in dic:
            err += min(count_sol, count_gue)
        
        return [corr, err]

1941 检查是否所有字符出现次数相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool areOccurrencesEqual(string s) {
        unordered_map<char ,int> hashtable;
        for (char c :s)
            hashtable[c]++;
        int n = hashtable[s[0]];
        for(char c :s){
            if(hashtable[c]!=n)
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        hashtable = defaultdict(int)
        for i in s:
            hashtable[i]+=1
        n = hashtable[s[0]]
        for i in hashtable:
            if n!=hashtable[i]:
                return False
        return True
# 优化
class Solution:
    def areOccurrencesEqual(self, s: str) -> bool:
        c = Counter(s)
        return len(set(c.values())) == 1

13 罗马数字转整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int romanToInt(string s) {
        unordered_map <char,int> dic = {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
        /*
        // 使用数组代替 unordered_map更快
        int dic[256] = {0}; // ASCII 表大小为 256
        dic['I'] = 1;
        dic['V'] = 5;
        dic['X'] = 10;
        dic['L'] = 50;
        dic['C'] = 100;
        dic['D'] = 500;
        dic['M'] = 1000;
        */
        int result = 0;
        for(int i =0;i<s.length();i++){
            if(i!=s.length()-1 && dic[s[i]]<dic[s[i+1]])
                result-=dic[s[i]];
            else
                result+=dic[s[i]];
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
class Solution:
    def romanToInt(self, s: str) -> int:
        dic = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        result = 0
        for  i in range(len(s)):
            if i !=len(s)-1 and dic[s[i]] < dic[s[i+1]]  :
                result -= dic[s[i]]
            else:
                result += dic[s[i]]
        return result

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        int n=s.length(),r=0,ans=0;
        for(int l = 0;l<n;l++){
            if(l!=0){
                set.erase(s[l-1]);
            }
            while(r<n && set.count(s[r])==0){
                set.insert(s[r]);
                r++;
            }
            ans = max(ans,r-l);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        occ = set()
        n = len(s)
        r,ans=0,0
        for l in range(n):
            if l != 0:
                occ.remove(s[l-1])
            while r<n and s[r] not in occ:
                occ.add(s[r])
                r+=1
            ans = max (ans,r-l)
        return ans

动态规划

5.最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string longestPalindrome(string s) {
        string result = "",odd,even;
        for(int i=0;i<s.length();i++){
            odd = expand(s,i,i);
            even = expand(s,i,i+1);
            if(odd.length()>result.length()) result = odd;
            if(even.length()>result.length()) result = even;
        }
        return result;        
    }
    string expand(string s,int l,int r){
        while(l>=0 && r<s.length() && s[l]==s[r]){
            l--,r++;
        }
        return s.substr(l+1,r-l-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        dp = [[False] * n for _ in range(n)]  # 初始化 dp 数组
        start, end = 0, 0  # 记录最长回文子串的起始和结束位置
        
        # 单个字符一定是回文
        for i in range(n):
            dp[i][i] = True
        
        # 检查长度为 2 的子串
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start, end = i, i + 1
        
        # 检查长度大于 2 的子串
        for length in range(3, n + 1):  # 子串长度从 3 到 n
            for i in range(n - length + 1):  # 子串起始位置
                j = i + length - 1  # 子串结束位置
                if s[i] == s[j] and dp[i + 1][j - 1]:  # 状态转移
                    dp[i][j] = True
                    if length > (end - start + 1):  # 更新最长回文子串
                        start, end = i, j
        
        return s[start:end + 1]  # 返回最长回文子串
//优化
class Solution:
    def longestPalindrome(self, s: str) -> str:
        def max_hw(l:int, r:int) -> str :
            while l>=0 and r<len(s) and s[l] == s[r]:
                l -= 1
                r += 1
            return s[l+1:r]

        result = s[0]
        for i in range(len(s)):
            odd = max_hw(i,i)
            even = max_hw(i,i+1)
            result = max(result,odd,even,key=len)
        return result

509.斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int fib(int n) {
        int f1=0,f2 =1,temp;
        if(n==0)
            return 0;
        for(int i=0;i<n-1;i++){
            temp = f1+f2;
            f1 = f2;
            f2 = temp;
        }
        return f2;
    }
};
1
2
3
4
5
6
7
8
class Solution:
    def fib(self, n: int) -> int:
        f1 ,f2 ,fn = 0,1,1
        if n ==0 :return 0
        for i in range(n-1):
            fn = f1 + f2
            f1, f2 = f2, fn
        return fn

300.最长增长子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n==0)
            return 0;
        vector<int> dp(n,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};
//优化
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;
        vector<int> dp;
        for(int num:nums){
            auto it = lower_bound(dp.begin(),dp.end(),num);
            if(it == dp.end()){
                dp.push_back(num);
            }
            else{
                *it = num;
            }
        }
        return dp.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        dp = [1]*n
        for i in range(1,n):
            for j in range(i):
                if nums[j]<nums[i]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)
# 优化：二分查找
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        dp = []  # 用于存储递增子序列
        for num in nums:
            # 使用二分查找找到插入位置
            pos = bisect.bisect_left(dp, num)
            if pos == len(dp):
                dp.append(num)  # 如果 num 大于所有元素，直接添加到末尾
            else:
                dp[pos] = num  # 否则替换掉第一个大于等于 num 的元素
        
        return len(dp)  # dp 的长度即为最长递增子序列的长度

72.编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.length(), n2 = word2.length();
        if(n1*n2==0) return n1+n2;
        vector<vector<int>> dp(n1+1,vector<int>(n2+1));
        for(int i=0;i<n1+1;i++) dp[i][0] = i;
        for(int j=0;j<n2+1;j++) dp[0][j] = j;
        for(int i=1;i<n1+1;i++){
            for(int j=1;j<n2+1;j++){
                if(word1[i-1]==word2[j-1])
                    dp[i][j]=dp[i-1][j-1];
                else
                    dp[i][j]=1+min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]});

            }
        }
        return dp[n1][n2];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1, n2 = len(word1), len(word2)
        if n1*n2 == 0:
            return n1+n2
        dp = [[0]*(n2+1) for _ in range(n1+1)]
        for i in range(n1+1):
            dp[i][0]=i
        for j in range(n2+1):
            dp[0][j]=j
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp [i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
        return dp[n1][n2]

198.打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size(),dp0=0,dp1=nums[0],temp;
        for(int i=1;i<n;i++){
            temp = max(dp0,dp1);
            dp1 = dp0 + nums[i];
            dp0 = temp;
        }
        return max(dp0,dp1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n ==0 :
            return 0
        dp = [[0]*2 for _ in range(n)]
        dp[0][1] = nums[0]
        for i in range(1,n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1])
            dp[i][1] = dp[i-1][0]+nums[i]
        return max(dp[n-1][0],dp[n-1][1])

贪心算法