力扣8.25

打印 上一主题 下一主题

主题 537|帖子 537|积分 1611

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)个空格
代码

  1. class Solution {
  2. public:
  3.     string blank(int n) {
  4.         return string(n, ' ');
  5.     }
  6.     vector<string> fullJustify(vector<string>& words, int maxWidth) {
  7.         vector<string> res;
  8.         int idx = 0;
  9.         int cnt = 0;
  10.         for(int i = 0; i < words.size(); i ++ ) {
  11.             // cout << i << ' ';
  12.             int j = i;
  13.             int sumSize = 0;
  14.             cnt = 0;
  15.             for(j = i; j < words.size(); j ++ ) {
  16.                 sumSize += words[j].size();
  17.                 cnt ++ ;
  18.                 if(sumSize > maxWidth - cnt + 1) break;
  19.             }
  20.             if(j < words.size()) {
  21.                 sumSize -= words[j].size();
  22.                 cnt -- ;
  23.             }
  24.             string tmp = "";
  25.             if(cnt == 1) {
  26.                 tmp += words[i];
  27.                 int zsize = tmp.size();
  28.                 tmp += blank(maxWidth - zsize);
  29.             } else if(j == words.size()) {
  30.                 for(int k = i; k < j; k ++ ) {
  31.                     tmp += words[k];
  32.                     if(tmp.size() < maxWidth) {
  33.                         tmp += " ";
  34.                     }
  35.                 }
  36.             } else {
  37.                 int last = maxWidth - sumSize;
  38.                 int mod = last % (cnt - 1);
  39.                 int fl = last / (cnt - 1);
  40.                 for(int k = i; k < j; k ++ ) {
  41.                     if(mod != 0) {
  42.                         mod -- ;
  43.                         tmp += words[k];
  44.                         tmp += blank(fl + 1);
  45.                     } else {
  46.                         tmp += words[k];
  47.                         if(k != j - 1) {
  48.                             tmp += blank(fl);
  49.                         }
  50.                     }
  51.                 }
  52.             }
  53.             if(tmp.size() < maxWidth) tmp += blank(maxWidth - tmp.size());
  54.             res.push_back(tmp);
  55.             i = j - 1;
  56.         }
  57.         return res;
  58.     }
  59. };
复制代码

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往后移动
代码

  1. class Solution {
  2. public:
  3.     bool isSubsequence(string s, string t) {
  4.         int l = 0, r = 0;
  5.         while(l < s.size() && r < t.size()) {
  6.             if(s[l] == t[r]) {
  7.                 l ++ ;
  8.                 r ++ ;
  9.             } else {
  10.                 r ++ ;
  11.             }
  12.         }
  13.         if(l == s.size()) return true;
  14.         else return false;
  15.     }
  16. };
复制代码

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个滑动窗口
代码

  1. class Solution {
  2. public:
  3.     unordered_map<string, int> cnts;
  4.     vector<int> findSubstring(string s, vector<string>& words) {
  5.         vector<int> res;
  6.         int wordSize = words[0].size();
  7.         int len = wordSize * words.size();
  8.         int n = words.size();
  9.         int num = words.size();
  10.         for(int i = 0; i < wordSize && i + len - 1 < s.size(); i ++ ) {
  11.             cnts.clear();
  12.             for(int j = i; j < i + len; j += wordSize) {
  13.                 cnts[s.substr(j, wordSize)] ++ ;
  14.             }
  15.             for(int j = 0; j < words.size(); j ++ ) {
  16.                 cnts[words[j]] -- ;
  17.                 if(cnts[words[j]] == 0) {
  18.                     cnts.erase(words[j]);
  19.                 }
  20.             }
  21.             for(int j = i; j + (n - 1) * wordSize < s.size(); j += wordSize) {
  22.                 if(j == i) {
  23.                     if(cnts.size() == 0) res.emplace_back(j);
  24.                 } else {
  25.                     string ts = s.substr(j + (n - 1) * wordSize, wordSize);
  26.                     cnts[ts] ++ ;
  27.                     if(cnts[ts] == 0) {
  28.                         cnts.erase(ts);
  29.                     }
  30.                     string ts2 = s.substr(j - wordSize, wordSize);
  31.                     cnts[ts2] -- ;
  32.                     if(cnts[ts2] == 0) {
  33.                         cnts.erase(ts2);
  34.                     }
  35.                     if(cnts.size() == 0) res.emplace_back(j);
  36.                 }
  37.             }
  38.         }
  39.         return res;
  40.     }
  41. };
复制代码

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即可,注意一下蛇形坐标的转换
代码

  1. typedef pair<int, int> PII;
  2. class Solution {
  3. public:
  4.     PII getPos(int x, int n, int m) {
  5.         int t = (x + n - 1) / n;
  6.         if(t % 2) return {n - t, x - (t - 1) * m - 1};
  7.         else return {n - t, m - (x - (t - 1) * m)};
  8.     }
  9.     int res = 0;
  10.     const static int N = 30;
  11.     bool vis[900];
  12.     struct node_ {
  13.         int pos;
  14.         int times;
  15.     };
  16.     bool check(int x, int n) {
  17.         if(vis[x]) return false;
  18.         if(x > n * n || x <= 0) return false;
  19.         return true;
  20.     }
  21.     int bfs(int pos, vector<vector<int>>& board) {
  22.         int n = board.size();
  23.         queue<node_> q;
  24.         q.push({pos, 0});
  25.         // vis[pos] = true;
  26.         while(q.size()) {
  27.             auto now = q.front();
  28.             q.pop();
  29.             for(int i = 1; i <= 6; i ++ ) {
  30.                 int ne = now.pos + i;
  31.                 if(ne > n * n) break;
  32.                 auto npos = getPos(ne, n, n);
  33.                 int nx = npos.first, ny = npos.second;
  34.                 if(board[nx][ny] > 0) {
  35.                     ne = board[nx][ny];
  36.                     npos = getPos(board[nx][ny], n, n);
  37.                     nx= npos.first, ny = npos.second;
  38.                 }
  39.                 if(ne == n * n) {
  40.                     return now.times + 1;
  41.                 }
  42.                 if(!vis[ne]) {
  43.                     vis[ne] = true;
  44.                     q.push({ne, now.times + 1});
  45.                 }
  46.             }
  47.         }
  48.         return -1;
  49.     }
  50.     int snakesAndLadders(vector<vector<int>>& board) {
  51.         return bfs(1, board);
  52.     }
  53. };
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
回复

使用道具 举报

0 个回复

正序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

惊落一身雪

金牌会员
这个人很懒什么都没写!

标签云

快速回复 返回顶部 返回列表