力扣8.25

本文主要是介绍力扣8.25，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

68.文本左右对齐

题目

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于maxWidth。
输入单词数组 words 至少包含一个单词。

数据范围

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i]由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth

分析

这是一道双指针的模拟题，分三种情况（题目没说，但其实有个默认条件，就是单词之间至少有一个空格）

情况1：对于最后一行的单词，左对齐，前面的单词分隔一个空格，后面补空格
情况2：对于一行只有一个单词的行，同情况1
情况3：对于一行有多个单词的行，假设那行单词个数为n，空格有k个，则要让左侧空格多于右侧且分布尽可能均匀，很容易想到，对于前k % (n-1)个需要插入k/(n-1)+1个空格，后面的插入k/(n-1)个空格

代码

class Solution {
public:string blank(int n) {return string(n, ' ');}vector<string> fullJustify(vector<string>& words, int maxWidth) {vector<string> res;int idx = 0;int cnt = 0;for(int i = 0; i < words.size(); i ++ ) {// cout << i << ' ';int j = i;int sumSize = 0;cnt = 0;for(j = i; j < words.size(); j ++ ) {sumSize += words[j].size();cnt ++ ;if(sumSize > maxWidth - cnt + 1) break;}if(j < words.size()) {sumSize -= words[j].size();cnt -- ;}string tmp = "";if(cnt == 1) {tmp += words[i];int zsize = tmp.size();tmp += blank(maxWidth - zsize);} else if(j == words.size()) {for(int k = i; k < j; k ++ ) {tmp += words[k];if(tmp.size() < maxWidth) {tmp += " ";}}} else {int last = maxWidth - sumSize;int mod = last % (cnt - 1);int fl = last / (cnt - 1);for(int k = i; k < j; k ++ ) {if(mod != 0) {mod -- ;tmp += words[k];tmp += blank(fl + 1);} else {tmp += words[k];if(k != j - 1) {tmp += blank(fl);}}}}if(tmp.size() < maxWidth) tmp += blank(maxWidth - tmp.size());res.push_back(tmp);i = j - 1;}return res;}
};

392.判断子序列

题目

给定字符串s 和t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

数据范围

0 <= s.length <= 100
0 <= t.length <= 10^4
两个字符串都只由小写字符组成。

分析

双指针，l指针从s开始，r指针从t开始，若s[l]==t[r]，则l和r都往后移动，否则r往后移动

代码

class Solution {
public:bool isSubsequence(string s, string t) {int l = 0, r = 0;while(l < s.size() && r < t.size()) {if(s[l] == t[r]) {l ++ ;r ++ ;} else {r ++ ;}}if(l == s.size()) return true;else return false;}
};

30.串联所有单词的子串

题目

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。

s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = ["ab","cd","ef"]，那么"abcdef"，"abefcd"，"cdabef"， "cdefab"，"efabcd"，和"efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。

数据范围

1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words.length <= 5000
words[i] 和 s 由小写英文字母组成

分析

最开始的暴力解法是遍历s，找到它的所有子串，然后分割子串，然后对每个子串计算它单词数量与words中的进行比较，若没有区别，则加入到答案中，但很不幸的是，它在第180个点处T了，令words.size()为n，s.size()为m，word的长度为k，判断两个子串是否相同使用的是map，因此暴力的复杂度应该是O(m*nlogn)，确实会超时，于是想其它办法。
正解的思路应该是使用滑动窗口，对于任意位置i开始遍历s，设置长度为k*n的滑动窗口，然后记录窗口内单词情况，使用一个map来记录，然后判断是否与words构成的子串有区别

若没区别，则记录答案
否则将窗口向右滑动，更新单词情况
对于遍历的位置i，可以发现只需要从前k个位置开始就能遍历可能的子串，因此实际上是构造了k个滑动窗口

代码

class Solution {
public:unordered_map<string, int> cnts;vector<int> findSubstring(string s, vector<string>& words) {vector<int> res;int wordSize = words[0].size();int len = wordSize * words.size();int n = words.size();int num = words.size();for(int i = 0; i < wordSize && i + len - 1 < s.size(); i ++ ) {cnts.clear();for(int j = i; j < i + len; j += wordSize) {cnts[s.substr(j, wordSize)] ++ ;}for(int j = 0; j < words.size(); j ++ ) {cnts[words[j]] -- ;if(cnts[words[j]] == 0) {cnts.erase(words[j]);}}for(int j = i; j + (n - 1) * wordSize < s.size(); j += wordSize) {if(j == i) {if(cnts.size() == 0) res.emplace_back(j);} else {string ts = s.substr(j + (n - 1) * wordSize, wordSize);cnts[ts] ++ ;if(cnts[ts] == 0) {cnts.erase(ts);}string ts2 = s.substr(j - wordSize, wordSize);cnts[ts2] -- ;if(cnts[ts2] == 0) {cnts.erase(ts2);}if(cnts.size() == 0) res.emplace_back(j);}}}return res;}
};