Home

题目链接 我们以12258为例分析如何从数字的第一位开始一步步计算不同的翻译方法的数目，我们有两种不同的选择来翻译第一位数字1。第一种选择是数字1单独翻译成“b”，后面剩下数字2258；第二种选择是1和紧挨着的2一起翻译成“m“，后面剩下数字258。当最开始的一个或者两个数字被翻译成一个字符后，我们接着翻译后面剩下的数字。显然我们可以用递归函数来计算翻译的数目。 我们定义函数f（i）表示从第i位数字开始的不同翻译的数目，那么f（i）= f（i+1）+ g（i，i+1）x f（i+1），当第i为和第i+1位两位数字拼接起来的数字在10-25的范围内时，函数g（i， i+1）的值为1；否则为0。 尽管我们用递归的思路来分析这个问题，但由于存在重复的子问题，递归并不是解决这个问题的最佳...

题目链接 这个题最直观的做法肯定是求出这个数组中所有数字的全排列，然后把每个排列拼起来，最后求拼起来的数字的最小值。但是我们知道n个数字共有n！个排列组合。这种算法显然是不够的，这道题其实是希望我们能找到一个排序规则，数组根据这个规则排序之后就能排成一个最小的数字。要确定排序规则，就要比较两个数字，也就是给出m和n，我们需要确定一个规则来判断m和n哪个应该排在前面，而不是仅仅比较这两个数字的大小。 根据题目要求，两个数字m和n能拼接成数字mn和nm，如果mn < nm，那么我们应该答应出mn，也就是m应该排在n的前面，我们定义此时m小于n；反之，如果nm < mn，则我们定义n小于m；如果mn = nm，则m等于n。接下去考虑怎么拼接数字，即给出数字m和n，怎么得到数字...

题目链接 此题与jz044.数字序列中某一位的数字相似。 class Solution: def findNthDigit1(self, n: int) -> int: digit, start, count = 1, 1, 9 while n > count: n -= count start *= 10 digit += 1 count = 9 * start * digit num = start + (n - 1) // digit return int(str(num)[(n - 1) % di...

题目链接 对于该题的直观想法大概是从0开始逐一枚举每一个数字，每枚举一个数字就求出某个数字有几位并将该数字的位数与前面的所有数字位数和累加。如果位数之和小于或等于输入n，则继续枚举，若大于，则所求必定在最新的数字里。但是显然这个思路会很慢，我们又可以试着去找找数字的规律。我们用例子，序列的第1001位是什么来阐述另外一种方法。 首先，对于序列的前10位，是0-9这十个只有一位的数字，我们显然可以跳过，那我们就可以在后面紧跟着的序列中找第991位的数字（991 = 1001 - 10）。又易知，接下来的180位数字是90个10-99的两位数，由于991 > 180，我们又可以跳过这一段，考虑接下去序列的第881位（881 = 991 - 180）。接下去我们会有900个100-...

题目链接 此题与jz042.连续子数组的最大和相同。可以用动态规划的思想解决该题。如果我们用函数f（i）表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f(i)]，其中0<=i < n。那么，我们可以用递归公示求f（i），当i=0或f（i-1）<=0时，f（i）就是数组中的第i个数字，如同上面的前面子数组和为负数的情况；如果i！=0并且f（i-1）> 0时，f（i）= f（i-1）+ nums[i]。虽然我们用递归的方式分析动态规划的问题，但最终都会基于循环去编码，这样写出来的代码如下。这个算法时间复杂度为O（N），空间复杂度为O（1）。 class Solution: def maxSubArray1(self, nums: List...

题目链接 这个题，很容易想到一个思路就是累加1-n中每个整数1出现的次数，我们每次可以通过对10求余判断整数的个位数字是不是1，如果这个数字大于10，则除以10以后再判断个位数是不是1。基于这种思路，我们很容易写出方法1，但是由于该算法需要对每个数字做除法与求余，那么如果输入数字n，n有O（logN）位，我们需要判断每一位是不是1，那么改算法的时间复杂度为O（NlogN），运算效率过低。 所以我们可以考虑从数字规律入手。首先对于一个数，如123456，我们定义digit为位数，比如3在1000位上，并且如果我们在考察在1000位上的数字3，那么将改位数字定义为cur，cur之前对数字如12则被定义为high，cur后面的数字如456则被定义为low。我们利用这些定义来促进问题的分析...

题目链接 这道题目最直观的做法是枚举数组的所有子数组并求出它们的和，但是对于一个长度为n的数组来说，总共有n（n+1）/2 个子数组，时间复杂度为O（N^2）。所以讨论另外两个更优的解法。 解法一，举例分析数组的规律。以数组[1, -2, 3, 10, -4, 7, 2, -5]为例，从头到尾逐个累加。先初始化和为0，第一步加上数字1，此时和为1。第二步加上数字-2，和就变成了-1。第三步加上数字3。我们注意到由于此前累加的和是-1，小于0，那如果用3加上-1，得到的和为2，比3本身还小，也就是说，从第一个数字开始考虑的子数组的和会小于从第三个数字开始的子数组和。因此我们不用去考虑从第一个数字开始的子数组，之前累加的和也被抛弃。我们从第三个数字重新开始累加，此时和为3。第四步加10...

题目链接 此题与jz039.数组中出现次数超过一半的数字相同。这个算法的时间复杂度是O（N），空间复杂度是O（N）。 class Solution: def majorityElement(self, nums: List[int]) -> int: votes = 0 for num in nums: if votes == 0: x = num if x == num: votes += 1 else: votes -= 1 return x

题目链接 这道题最简单的思路莫过于把输入的n个整数排序，排序之后位于最前面的k个数就是最小的k个数，这种思路的时间复杂度为O（NlogN）。 但是上面的算法并不是最快的，还有一种思想，可以从jz039中得到启发，我们也同样可以基于Partition函数来解决问题。如果基于数组的第k个数字来调整，则使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都在数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。代码如2所示，随机选择pivot可以让平均情况更快，否则容易被某些特例拖长时间。这个算法的时间复杂度是O（N），空间复杂度由于是在原地排序所以是O（1）。 第三个方法是用堆来实现，见3，之后来更新。 import r...

题目链接 这个题的思路很简单，求排列组合，我们可以将问题分解成小的问题。比如，我们把一个字符串堪称由两部分组成：第一部分是它的第一个字符；第二部分是后面的所有字符。我们求整个字符串的排列，可以看成两步：第一步求所有可能出现在第一个位置的字符，即把所有第一个字符和后面的所有字符交换；第二步固定第一个字符，求后面所有字符的排列。求后面所有字符的排列的时候，我们仍把后面的所有字符分成两部分：后面字符中的第一个字符，以及这个字符之后的所有字符。这个思路就是典型的递归思路。这个算法的时间复杂度是O（N!），空间复杂度是O（N^2）。 class Solution: def permutation(self, s: str) -> List[str]: c, re...