商城网站建设套餐报价,做彩妆网站的公司,手机怎么注册自己的网站,网络结构分几层目录 100191. 输入单词需要的最少按键次数 I
原题链接
题目描述
思路分析
AC代码
100188. 按距离统计房屋对数目 I
原题链接
题目描述
思路分析
AC代码
100192. 输入单词需要的最少按键次数 II
原题链接
题目描述
思路分析
AC代码
100213. 按距离统计房屋对数目…目录 100191. 输入单词需要的最少按键次数 I
原题链接
题目描述
思路分析
AC代码
100188. 按距离统计房屋对数目 I
原题链接
题目描述
思路分析
AC代码
100192. 输入单词需要的最少按键次数 II
原题链接
题目描述
思路分析
AC代码
100213. 按距离统计房屋对数目 II
原题链接
题目描述
思路分析
AC代码 100191. 输入单词需要的最少按键次数 I
原题链接
输入单词需要的最少按键次数 I - 力扣 (LeetCode) 竞赛
题目描述 给你一个字符串 word由 不同 小写英文字母组成。 电话键盘上的按键与 不同 小写英文字母集合相映射可以通过按压按键来组成单词。例如按键 2 对应 [a,b,c]我们需要按一次键来输入 a按两次键来输入 b按三次键来输入 c。 现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。 返回重新映射按键后输入 word 所需的 最少 按键次数。 下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1*# 和 0 不 对应任何字母。 思路分析
贪心的映射出现次数越多的字符映射的按键次数少
记录每个字符出现次数然后升序排序出现次数最多的前八个字符都映射到按键1次次8个映射到按2次再8个映射到3次剩下的映射到4次
时间复杂度O(n UlogU) 空间复杂度O(U UlogU)U为字符集大小
第三题思路和代码和本题一样
AC代码
class Solution {
public:int minimumPushes(string word) {int cnt[26]{0} , ret 0;for(auto x : word) cnt[x - a];sort(cnt,cnt26);return accumulate(cnt 18 , cnt 26 , 0) accumulate(cnt 10 , cnt 18 , 0) * 2 accumulate(cnt 2 , cnt 10 , 0) * 3 accumulate(cnt , cnt 2 , 0) * 4; }
};
100188. 按距离统计房屋对数目 I
原题链接
100188. 按距离统计房屋对数目 I - 力扣LeetCode
题目描述 给你三个 正整数 n 、x 和 y 。 在城市中存在编号从 1 到 n 的房屋由 n 条街道相连。对所有 1 i n 都存在一条街道连接编号为 i 的房屋与编号为 i 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。 对于每个 k1 k n你需要找出所有满足要求的 房屋对 [house1, house2] 即从 house1 到 house2 需要经过的 最少 街道数为 k 。 返回一个下标从 1 开始且长度为 n 的数组 result 其中 result[k] 表示所有满足要求的房屋对的数量即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。 注意x 与 y 可以 相等 。 思路分析
由于floyd太好写了直接无脑Floyd求最短路然后遍历加上路径为k的就行
时间复杂度O(n^3) 空间复杂度O(n^2)
当然这个代码肯定过不了第四题
AC代码
class Solution {
public:long long g[101][101];vectorint countOfPairs(int n, int x, int y) {memset(g,0x3f,sizeof(g));g[x][y] g[y][x] 1;for(int i 1 ; i n - 1 ; i)g[i][i 1] g[i 1][i] 1 , g[i][i] 0;g[n][n] 0;for(int k 1 ; k n ; k)for(int i 1 ; i n ; i)for(int j 1 ; j n ; j)if(g[i][j] - g[i][k] g[k][j])g[i][j] g[i][k] g[k][j];vectorint ret(n);for(int k 1 ; k n ; k)for(int i 1 ; i n ; i)for(int j 1 ; j n ; j)if(g[i][j] k)ret[k - 1];return ret;}
};
100192. 输入单词需要的最少按键次数 II
原题链接
100192. 输入单词需要的最少按键次数 II - 力扣LeetCode
题目描述 给你一个字符串 word由 不同 小写英文字母组成。 电话键盘上的按键与 不同 小写英文字母集合相映射可以通过按压按键来组成单词。例如按键 2 对应 [a,b,c]我们需要按一次键来输入 a按两次键来输入 b按三次键来输入 c。 现在允许你将编号为 2 到 9 的按键重新映射到 不同 字母集合。每个按键可以映射到 任意数量 的字母但每个字母 必须 恰好 映射到 一个 按键上。你需要找到输入字符串 word 所需的 最少 按键次数。 返回重新映射按键后输入 word 所需的 最少 按键次数。 下面给出了一种电话键盘上字母到按键的映射作为示例。注意 1*# 和 0 不 对应任何字母。 思路分析
见第二题
AC代码
class Solution {
public:int minimumPushes(string word) {int cnt[26]{0} , ret 0;for(auto x : word) cnt[x - a];sort(cnt,cnt26);return accumulate(cnt 18 , cnt 26 , 0) accumulate(cnt 10 , cnt 18 , 0) * 2 accumulate(cnt 2 , cnt 10 , 0) * 3 accumulate(cnt , cnt 2 , 0) * 4; }
};
100213. 按距离统计房屋对数目 II
原题链接
按距离统计房屋对数目 II - 力扣 (LeetCode) 竞赛
题目描述 给你三个 正整数 n 、x 和 y 。 在城市中存在编号从 1 到 n 的房屋由 n 条街道相连。对所有 1 i n 都存在一条街道连接编号为 i 的房屋与编号为 i 1 的房屋。另存在一条街道连接编号为 x 的房屋与编号为 y 的房屋。 对于每个 k1 k n你需要找出所有满足要求的 房屋对 [house1, house2] 即从 house1 到 house2 需要经过的 最少 街道数为 k 。 返回一个下标从 1 开始且长度为 n 的数组 result 其中 result[k] 表示所有满足要求的房屋对的数量即从一个房屋到另一个房屋需要经过的 最少 街道数为 k 。 注意x 与 y 可以 相等 。 思路分析
树状数组区间维护
代码很长主要是树状数组占一部分然后情况特判占一部分
基本思路是我们计算每个点对于距离1~n的贡献然后累加即可。
假如没有(xy)这条边那么点1对1~n-1都有1点贡献点2对1~n-2都有1点贡献……
现在加上了(x,y)之后会对某些点之间的最短距离产生影响
我们不妨假设x y有些样例x y需要处理
如果y - x 1 则点对之间的最短距离无影响直接按照没有(x,y)这条边去做即可如果y - x 1 令mid (y x 1) / 2 , 那么(x,y)的影响分为为 对x以及x左边的点来说他们到达mid的距离不变到达[mid , n]的距离变短对[x,y]内的部分点i来说令m (i y i - x 2) / 2他们到达[i , m - 1]内的点的距离不变到达[m , y]和y右侧的点的距离变短对于剩下的点到达右侧点的距离不变
这里单独说一下2.1.2中m的取法2.1.2讨论的部分点都是走左边捷径到达区间内某些点距离变短的点m就可以看成把y向右延长i - x 1后取得i到右边新边界这段区间上得中点
我们维护树状数组然后求贡献即可
由于我们只计算每个点到其右边点的贡献所以最终答案要乘2
按照这个方法代码很容易写错主要在于m下标的取法可以画图理解一下
时间复杂度:O(nlogn) 空间复杂度:O(n)
AC代码
long long t[100010];
int n;
void update(int x, int k)
{for (; x n; x x -x)t[x] k;
}int query(int x)
{int sum 0;for (; x 0; x (x - 1))sum t[x];return sum;
}inline void change(int l , int r , int k)
{if(l r) return;update(l , k) , update(r 1 , -k);
}class Solution {
public:vectorlong long countOfPairs(int N, int x, int y) {memset(t,0,sizeof(t));n N;vectorlong long ret(n);if(x y) swap(x,y);if(y - x 1){for(int i 1 ; i n ; i)change(1 , n - i , 1);for(int i 1 ; i n ; i)ret[i - 1] query(i) * 2; return ret;}int mid (y x 1) / 2;for(int i 1 ; i x ; i){change(1 , mid - i , 1) , change(x - i 1 , x - i y - mid , 1);if(y n)change(x - i 2 , x - i n - y 1 , 1);}int i x 1;for(i x 1 ; i n ; i){int m (i y i - x 2) / 2;if(m y)break;change(1 , m - 1 - i , 1) , change(i - x 1 , i - x 1 y - m , 1);if(y n)change(i - x 2 , i - x 1 n - y , 1);}for( ; i n ; i)change(1 , n - i , 1);for(int i 1 ; i n ; i)ret[i - 1] query(i) * 2;return ret;}
};
