字符串問題
單詞拆分
輸入: s = "applepenapple", wordDict = ["apple", "pen"]
輸出: true
解釋: 返回 true 因?yàn)?"applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重復(fù)使用字典中的單詞圆仔。
bool wordBreak(string &s, vector<string> &dict) {
int n= s.length();
if(n == 0) return true;
if(dict.size() == 0) return false;
vector<bool> res(n+1,false);
res[0] = true;
//時(shí)間復(fù)雜度是O(n*m)
for(int i=1; i<=n; i++)
{
for(int k=0; k<dict.size(); ++k)
{
int j = dict[k].size(); //從0開始找s的子結(jié)構(gòu)细办，看是否在dict中
if(i<j) continue;
if(dict[k] == s.substr(i-j,j)) //取當(dāng)前的s子結(jié)構(gòu)
{
if(res[i-j])
{
res[i] = true;
}
}
}
}
return res[n];
}
單詞拆分2
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:[ "cats and dog", "cat sand dog"]
思路：dfs母怜，回溯
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
vector<string> res;
string out;
vector<bool> possible(s.size() + 1, true);
wordBreakDFS(s, wordDict, 0, possible, out, res);
return res;
}
void wordBreakDFS(string &s, unordered_set<string> &wordDict, int start, vector<bool> &possible, string &out, vector<string> &res) {
if (start == s.size()) {
res.push_back(out.substr(0, out.size() - 1));
return;
}
for (int i = start; i < s.size(); ++i) {
string word = s.substr(start, i - start + 1);
if (wordDict.find(word) != wordDict.end() && possible[i + 1]) {
out.append(word).append(" ");
int oldSize = res.size();
wordBreakDFS(s, wordDict, i + 1, possible, out, res);
if (res.size() == oldSize) possible[i + 1] = false;
out.resize(out.size() - word.size() - 1); //s.resize(100); // 相當(dāng)于 new char[100];
}
}
}
字符串的排列
給定兩個字符串 s1 和 s2禽翼，寫一個函數(shù)來判斷 s2 是否包含 s1 的排列。
輸入: s1 = "ab" s2 = "eidbaooo"
輸出: True
解釋: s2 包含 s1 的排列之一 ("ba").
思路：這道題不能用全排列的思路來做梁厉，否則一定會出現(xiàn)超時(shí)的情況滑废，我們需要兩個長度為26的哈希表memo1和memo2，用來記錄s1和s2中每個字符出現(xiàn)的次數(shù)寂屏，我們維護(hù)一個長度為s1.size()的滑動窗口贰谣，逐漸從0到s2.size()滑動，如果滑動窗口內(nèi)的memo2累計(jì)的在窗口內(nèi)的各個字符對應(yīng)次數(shù)等于memo1迁霎，那么返回true吱抚，否則返回false
bool checkInclusion(string s1, string s2) {
if (s1.size() > s2.size()) return false;
vector<int> memo1(26, 0);
vector<int> memo2(26, 0);
for (int i = 0; i < s1.size(); i++) {
memo1[s1[i] - 'a']++;
}
for (int i = 0; i < s2.size(); i++) {
if(i<s1.size()) memo2[s2[i] - 'a']++;
else {
memo2[s2[i] - 'a']++;
memo2[s2[i-s1.size()] - 'a']--;
}
if (memo1 == memo2) return true;
}
return false;
}
翻轉(zhuǎn)字符串里的單詞
輸入: "the sky is blue",
輸出: "blue is sky the".
思路：先把字符串整個反轉(zhuǎn)，然后找第一個空格的地方考廉，然后秘豹，反轉(zhuǎn)開始到空格的地方
void reverseWords(string &s) {
int storeIndex = 0, n = s.size();
reverse(s.begin(), s.end());
for (int i = 0; i < n; ++i) {
if (s[i] != ' ') {
if (storeIndex != 0) s[storeIndex++] = ' ';
int j = i;
while (j < n && s[j] != ' ') s[storeIndex++] = s[j++];
reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
i = j;
}
}
s.resize(storeIndex);
}
[翻轉(zhuǎn)字符串2]
輸入：["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
輸出：["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
void reverseWords(vector<char>& str) {
reverse(str.begin(), str.end());
for (int i = 0, j = 0; i < str.size(); i = j + 1) {
for (j = i; j < str.size(); ++j) {
if (str[j] == ' ') break;
}
reverse(str.begin() + i, str.begin() + j);
}
}
[簡化路徑]
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
思路：主要是用到getline函數(shù)，每次讀/之間的字母
#include <sstream>
string simplifyPath(string path) {
string res, t;
stringstream ss(path);
vector<string> v;
while (getline(ss, t, '/')) { //從ss中讀昌粤，存到t中既绕，/不讀
if (t == "" || t == ".") continue;
if (t == ".." && !v.empty()) v.pop_back();
else if (t != "..") v.push_back(t);
}
for (string s : v) res += "/" + s;
return res.empty() ? "/" : res;
}
數(shù)字拼接最小值
輸入一個正整數(shù)數(shù)組，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)涮坐，打印能拼接出的所有數(shù)字中最小的一個凄贩。例如輸入數(shù)組{3，32膊升，321}怎炊，則打印出這三個數(shù)字能排成的最小數(shù)字為321323
思路：數(shù)字m和n,兩種拼接方式mn和nm,因?yàn)殚L度都一樣，所以可以用比較字符串的方式比較他們的大小廓译。用快速排序评肆，得到的第一個字符串表示和其他字符串的組合，它都需要放在前面才能使得組合的數(shù)字更小非区，所以它在排序的結(jié)果中位于第一個
bool compare(const string& str1, const string& str2) {
return str1 + str2 < str2 + str1;
}
string PrintMinNumber(vector<int> numbers) {
vector<string> tb;
for (int i = 0; i < numbers.size(); i++) {
tb.push_back(to_string(numbers[i]));
}
sort(tb.begin(), tb.end(), compare);
string res = "";
for (int i = 0; i < tb.size(); i++) {
res += tb[i];
}
return res;
}
字符串翻轉(zhuǎn)
這道題考的核心是是不是可以靈活利用字符串翻轉(zhuǎn)瓜挽。假設(shè)字符串a(chǎn)bcdef，n=3征绸，設(shè)X=abc久橙，Y=def俄占，所以字符串可以表示成XY，如題干淆衷，問如何求得YX缸榄。假設(shè)X的翻轉(zhuǎn)為XT，XT=cba祝拯，同理YT=fed甚带，那么YX=(XTYT)T，三次翻轉(zhuǎn)后可得結(jié)果佳头。
表示數(shù)值的字符串
請實(shí)現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）鹰贵。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值康嘉。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是碉输。
思路:
E后面一定是數(shù)字并且不能同時(shí)出現(xiàn)兩個E
不能出現(xiàn)兩個小數(shù)點(diǎn) 并且小數(shù)點(diǎn)不能出現(xiàn)在E后面
如果符號第二次出現(xiàn)，則符號前面的字符一定是E (-1E-16)
如果符號是第一次出現(xiàn)并且不是在第一位亭珍，那么符號前面的字符也一定是E (5e+2)
bool isNumeric(char* string) {
bool sign=false, dot=false, hasE=false;
int i=0;
while(string[i]!='\0'){
if(string[i]=='e' || string[i]=='E'){
if(hasE || string[i+1]=='\0') return false;
hasE = true;
}else if(string[i]=='.'){
if(dot || hasE) return false;
dot = true;
}else if(string[i]=='+' || string[i]=='-'){
if(sign && string[i-1]!='E' && string[i-1]!='e') return false;
if(!sign && i>0 && string[i-1]!='E' && string[i-1]!='e') return false;
sign = true;
}else if(!isdigit(string[i])) return false;
i++;
}
return true;
}
字符串相乘
string multiply(string num1, string num2) {
string res;
int n1 = num1.size(), n2 = num2.size();
int k = n1 + n2 - 2, carry = 0;
vector<int> v(n1 + n2, 0);
for (int i = 0; i < n1; ++i) {
for (int j = 0; j < n2; ++j) {
v[k - i - j] += (num1[i] - '0') * (num2[j] - '0');
}
}
for (int i = 0; i < n1 + n2; ++i) {
v[i] += carry;
carry = v[i] / 10;
v[i] %= 10;
}
int i = n1 + n2 - 1;
while (v[i] == 0) --i;
if (i < 0) return "0";
while (i >= 0) res.push_back(v[i--] + '0');
return res;
}
最大子序列和：加和敷钾，有負(fù)數(shù)就拋棄，重新加和
求最大子序列和
int a[]={0,-2,3,5,-1,2};
res:9 (3,5,-1,2)
連續(xù)肄梨，如果是不連續(xù)的闰非，就是取正數(shù)加和就</pre>
最大子序和，需要連續(xù)
//遍歷這個數(shù)組峭范，一個一個加，同時(shí)用變量標(biāo)記和當(dāng)前求和比較瘪贱，保存最大值纱控，當(dāng)當(dāng)前求和是小于0時(shí)
//直接丟棄，重新加和
int Sum(int *a, int n){
int res=INT_MIN; //注意這個地方菜秦，當(dāng)數(shù)組里面都是負(fù)數(shù)時(shí)
int sum=0;
for(int i=0;i<n;i++){ //當(dāng)前面的sum<0是甜害，再加后面的只會更小，所以丟棄
if(sum<0){
sum=a[i];
}else{
sum+=a[i];
}
if(sum>res){
res=sum;
}
}
return res;
}
//最小子序和球昨，需要連續(xù)尔店，和上面邏輯一樣
//遍歷這個數(shù)組，一個一個加主慰，同時(shí)用變量標(biāo)記和當(dāng)前求和比較嚣州，保存最小值，當(dāng)當(dāng)前求和是大于0時(shí)
//直接丟棄共螺，重新加和
int Sum(int *a, int n){
int res=INT_MAX; //注意這個地方该肴，當(dāng)數(shù)組里面都是正數(shù)時(shí)
int sum=0;
for(int i=0;i<n;i++){ //當(dāng)前面的sum>0的時(shí)候，再加后面的只會更大藐不，所以丟棄
if(sum>0){
sum=a[i];
}else{
sum+=a[i];
}
if(sum<res){
res=sum;
}
}
return res;
}
//乘積最大子序列
輸入: [2,3,-2,4]
輸出: 6
解釋: 子數(shù)組 [2,3] 有最大乘積 6匀哄。
//因?yàn)橛胸?fù)數(shù)的關(guān)系秦效，所以需要記錄最大值、最小值兩個
int maxProduct(vector<int>& nums) {
int res=nums[0];
int mx=nums[0];
int mn=nums[0];
for(int i=1;i<nums.size();i++){
int tmp=mx*nums[i];//因?yàn)閙x更新了涎嚼，算mn的時(shí)候需要
mx=max(nums[i], max(mx*nums[i], mn*nums[i]));
mn=min(nums[i], min(tmp, mn*nums[i]));
if(mx>res){
res=mx;
}
}
return res;
}
//同時(shí)打印了開始和結(jié)束index
vector<int> Sum(int *a, int n){
int res=INT_MIN;
int sum=0;
int tmp=0,end=0,start=0;
vector<int> result;
for(int i=0;i<n;i++){
if(sum<0){
sum=a[i];
tmp=i;
}else{
sum+=a[i];
}
if(sum>res){
res=sum;
start=tmp;
end=i;
}
}
result.push_back(res);
result.push_back(start);
result.push_back(end);
return result;
}
最長連續(xù)序列：map結(jié)構(gòu)來存儲左右區(qū)間的長度
輸入: [100, 4, 200, 1, 3, 2]
輸出: 4
解釋: 最長連續(xù)序列是 [1, 2, 3, 4]阱州。它的長度為 4。
思路：聲明一個map法梯，此題中苔货，最后map表示{100:1, 4:4, 200:1, 1:4, 3:2, 2:4}
取出其左右相鄰數(shù)已有的連續(xù)區(qū)間長度 left 和 right
計(jì)算當(dāng)前數(shù)的區(qū)間長度為：cur_length = left + right + 1
根據(jù) cur_length 更新最大長度 max_length 的值
更新區(qū)間兩端點(diǎn)的長度值
int longestConsecutive(vector<int>& nums) {
unordered_map<int,int> ma;
int ans=0;
for(int i=0;i<nums.size();i++){
int t=nums[i];
if(!ma[t]){
int l=ma[t-1],r=ma[t+1];
ma[t]=ma[t+r]=ma[t-l]=l+r+1;
ans=max(ans,ma[t]);
}
}
return ans;
}
最長遞增子序列：遍歷i，和i之前的數(shù)比較
//求最長子序列的個數(shù)
int a[]={1,5,8,2,3,4};
res:4 (1,2,3,4)
不連續(xù)鹊汛，如果是連續(xù)的比較簡單
三種種計(jì)算方式O(N^2) 和 O(NlogN)
一種是兩次循環(huán)蒲赂；第二種是將數(shù)組排序后，與原數(shù)組求最長公共子序列刁憋；
第三種用動態(tài)規(guī)劃滥嘴，用一個數(shù)組保存子序列，在第二次循環(huán)的時(shí)候用二分查找至耻，
第三種方法可以打印出最長的子序列
int helper(int *a, int n){
vector<int> tmp(n,1);// 1,1,1,1,1,1
int mx=1;
vector<int> result; // 這里去掉
for(int i=1;i<n;++i){
for(int j=0;j<i;j++){
if(a[i]>a[j]){
tmp[i]=max(tmp[i],tmp[j]+1);
mx=max(tmp[i], mx);
}
}
}
return mx;
}
最長公共子序列
X="GHHABDCAB"和Y=“BDCAMBAE”,
最長公共子序列為:BDCAB
注意最長公共子序列不連續(xù)
image.png
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1)); //需要有個base
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (text1[i]==text2[j]) {
dp[i+1][j+1] = dp[i][j]+1;
} else {
dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[m][n];
}
最長公共子串
最長公共子串和序列不同的是若皱，它是連續(xù)的，所以當(dāng)X[i]!=Y[j]時(shí)尘颓，需要從0開始重新掃描
image.png
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1)); //需要有個base
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (text1[i]==text2[j]) {
dp[i+1][j+1] = dp[i][j]+1;
} else {
dp[i+1][j+1]=max(dp[i][j+1], dp[i+1][j]); //同上一樣走触，不過這里應(yīng)該是0
}
}
}
return dp[m][n];
}
最長不重復(fù)子串：用set記錄，有重復(fù)就刪除前面的
輸入: s = "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"疤苹，所以其長度為 3互广。
遍歷一遍數(shù)組，用set存數(shù)字卧土，如果有重復(fù)的就把之前的一個丟棄惫皱。mx維護(hù)一個最大值
i:表示起始位置，所以判斷時(shí)用i+mx<n && j<n
j:表示終止位置尤莺，mx=j-i+1
int lengthOfLongestSubstring(string s) {
int n=s.size();
if (n==0) return 0;
int mx=1, i=0, j=0;
set<int> res;
while(i+mx<n && j<n){
if(res.find(s[j]) != res.end()){
res.erase(s[i++]);
}else{
res.insert(s[j++]);
mx=max(mx,j-i);
}
}
return mx;
}
最長回文子串：用a[i][j]表示從i到j(luò)是否是回文串
輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案旅敷。
用數(shù)組a[i][j](取值只有0，1)表示字符串從i到j(luò)是否是回文串
用i-j+1表是回文長度颤霎，記錄最長的回文子串媳谁，同時(shí)記錄開始位置j
之所以j是開始位置，是習(xí)慣計(jì)算矩陣的左下角(在本題中友酱，是一個對稱矩陣)
string longestStr(string s){
int n=s.size();
vector<vector<int, int>> vec(0);
int max=0, start=0;
for(int i=0; i<n; ++i){
for(int j=0; j<=i; ++j){ // 這里等號是需要的晴音，對角線是1
if(i-j <=2) a[i][j] = s[i]==s[j];
else a[i][j] = (s[i]==s[j]) && s[i-1][j+1]; //當(dāng)長度大于2時(shí)，需要再判斷內(nèi)部
if(j-i+1 > max && a[i][j]){
max=j-i+1;
start=j;
}
}
}
return s.substr(start,max);
}
三個數(shù)的最大乘積
分析： 對于如果使三個數(shù)乘積達(dá)到最大缔杉，大家都會想到將三個值都取到最大即可段多，
蛋式還有一種情況就是兩個最小的負(fù)數(shù)和最大的正數(shù)也可能達(dá)到最大值。
方法一：先將數(shù)組進(jìn)行升序排序壮吩，然后找出上述的兩種情況取較大值进苍。（時(shí)間復(fù)雜度O(nlog2 n)加缘，額外空間復(fù)雜度O(1)）
方法二：掃描數(shù)組，直接確定上面兩種情況需要的五個值觉啊。（時(shí)間復(fù)雜度O(n)拣宏，額外空間復(fù)雜度O(1)）
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
return max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
}
};
信封嵌套問題(最長遞增子序列)
輸入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出：3
解釋：最多信封的個數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。
先按第一個排序杠人，第一個數(shù)大小一樣的勋乾，按第二個降序排列，然后找第二個的最長遞增子序列
先按第一個排序嗡善，第一個數(shù)大小一樣的辑莫，按第二個降序排列，然后找第二個的最長遞增子序列
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty()) {
return 0;
}
int n = envelopes.size();
sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
});
vector<int> f(n, 1); // 最長遞增子序列罩引，同上面一樣
int mx=1;
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (envelopes[j][1] < envelopes[i][1]) {
f[i] = max(f[i], f[j] + 1);
mx = max(f[i], mx);
}
}
}
return mx;
}
