每日leetcode第0086天 0231. Power of Two

首先,要判断是否为正整数,如果不是,那么就不可能是2的幂。

接下来可以不使用循环或递归,而使用位运算。

位运算的话,如果这个数是2的幂,那么二进制肯定是100000的形式。

如果它自身减去1,就会变成11111的形式。

这个时候我们按位与,结果就会变成0。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0085天 1926. Nearest Exit from Entrance in Maze

这是一道快乐的宽度优先搜索题目。

我做宽度优先搜索都很快乐,经常是洋洋洒洒一大堆代码,一次跑通。

 

先是读数据,把maze读进来,把入口读进来。

入门放入可以抵达的reaches队列中。

还有一些需要预处理,比如四周这一圈四条边判断那些是点的就是出口,建一个is_exit二维数组,但是入口不能是出口,这里还要再加一句代码。

判断每个点有没有去过,建一个is_visited二维数组,入口要设置为去过了。

四个方向开一个二维数组direction。

 

然后开始搜索,搜索到队列为空,如果一直搜不到就输出-1。

搜的时候先判断这个点是不是出口了,出口到了就输出返回。

往四个方向走,如果走出地图就不允许,如果去过就不允许,如果是墙就不允许。

把可以去的点叫做nr添加进队列中,然后标记这个点去过了已经。

搜完一个点的四方向,就把这个点弹出。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0084天 1464. Maximum Product of Two Elements in an Array

这是一道堆的题目,也就是优先队列的题目。

按照leetcode的方式,我们会获得一个数组,这样我们有三种好方法。

第一种,排序,找出最大两个相乘。

第二种,找一遍用两个变量找出最大和第二大相乘。

第三种,转成优先队列,然后弹出最大两个来相乘。

排序复杂度为nlogn,不排序复杂度为n,转成优先队列复杂度为n。

这里考查的就是堆的知识了,把数据转成优先队列和构建一个优先队列的复杂度其实不一样。

构建一个新的,复杂度是nlogn,但本就有的空间变优先队列复杂度只要n。

用优先队列来写,也很轻松写意。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0083天 0781. Rabbits in Forest

这是一道有趣的数学方面的问题。

今天刚好是中秋节,我们就不管月宫的兔子,来数数森林中的兔子吧。

比如我们遇到了2只兔子说7,那么他们俩可能是颜色一样的,也就是这个颜色兔子得有8只。

比如我们遇到了8只兔子说7,那么这8只可能是颜色一样的,也就是这个颜色兔子得有8只。

比如我们遇到了9只兔子说7,那么不可能是颜色都一样的,也就是这个颜色兔子至少得有16只。

比如我们遇到了17只兔子说7,那么不可能是颜色都一样的,也就是这个颜色兔子至少得有24只。

我们会发现规律,兔子的只数,取决于他们说的数字和多少只说了同样的数字。

1个7,为8只。

2个7,为8只。

3个7,为8只。

4个7,为8只。

5个7,为8只。

6个7,为8只。

7个7,为8只。

8个7,为8只。

9个7,为16只。

也就是拿报号的只数除以8,除完得是向上去整,最后乘以8。

那么向上去整怎么做呢?以8为例,有两种方案:

((报号只数 – 1) / 8) + 1 这样就向上去整了最终结果+1,但也考虑刚好整除,所以预先-1。

(报号只数 + (8 – 1)) / 8 这样也可以向上去整,因为刚好整除的加上7也不够多一位。

 

处理完每一种兔子报的数字和兔子的数量的关联系后,我们就差用什么数据结构来装这些兔子报的号码了。

把数字都存起来,然后再数,时间复杂度会较高。

我们用桶排序来装的话,可以实现,但怕某一只兔子报个很大的数字,这样我们得开很大的数组。空间又是问题。

所以最佳方案应该是哈希表,如果这个数字有,那就这个数字的数量+=1,如果没有,就建立键值对,值开始就是1。

最终根据哈希表的迭代器来加总输出。

 

真是一道有趣的题目,祝大家中秋节快乐。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0082天 1295. Find Numbers with Even Number of Digits

非常简单的一道计数题,

这里模2其实可以使用位运算按位与1会更好。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0081天 0935. Knight Dialer

欢迎来到骑士拨号器。

这是一道很有趣的看上去像二维数组矩阵,实际上完全不用模拟的题。

这道题我们需要用到的是动态规划。

一个点可以去另两个点,那么这个点也只能从那两个点过来。

所以我们可以建立一个二维数组phone_numbers[i][j],其中i代表走几步,j代表最终走到的数字,值表示电话号码的可能性有多少种。

状态转移方程式则为:……

天那,写状态转移时候写疯我了,我要根据j来判断怎么转换,我一开始本能用if,后来发现0-9有10个,应该用switch。当我写完switch我发现全部都是要走一遍的,压根不用判断j,就写它个十行状态转移方程式,这样内层循环都省了。

最终把10个数字的方案加总,输出。

这里注意会一直做module1000000007的操作,所以用int也行。毕竟两个小于10亿的数字加起来也超不过21个亿。

这道题还有别的思路,就是根据号码的对称性来分类,这样算前算后乘一下对称的号码数量也可以。可以少算一点点,不太多。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0080天 1388. Pizza With 3n Slices

这是一道有意思的动态规划题。

