《剑指offer》（6）其他算法

先计算下三角，再遍历一次计算上三角。

class Solution:

def multiply(self , A: List[int]) -> List[int]:

#长度判断

n = len(A)

if n <= 1:

return []

B = [1]*n

#计算乘矩阵的下三角，B中的每一个数都是A的前一个数和B的前一个数相乘

for i in range(1,n):

B[i] = B[i-1] * A[i-1]

#计算乘矩阵的上三角，倒着数A，用变量存累乘

temp = 1

for i in range(n-1,-1,-1):

B[i] *= temp

temp *= A[i] #累乘

return B

class Solution:

def FirstNotRepeatingChar(self , s: str) -> int:

dict_s = {}

#利用哈希表，第一次遍历后，将元素的数值统计

for i in s:

if i in dict_s:

dict_s[i] += 1

else:

dict_s[i] = 1

#第二次遍历找到第一个值为1的下标输出

for i in s:

if dict_s[i] == 1:

return s.index(i)

#否则返回-1

return -1

class Solution:

def replaceSpace(self , s: str) -> str:

if len(s) == 0:

return ''

res = []

for i in range(len(s)):

if s[i] == ' ':

res.append('%20')

else:

res.append(s[i])

return ''.join(res)

class Solution:

def reOrderArray(self , array: List[int]) -> List[int]:

if len(array) == 0:

return []

a , b = [] ,[]

for i in array:

if i % 2 == 0:

b.append(i)

else:

a.append(i)

return a+b

class Solution:

def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int:

dict_m = {}

for i in numbers:

if i in dict_m:

dict_m[i] += 1

else:

dict_m[i] = 1

n = len(numbers)

