优化时间和空间效率

Q. 数组中出现次数超过一半的数字：数组中有一个数字出现次数超过了数组长度的一半，请找出这个数字
A. 思路

思路1: 用map记录出现次数, O(n)
思路2: 快排思路，出现频次超过一半即要寻找中位数，利用partition k将小于k的全部排在k左边，大于的排在右边。如果k的下标正好是中位数，则返回k，否则去数更多的半边寻找。
思路3: （因为结果数超过一半，所以和不一样的数抵消后肯定只剩结果数）使用两个变量num和numCnt，分别记录一个数字和出现次数，如果新遍历到的数字和所记录数字不符，则减1，否则加1；直到为0时将所记录数字置为新数字。O(n)

def MoreThanHalfNum(number: list):
    if number == None or len(number) == 0:
        return

    num = number[0]
    numCnt = 1
    for i in range(1, len(number)):
        if numCnt == 0:
            num = number[i]
            numCnt = 1
            continue
        if num == number[i]:
            numCnt += 1
        else:
            numCnt -= 1

    return num

Q. 最小的k个数：输入你个整数，找出最小的k个数。{4,5,1,6,2,7,3,8}->{1,2,3,4}
A. 思路：

思路1: 快排并输出，O(nlogn)
思路2: 快排思路，将中位数退化为k分位数的问题。O(n)
思路3: 创建一个额外的容器来存储最小的k个数，总体复杂度O(nlogk)，适合海量数据:
- 如果容器未满，则直接插入容器；
- 如果容器已满，先找出这k个中最大的数字，与待插入值进行比较：如果比最大值大，则不进入容器，否则替换最大值。
- 由于每次都要选出最大值，可以使用大顶堆（如heapq）、红黑树（如STL的set）来实现容器。

# 快排思路，找到partitionIndex
def Partition(numbers, left, right):
    partition = numbers[left]
    partitionIndex = left
    while left < right:
        while right > left and numbers[right] >= partition:
            right -= 1
        numbers[left], numbers[right] = numbers[right], numbers[left]
        partitionIndex = right
        while right > left and numbers[left] <= partition:
            left += 1
        numbers[left], numbers[right] = numbers[right], numbers[left]
        partitionIndex = left

    return partitionIndex, numbers

def MinKNumbers(numbers: list, k: int):
    if numbers == None or len(numbers) <= 0 or k <= 0 or k >= len(numbers):
        return

    left = 0
    right = len(numbers) - 1
    index, numbers = Partition(numbers, left, right)
    while index != k - 1:
        if index < k - 1:
            left = index + 1
            index, numbers = Partition(numbers, left, right)
        else:
            right = index - 1
            index, numbers = Partition(numbers, left, right)

    print(numbers[:index+1])

Q. 连续子数组的最大和：输入一个整数数组，数组里有正数也有负数，数组中的一个或多个连续整数组成一个子数组，求所有子数组和的最大值，要求时间复杂度为O(n)
A. 思路：

枚举数列{1,-2,3,10,-4,7,2,-5}->{3,10,-4,7,2}=18，可以总结出规律，如果当连续数列之和小于当前数字时，则抛弃之前的连续计数，重新开始累积子数列。
动态规划：f(i) = pData[i] if i == 0 or f(i-1)≤0; f(i) = f(i-1) + pData[i] if i ≠ 0 or f(i-1)>0

def FindGreatestSumOfSubArray(numbers: list):
    if numbers == None or len(numbers) == 0:
        return

    maxSum = numbers[0]
    currentSum = numbers[0]
    for i in range(1, len(numbers)):
    	# 等效于 if currentSum <= 0:
        if currentSum + numbers[i] < numbers[i]:
            maxSum = currentSum
            currentSum = numbers[i]
        else:
            currentSum += numbers[i]
            maxSum = max(maxSum, currentSum)

    print(maxSum)

Q. 输入一个整数n，输出1～n十进制表示中1的出现次数。{12} -> {1,10,11,12}=5
A. 思路：以21345为例

