LeetCode 第381场周赛个人题解

2024-01-21 23:28

本文主要是介绍LeetCode 第381场周赛个人题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

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,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

原题链接

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];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

原题链接

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,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;       }
};

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的贡献,然后累加即可。

假如没有(x,y)这条边,那么点1对1~n-1都有1点贡献,点2对1~n-2都有1点贡献……

现在加上了(x,y)之后,会对某些点之间的最短距离产生影响

我们不妨假设x < y(有些样例x > y,需要处理)

  1. 如果y - x <= 1
    1. 则点对之间的最短距离无影响,直接按照没有(x,y)这条边去做即可
  2. 如果y - x > 1
    1. 令mid = (y + x + 1) / 2 , 那么(x,y)的影响分为为:
      1. 对x以及x左边的点来说,他们到达mid的距离不变,到达[mid , n]的距离变短
      2. 对[x,y]内的部分点i来说,令m = (i + y + i - x + 2) / 2,他们到达[i , m - 1]内的点的距离不变,到达[m , y]和y右侧的点的距离变短
      3. 对于剩下的点,到达右侧点的距离不变

这里单独说一下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: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;}
};

这篇关于LeetCode 第381场周赛个人题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/631156

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

HomeBank:开源免费的个人财务管理软件

在个人财务管理领域,找到一个既免费又开源的解决方案并非易事。HomeBank&nbsp;正是这样一个项目,它不仅提供了强大的功能,还拥有一个活跃的社区,不断推动其发展和完善。 开源免费:HomeBank 是一个完全开源的项目,用户可以自由地使用、修改和分发。用户友好的界面:提供直观的图形用户界面,使得非技术用户也能轻松上手。数据导入支持:支持从 Quicken、Microsoft Money

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

分布式系统的个人理解小结

分布式系统:分的微小服务,以小而独立的业务为单位,形成子系统。 然后分布式系统中需要有统一的调用,形成大的聚合服务。 同时,微服务群,需要有交流(通讯,注册中心,同步,异步),有管理(监控,调度)。 对外服务,需要有控制的对外开发,安全网关。