div使用太多影响网站收录,wordpress注册直接输入密码,wordpress图片二级域名,做网站点文章目录 2810.故障键盘1.直接用reverse解决2.双端队列 2811.判断能否拆分数组#xff08;比较巧妙的贪心#xff09;思路完整版 2812.找出最安全路径2810.故障键盘1.直接用reverse解决2.双端队列 2811.判断能否拆分数组#xff08;比较巧妙的贪心#xff09;思路完整版 28… 文章目录 2810.故障键盘1.直接用reverse解决2.双端队列 2811.判断能否拆分数组比较巧妙的贪心思路完整版 2812.找出最安全路径2810.故障键盘1.直接用reverse解决2.双端队列 2811.判断能否拆分数组比较巧妙的贪心思路完整版 2812.找出最安全路径 2810.故障键盘
你的笔记本键盘存在故障每当你在上面输入字符 i 时它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s 请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
示例 1
输入s string
输出rtsng
解释
输入第 1 个字符后屏幕上的文本是s 。
输入第 2 个字符后屏幕上的文本是st 。
输入第 3 个字符后屏幕上的文本是str 。
因为第 4 个字符是 i 屏幕上的文本被反转变成 rts 。
输入第 5 个字符后屏幕上的文本是rtsn 。
输入第 6 个字符后屏幕上的文本是 rtsng 。
因此返回 rtsng 。示例 2
输入s poiinter
输出ponter
解释
输入第 1 个字符后屏幕上的文本是p 。
输入第 2 个字符后屏幕上的文本是po 。
因为第 3 个字符是 i 屏幕上的文本被反转变成 op 。
因为第 4 个字符是 i 屏幕上的文本被反转变成 po 。
输入第 5 个字符后屏幕上的文本是pon 。
输入第 6 个字符后屏幕上的文本是pont 。
输入第 7 个字符后屏幕上的文本是ponte 。
输入第 8 个字符后屏幕上的文本是ponter 。
因此返回 ponter 。提示
1 s.length 100s 由小写英文字母组成s[0] ! i
1.直接用reverse解决
反转字符串可以直接用reverse来解决如下
class Solution {
public:string finalString(string s) {string result ;for(char c:s){if(ci){reverse(result.begin(),result.end());}else{result.push_back(c);}}return result;}
};2.双端队列
遇到字符i时可以通过栈来实现字符串反转的效果。这是因为栈是后进先出(LIFO)的数据结构它可以帮助我们将之前输入的字符逆序输出。
但是用栈的话无法处理字符串本身没有i这种情况因此应该使用双端队列。
双端队列思路 初始化一个双端队列 dequechar q双端队列允许我们在队列的头部和尾部都进行添加和删除操作。 使用一个布尔变量 right 来确定插入的方向当 right 为 true 时我们在队列的尾部插入字符当 right 为 false 时我们在队列的头部插入字符。 遍历输入的字符串 s 中的每个字符 如果字符是 ‘i’则将 right 的值取反即改变插入方向。因此如果之前是在尾部插入现在就在头部插入反之亦然。如果字符不是 ‘i’ 且 right 为 true则在双端队列的尾部插入该字符。如果字符不是 ‘i’ 且 right 为 false则在双端队列的头部插入该字符。 将双端队列 q 转化为字符串 result这里利用了字符串的迭代器构造函数将 q 的所有字符转化为一个字符串。 检查最后的插入方向如果最后的插入方向是在头部即 right 为 false说明队列中的字符序列是相反的因此我们需要将 result 反转。 返回结果字符串 result。 关键思想是利用双端队列模拟字符串的插入过程每当遇到字符 ‘i’ 时改变插入的方向。这种方法的效率很高因为在双端队列的头部和尾部插入字符的时间复杂度都是 O(1)。
class Solution {
public:string finalString(string s) {//双端队列dequecharq;bool right true;//设定一个量用来修改添加方向for(char c:s){if(ci){right!right;//方向返过来而且i本身是不管的所以可以直接else if}else if(right){q.push_back(c);}else {q.push_front(c);}}string result(q.begin(),q.end());//可以直接把双端队列放在字符串里if(!right){//有偶数个i的时候实际上最后的result是不变的直接看right是不是true就可以reverse(result.begin(),result.end());}return result;}
};2811.判断能否拆分数组比较巧妙的贪心
给你一个长度为 n 的数组 nums 和一个整数 m 。请你判断能否执行一系列操作将数组拆分成 n 个 非空 数组。
在每一步操作中你可以选择一个 长度至少为 2 的现有数组之前步骤的结果 并将其拆分成 2 个子数组而得到的 每个 子数组至少 需要满足以下条件之一
子数组的长度为 1 或者子数组元素之和 大于或等于 m 。
如果你可以将给定数组拆分成 n 个满足要求的数组返回 true 否则返回 false 。
**注意**子数组是数组中的一个连续非空元素序列。
示例 1
输入nums [2, 2, 1], m 4
输出true
解释
第 1 步将数组 nums 拆分成 [2, 2] 和 [1] 。
第 2 步将数组 [2, 2] 拆分成 [2] 和 [2] 。
因此答案为 true 。示例 2
输入nums [2, 1, 3], m 5
输出false
解释
存在两种不同的拆分方法
第 1 种将数组 nums 拆分成 [2, 1] 和 [3] 。
第 2 种将数组 nums 拆分成 [2] 和 [1, 3] 。
然而这两种方法都不满足题意。因此答案为 false 。示例 3
输入nums [2, 3, 3, 2, 3], m 6
输出true
解释
第 1 步将数组 nums 拆分成 [2, 3, 3, 2] 和 [3] 。
第 2 步将数组 [2, 3, 3, 2] 拆分成 [2, 3, 3] 和 [2] 。
第 3 步将数组 [2, 3, 3] 拆分成 [2] 和 [3, 3] 。
第 4 步将数组 [3, 3] 拆分成 [3] 和 [3] 。
因此答案为 true 。 提示
1 n nums.length 1001 nums[i] 1001 m 200
思路
这道题用的是贪心的思想只要有两个连续的数字加起来m就可以把除了这俩之外的都拆出去。
也就是说只要有一组连续数字相加m那么一定可以满足条件2。条件1是一定可以满足的需要满足的是有两个连续的数字相加m。这样最后才能拆出来两个1。
完整版
class Solution {
public:bool canSplitArray(vectorint nums, int m) {if(nums.size()1||nums.size()2){return true;}for(int i0;inums.size()-1;i){if(nums[i]nums[i1]m){return true;}}return false;}
};这是一种很巧妙的贪心主要是这道题两个条件满足一个即可而且数组全是正整数有两个相加m最后结果一定m。
2812.找出最安全路径
给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid 其中 (r, c) 表示
如果 grid[r][c] 1 则表示一个存在小偷的单元格如果 grid[r][c] 0 则表示一个空单元格
你最开始位于单元格 (0, 0) 。在一步移动中你可以移动到矩阵中的任一相邻单元格包括存在小偷的单元格。
矩阵中路径的 安全系数 定义为从路径中任一单元格到矩阵中任一小偷所在单元格的 最小 曼哈顿距离。
返回所有通向单元格 (n - 1, n - 1) 的路径中的 最大安全系数 。
单元格 (r, c) 的某个 相邻 单元格是指在矩阵中存在的 (r, c 1)、(r, c - 1)、(r 1, c) 和 (r - 1, c) 之一。
两个单元格 (a, b) 和 (x, y) 之间的 曼哈顿距离 等于 | a - x | | b - y | 其中 |val| 表示 val 的绝对值。
示例 1
2810.故障键盘
你的笔记本键盘存在故障每当你在上面输入字符 i 时它会反转你所写的字符串。而输入其他字符则可以正常工作。
给你一个下标从 0 开始的字符串 s 请你用故障键盘依次输入每个字符。
返回最终笔记本屏幕上输出的字符串。
示例 1
输入s string
输出rtsng
解释
输入第 1 个字符后屏幕上的文本是s 。
输入第 2 个字符后屏幕上的文本是st 。
输入第 3 个字符后屏幕上的文本是str 。
因为第 4 个字符是 i 屏幕上的文本被反转变成 rts 。
输入第 5 个字符后屏幕上的文本是rtsn 。
输入第 6 个字符后屏幕上的文本是 rtsng 。
因此返回 rtsng 。示例 2
输入s poiinter
输出ponter
解释
输入第 1 个字符后屏幕上的文本是p 。
输入第 2 个字符后屏幕上的文本是po 。
因为第 3 个字符是 i 屏幕上的文本被反转变成 op 。
因为第 4 个字符是 i 屏幕上的文本被反转变成 po 。
输入第 5 个字符后屏幕上的文本是pon 。
输入第 6 个字符后屏幕上的文本是pont 。
输入第 7 个字符后屏幕上的文本是ponte 。
输入第 8 个字符后屏幕上的文本是ponter 。
因此返回 ponter 。提示
1 s.length 100s 由小写英文字母组成s[0] ! i
1.直接用reverse解决
反转字符串可以直接用reverse来解决如下
class Solution {
public:string finalString(string s) {string result ;for(char c:s){if(ci){reverse(result.begin(),result.end());}else{result.push_back(c);}}return result;}
};2.双端队列
遇到字符i时可以通过栈来实现字符串反转的效果。这是因为栈是后进先出(LIFO)的数据结构它可以帮助我们将之前输入的字符逆序输出。
但是用栈的话无法处理字符串本身没有i这种情况因此应该使用双端队列。
双端队列思路 初始化一个双端队列 dequechar q双端队列允许我们在队列的头部和尾部都进行添加和删除操作。 使用一个布尔变量 right 来确定插入的方向当 right 为 true 时我们在队列的尾部插入字符当 right 为 false 时我们在队列的头部插入字符。 遍历输入的字符串 s 中的每个字符 如果字符是 ‘i’则将 right 的值取反即改变插入方向。因此如果之前是在尾部插入现在就在头部插入反之亦然。如果字符不是 ‘i’ 且 right 为 true则在双端队列的尾部插入该字符。如果字符不是 ‘i’ 且 right 为 false则在双端队列的头部插入该字符。 将双端队列 q 转化为字符串 result这里利用了字符串的迭代器构造函数将 q 的所有字符转化为一个字符串。 检查最后的插入方向如果最后的插入方向是在头部即 right 为 false说明队列中的字符序列是相反的因此我们需要将 result 反转。 返回结果字符串 result。 关键思想是利用双端队列模拟字符串的插入过程每当遇到字符 ‘i’ 时改变插入的方向。这种方法的效率很高因为在双端队列的头部和尾部插入字符的时间复杂度都是 O(1)。
class Solution {
public:string finalString(string s) {//双端队列dequecharq;bool right true;//设定一个量用来修改添加方向for(char c:s){if(ci){right!right;//方向返过来而且i本身是不管的所以可以直接else if}else if(right){q.push_back(c);}else {q.push_front(c);}}string result(q.begin(),q.end());//可以直接把双端队列放在字符串里if(!right){//有偶数个i的时候实际上最后的result是不变的直接看right是不是true就可以reverse(result.begin(),result.end());}return result;}
};2811.判断能否拆分数组比较巧妙的贪心
给你一个长度为 n 的数组 nums 和一个整数 m 。请你判断能否执行一系列操作将数组拆分成 n 个 非空 数组。
在每一步操作中你可以选择一个 长度至少为 2 的现有数组之前步骤的结果 并将其拆分成 2 个子数组而得到的 每个 子数组至少 需要满足以下条件之一
子数组的长度为 1 或者子数组元素之和 大于或等于 m 。
如果你可以将给定数组拆分成 n 个满足要求的数组返回 true 否则返回 false 。
**注意**子数组是数组中的一个连续非空元素序列。
示例 1
输入nums [2, 2, 1], m 4
输出true
解释
第 1 步将数组 nums 拆分成 [2, 2] 和 [1] 。
第 2 步将数组 [2, 2] 拆分成 [2] 和 [2] 。
因此答案为 true 。示例 2
输入nums [2, 1, 3], m 5
输出false
解释
存在两种不同的拆分方法
第 1 种将数组 nums 拆分成 [2, 1] 和 [3] 。
第 2 种将数组 nums 拆分成 [2] 和 [1, 3] 。
然而这两种方法都不满足题意。因此答案为 false 。示例 3
输入nums [2, 3, 3, 2, 3], m 6
输出true
解释
第 1 步将数组 nums 拆分成 [2, 3, 3, 2] 和 [3] 。
第 2 步将数组 [2, 3, 3, 2] 拆分成 [2, 3, 3] 和 [2] 。
第 3 步将数组 [2, 3, 3] 拆分成 [2] 和 [3, 3] 。
第 4 步将数组 [3, 3] 拆分成 [3] 和 [3] 。
因此答案为 true 。 提示
1 n nums.length 1001 nums[i] 1001 m 200
思路
这道题用的是贪心的思想只要有两个连续的数字加起来m就可以把除了这俩之外的都拆出去。
也就是说只要有一组连续数字相加m那么一定可以满足条件2。条件1是一定可以满足的需要满足的是有两个连续的数字相加m。这样最后才能拆出来两个1。
完整版
class Solution {
public:bool canSplitArray(vectorint nums, int m) {if(nums.size()1||nums.size()2){return true;}for(int i0;inums.size()-1;i){if(nums[i]nums[i1]m){return true;}}return false;}
};这是一种很巧妙的贪心主要是这道题两个条件满足一个即可而且数组全是正整数有两个相加m最后结果一定m。
2812.找出最安全路径
给你一个下标从 0 开始、大小为 n x n 的二维矩阵 grid 其中 (r, c) 表示
如果 grid[r][c] 1 则表示一个存在小偷的单元格如果 grid[r][c] 0 则表示一个空单元格
你最开始位于单元格 (0, 0) 。在一步移动中你可以移动到矩阵中的任一相邻单元格包括存在小偷的单元格。
矩阵中路径的 安全系数 定义为从路径中任一单元格到矩阵中任一小偷所在单元格的 最小 曼哈顿距离。
返回所有通向单元格 (n - 1, n - 1) 的路径中的 最大安全系数 。
单元格 (r, c) 的某个 相邻 单元格是指在矩阵中存在的 (r, c 1)、(r, c - 1)、(r 1, c) 和 (r - 1, c) 之一。
两个单元格 (a, b) 和 (x, y) 之间的 曼哈顿距离 等于 | a - x | | b - y | 其中 |val| 表示 val 的绝对值。
示例 1
输入grid [[1,0,0],[0,0,0],[0,0,1]]
输出0
解释从 (0, 0) 到 (n - 1, n - 1) 的每条路径都经过存在小偷的单元格 (0, 0) 和 (n - 1, n - 1) 。示例 2 输入grid [[0,0,1],[0,0,0],[0,0,0]]
输出2
解释
上图所示路径的安全系数为 2
- 该路径上距离小偷所在单元格02最近的单元格是00。它们之间的曼哈顿距离为 | 0 - 0 | | 0 - 2 | 2 。
可以证明不存在安全系数更高的其他路径。示例 3 输入grid [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
输出2
解释
上图所示路径的安全系数为 2
- 该路径上距离小偷所在单元格03最近的单元格是12。它们之间的曼哈顿距离为 | 0 - 1 | | 3 - 2 | 2 。
- 该路径上距离小偷所在单元格30最近的单元格是32。它们之间的曼哈顿距离为 | 3 - 3 | | 0 - 2 | 2 。
可以证明不存在安全系数更高的其他路径。提示
1 grid.length n 400grid[i].length ngrid[i][j] 为 0 或 1grid 至少存在一个小偷
这道题是bfs笔试考的比较多。先记录一下做法。
class Solution {
public:int maximumSafenessFactor(vectorvectorint grid) {int n grid.size();vectorvectorint dist(n, vectorint(n, INT_MAX));vectorvectorint safe(n, vectorint(n, 0));queuepairint, int q;for (int i 0; i n; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {dist[i][j] 0;q.push({i, j});}}}vectorvectorint dirs {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};while (!q.empty()) {int r q.front().first, c q.front().second;q.pop();for (auto dir : dirs) {int nr r dir[0], nc c dir[1];if (nr 0 nr n nc 0 nc n dist[r][c] 1 dist[nr][nc]) {dist[nr][nc] dist[r][c] 1;q.push({nr, nc});}}}safe[n-1][n-1] dist[n-1][n-1];q.push({n-1, n-1});while (!q.empty()) {int r q.front().first, c q.front().second;q.pop();for (auto dir : dirs) {int nr r dir[0], nc c dir[1];if (nr 0 nr n nc 0 nc n) {int newSafe min(safe[r][c], dist[nr][nc]);if (newSafe safe[nr][nc]) {safe[nr][nc] newSafe;q.push({nr, nc});}}}}return safe[0][0];}
};
