本题为1月16日力扣每日一题 题目来源:力扣第2719题 题目tag:数位dp动态规划 题面 题目描述 给你两个数字字符串num1和num2，以及两个整数max_sum和min_sum。如果一个整数x满足以下条件，我们称它是一个好整数： \(num1\leqx\leqnum2\) \(min\_sum\leqdigit\_sum(x)\leqmax\_sum\) 请你返回好整数的数目。答案可能很大，请返回答案对$10^9+7$取余后的结果。 注意，digit_sum(x)表示x各位数字之和。 示例 示例1 输入： num1="1",num2="12",min_num=1,max_num=8...

本题为1月18日力扣每日一题 题目来源:力扣第2171题 题目tag:数位dp动态规划 题面 题目描述 给定一个正整数数组beans，其中每个整数表示一个袋子里装的魔法豆的数目。 请你从每个袋子中拿出一些豆子（也可以不拿出），使得剩下的非空袋子中（即至少还有一颗魔法豆的袋子）魔法豆的数目相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。 请返回你需要拿出魔法豆的最少数目。 示例 示例1 输入： beans=[4,1,6,5] 输出： 4 解释: 我们从有1个魔法豆的袋子中拿出1颗魔法豆。剩下袋子中魔法豆的数目为：[4,0,6,5] 然后我们从有6个魔法豆的袋子中拿出2个魔法...

本题为1月16日力扣每日一题 题目来源:力扣第2719题 题目tag:数位dp动态规划 题面 题目描述 给你两个数字字符串num1和num2，以及两个整数max_sum和min_sum。如果一个整数x满足以下条件，我们称它是一个好整数： \(num1\leqx\leqnum2\) \(min\_sum\leqdigit\_sum(x)\leqmax\_sum\) 请你返回好整数的数目。答案可能很大，请返回答案对$10^9+7$取余后的结果。 注意，digit_sum(x)表示x各位数字之和。 示例 示例1 输入： num1="1",num2="12",min_num=1,max_num=8...

本题为1月15日力扣每日一题 题目来源:力扣第82题 题目tag:链表双指针 题面 题目描述 给定一个已排序的链表的头head，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。 示例 示例1 输入： head=[1,2,3,3,4,4,5] 输出： [1,2,5] 示例2 输入： head=[1,1,1,2,3] 输出： [2,3] 提示 链表中节点数目在范围$[0,300]$内 $-100\leqNode.val\leq100$ 题目数据保证链表已经按升序排列 思路分析 本题要做的其实就两件事,一是在链表中找到重复元素,二是删除链表的一些元素. 第一件事很...

本题是组合数学中的卡特兰数问题,此处给出了用分治思想推出卡特兰数递推公式的分析思路. 题目来源:(未知) 我们先来看一下这题的题面. 题面 题目描述 西安发生新冠疫情了。不少人进了隔离区。隔离区是一个凸多边形，为了隔离人员的安全，我们需要用木板将隔离区分隔开。为了隔板的稳定，隔板两边分别与凸多边形的顶点相接，当然隔板不能被其他隔板断开。凸多边形是5的情况，有上面5种划分方案。现在知道顶点个数，你知道有多少种隔离方案,使得每个区域是三角形？ 输入 一个整数n(3<=n<=20) 输出 一个整数,即方案数 样例输入 5 样例输出 5 题目分析与常见错误思路 显然,这是一道卡特...

本题是一道背包上限可以变化的多重部分和问题,此处给出了粗略题解 题目来源:(未知) 题面 题目描述 llk经常和wy一起去yh小饭馆吃盖浇饭，一天他们吃完后llk把两个人的钱一起付了，但是wy不想欠llk的钱。 现在wy手中有一些散钱，llk手中也有一些散钱，wy想知道能不能刚好使得两不相欠，但是wy很笨，你能帮助wy吗？ 输入 多组测试数据，每组第一行输入3个非负整数，C，n，m。C代表wy欠llk的钱，n代表wy手中钱面值的种类，m代表llk手中钱面值的种类。 接下来的n行，每行两个数v，c，分别代表wy手中面值为v的钱币有c个。再接下来的m行，每行两个数v，c，分别代表llk手中面值...

本题为11月20日力扣每日一题 题目来源:力扣第799题 题目tag:动态规划模拟 题面 题目描述 我们把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层，每个玻璃杯(250ml)将盛有香槟。 从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上） 例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了此时总共有三个...

