leetcode解题思路分析（一百五十二）1320

思路分析（一百五十二）1320"/>

leetcode解题思路分析（一百五十二）1320

1320. 二指输入的的最小距离
      二指输入法定制键盘在 X-Y 平面上的布局如上图所示，其中每个大写英文字母都位于某个坐标处。
      例如字母 A 位于坐标 (0,0)，字母 B 位于坐标 (0,1)，字母 P 位于坐标 (2,3) 且字母 Z 位于坐标 (4,1)。
      给你一个待输入字符串 word，请你计算并返回在仅使用两根手指的情况下，键入该字符串需要的最小移动总距离。

动态规划解题：word第i位和i-1位的dp关系，取决于i-1时左右手位置及距离word[i]的距离。由此可以列出递推公式。

class Solution {
public:int getDistance(int p, int q) {int x1 = p / 6, y1 = p % 6;int x2 = q / 6, y2 = q % 6;return abs(x1 - x2) + abs(y1 - y2);}int minimumDistance(string word) {int n = word.size();vector<vector<int>> dp(n, vector<int>(26, INT_MAX >> 1));fill(dp[0].begin(), dp[0].end(), 0);for (int i = 1; i < n; ++i) {int cur = word[i] - 'A';int prev = word[i - 1] - 'A';int d = getDistance(prev, cur);for (int j = 0; j < 26; ++j) {dp[i][j] = min(dp[i][j], dp[i - 1][j] + d);if (prev == j) {for (int k = 0; k < 26; ++k) {int d0 = getDistance(k, cur);dp[i][j] = min(dp[i][j], dp[i - 1][k] + d0);}}}}int ans = *min_element(dp[n - 1].begin(), dp[n - 1].end());return ans;}
};

1321. 餐馆营业额变化增长
      你是餐馆的老板，现在你想分析一下可能的营业额变化增长（每天至少有一位顾客）。计算以 7 天（某日期 + 该日期前的 6 天）为一个时间段的顾客消费平均值。average_amount 要 保留两位小数。结果按 visited_on 升序排序。返回结果格式的例子如下。

# Write your MySQL query statement below
SELECTvisited_on,sum_amount amount,ROUND( sum_amount / 7, 2 ) average_amount
FROM (SELECTvisited_on,SUM( sum_amount ) OVER ( ORDER BY to_days(visited_on) RANGE BETWEEN 6 PRECEDING AND current ROW ) sum_amountFROM (SELECTvisited_on,SUM( amount ) sum_amountFROM CustomerGROUP BY visited_on) tmp1
) tmp2
WHERE DATEDIFF(visited_on, ( SELECT MIN( visited_on ) FROM Customer )) >= 6;

1323. 6 和 9 组成的最大数字
      给你一个仅由数字 6 和 9 组成的正整数 num。你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。请返回你可以得到的最大数字。

转字符串，处理最高位，完事。

class Solution {
public:int maximum69Number(int num) {string s = to_string(num);for (char& ch: s) {if (ch == '6') {ch = '9';break;}}return stoi(s);}
};

1324. 竖直打印单词
      给你一个字符串 s。请你按照单词在 s 中的出现顺序将它们全部竖直返回。
      单词应该以字符串列表的形式返回，必要时用空格补位，但输出尾部的空格需要删除（不允许尾随空格）。
      每个单词只能放在一列上，每一列中也只能有一个单词。

很无聊的一道题，模拟过程即可，坑在于单词尾部空格要删除。这里有个点：auto循环其实是一个原值的拷贝构造，并不会修改原值。

class Solution {
public:vector<string> printVertically(string s) {int nIndex = 0, nSize = 0, tmpSize = 0;vector<string> ret;for (int i = 0; i < s.size(); ++i){while (s[i] != ' ' && i < s.size()){tmpSize++;i++;}nSize = max(nSize, tmpSize);tmpSize = 0;}ret.resize(nSize, "");for (int i = 0; i < s.size(); ++i){if (s[i] == ' ' && nIndex < nSize){if (nIndex == 0) continue;for (int j = nIndex; j < nSize; ++j)ret[j] += ' ';nIndex = nSize;}else{ret[nIndex] += s[i];nIndex++;}if (nIndex == nSize)nIndex = 0;}for (int j = 0; j < ret.size(); j++ ){int i = ret[j].size() - 1;while (i && ret[j][i] == ' '){i--;}if (i != ret[j].size() - 1)ret[j][i + 1] = '\0';}return ret;}
};

1325. 删除给定值的叶子节点
      给你一棵以 root 为根的二叉树和一个整数 target ，请你删除所有值为 target 的 叶子节点 。
      注意，一旦删除值为 target 的叶子节点，它的父节点就可能变成叶子节点；如果新叶子节点的值恰好也是 target ，那么这个节点也应该被删除。
      也就是说，你需要重复此过程直到不能继续删除。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* removeLeafNodes(TreeNode* root, int target) {if (!root) return NULL;root->left = removeLeafNodes(root->left, target);root->right = removeLeafNodes(root->right, target);if (root->left == NULL && root->right == NULL && root->val == target)return NULL;return root;}
};

1326. 灌溉花园的最少水龙头数目
      在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。花园里总共有 n + 1 个水龙头，分别位于 [0, 1, …, n] 。
      给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]] 。请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

class Solution {
public:int minTaps(int n, vector<int>& ranges) {vector<int> rightMost(n + 1);iota(rightMost.begin(), rightMost.end(), 0);for (int i = 0; i <= n; i++) {int start = max(0, i - ranges[i]);int end = min(n, i + ranges[i]);rightMost[start] = max(rightMost[start], end);}int last = 0, ret = 0, pre = 0;for (int i = 0; i < n; i++) {last = max(last, rightMost[i]);if (i == last) {return -1;}if (i == pre) {ret++;pre = last;}}return ret;}
};