数学

题解-通过操作使数组长度最小筑-脑筋急转弯,用小数踢掉大数

Problem: 100164. 通过操作使数组长度最小 思路 观察$nums[i]%nums[j]$有如下的可能性 如果$nums[i]<nums[j]$,最后只是将数组中的$nums[j]$踢出 $nums[i]>=nums[j]$则是二者踢出,$nums[i]%nums[j]$进入数组,且显然$nums[i]%nums[j]<nums[j]<=nums[i]$ 因为没有限定ij的关系,发现这种操作要么是小数将大数从数组中踢掉,要么是引入一个更小的数,将二者踢掉 最后剩下的长度应该和数组中最小值有关,且这个最小值包括操作中可能产生的 如果没有产生新的最小值,则很容易知道最后剩下的数就是原始数组中最小值的数量,然后将其两两组合,引进0,就能得到答案 如何产生更小值: 回顾1,我们将所有数与最小值相模 如果余数不为0,就为新的最小值 如果余数全为0,说明所有数都是最小值的倍数,则它们之间两两相模的最小值大于等于原始数组的最小值 我们只需要产生一个新的更小值就能把所有其他数都踢掉,此时答案是1 时间复杂度:$O(n)$ Code class Solution: def minimumArrayLength(self, nums: List[int]) -> int: m=min(nums) for num in nums: if num%m!=0:# 可以产生新的最小值 return 1 length=nums.count(m) return length//2+length%2

题解-求和游戏-数学,以及简单分类证明

Problem: 1927. 求和游戏 初始思路 考虑一些等价:我们先把这个数分为两个部分$left,right$,分别是左右两边数字的和,形式化写为$\displaystyle right=\sum_{i=n/2}^{n}num_i(0<=num_i<=9)$剩下的问号数量分别为$n_{left},n_{right}$ 我们要做的实际上是对$left和right$分别操作$n_{left},n_{right}$n次,其中我们允许的操作就是对该数加上0-9的任意一个数 显然操作是对称的,所以我们只考虑有效的操作数,也就是$abs(n_{left}-n_{right})$,而且显然有效的操作数只会存在于一个数身上:如果出现在两个身上就会对称消除 我们可以先除去一些情况: 如果剩下的有效操作是奇数,则Alice一定赢,因为她一定不会选择让数相等的操作(只有一个选择),而Alice有10个合法选择 然后我们发现操作一定会让数增加,也就是说,如果存在有效操作的是较大的那个数,则一定不可能相等 现在我们只剩下了一种情况:有一个较小的数能够让双方都操作$x$次,如何让较小的数变为较大的数 设两数相差的绝对值为$gap$,每个人能操作$x$次 Alice有两个选择: 一个是积极加,在自己的回合里都加9,这样会让较小的数飞快增长,如果两数相差比较小,就能让这个数超过大点的数,从而Bob不能选出来:也就是$9x>gap$,Alice能赢 另一个是完全消极,每次都加0,这样会让数缓慢增长,单靠Bob变数增加,如果$gap>9x$,此时Alice也赢 我们惊讶地发现此时出现了9x大于小于gap,Bob都会输,就只剩下了$$9x==gap$$,所幸,我们能发现此时Bob会赢,因为不管此时Alice如何操作,Bob后手都能补齐9 Code class Solution: def sumGame(self, num: str) -> bool: n=len(num) nums=0 left=0 right=0 for i in range(n//2): if num[i]=='?': nums+=1 else: left+=ord(num[i])-ord('0') for i in range(n//2,n): if num[i]=='?': nums-=1 else: right+=ord(num[i])-ord('0') if nums%2!=0 or (left>right and nums>0) or (left<right and nums<0): #最后轮到Alice或者一定不能赢的情况 return True AliceCan=abs(nums)//2 want=abs(left-right) if AliceCan*9!=want: return True return False

题解-英雄的力量

对一道LeetCode的hard题做了一个有趣的解释

题解-全局倒置和部分倒置-找数学规律

思路 根据题意可知全局倒置包含局部倒置，对于本题如果有 非局部倒置 的全局倒置，则返回false，不然就返回true 很容易相出用暴力去搜索自己2位之后的数组元素中是否有比自己小的，时间复杂度:$O(n^2)$ 倒置是根据的是递增数组出现的，也就是说我们得到的数组实际上是对递增数组进行过几次置换的数组 根据定义可以知道局部倒置的实质就是将相邻的数组元素进行的交换，所以要做的就是与原数组进行比较 位置不变的跳过 位置变化的判断是否和原数组相邻位置的值相等，相等则跳过 不满足上述两个条件的就是全局置换，返回false 代码 class Solution { public: bool isIdealPermutation(vector<int>& nums) { int n=nums.size()-1; int i=0; while (i<n){ if (nums[i]==i) i++; else if (nums[i]==i+1&&nums[i+1]==i) i+=2; else return false; } return true; } };