ToB企服应用市场:ToB评测及商务社交产业平台
标题:
力扣8.25
[打印本页]
作者:
惊落一身雪
时间:
2024-8-27 09:00
标题:
力扣8.25
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企服之家，中国第一个企服评测及商务社交产业平台。
欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)
Powered by Discuz! X3.4