位运算做加法
1 |
|
位运算做减法
1 | int subtraction(int a ,int b){ |
位运算做乘法
1 |
|
位运算做除法
1 |
|
1 |
|
1 | int subtraction(int a ,int b){ |
1 |
|
1 |
|
1 | 请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。 |
辅助队列中维护最大值的递减序列,当插入一个元素时:
如果需要查询最大元素,那么只需要查询队头的元素。
当真正维护所有元素的队列中的某个元素删除时,只需要判断当前删除的元素是不是最大值队列中的第一个元素就可以继续维护最大元素。
1 | class MaxQueue { |
参考文献
作者:LeetCode-Solution 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1 | 给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。 |
1 | class Solution { |
1 | class Solution { |
难度中等122收藏分享切换为英文接收动态反馈
在一个数组 nums
中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1:
1 | 输入:nums = [3,4,3,3] |
示例 2:
1 | 输入:nums = [9,1,7,9,7,9,7] |
限制:
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
一个数组中某个元素只出现一次,其余数字出现m次,只需对每个数字的每一位求和,然后对每一位模m即可得到的每一位是只出现一次数字的每一位的数字
1 | class Solution { |
参考文献
面试题56 - II. 数组中数字出现的次数 II(位运算 + 有限状态自动机,清晰图解)Krahets发布于 2020-04-23
难度中等
一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
示例 1:
1 | 输入:nums = [4,1,4,6] |
示例 2:
1 | 输入:nums = [1,2,10,4,1,4,3,3] |
限制:
2 <= nums.length <= 10000
如果一个数组中除了一个数字以外,其他数字都出现了两次,那么如何找到出现一次的数字?
对全部数字异或操作即可得到结果,原因如下:
对于两个操作数的每一位,相同的时候结果位0,不同的时候结果为1.那么在计算的过程中,成对出现的数字的所有位会两两抵消为0,最终得到的结果就是那个在数组中只出现一次的数字。
如果可以把所有的数字分成两组,使得:
那么这个问题就可以解决。
1 | class Solution { |
参考文献
作者:LeetCode-Solution
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1 | 老师想给孩子们分发糖果,有 N 个孩子站成了一条直线,老师会根据每个孩子的表现,预先给他们评分。 |
1 | class Solution{ |
我们无需显式地额外分配糖果,只需要记录当前的递减序列长度,即可知道需要额外分配的糖果数量。
同时注意当当前的递减序列长度和上一个递增序列等长时,需要把最近的递增序列的最后一个同学也并进递减序列中。
这样,我们只要记录当前递减序列的长度dec,最近的递增序列的长度inc 和前一个同学分得的糖果数量pre 即可。
1 | class Solution { |
参考文献
作者:LeetCode-Solution 来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
1 | 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 |
我们有n个数,下标从0到n-1,然后从index=0开始数,每次数m个数,最后看能剩下谁。我们假设能剩下的数的下标为y,则我们把这件事表示为
f(n,m) = y
这个y到底表示了啥呢?注意,y是下标,所以就意味着你从index=0开始数,数y+1个数,然后就停,停谁身上谁就是结果。
行了,我们假设f(n-1,m)=x,然后来找一找f(n,m)和f(n-1,m)到底啥关系。
f(n-1,m)=x意味着啥呢?意味着有n-1个数的时候从index=0开始数,数x+1个数你就找到这结果了。那我不从index=0开始数呢?比如我从index=i开始数?那很简单,你把上面的答案也往后挪i下,就得到答案了。当然了,你要是挪到末尾了你就取个余,从头接着挪。
于是我们来思考f(n,m)时考虑以下两件事:
有n个数的时候,要划掉一个数,然后就剩n-1个数了呗,那划掉的这个数,下标是多少?
划完了这个数,往后数,数x+1个数,停在谁身上谁就是我们的答案。当然了,数的过程中你得取余
问题一:有n个数的时候,划掉了谁?下标是多少?
因为要从0数m个数,那最后肯定落到了下标为m-1的数身上了,但这个下标可能超过我们有的最大下标(n-1)了。所以攒满n个就归零接着数,逢n归零,所以要模n。
所以有n个数的时候,我们划掉了下标为(m-1)%n的数字。
问题二:我们划完了这个数,往后数x+1下,能落到谁身上呢,它的下标是几?
你往后数x+1,它下标肯定变成了(m-1)%n +x+1,和第一步的想法一样,你肯定还是得取模,所以答案为[(m-1)%n+x+1]%n,则
1 | f(n,m)=[(m-1)%n+x+1]%n |
其中x=f(n-1,m)
定理一:两个正整数a,b的和,模另外一个数c,就等于它俩分别模c,模完之后加起来再模。
1 | (a+b)%c=((a%c)+(b%c))%c |
定理二:一个正整数a,模c,模一遍和模两遍是一样的。
1 | a%c=(a%c)%c |
所以
1 | f(n,m)=[(m-1)%n+x+1]%n |
1 | class Solution { |
1 | class Solution { |
参考文献
1 | 输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。 |
1 | class Solution{ |
1 | 输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。 |
1 | class Solution { |
tag:
缺失模块。
1、请确保node版本大于6.2
2、在博客根目录(注意不是yilia根目录)执行以下命令:
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置:
jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true