目录
输入单词需要的最少按键次数 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为字符集大小
第三题思路和代码和本题一样
class Solution {
public:
int minimumPushes(string word) {
int cnt[26]{0} , ret = 0;
for(auto x : word) cnt[x - 'a']++;
sort(cnt,cnt+26);
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 - 力扣（LeetCode）
给你三个?正整数?
n?、x?和?y?。在城市中，存在编号从?
1?到?n?的房屋，由?n?条街道相连。对所有?1 <= i < n?，都存在一条街道连接编号为?i?的房屋与编号为?i + 1?的房屋。另存在一条街道连接编号为?x?的房屋与编号为?y?的房屋。对于每个?
k（1 <= k <= n），你需要找出所有满足要求的?房屋对?[house1, house2]?，即从?house1?到?house2?需要经过的?最少?街道数为?k?。返回一个下标从?1?开始且长度为?
n?的数组?result?，其中?result[k]?表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的?最少?街道数为?k?。注意，
x?与?y?可以?相等?。
由于floyd太好写了，直接无脑Floyd求最短路，然后遍历加上路径为k的就行，
时间复杂度：O(n^3) 空间复杂度：O(n^2)
当然，这个代码肯定过不了第四题
class Solution {
public:
long long g[101][101];
vector<int> 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];
vector<int> 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 - 力扣（LeetCode）
给你一个字符串?
word，由?不同?小写英文字母组成。电话键盘上的按键与?不同?小写英文字母集合相映射，可以通过按压按键来组成单词。例如，按键?
2?对应?["a","b","c"]，我们需要按一次键来输入?"a"，按两次键来输入?"b"，按三次键来输入?"c"。现在允许你将编号为?
2?到?9?的按键重新映射到?不同?字母集合。每个按键可以映射到?任意数量?的字母，但每个字母?必须?恰好?映射到?一个?按键上。你需要找到输入字符串?word?所需的?最少?按键次数。返回重新映射按键后输入?
word?所需的?最少?按键次数。下面给出了一种电话键盘上字母到按键的映射作为示例。注意?
1，*，#?和?0?不?对应任何字母。
见第二题
class Solution {
public:
int minimumPushes(string word) {
int cnt[26]{0} , ret = 0;
for(auto x : word) cnt[x - 'a']++;
sort(cnt,cnt+26);
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;
}
};按距离统计房屋对数目 II - 力扣 (LeetCode) 竞赛
给你三个?正整数?
n?、x?和?y?。在城市中，存在编号从?
1?到?n?的房屋，由?n?条街道相连。对所有?1 <= i < n?，都存在一条街道连接编号为?i?的房屋与编号为?i + 1?的房屋。另存在一条街道连接编号为?x?的房屋与编号为?y?的房屋。对于每个?
k（1 <= k <= n），你需要找出所有满足要求的?房屋对?[house1, house2]?，即从?house1?到?house2?需要经过的?最少?街道数为?k?。返回一个下标从?1?开始且长度为?
n?的数组?result?，其中?result[k]?表示所有满足要求的房屋对的数量，即从一个房屋到另一个房屋需要经过的?最少?街道数为?k?。注意，
x?与?y?可以?相等?。
树状数组，区间维护
代码很长主要是树状数组占一部分，然后情况特判占一部分
基本思路是我们计算每个点对于距离1~n的贡献，然后累加即可。
假如没有(x，y)这条边，那么点1对1~n-1都有1点贡献，点2对1~n-2都有1点贡献……
现在加上了(x,y)之后，会对某些点之间的最短距离产生影响
我们不妨假设x < y（有些样例x > y，需要处理）
这里单独说一下2.1.2中m的取法，2.1.2讨论的部分点都是走左边捷径到达区间内某些点距离变短的点，m就可以看成把y向右延长i - x + 1后取得i到右边新边界这段区间上得中点
我们维护树状数组，然后求贡献即可
由于我们只计算每个点到其右边点的贡献，所以最终答案要乘2
按照这个方法，代码很容易写错，主要在于m下标的取法，可以画图理解一下
时间复杂度:O(nlogn) 空间复杂度:O(n)
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:
vector<long long> countOfPairs(int N, int x, int y) {
memset(t,0,sizeof(t));
n = N;
vector<long 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;
}
};