首先我们需要做过打家劫舍和打家劫舍2。

我们可以确定的是,你选了一块,这一块相邻的两块就会不见,所以你选的每一块披萨都不允许相邻。

但你如果去用打家劫舍2去做,就会悲剧。

分析一下原因:

打家劫舍2只是不允许打劫相邻的,所以一共打劫的是len / 2家。

但是披萨这道题目只允许我们拿len / 3块。

怎么样可以保证我们拿的并不会过量呢?

但本身的一维数组并没有记录数量,也就是说数据有丢失导致失真。

这个时候我们必须要使用升维,我们需要多记录一个数据,就是已经拿了几块披萨。

total[i][j]表示的是一只到第i块披萨,已经拿了j块披萨,所拿的最大值。

这样一来,我们的状态转移方程式也就出来了。

可以选择拿或者不拿。

不拿:total[i – 1][j]

拿:total[i – 2][j – 1] + s[i – 1]

这里需要考虑一下越界i为1的时候会越界,所以i为1要单独考虑做预处理。

因为要重复算两次,所以我们就写成一个函数来找最大值。

从两个最大值中找较大的输出。

 

以898611举例,我们先算89861最大值16。再算98611最大值15。

 

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0079天 1449. Form Largest Integer With Digits That Add up to Target

非常有趣,我们要使用一定的金额购买数字,拿买的数字拼一个最大的数。

钱还必须得花完,不能有剩下的。(这点很重要)

这道题目如果想到了动态规划,那么距离成功就不远了。

这道题就像是完全背包问题,每个数字都是价值为1,重量为cost的货物。

数字是越多越好,要先考虑多,再考虑大。

先初始化dp数组,0到target,每个先写成”0″,0写成空串””。

接下来就开始尝试去拼接。

状态转移方程式:paint[i] = to_string(j) + paint[ori];

转移之前,我们就要先考虑

1.如果原串下标左得越界了,就不用考虑了。

2.如果原串就是“0”,那也不用考虑转移了。

3.原串的长度如果和现在一样长,那么就说明可以加一位,得加,需要状态转移。如果只短一位,说明之前有更小的数字拼接过,但现在j是从小到大遍历的,所以肯定也更大,就需要状态转移。如果加了一位还没现在这个长,那么就别转了,肯定没用。

最终输出的就是paint[target]的数字。

这道题目巧在数字可能比较大,所以我们不可以傻乎乎用int或longlong,而用string。用了string怎么来比较两个数字大小,其实就是比长度,长度一样,丝毫不慌,因为j的遍历顺序设计得好。哈哈。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0078天 1316. Distinct Echo Substrings

今天来做一道字符串的题目。

明确的回声字符串。回声字符串就是两个一样的字符串拼成的字符串。

我采用的是暴力解法和哈希集合的方式来做。

暴力解法有很多种方案,第一种是遍历所有i和j,判断从i到j是否为回声字符串。

这种情况把奇数的也都遍历进去了,不好。

第二种就是只遍历偶数的,这种遍历方式算是优化过了。

第三种就是遍历的i和j只跑一半,然后去后一段找是否回声。这个其实效率和上面差不多,就是写起来更巧妙。

第四种是只跑一半,并且完全思考清楚i和j跑的范围。

left1也就是i,我认为范围是0到len-1因为最后一个字母后面不可能还有东西和它形成回声了。

right1也就是j是有点绕的。它应该跑到从i到终点的一半,跑多了,后面的空间不够回声的长度。那么具体是多少呢。如果left1=0,那么我们计算一下就是(len – 1) / 2了,这个式子可以让奇数偶数都能用。那么left1变大后,这个范围跑动也就缩小了。变成了(len – left1 – 1) / 2 + left相当于还是剩下的一半或少一个的一半再加上left+1的右移。

使用substr来确定两个串是否回声,接下来。我们就再去哈希集合里面找,在不在里面,在就拉倒了,不在就要ans自增并把回声串放入哈希集合。

发表在 每日LeetCode | 标签为 , | 留下评论

每日leetcode第0077天 0517. Super Washing Machines

这是一道特别有意思的题目。

自己可以尝试多举几个数字来尝试。

这样我们就可以得到最佳的策略。甚至可以自己写一个模拟算法。

考虑到每一次每一个洗衣机可以向左右丢一件,每一台洗衣机可以最多接受两件。

所以麻烦的是丢的,而不是接的。

 

如果是模拟算法,我们需要怎么判断往哪里丢呢。

比如3 7 4 6,目标是集体变5。

7必然要往左丢,因为左边的平均值低于目标。

而右边平均值等于目标,就不需要往右边丢了。

丢了还得收回来,这不扯淡么。

又比如1 6 2,那么应该怎么丢呢?

其实就是中间那个往两边都得丢,先往左还是右有差吗?

没差,因为反正要丢3次。

2 0 11 0 2,如果像这样左右会有0导致无法一次性传递到两边,怎么办?

其实完全不用担心,只需要保证每一次都尽力往外传往外丢就可以了。

这个情况也就是丢11-目标值3,也就是8次。

 

弄清楚模拟算法后,我们就可以用贪心算法了。

直接看哪个比目标多得最多,多余的值输出就可以了。

发表在 每日LeetCode | 标签为 , | 留下评论