将21345 分为 {1, 1345} {1346, 21345}
其中{1346, 21345}中，
- 1出现在第一位的区间为{10000, 19999}，即numFirstDigit = 10^4
- 1在区间{1346, 21345} = {1346,11345} + {11346, 21345}，在每一个区间出现在除了第一位的个数可计算为：在剩下的四个位置中，选择其中一位是1，剩下三位在[0,9]中任选，即numOtherDigit = 2·4·10^3
其中{1, 1345}可以由递归n[1:]取得

def NumberOf1(nstr: str):
    if nstr == '0':
        return 0
    if len(nstr) == 1:
        return 1

    # 在第一位出现的次数
    numFirstDigit = 0
    firstDigit = eval(nstr[0])
    if firstDigit > 1:
        numFirstDigit += 10 ** (len(nstr) - 1)
    elif firstDigit == 1:
        numFirstDigit += eval(nstr[1:]) + 1

    # 除了在第一位之外出现的次数 = 区间个数 * 能放1的位置数 * 排列组合
    numOtherDigit = firstDigit * (len(nstr) - 1) * 10 ** (len(nstr) - 2)

    # 递归求nstr[1: ]
    numRecursive = NumberOf1(nstr[1:])

    return numFirstDigit + numOtherDigit + numRecursive

Q. 数字序中某一位的数字：在01234567891011···的序列中，第0位是0(从0开始计数)，第5位是5，第13位是1，求任意第n位对应的数字
A. 思路：以811位为例

先确定其位于几位数的区间：一位数区间[0,9]有10个数字，二位数区间[10,99]有2·90=180个数字，三位数区间[100,999]有3·900=2700个数字…；
811属于[190，2890]区间，对应一个三位数
再确定其对应哪个三位数；
811/3=270，811%3=1，其对应270的第1位，即7

Q. 把数组排成最小的数：输入一个正整数数组，把数组里所有的数字拼成一个数，打印最小的那一个。{3,32,321}->321323
A. 思路：

全排列比较O(n!)
定义字符串strcmp比较规则直接qsort排序O(nlogn)

def PrintMinNumbers(numbers: list):
    if numbers == None or len(numbers) == 0:
        return

    def strcmp(n1: str, n2: str):
        if n1 == n2:
            return 0

        len1 = len(n1)
        len2 = len(n2)
        i = 0
        j = 0
        while i < len1 and j < len2:
            if n1[i] == n2[j]:
                i += 1
                j += 1
                if i == len1:
                    return 1
                if j == len2:
                    return -1
            elif n1[i] > n2[j]:
                return -1
            elif n1[i] < n2[j]:
                return 1

    strNumbers = [str(num) for num in numbers]
    strNumbers = sorted(strNumbers, key=functools.cmp_to_key(strcmp))

    print(strNumbers)

Q. 把数字翻译成字符串：给定一个数字，按规则翻译：0翻译为a，1翻译为b…，11翻译为l…，25翻译为z。一个数字可能有多种翻译，例如12258分别可以对应’bccfi’,’bwfi’,’bczi’,’mcfi’,’mzi’，计算一个数字有多少种不同的翻译方法。
A. 思路：定义f(i)表示从第i位数字开始的不同翻译的数目，f(i) = f(i+1)+g(i,i+1)·f(i+2)，其中g(i,i+1)代表[i, i+1]是否在[10,25]的区间内。从右向左翻译。

def GetTranslateCount(digit: int):
    if digit == None or digit < 0:
        return

    digit = str(digit)
    length = len(digit)
    if length == 1:
        return 1

    dp = [0 for i in range(length)]
    dp[-1] = 1
    dp[-2] = 1
    if eval(digit[-2:]) < 26:
        dp[length-2] = 2

    for i in range(length-3, -1, -1):
        flag = 0
        if eval(digit[i:i+2]) < 26:
            flag = 1
        dp[i] = dp[i+1] + flag*dp[i+2]

    print(dp[0])

Q. 在一个m·n的棋盘上每一个都放有一个礼物，每个礼物都有一定价值(>0)，从左上角开始（每次只能向右或向下移动一格）到右下角，最多能拿到多少价值的礼物。
A. 思路：动态规划 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + gift[i][j]