本题为11月23日力扣每日一题 题目来源:力扣第1742题 题目tag:哈希表 题面 题目描述 你在一家生产小球的玩具厂工作，有n个小球，编号从lowLimit开始，到highLimit结束（包括lowLimit和 highLimit，即 nhighLimitlowLimit+1）。另有无限数量的盒子，编号从1到infinity。 你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号321的小球应当放入编号3+2+1=6的盒子，而编号10的小球应当放入编号1+0=1的盒子。 给你两个整数lowLimit和highLimit，返回放有最...

本题为11月30日力扣每日一题 题目来源:力扣第895题 题目tag:哈希表 题面 题目描述 设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。 实现FreqStack类: FreqStack()构造一个空的堆栈。 voidpush(intval)将一个整数val压入栈顶。 intpop()删除并返回堆栈中出现频率最高的元素。如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。 示例 输入： ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"]...

本题为12月1日力扣每日一题 题目来源:力扣第1779题 题目tag:模拟 题面 题目描述 给你两个整数 x和 y ，表示你在一个笛卡尔坐标系下的 (x,y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i]=[ai,bi] 表示在 (ai,bi) 处有一个点。当一个点与你所在的位置有相同的x坐标或者相同的y坐标时，我们称这个点是有效的。 请返回距离你当前位置曼哈顿距离最近的有效点的下标（下标从0开始）。如果有多个最近的有效点，请返回下标最小的一个。...

本题为12月3日力扣每日一题 题目来源:力扣第1796题 题目tag:遍历 题面 题目描述 给你一个混合字符串s，请你返回s中第二大的数字，如果不存在第二大的数字，请你返回-1。 混合字符串由小写英文字母和数字组成。 示例 示例1 输入: s="dfa12321afd" 输出: 2 解释: 出现在s中的数字包括[1,2,3]。第二大的数字是2。 示例2 输入: s="abc1111" 输出: -1 解释: 出现在s中的数字只包含[1]。没有第二大的数字。 提示 1<=s.length<=500s 只包含小写英文字母和（或）数字。 思路分析 很简单的一道遍历题...

本题为12月6日力扣每日一题 题目来源:力扣第1805题 题目tag:查找表双指针 题面 题目描述 给你一个字符串word，该字符串由数字和小写英文字母组成。 请你用空格替换每个不是数字的字符。例如，"a123bc34d8ef34"将会变成"123 348 34"。注意，剩下的这些整数为（相邻彼此至少有一个空格隔开）："123"、"34"、"8"和"34"。 返回对word完成替换后形成的不同整数的数目。 只有当两个整数的不含前导零的十进制表示不同，才认为这两个整数也不同。 示例 示例1 输入: word="a123bc34d8ef34" 输出: 3 解释: 不同的...

本题为12月15日力扣每日一题 题目来源:力扣第1945题 题目tag:模拟 题面 题目描述 给你一个由小写字母组成的字符串s，以及一个整数k。 首先，用字母在字母表中的位置替换该字母，将s转化为一个整数（也就是，'a'用1替换，'b'用2替换，...'z'用26替换）。接着，将整数转换为其各位数字之和。共重复转换操作k次。 例如，如果s="zbax"且k=2，那么执行下述步骤后得到的结果是整数8： 转化："zbax"➝"(26)(2)(1)(24)"➝"262124"➝262124 转换1：262124 ➝2+6+2+1+2+4 ➝17 转换2：17➝1+7➝8 返回...

本题为12月16日力扣每日一题 题目来源:力扣第1785题 题目tag:贪心 题面 题目描述 给你一个整数数组nums，和两个整数limit与goal。数组nums有一条重要属性：abs(nums[i])<=limit。 返回使数组元素总和等于goal所需要向数组中添加的最少元素数量，添加元素不应改变数组中abs(nums[i])<=limit这一属性。 注意，如果x>=0，那么abs(x)等于x；否则，等于-x。 示例 示例1 输入： nums=[1,-1,1],limit=3,goal=-4 输出： 2 解释： 可以将-2和-3添加到数组中，数组的元素总和变为1...

