怎么用递归解决《344. 反转字符串》

这个题目太简单了,我就不贴题目的原文了。意思是这样的,给你一个字符数组(字符串),然后,你要原地把这个数组的元素顺序反转。这道题目是非常平凡的,常规解法是使用双指针,头尾指针向中间夹逼,交换头尾指针指向的字符。

用 Python 写,会非常短小。时间复杂度是 O(n),空间复杂度是 O(1)。

继续阅读 -- 共 432 字

377. 组合总和 IV

这是今天的打卡题目,看标题,就知道这是系列题目,不过那不重要的。我们先来看看题目:

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1:
输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。

示例 2:
输入:nums = [9], target = 3
输出:0
 

提示:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000

377. 组合总和IV <-- 传送门

继续阅读 -- 共 1983 字

1006. 笨阶乘

通常,正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如,factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反,我们设计了一个笨阶乘 clumsy:在整数的递减序列中,我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符:乘法(*),除法(/),加法(+)和减法(-)。

例如,clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而,这些运算仍然使用通常的算术运算顺序:我们在任何加、减步骤之前执行所有的乘法和除法步骤,并且按从左到右处理乘法和除法步骤。

另外,我们使用的除法是地板除法(floor division),所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数:给定一个整数 N,它返回 N 的笨阶乘。

示例 1:
输入:4
输出:7
解释:7 = 4 * 3 / 2 + 1

示例 2:
输入:10
输出:12
解释:12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

1006. 笨阶乘 <--- 传送门

继续阅读 -- 共 1280 字

338.比特位计数

[latexpage]这道题目的意思是,计算每个数字的二进制表示里 1 的数量。其实,计算方法,也比较简单,就是写个循环,计算当前循环中的数字的 bit 位数。怎么计算一个数字的 bit 里的 1 的位数呢?

我想到的方法很简单,就是使用 “位与” 计算,一个整数,与 1 进行 & 运算,结果 1,说明最低位是 1,结果是 0,说明最低位是 0。然后,我们把这个数字往右移 1 位。重复这个过程,直到这个数字变为 0。就统计出了所有的 1 的数量。

继续阅读 -- 共 1020 字

341. 扁平化嵌套列表迭代器

这是今天的打卡题,说实在做得我实在是心态崩坏,先来看看题目,我再来细说:

给你一个嵌套的整型列表。请你设计一个迭代器,使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数,或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:

输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false,next 返回的元素的顺序应该是: [1,4,6]。

341. 扁平化嵌套列表迭代器 <-- 传送门 力扣(LeetCode)

继续阅读 -- 共 905 字

453. 最小操作次数使数组元素相等

这道题虽然是简单,但是一看这复杂的操作,我就彻底懵逼了。每次将 n-1 个数字加一,最后要所有的数字相等。

这是太抽象的一个过程,脑海里自然联想到了滑块拼图之类的东西,或者覆盖问题,想得极其复杂,所以马上就不知道怎么做了。然后还草稿上画了很多,找这个问题的规律。找了半天也没找到。

继续阅读 -- 共 842 字

怎么推导出《115. 不同的子序列》的动态规划解法

[latexpage]今天的打卡题,是一道“困难”,先来看看题目:

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)

题目数据保证答案符合 32 位带符号整数范围。

115. 不同的子序列 <-- 传送门
继续阅读 -- 共 2453 字

401. 二进制手表

这道题目,展示了一款二进制手表,然后问,给定点亮的灯的数量,计算可能展示出来的所有时间。这个题目,一看就知道可能要用回溯法了。

回溯法,其实就是穷举法的一种,只不过穷举得比较有章法而已,有时候我们说回溯法是深度优先搜索。回溯法的关键是,第一步,确认目标达成条件,作为回溯停止的点;第二步,找出状态空间,确认扩展下一步的方法;第三步,确认所有需要保存的状态;最后,写出递归算法。

继续阅读 -- 共 1006 字

54. 螺旋矩阵 & 59. 螺旋矩阵 II

好几天没有写题解了,为什么没有写呢?就是我觉得好像这道题没有什么意义:比如,这道题,极其繁琐,没什么巧思;或者,这道题,根本就是脑筋急转弯,想得出来就无比轻易,想不出来就误入歧途,功底无用。

这种状态就是极其危险的状态,所谓的高不成、低不就。非要等一道完美的题目出现,才去认真学习和分析么?这是心飘了。要警惕,深刻地警惕。每道题,都要认真对待,尽量读懂,自己做出来了,要跟别人的做法去比较,自己做不出来,要看懂别人的做法,不能轻视一道题目。

自勉结束,看看今天的打卡题。题目要求是按照顺时针螺旋顺序,打印一个给定的 m×n 的矩阵。也就是字面意思,我不想抄题目了,给个传送门吧。这里是传送门


继续阅读 -- 共 1877 字