剑指offer思路整理（个人向）38

剑指offer思路整理（个人向）38"/>

剑指offer思路整理（个人向）38

剑指38.字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

1.dfs，一个位置一个位置的选，当这个位置有重复元素的时候，后面重复的元素直接跳过

class Solution:def permutation(self, s: str) -> List[str]:if s == "":return []self.result = []self.length = len(s)self.recursion(s,[])return self.resultdef recursion(self,string,tmp):if len(tmp) == self.length:self.result.append("".join(tmp))return  for i in range(len(string)):if string.index(string[i]) < i:continuetmp.append(string[i])if i+1<len(string):tmp_string = string[:i]+string[i+1:]else:tmp_string = string[:i]self.recursion(tmp_string,tmp)tmp.pop()

2.同样是dfs，不过判断重复元素的方式与我不同，K神定义了一个set用于存放该位置用过的元素，同时原地算法，在原序列上直接进行字符交换。

class Solution:def permutation(self, s: str) -> List[str]:temp, result = list(s), []def dfs(x):if x == len(s) - 1:result.append(''.join(temp))returndic = set()for i in range(x,len(s)):if temp[i] not in dic:dic.add(temp[i])temp[x], temp[i] = temp[i], temp[x]dfs(x+1)temp[x], temp[i] = temp[i], temp[x]dfs(0)return result

**自我反思：**细节细节细节，大佬的代码永远能在细节处提升效率。

剑指39.数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

1.自己的方法太呆了，效率也低就不放出来献丑了。一般容易想到的方法有哈希表法和数组排序法。这里介绍一种比较神奇的方法摩尔投票法，遍历数组，对于数字进行投票，设当前数字num为众数，遇到相同的数字就vote+1，不然vote-1，若vote==0，则设下一个数字为众数重复上述流程。

class Solution:def majorityElement(self, nums: List[int]) -> int:vote = 0for num in nums:if vote == 0: x = numvote += 1 if x == num else -1return x

**自我反思：**相较于哈希表法和数组排序法，摩尔投票法不仅只需要简单遍历，还把空间复杂度压缩到了O(1)。

剑指40.最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

1.恕我直言，一看是简单题，本大聪明直接两行解决，效率还超了95%。。。

class Solution:def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:arr.sort()return arr[:k]

2.借这个机会把快排复习一下。

class Solution:def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:def quick_sort(arr,l,r):if l >= r:returni, j = l, rwhile i < j:while i < j and arr[j]>=arr[l]: j-=1while i < j and arr[i]<=arr[l]: i+=1arr[i], arr[j] = arr[j], arr[i]arr[l], arr[i] = arr[i], arr[l]quick_sort(arr,l,i-1)quick_sort(arr,i+1,r)quick_sort(arr,0,len(arr)-1)return arr[:k]

这里有个小tips，下面两句话的顺序很重要，如果先排j，最后i，j会共同指向一个小于标杆的数。如果互换，先排i，最后i，j会共同指向一个大于标杆的数。这与后面标杆的位置交换方式有直接的联系。

while i < j and arr[j]>=arr[l]: j-=1
while i < j and arr[i]<=arr[l]: i+=1

**自我反思：**其实快排的方式还可以继续优化，因为题目没有要求顺序返回，所以时刻关注标杆i与k的关系，只要某次排序完后，标杆正好是第K+1个数，那就可以直接返回前K个数了

if k < i: return quick_sort(l, i - 1) 
if k > i: return quick_sort(i + 1, r)

剑指41.数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

1.效率爆炸，直接击败5%的用户。。。就是每次新数字进行插入排序，然后每次返回中位数，就按照当前队列的长度来计算。

class MedianFinder:def __init__(self):"""initialize your data structure here."""self.seq = []def addNum(self, num: int) -> None:if self.seq == []:self.seq.append(num)returnelse:for i in range(len(self.seq)):if self.seq[i]>num:self.seq.insert(i,num)returnself.seq.append(num)returndef findMedian(self) -> float:if self.seq == []:returnlength = len(self.seq)mid = length//2if length%2==1:return self.seq[mid]else:return (self.seq[mid]+self.seq[length//2-1])/2

2.这道题的执行效率其实与插入的方式密切相关，K神选择了使用堆结构。这个大顶堆和小顶堆，还真是没用过，借这个机会学习一下
python heapq是小顶堆，实现大顶堆只需要将元素全部取相反数就可以了。相比于我用插入排序，效率是指数级别的提升。。。

from heapq import *class MedianFinder:def __init__(self):self.A = [] # 小顶堆，保存较大的一半self.B = [] # 大顶堆，保存较小的一半def addNum(self, num: int) -> None:if len(self.A) != len(self.B):heappush(self.B, -heappushpop(self.A, num))else:heappush(self.A, -heappushpop(self.B, -num))def findMedian(self) -> float:return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0

**自我反思：**堆结构是面试中经常会问的问题，后面要好好整理一下堆结构。

剑指42.连续子数组的最大和

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

示例1:

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

1.有点类似于股票最大价值那道题，由于时间复杂度为O(n)，所以单次遍历的过程中，既要维护子数组的start，同时还要维护Sum。当前和temp_sum小于0的时候，可以换新的start。

class Solution:def maxSubArray(self, nums: List[int]) -> int:sum_ = -100start = 0temp_sum = 0for i in range(len(nums)):if temp_sum<0:start = itemp_sum = nums[start]sum_ = max(sum_,temp_sum)continuetemp_sum = temp_sum + nums[i]sum_ = max(sum_,temp_sum)return sum_

