Leetcode每日一题 —— 1320. 二指输入的的最小距离
- 内容介绍
- 文章标签
- 相关推荐
1320. 二指输入的的最小距离 - 力扣（LeetCode）
1320. 二指输入的的最小距离 - [https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/01/11/leetcode_keyboard.png] 二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。 * 例如字母A位于坐标(0,0)，字母B位于坐标(0,1)，字母P位于坐标(2,3)且字母...
思路
看上去是困难题，但是先别慌，输入规模不算很大，可以先试试 DFS 和记忆化。
首先要搞清楚我们要维护某一时刻的哪些状态：
- 手指 1 落在的字符
- 手指 2 落在的字符
- 已经输入到了
word中的哪个字符
可以看到我们可以顺着“输入 word 中的字符”这条路来拆分子问题来递归求解：每要输入一个字符时，要不用第一根手指，要不用第二根手指。
值得注意的一点是，为了让初始代价最小，手指输入的第一个字符的代价可以忽略掉（假设这根手指最开始就在这个字符上）。
怎么判断手指是不是第一次输入呢？咱的想法是在 0-25 之外再加个状态值 26，用 26 表示手指还没输入过一个字符。
直接用 DFS 很容易超时，幸运的是上面我们把状态找出来后，做记忆化就很容易了，开个 memo[n][27][27] 数组即可。
∘₊✧───────────────────────✧₊∘
代码
class Solution {
public:
int minimumDistance(string word) {
// 曼哈顿距离
// 输入必须按字符顺序来，但是两根手指可以交替使用
// 两根手指最开始应该都落在 word 中的字符上，这样最开始输入的就可以是 0 代价
int n=word.size();
// 便捷方法，计算两个字符在网格中的距离
auto cDist=[&](char c1, char c2) -> int{
int c1Pos=c1-'A';
int c2Pos=c2-'A';
return abs(c1Pos/6 - c2Pos/6) + abs(c1Pos%6 - c2Pos%6);
};
// 记忆化搜索
int memo[n][27][27];
for(int i=0;i<n;i++){
for(int j=0;j<27;j++){
for(int k=0;k<27;k++){
memo[i][j][k]=-1;
}
}
}
// word[idx] 为当前要输入的字符
// f1 为目前第一根手指落在的字符，f2 则是第二根手指所落的字符编号 (0-25), 为 26 说明还没用过这个手指
auto dfs=[&](auto&& self,int idx,int f1,int f2) -> int{
if(idx>=n){
// 输入完了
return 0;
}
if(memo[idx][f1][f2]!=-1){
// 记忆化
return memo[idx][f1][f2];
}
// 这个字符由第一根手指输入
int firstCost=0;
if(f1!=26){
// 不是第一次用第一根手指，则可能要移动手指
firstCost=cDist('A'+f1,word[idx]);
}
firstCost+=self(self,idx+1,word[idx]-'A',f2);
// 这个字符若由第二根手指输入
int secondCost=0;
if(f2!=26){
secondCost=cDist('A'+f2,word[idx]);
}
secondCost+=self(self,idx+1,f1,word[idx]-'A');
// 取二者中最小代价
int res= min(firstCost,secondCost);
memo[idx][f1][f2]=res;
return res;
};
return dfs(dfs,0,26,26);
}
};
看到 memo[n][27][27] 这玩意，很明显这题也可以按动态规划来写了 (╭ರ_•́)。
继续复习一些题
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
递归写法：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 递归当然是可以实现的
auto rm=[&](auto&& self, ListNode* node) -> int {
if(node==nullptr){
return 0;
}
int cnt=self(self, node->next);
if(cnt==n&&node->next!=nullptr){
node->next=node->next->next;
}
return cnt+1;
};
int cnt=rm(rm,head);
if(cnt==n){
// 首个节点被移除
return head->next;
}else{
return head;
}
}
};
双指针写法，比较巧（符合题目要求的“扫描一遍”）：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 可以用快慢指针
// 快指针先走 n，保持 fast 与 slow 指向的节点的间隔为 n，一起后移直至 fast 为 null
ListNode* dummy=new ListNode(); // 头结点，防止要删除的是 head
dummy->next=head;
ListNode *fast=dummy,*slow=dummy;
while(n>0){
fast=fast->next;
n--;
}
while(fast->next!=nullptr){
slow=slow->next;
fast=fast->next;
}
// 此时 slow 下一个节点就是要删的
slow->next=slow->next->next;
return dummy->next;
}
};
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
- 递归建树，BST 中序序列正好是有序序列，二分即可。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
// BST 中序遍历结果就是有序序列，可以这样不断二分去构造树
auto build=[&](auto&& self,int left,int right) -> TreeNode* {
if(left==right){
return new TreeNode(nums[left]);
}else if(left>right){
return nullptr;
}
int mid=(left+right)>>1;
TreeNode* node=new TreeNode(nums[mid]);
node->left=self(self,left,mid-1);
node->right=self(self,mid+1,right);
return node;
};
return build(build,0,nums.size()-1);
}
};
543. 二叉树的直径 - 力扣（LeetCode）
- 注意长度是用边数表示的。
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int res=0;
auto getHeight=[&](auto&& self,TreeNode* node) -> int{
if(node==nullptr){
return 0;
}
int leftH=self(self,node->left);
int rightH=self(self,node->right);
// 注意长度是用边数表示的
res=max(res,leftH+rightH);
return max(leftH,rightH)+1;
};
getHeight(getHeight,root);
return res;
}
};
--【壹】--：
没写出来嘻嘻，hard的压迫感还是太强了。
1320. 二指输入的的最小距离 - 力扣（LeetCode）
1320. 二指输入的的最小距离 - [https://assets.leetcode.cn/aliyun-lc-upload/uploads/2020/01/11/leetcode_keyboard.png] 二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。 * 例如字母A位于坐标(0,0)，字母B位于坐标(0,1)，字母P位于坐标(2,3)且字母...
思路
看上去是困难题，但是先别慌，输入规模不算很大，可以先试试 DFS 和记忆化。
首先要搞清楚我们要维护某一时刻的哪些状态：
- 手指 1 落在的字符
- 手指 2 落在的字符
- 已经输入到了
word中的哪个字符
可以看到我们可以顺着“输入 word 中的字符”这条路来拆分子问题来递归求解：每要输入一个字符时，要不用第一根手指，要不用第二根手指。
值得注意的一点是，为了让初始代价最小，手指输入的第一个字符的代价可以忽略掉（假设这根手指最开始就在这个字符上）。
怎么判断手指是不是第一次输入呢？咱的想法是在 0-25 之外再加个状态值 26，用 26 表示手指还没输入过一个字符。
直接用 DFS 很容易超时，幸运的是上面我们把状态找出来后，做记忆化就很容易了，开个 memo[n][27][27] 数组即可。
∘₊✧───────────────────────✧₊∘
代码
class Solution {
public:
int minimumDistance(string word) {
// 曼哈顿距离
// 输入必须按字符顺序来，但是两根手指可以交替使用
// 两根手指最开始应该都落在 word 中的字符上，这样最开始输入的就可以是 0 代价
int n=word.size();
// 便捷方法，计算两个字符在网格中的距离
auto cDist=[&](char c1, char c2) -> int{
int c1Pos=c1-'A';
int c2Pos=c2-'A';
return abs(c1Pos/6 - c2Pos/6) + abs(c1Pos%6 - c2Pos%6);
};
// 记忆化搜索
int memo[n][27][27];
for(int i=0;i<n;i++){
for(int j=0;j<27;j++){
for(int k=0;k<27;k++){
memo[i][j][k]=-1;
}
}
}
// word[idx] 为当前要输入的字符
// f1 为目前第一根手指落在的字符，f2 则是第二根手指所落的字符编号 (0-25), 为 26 说明还没用过这个手指
auto dfs=[&](auto&& self,int idx,int f1,int f2) -> int{
if(idx>=n){
// 输入完了
return 0;
}
if(memo[idx][f1][f2]!=-1){
// 记忆化
return memo[idx][f1][f2];
}
// 这个字符由第一根手指输入
int firstCost=0;
if(f1!=26){
// 不是第一次用第一根手指，则可能要移动手指
firstCost=cDist('A'+f1,word[idx]);
}
firstCost+=self(self,idx+1,word[idx]-'A',f2);
// 这个字符若由第二根手指输入
int secondCost=0;
if(f2!=26){
secondCost=cDist('A'+f2,word[idx]);
}
secondCost+=self(self,idx+1,f1,word[idx]-'A');
// 取二者中最小代价
int res= min(firstCost,secondCost);
memo[idx][f1][f2]=res;
return res;
};
return dfs(dfs,0,26,26);
}
};
看到 memo[n][27][27] 这玩意，很明显这题也可以按动态规划来写了 (╭ರ_•́)。
继续复习一些题
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
递归写法：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 递归当然是可以实现的
auto rm=[&](auto&& self, ListNode* node) -> int {
if(node==nullptr){
return 0;
}
int cnt=self(self, node->next);
if(cnt==n&&node->next!=nullptr){
node->next=node->next->next;
}
return cnt+1;
};
int cnt=rm(rm,head);
if(cnt==n){
// 首个节点被移除
return head->next;
}else{
return head;
}
}
};
双指针写法，比较巧（符合题目要求的“扫描一遍”）：
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 可以用快慢指针
// 快指针先走 n，保持 fast 与 slow 指向的节点的间隔为 n，一起后移直至 fast 为 null
ListNode* dummy=new ListNode(); // 头结点，防止要删除的是 head
dummy->next=head;
ListNode *fast=dummy,*slow=dummy;
while(n>0){
fast=fast->next;
n--;
}
while(fast->next!=nullptr){
slow=slow->next;
fast=fast->next;
}
// 此时 slow 下一个节点就是要删的
slow->next=slow->next->next;
return dummy->next;
}
};
108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
- 递归建树，BST 中序序列正好是有序序列，二分即可。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
// BST 中序遍历结果就是有序序列，可以这样不断二分去构造树
auto build=[&](auto&& self,int left,int right) -> TreeNode* {
if(left==right){
return new TreeNode(nums[left]);
}else if(left>right){
return nullptr;
}
int mid=(left+right)>>1;
TreeNode* node=new TreeNode(nums[mid]);
node->left=self(self,left,mid-1);
node->right=self(self,mid+1,right);
return node;
};
return build(build,0,nums.size()-1);
}
};
543. 二叉树的直径 - 力扣（LeetCode）
- 注意长度是用边数表示的。
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int res=0;
auto getHeight=[&](auto&& self,TreeNode* node) -> int{
if(node==nullptr){
return 0;
}
int leftH=self(self,node->left);
int rightH=self(self,node->right);
// 注意长度是用边数表示的
res=max(res,leftH+rightH);
return max(leftH,rightH)+1;
};
getHeight(getHeight,root);
return res;
}
};
--【壹】--：
没写出来嘻嘻，hard的压迫感还是太强了。