本题为12月17日力扣每日一题 题目来源:力扣第1764题 题目tag:双指针kmp 题面 题目描述 给你一个长度为n的二维整数数组groups，同时给你一个整数数组nums。 你是否可以从nums中选出n个不相交的子数组，使得第i个子数组与groups[i]（下标从0开始）完全相同，且如果i>0，那么第(i-1)个子数组在nums中出现的位置在第i个子数组前面。（也就是说，这些子数组在nums中出现的顺序需要与groups顺序相同） 如果你可以找出这样的n个子数组，请你返回true，否则返回false。 如果不存在下标为k的元素nums[k]属于不止一个子数组，就称这些子数组是不相...

本题为12月22日22寒假集训每日一题题解 题目来源:COCO_2022.4.9 题面 题目描述 Themomenthasfinallyarrived.NotonlyisitthelastroundofCOCIthisseason,itisalsothelastroundofCOCBtheCroatianOpenCompetitioninBeekeeping.Notmanypeopleknowthatthetwocompetitionssharethesamescoringsystem.Moreprecisely,bothcompetitionsconsistofsixrounds,the...

本题为12月25日22寒假集训每日一题题解 题目来源:(未知) 题面 题目描述 李白斗酒诗百篇，长安市上酒家眠，天子呼来不上船，自称臣是酒中仙。 出自唐代杜甫的《饮中八仙歌》知章骑马似乘船，眼花落井水底眠。汝阳三斗始朝天，道逢麴车口流涎，恨不移封向酒泉。左相日兴费万钱，饮如长鲸吸百川，衔杯乐圣称避贤。宗之潇洒美少年，举觞白眼望青天，皎如玉树临风前。苏晋长斋绣佛前，醉中往往爱逃禅。李白斗酒诗百篇，长安市上酒家眠，(斗酒一作：一斗)天子呼来不上船，自称臣是酒中仙。张旭三杯草圣传，脱帽露顶王公前，挥毫落纸如云烟。焦遂五斗方卓然，高谈雄辩惊四筵。 且说李白喝了酒，吟完诗，准备回自己的房间睡觉。...

本题为12月27日22寒假集训每日一题题解 题目来源:(未知) 题面 题目描述 cad和jyx最近迷上了一款名为插入数列的游戏，有一个n行m列的网格，你每次可以按下1个或多个格子，但必须要在同一列且连续，已经按过的地方不可以再按，谁按下最后一个格子，谁就输了，刚开始的时候互有胜负，但玩过几把之后两个人慢慢的就知道了自己最优的走法是什么，现在问题来了，给你n和m你能告诉我谁会赢吗？（cad先手） 输入 多组测试样例 每组测试样例两个数分别表示行和列（n,m<=1e5） 输出 输出赢的人的名字 样例输入 11 样例输出 jyx 思路分析 显然,这是一个反Nim问题,列为堆,行为堆里元素...

本题为12月28日22寒假集训每日一题题解 题目来源:(未知) 题面 题目描述 《观沧海》曹操东临碣石，以观沧海。水何澹澹，山岛竦峙。树木丛生，百草丰茂。秋风萧瑟，洪波涌起。日月之行，若出其中；星汉灿烂，若出其里。幸甚至哉，歌以咏志。 话说曹操，写完这首诗后，看到星光灿烂的星空，发现很多颗星星可以组成正三角形。 等边三角形又称为正三角形，是指三条边相等的三角形。 你的任务：对于给定的N个正整数（代表三角形的边长），统计能够组成等边三角形的个数。 输入 第一行：N 第二行：N个正整数，相互之间用空格隔开。 输出 一行，为等边三角形的个数；如果拼不出等边三角形，输出“None”（不含引号）...

本题为12月30日22寒假集训每日一题题解 题目来源:(未知) 题面 题目描述 懒羊羊和小灰灰在玩一种棋盘游戏，棋盘的尺寸为n个方格m个方格。一开始在棋盘的右上角（1，m）放一枚硬币，每次一个人可以将硬币向左、下或左下的方格移动。 当某个人无法再移动硬币了，那么这个人就输了。游戏总是懒羊羊先开始，如果他们两个每步都是最优策略，则谁将赢得游戏？ 输入 输入包含多组测试数据。每组输入两个整数n和m（0<n,m<=2000）。当n=m=0时，输入结束。 输出 对于每组输入，如果懒羊羊赢，输出“Wonderful!”，否则输出“Whatapity!”。 样例输入Copy 53 54 6...