2.看了K神的解释，其实这道题规定时间复杂度为O(n)的时候，就已经决定了暴力O(N^2)和分治O(NlogN)不适用了，最合适的就是动态规划。设动态规划列表 dp，dp[i] 代表以元素 nums[i] 为结尾的连续子数组最大和。
状态转移方程
若 dp[i−1]≤0 ，说明 dp[i - 1]对 dp[i] 产生负贡献，即 dp[i-1] + nums[i]还不如 nums[i]本身大。

当 dp[i - 1] > 0时：执行 dp[i] = dp[i-1] + nums[i] ；
当 dp[i - 1] <= 0时：执行 dp[i] = nums[i] ；

class Solution:def maxSubArray(self, nums: List[int]) -> int:for i in range(1,len(nums)):nums[i] += max(0,nums[i-1])return max(nums)

但其实运行效率并不是很高，可能是因为最后那个max的原因。

**自我反思：**动态规划的题真的太多遍了，反正看到对时间复杂度要求比较高的题，尽量往动态规划上想想。

剑指43. 1～n中整数中1出现的次数

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

示例 1：

输入：n = 12
输出：5

1.说实话，这道题当时真的恶心到我了。而现在，我被自己当时的代码恶心到了。看了一下，自己当时的大致思路是这样的，每个数位上能出现1的个数，与它两边是有关系的，比如213，十位数字是1的次数，与2和3都有关系。

class Solution:def countDigitOne(self, n: int) -> int:place = []result = 0temp = nwhile temp!=0:place.append(temp%10)temp = temp//10place.insert(0,0)place.append(0)print(place)for i in range(1,len(place)-1):if place[i] > 1:result += (10**(i-1))*((n//(10**i))+1)elif place[i] == 1:result += (10**(i-1))*(n//(10**i))+(n%(10**(i-1))+1)else:result += (10**(i-1))*(n//(10**i))return result

2.K神的思路貌似和我差不多，不，是一毛一样，总结来讲
设当前位i为cur，低位为low，高位为high，10的i次方为位因子digit，
1.当cur为0时，当前位为1的个数只与high和dight有关，high×digit
2.当cur为1时，当前位为1的个数与high、low和digit有关，high×digit+low+1
3.当cur大于1时，当前位为1的个数与high和dight有关，(high+1)×digit
代码：

class Solution:def countDigitOne(self, n: int) -> int:digit, res = 1, 0high, cur, low = n // 10, n % 10, 0while high != 0 or cur != 0:if cur == 0: res += high * digitelif cur == 1: res += high * digit + low + 1else: res += (high + 1) * digitlow += cur * digitcur = high % 10high //= 10digit *= 10return res

**自我反思：**其实这种类型的题没有什么技巧可言，就多积累多思考吧。

剑指44.数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。

示例 1：

输入：n = 3
输出：3

1.先根据n求出这是几位数，然后从同位数除法，根据取整取余，判断这是第几个数字的第几位。

class Solution:def findNthDigit(self, n: int) -> int:nth = 10n_ = 1temp = 0n = nwhile True:if nth>n:breakn_ += 1temp = nthnth += n_*(10**n_ - 10**(n_-1))a = (n - temp)//n_b = (n - temp)%n_start = 10**(n_-1)if start == 1:start = 0a = start + aa = str(a)return int(a[b])

2.K神的思路与我的基本一致，不过他的代码真的学到了，再手打一遍。

class Solution:def findNthDigit(self, n: int) -> int:digit, start, count = 1, 1, 9while n > count:n -= countdigit += 1start = 10**(digit-1)count = 9 * start * digitnum = start + (n-1)//digitindex = (n-1)%digitreturn int(str(num)[index])

**自我反思：**为什么我的代码总是那么冗长。

剑指45.把数组排成最小的数

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

1.基本思路大家都知道，最高位越小越放前面，但这里有个问题50、51和504，它们的排序方式应该是504、50、51，这并不是一个简单的比大小，如果强行按位算，会非常麻烦。这里用快速排序的同时，引入了字符串比较规则，if str(num) + str(mid) >= str(mid) + str(num)，则num是“更小的数”也就是要放在前面的数。

class Solution:def minNumber(self, nums: List[int]) -> str:stic = {str(x):[] for x in range(10)}result = ""for num in nums:stic[str(num)[0]].append(num)for k in stic:result += self.qksort(stic[k])return resultdef qksort(self,data):if len(data) >= 2:         mid = data[len(data)//2]  left, right = [], []data.remove(mid)for num in data:            if str(num) + str(mid) >= str(mid) + str(num):                right.append(num)           else:                left.append(num)    return self.qksort(left) + str(mid) + self.qksort(right)    elif len(data) == 1:return str(data[0])else:return ""

2.菜鸟的代码如上，大神的代码如下

class Solution:def minNumber(self, nums: List[int]) -> str:strs = [str(num) for num in nums]def quick_sort(l,r):if l >= r:returni, j = l, rwhile i < j:while i < j and strs[j]+strs[l]>=strs[l]+strs[j]: j-=1while i < j and strs[i]+strs[l]<=strs[l]+strs[i]: i+=1strs[i], strs[j] = strs[j], strs[i]strs[l], strs[i] = strs[i], strs[l]quick_sort(l,i-1)quick_sort(i+1,r)quick_sort(0,len(strs)-1)return ''.join(strs)

**自我反思：**快排的代码一定要非常非常熟练

剑指46.把数字翻译成字符串

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

1.动态规划。当时在这道题上卡了好久，甚至想用递归。

class Solution:def translateNum(self, num: int) -> int:num = str(num)a, b = 1, 1for i in range(len(num)-1):a, b = (a+b if '10'<=num[i:i+2]<='25' else a), areturn a

**自我反思：**万物皆可动态规划