if gift == None or len(gift) == 0:
    return

rows = len(gift)
cols = len(gift[0])
dp = [[0 for j in range(cols)] for i in range(rows)]
dp[0][0] = gift[0][0]
dp[0][1] = dp[0][0] + gift[0][1]
dp[1][0] = dp[0][0] + gift[1][0]
for i in range(rows):
    for j in range(cols):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + gift[i][j]

print(dp[rows-1][cols-1])

Q. 在一个字符串中找出：最长不含重复字符的子字符串。{arabcacfr}->{acfr}
A. 思路：动态规划: f(i)记录不包含重复字符串的最大子串长度

如果str[i]没出现过，则f(i)=f(i-1)+1
如果str[i]出现过，记录str[i]和上一次出现在字符串中的距离d
- 如果d≤f(i-1)，即str[i]出现在f(i-1)对应的最长子串中，则f(i)=d，即[i-d,i]之间无重复字符串，更新最长子串为str[i-d-1, i-1]->str[i-d, i]
- 如果d>f(i-1)，即str[i]出现在f(i-1)对应的最长子串之前，则f(i)=f(i-1)+1

可以再单独使用一个position数组记录str[i]上次出现的位置，以替换substr.find函数。

def longestSubstringWithoutDuplication(string: str):
    if string == None or len(string) == 0:
        return

    lens = len(string)
    dp = [0 for i in range(lens)]
    dp[0] = 1
    substr = string[0]
    for i in range(1, lens):
        if substr.find(string[i]) == -1:
            substr += string[i]
            dp[i] = dp[i-1] + 1
        else:
            index = substr.find(string[i])
            substr = substr[index+1:] + string[i]
            # str[i]出现在f(i-1)对应的最长子串中, 则f(i)=d
            dp[i] = len(substr)

    print(max(dp))

Q. 丑数：只包含因子2,3,5的数字叫做丑数。求第1500个丑数（1是第一个丑数）。{6, 8}是丑数，14不是，因为包含14%7=0
A. 思路：从第一个丑数1开始，分别乘2、3、5，每次插入乘235后最小的数，然后更新235对应下标。

def GetUglyNumber(index: int):
    if index < 0:
        return

    uglyNumber = [1]
    nextIndex = 1
    index2 = index3 = index5 = 0
    while nextIndex < index:
        minNum = min(uglyNumber[index2]*2, min(uglyNumber[index3]*3, uglyNumber[index5]*5))
        uglyNumber.append(minNum)

        while uglyNumber[index2]*2 <= minNum:
            index2 += 1

        while uglyNumber[index3]*3 <= minNum:
            index3 += 1

        while uglyNumber[index5]*5 <= minNum:
            index5 += 1

        nextIndex += 1

    return uglyNumber

Q. 寻找字符串中第一个只出现一次的字符。
A. 思路：hashmap遍历<key=ch> -> <count, index>，最后筛选出count==1的最小index对应的key。

Q. 逆序对：求一个数组逆序对的总数，{7,5,6,4}->{(7,6),(7,5),(7,4),(5,4),(6,4)}
A. 思路：实质是归并排序


def mergeSort(numbers: list, left: int, right: int):
    # 逆序对在merge步骤变为倒序比较
    if left < right:
        mid = (left + right) // 2
        mergeSort(numbers, left, mid)
        mergeSort(numbers, mid + 1, right)
        merge(numbers, left, mid, right)

    return numbers

def merge(numbers: list, left: int, mid: int, right: int):
    nLeft = mid - left + 1
    nRight = right - mid

    numLeft = numbers[left: mid+1]
    numRight = numbers[mid+1: right+1]

    i, j, k = 0, 0, left
    while i < nLeft and j < nRight:
        if numLeft[i] < numRight[j]:
            numbers[k] = numLeft[i]
            i += 1
        else:
            numbers[k] = numRight[j]
            j += 1
        k += 1

    while i < nLeft:
        numbers[k] = numLeft[i]
        i += 1
        k += 1

    while j < nRight:
        numbers[k] = numRight[j]
        j += 1
        k += 1