res = [i[0] for i in dict_m.items() if i[1] > (n//2)]

return res[0]

class Solution:

def reOrderArrayTwo(self , array: List[int]) -> List[int]:

#用两个指针一个是奇数开始的地方，一个是偶数开始的地方。

n = len(array)

if n == 0:

return []

start = 0 #偶数开始的位置

for i in array:

if i % 2 != 0:

start += 1

i = 0

while i < n and start < n:

if array[i] % 2 == 0 and array[start] % 2 != 0: #如果是奇偶就互换

array[i], array[start] = array[start], array[i]

start += 1

i += 1

elif array[i] % 2 == 0 and array[start] % 2 == 0: #都是偶数就移动start

start += 1

else: #否则就移动i

i += 1

return array

class Solution:

def printNumbers(self , n: int) -> List[int]:

if n == 0:

return []

s = 1

#从1开始连乘10或者直接用次方计算10^n

for i in range(n):

s *= 10

res = []

#从1开始遍历到10^n-1

for i in range(1,s):

res.append(i)

return res

class Solution:

def PrintMinNumber(self , numbers: List[int]) -> str:

import functools

#判断长度

if len(numbers) == 0:

return ''

#将整型数组转换成字符串数组

number = list(map(str,numbers))

#定义特定的排序规则

camp = lambda a,b: 1 if a+b > b+a else -1

#用定义的排序规则对字符串进行排序

number = sorted(number,key = functools.cmp_to_key(camp))

# number.sort(key=functools.cmp_to_key(camp))

#拼接输出

return ''.join(number)

class Solution:

def FindContinuousSequence(self , s: int) -> List[List[int]]:

#用两个指针，先从1开始加，如果加到大于等于后，判断是等于就存答案，大于就移动start继续重新加

if s == 0:

return []

num = [i for i in range(1,s+1)]

start = 1

res = []

while start < s:

end = start

val = 0

while end < s and val < s:

val += end

end += 1

if val == s: #存答案

res.append(num[start-1:end-1])

start += 1

else: #重新加

start += 1

return res

class Solution:

def FindNumbersWithSum(self , array: List[int], s: int) -> List[int]:

# 左右指针

if len(array) == 0:

return []

left = 0

right = len(array) - 1

while left < right:

val = array[left] + array[right]

if val > s:

right -= 1

elif val < s:

left += 1

else:

return [array[left],array[right]]

return []

class Solution:

def LeftRotateString(self , s: str, n: int) -> str:

#判断长度

if len(s) == 0 or n == 0:

return s

length = len(s)

n = n % length #剔除循环到原字符串的次数，取余数

for i in range(n):

s += s[i]

s = s[n:]

return s

class Solution:

def LastRemaining_Solution(self , n: int, m: int) -> int:

#用两个指针，index来做循环，out来控制出列数

res = [i for i in range(n)]

index = 0 #从0开始数数

out = 0

while len(res) > 1:

if index > len(res)-1: #查看是否需要循环数组

index = 0

if out == m-1: #确定出列数

res.pop(index)

out = 0

if index > len(res) - 1: #如果当前出列后，index已经大于数组长度，就循环数组

index = 0

index += 1

out += 1

return res[0]

class Solution:

#存储字符流和字符出现的次数

s = []

dict_s = {}

#遍历字符流并且找到第一个为1的字符并且return

def FirstAppearingOnce(self):

for c in self.s:

if self.dict_s[c] == 1:

return c

return '#'

#插入时，一边插入字符流，一边统计数值

def Insert(self, char):

self.s.append(char)

if char in self.dict_s:

self.dict_s[char] += 1

else:

self.dict_s[char] = 1

动态规划：如果绳子只有2，那么不分开（2）比分开（1*1）大，3同理。也就是说绳子会有一个不可分割的长度j，在这个长度下，不分开会比分开更好。假设长度为i的绳子的不可分割长度是j，那么此时的最大乘积是dp[i] = max(dp[i], j*dp[i-j]) 初始化dp，前面四个数是1,2,3,4

class Solution:

def cutRope(self , n: int) -> int:

# 动态规划

#检查当数组长度小于等于3的时候直接算：

if n <= 3:

return n-1

#初始化前4个乘积

dp = [1]*(n+1)

dp[1],dp[2],dp[3],dp[4] = 1,2,3,4 #跳过0

#遍历长度，对于每一个长度i，最大值是当前长度或者（不可分的j）*dp[i-j]

for i in range(5,n+1):

for j in range(1,i):

dp[i] = max(dp[i],j*dp[i-j])

# 返回数组最后一位就是答案

return dp[-1]

数学计算：要使乘积最大，要尽可能的相等的将绳子分开。假设绳子分成m段，每段长度是x，

n = m*x, 最大乘积是x^m, m=n/x , 所以最大乘积是x^(n/x) ,将常数n提出，最大乘积是x^(1/x)

但是由于数据量巨大，所以求幂需要重新实现，否则会超时。

把一个数a乘n次，按照二分的思想，将n不断除以2，如果是偶数，就累乘a = a*a ,如果是奇数，就将当前的a和结果相乘。直到n为0.（所以每次循环a不是一个一个乘上去的，是直接2的指数级乘上去的）

class Solution:

def pow(self,a,n):

MOD = 998244353 #值太大需要取模

ans = 1

while n>0:

if n%2 == 1:

ans = (ans*a)%MOD

a =(a*a)%MOD

n = n // 2 #不断分割n

return ans

def cutRope(self , number: int) -> int:

#不超3的直接结算

if number <= 3:

return number - 1

#能整除3

if number % 3 == 0:

n = self.pow(3,(number//3))

return n

#最后剩余1，就拆掉一个分组，变成2*2

elif number % 3 == 1:

n = self.pow(3,number//3-1)

return 4*n %998244353 #最后数太大要取模

#剩余一个2就直接乘

else:

n = self.pow(3,number//3)

return 2*n %998244353 #最后数太大要取模

丑数 = 已有的丑数 * (2,3,5) 得到三个新的丑数，但是新的丑数位置不一定正确，而且可能会有重复。用p2,p3,p5三个指针，分别指向当前2,3,5因子得到的最大丑数。每次取这几个丑数中的最小值。使用一次质因子，就把相应的指针向前移动。（相当于每次都是最小的丑数的基础上形成下一个丑数，保证了递增）

class Solution:

def GetUglyNumber_Solution(self , index: int) -> int:

if index <= 0:

return 0

uglylist = [1]

p2,p3,p5 = 0,0,0

for i in range(index-1): #因为1已经在数组中，只需要再要后面的index-1

new = min(uglylist[p2]*2,uglylist[p3]*3,uglylist[p5]*5)

uglylist.append(new)

if new % 2 == 0:

p2 += 1

if new % 3 == 0: