环保网站建设,网站源码44444kt,闸北区网站设计与制作,金融投资网站方案LeetCode-1138. 字母板上的路径【哈希表#xff0c;字符串】题目描述#xff1a;解题思路一#xff1a;首先考虑坐标位置#xff0c;字符是有序的从0开始#xff0c;当前字符c的行为(c-a)/5,列为(c-a)%5。其次是考虑特殊情况z。若当前从‘z’开始则只能往上走;若是其他字符…
LeetCode-1138. 字母板上的路径【哈希表字符串】题目描述解题思路一首先考虑坐标位置字符是有序的从0开始当前字符c的行为(c-a)/5,列为(c-a)%5。其次是考虑特殊情况z。若当前从‘z’开始则只能往上走;若是其他字符到z统一先往左走再往下走。那么每次移动时优先保证选择上移和左移即可。解题思路二优化判断条件。解题思路三0题目描述
我们从一块字母板上的位置 (0, 0) 出发该坐标对应的字符为 board[0][0]。
在本题里字母板为board [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”]如下所示。 我们可以按下面的指令规则行动
如果方格存在‘U’ 意味着将我们的位置上移一行 如果方格存在‘D’ 意味着将我们的位置下移一行 如果方格存在‘L’ 意味着将我们的位置左移一列 如果方格存在‘R’ 意味着将我们的位置右移一列 ‘!’ 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。 注意字母板上只存在有字母的位置。
返回指令序列用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。
示例 1
输入target “leet” 输出“DDR!UURRR!!DDD!”
示例 2
输入target “code” 输出“RR!DDRR!UUL!R!”
提示
1 target.length 100 target 仅含有小写英文字母。
https://leetcode.cn/problems/alphabet-board-path/description/
解题思路一首先考虑坐标位置字符是有序的从0开始当前字符c的行为(c-‘a’)/5,列为(c-‘a’)%5。其次是考虑特殊情况’z’。若当前从‘z’开始则只能往上走;若是其他字符到’z’统一先往左走再往下走。那么每次移动时优先保证选择上移和左移即可。
class Solution {
public:string alphabetBoardPath(string target) {string ans;int x 0, y 0;//当前位置for (char c:target) {int nx(c-a)/5,ny(c-a)%5;//目标位置(x是行y是列)if(nxx) ans.append(x-nx,U);//目标行小在上边添加x-nx个Uif(nyy) ans.append(y-ny,L);//目标列小在左边添加y-ny个Lif(nxx) ans.append(nx-x,D);//目标行大在下边添加nx-x个Dif(nyy) ans.append(ny-y,R);//目标列大在右边添加ny-y个Rans.push_back(!);//取当前字符xnx,yny;//更新当前位置}return ans;}
};时间复杂度O(n*(rc))//其中 n表示给定字符串的长度r表示字母板的行数 c表示字母板的列数。每次移动到新的字符生成移动指令时需要的时间复杂度为rc一共需要生成指令 n 次因此时间复杂度为O(n×(rc))。 空间复杂度O(1)
解题思路二优化判断条件。
class Solution {
public:string alphabetBoardPath(string target) {string ans;int x 0, y 0;//当前位置for (char c:target) {int nx(c-a)/5,ny(c-a)%5;//目标位置(x是行y是列)string v(abs(nx-x), UD[nx x]);//竖直例如nxx那么条件为true即是1取的是nx-x个Dstring h(abs(ny-y), LR[ny y]);//水平ans(c!z?vh:hv)!;//是z则先竖直后水平非z相反xnx,yny;//更新当前位置}return ans;}
};时间复杂度O(n*(rc))//其中 n表示给定字符串的长度r表示字母板的行数 c表示字母板的列数。每次移动到新的字符生成移动指令时需要的时间复杂度为rc一共需要生成指令 n 次因此时间复杂度为O(n×(rc))。 空间复杂度O(1)
解题思路三0
