字符串问题
单词拆分
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
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;
//时间复杂度是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的子结构，看是否在dict中
if(i<j) continue;
if(dict[k] == s.substr(i-j,j)) //取当前的s子结构
{
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); // 相当于 new char[100];
}
}
}
字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
思路：这道题不能用全排列的思路来做，否则一定会出现超时的情况，我们需要两个长度为26的哈希表memo1和memo2，用来记录s1和s2中每个字符出现的次数，我们维护一个长度为s1.size()的滑动窗口，逐渐从0到s2.size()滑动，如果滑动窗口内的memo2累计的在窗口内的各个字符对应次数等于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;
}
翻转字符串里的单词
输入: "the sky is blue",
输出: "blue is sky the".
思路：先把字符串整个反转，然后找第一个空格的地方，然后，反转开始到空格的地方
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);
}
[翻转字符串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函数，每次读/之间的字母
#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;
}
数字拼接最小值
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323
思路：数字m和n,两种拼接方式mn和nm,因为长度都一样，所以可以用比较字符串的方式比较他们的大小。用快速排序，得到的第一个字符串表示和其他字符串的组合，它都需要放在前面才能使得组合的数字更小，所以它在排序的结果中位于第一个
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;
}
字符串翻转
这道题考的核心是是不是可以灵活利用字符串翻转。假设字符串abcdef，n=3，设X=abc，Y=def，所以字符串可以表示成XY，如题干，问如何求得YX。假设X的翻转为XT，XT=cba，同理YT=fed，那么YX=(XTYT)T，三次翻转后可得结果。
表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路:
E后面一定是数字并且不能同时出现两个E
不能出现两个小数点 并且小数点不能出现在E后面
如果符号第二次出现，则符号前面的字符一定是E (-1E-16)
如果符号是第一次出现并且不是在第一位，那么符号前面的字符也一定是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;
}
最大子序列和：加和，有负数就抛弃，重新加和
求最大子序列和
int a[]={0,-2,3,5,-1,2};
res:9 (3,5,-1,2)
连续，如果是不连续的，就是取正数加和就</pre>
最大子序和，需要连续
//遍历这个数组，一个一个加，同时用变量标记和当前求和比较，保存最大值，当当前求和是小于0时
//直接丢弃，重新加和
int Sum(int *a, int n){
int res=INT_MIN; //注意这个地方，当数组里面都是负数时
int sum=0;
for(int i=0;i<n;i++){ //当前面的sum<0是，再加后面的只会更小，所以丢弃
if(sum<0){
sum=a[i];
}else{
sum+=a[i];
}
if(sum>res){
res=sum;
}
}
return res;
}
//最小子序和，需要连续，和上面逻辑一样
//遍历这个数组，一个一个加，同时用变量标记和当前求和比较，保存最小值，当当前求和是大于0时
//直接丢弃，重新加和
int Sum(int *a, int n){
int res=INT_MAX; //注意这个地方，当数组里面都是正数时
int sum=0;
for(int i=0;i<n;i++){ //当前面的sum>0的时候，再加后面的只会更大，所以丢弃
if(sum>0){
sum=a[i];
}else{
sum+=a[i];
}
if(sum<res){
res=sum;
}
}
return res;
}
//乘积最大子序列
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
//因为有负数的关系，所以需要记录最大值、最小值两个
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];//因为mx更新了，算mn的时候需要
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;
}
//同时打印了开始和结束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;
}
最长连续序列：map结构来存储左右区间的长度
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路：声明一个map，此题中，最后map表示{100:1, 4:4, 200:1, 1:4, 3:2, 2:4}
取出其左右相邻数已有的连续区间长度 left 和 right
计算当前数的区间长度为：cur_length = left + right + 1
根据 cur_length 更新最大长度 max_length 的值
更新区间两端点的长度值
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之前的数比较
//求最长子序列的个数
int a[]={1,5,8,2,3,4};
res:4 (1,2,3,4)
不连续，如果是连续的比较简单
三种种计算方式O(N^2) 和 O(NlogN)
一种是两次循环；第二种是将数组排序后，与原数组求最长公共子序列；
第三种用动态规划，用一个数组保存子序列，在第二次循环的时候用二分查找，
第三种方法可以打印出最长的子序列
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
注意最长公共子序列不连续
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[i]!=Y[j]时，需要从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]); //同上一样，不过这里应该是0
}
}
}
return dp[m][n];
}
最长不重复子串：用set记录，有重复就删除前面的
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
遍历一遍数组，用set存数字，如果有重复的就把之前的一个丢弃。mx维护一个最大值
i:表示起始位置，所以判断时用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是否是回文串
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
用数组a[i][j](取值只有0，1)表示字符串从i到j是否是回文串
用i-j+1表是回文长度，记录最长的回文子串，同时记录开始位置j
之所以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]; //当长度大于2时，需要再判断内部
if(j-i+1 > max && a[i][j]){
max=j-i+1;
start=j;
}
}
}
return s.substr(start,max);
}
三个数的最大乘积
分析： 对于如果使三个数乘积达到最大，大家都会想到将三个值都取到最大即可，
蛋式还有一种情况就是两个最小的负数和最大的正数也可能达到最大值。
方法一：先将数组进行升序排序，然后找出上述的两种情况取较大值。（时间复杂度O(nlog2 n)，额外空间复杂度O(1)）
方法二：扫描数组，直接确定上面两种情况需要的五个值。（时间复杂度O(n)，额外空间复杂度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
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
先按第一个排序，第一个数大小一样的，按第二个降序排列，然后找第二个的最长递增子序列
先按第一个排序，第一个数大小一样的，按第二个降序排列，然后找第二个的最长递增子序列
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;
}
