68.文本左右对齐
题目
给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰恰有 maxWidth 个字符,且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单词。须要时可用空格 ’ ’ 添补,使得每行恰恰有 maxWidth 个字符。
要求尽可能匀称分配单词间的空格数目。如果某一行单词间的空格不能匀称分配,则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐,且单词之间不插入额外的空格。
注意
- 单词是指由非空格字符组成的字符序列。
- 每个单词的长度大于 0,小于即是maxWidth。
- 输入单词数组 words 至少包罗一个单词。
数据范围
- 1 <= words.length <= 300
- 1 <= words.length <= 20
- words由小写英文字母和符号组成
- 1 <= maxWidth <= 100
- words.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 和 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;
- }
- };
复制代码 909.蛇梯棋
题目
给你一个大小为 n x n 的整数矩阵 board ,方格按从 1 到 n2 编号,编号遵照 转行交替方式 ,从左下角开始 (即,从 board[n - 1][0] 开始)每一行交替方向。
玩家从棋盘上的方格 1 (总是在最后一行、第一列)开始出发。
每一回合,玩家需要从当前方格 curr 开始出发,按下述要求前进:
- 选定目标方格 next ,目标方格的编号符合范围 [curr + 1, min(curr + 6, n2)] 。
- 该选择模拟了掷 六面体骰子 的情景,无论棋盘大小如何,玩家最多只能有6个目标地。
- 传送玩家:如果目标方格 next 处存在蛇或梯子,那么玩家会传送到蛇或梯子的目标地。否则,玩祖传送到目标方格 next
- 当玩家到达编号 n2 的方格时,游戏结束。
r 行c列的棋盘,按前述方法编号,棋盘格中可能存在 “蛇” 或 “梯子”;如果 board[r][c] != -1,谁人蛇或梯子的目标地将会是 board[r][c]。编号为 1 和 n2 的方格不是任何蛇或梯子的起点。
注意,玩家在每回合的前进过程中最多只能爬过蛇或梯子一次:就算目标地是另一条蛇或梯子的起点,玩家也 不能 继承移动。
举个例子,假设棋盘是 [-1,4],[-1,3]] ,第一次移动,玩家的目标方格是 2 。那么这个玩家将会顺着梯子到达方格 3 ,但 不能 顺着方格 3 上的梯子前往方格 4 。
返回达到编号为 n2 的方格所需的最少移动次数,如果不可能,则返回 -1。
数据范围
- n == board.length == board.length
- 2 <= n <= 20
- board[j] 的值是 -1 或在范围 [1, n2] 内
- 编号为 1 和 n2 的方格上没有蛇或梯子
分析
bfs即可,注意一下蛇形坐标的转换
代码
- typedef pair<int, int> PII;
- class Solution {
- public:
- PII getPos(int x, int n, int m) {
- int t = (x + n - 1) / n;
- if(t % 2) return {n - t, x - (t - 1) * m - 1};
- else return {n - t, m - (x - (t - 1) * m)};
- }
- int res = 0;
- const static int N = 30;
- bool vis[900];
- struct node_ {
- int pos;
- int times;
- };
- bool check(int x, int n) {
- if(vis[x]) return false;
- if(x > n * n || x <= 0) return false;
- return true;
- }
- int bfs(int pos, vector<vector<int>>& board) {
- int n = board.size();
- queue<node_> q;
- q.push({pos, 0});
- // vis[pos] = true;
- while(q.size()) {
- auto now = q.front();
- q.pop();
- for(int i = 1; i <= 6; i ++ ) {
- int ne = now.pos + i;
- if(ne > n * n) break;
- auto npos = getPos(ne, n, n);
- int nx = npos.first, ny = npos.second;
- if(board[nx][ny] > 0) {
- ne = board[nx][ny];
- npos = getPos(board[nx][ny], n, n);
- nx= npos.first, ny = npos.second;
- }
- if(ne == n * n) {
- return now.times + 1;
- }
- if(!vis[ne]) {
- vis[ne] = true;
- q.push({ne, now.times + 1});
- }
- }
- }
- return -1;
- }
- int snakesAndLadders(vector<vector<int>>& board) {
- return bfs(1, board);
- }
- };
复制代码 免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |