1. 合并有序数组

from typing import List
# 方法一 时间复杂度O(m+k),空间复杂度O(k)
def merge_list(lst1:List[int],lst2:[int]):
    l1, l2 = len(lst1), len(lst2)
    lst1 += l2 * [0] # 控制空间复杂度到k=len(lst2)
    l1,l2,cur = l1 - 1, l2 - 1,l1 + l2 - 1
    while cur >= 0 and l2 >= 0:
        if lst1[l1] > lst2[l2]:
            lst1[cur] = lst1[l1]
            l1 -= 1
        else:
            lst1[cur] = lst2[l2]
            l2 -= 1
        cur -= 1
    lst1[:l2+1] = lst2[0:l2+1]
    return lst1

# 方法二 O(NlogN) 空间复杂度O(k) k=len(lst2)
def merge_list2(lst1:List[int],lst2:List[int]):
    lst1.extend(lst2)
    lst1.sort()
    return lst1

print(merge_list([1,3,11],[2,12,15,18]))

2. 替换空格

class Solution:
    def replaceSpace(self, s: str) -> str:
        l = len(s)
        nums = s.count(' ')
        n_l = l + (nums << 1)#%20 替换原位置外，还需要加两倍的替换空间
        arr = [''] * n_l
        i = 0
        for char in s:
            if char == " ":
                arr[i] = '%'
                arr[i + 1] = '2'
                arr[i + 2] = '0'
                i += 3
            else:
                arr[i] = char
                i += 1
                print(char)
        return ''.join(arr)
# 测试代码
print(Solution().replaceSpace('hello wor ld !'))

3. 两个数组相对排序

from typing import List
class Solution:
    # 方法一 sort(key)
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:        
        ranks = {x: i for i, x in enumerate(arr2)}
        arr1.sort(key=lambda x:(0,ranks[x]) if x in ranks else (1,x))
        return arr1
    # 方法二 计数排序法
    def relativeSortArray2(self,arr1: List[int], arr2: List[int]) -> List[int]:
        upper = max(arr1)
        frequency = [0] * (upper + 1)
        for x in arr1:
            frequency[x] += 1

        ans = list()
        for x in arr2:
            ans.extend([x] * frequency[x])
            frequency[x] = 0
        for x in range(upper + 1):
            if frequency[x] > 0:
                ans.extend([x] * frequency[x])
        return ans
# 通过sort()参数指定键排序
arr1,arr2 = [2,3,1,3,2,4,6,7,9,2,20,19,5,1],[2,4,3,6]
print(Solution().relativeSortArray(arr1,arr2))

4. Z字变换

# 将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列
# 输入：s = "PAYPALISHIRING", numRows = 3
# 输出："PAHNAPLSIIGYIR"
# 输入：s = "PAYPALISHIRING", numRows = 4
# 输出："PINALSIGYAHRPI"
# 以 V 字型为一个循环, 循环周期为 n = (2 * numRows - 2)
# 索引值i：计算 x = i % n , 行号y = min(x, n - x)
class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1: return s
        rows = [""] * numRows
        n = 2 * numRows - 2
        for i, char in enumerate(s):
            x = i % n
            rows[min(x, n - x)] += char
        return "".join(rows)
# 测试代码
print(Solution().convert('PAYPALISHIRING',4))

5. 移除K位数后的最小数字

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        n = len(num) - k
        for digit in num:
            while k and stack and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        res = ''.join(stack[:n]).lstrip('0')
        return res or '0'
#UT
print(Solution().removeKdigits('1432219',3))

6. 顺时针打印矩阵（剥洋葱打印）

from typing import List
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(Solution().spiralOrder(matrix))

7. 杨辉三角

from typing import List
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ret = []
        for i in range(1, numRows + 1):
            tmp = [1 for _ in range(i)]
            for j in range(1, len(tmp) - 1):
                # i - 2
                tmp[j] = ret[i - 2][j - 1] + ret[i - 2][j]
            ret.append(tmp)
        return ret
# UT
print(Solution().generate(5))

8. 整数反转

class Solution:
    def reverse(self, x: int) -> int:
        # 特殊情况0
        if x == 0: return 0
        # 边界判断，既要判断输入还要判断输出
        def _f(x):
            if 2**31 < x + 1 or x < -(2**31) or x == 0:
                return 0
            else:
                return 1

        def _reverse(x):
            return str(x).strip("0")[::-1]
        if x > 0:
            k = int(_reverse(x))
        else:
            k = -int(_reverse(-x))
        if _f(k):
            return k
        else:
            return 0
# UT
print(Solution().reverse(-123))

9. 回文数验证

class Solution:
    # 方法一：转字符串
    def isPalindrome(self, s: int) -> bool:
        return False if x < 0 else (x == int(str(x)[::-1]))
        # s = str(x)
        # l = len(s)
        # h = l//2
        # return s[:h] == s[-1:-h-1:-1] # 省一半空间
    # 方法二
    def isPalindrome2(self, x: int) -> bool:
        if x<0 or (x%10==0 and x!=0):
            return False
        elif x == 0:
            return True
        ans = 0
        # 只需判断一半长度
        while x>ans:
            ans = ans*10 + x%10 # 答案*10+新末尾数
            x //= 10 # 新末尾数 = 原数字的最后一位
        return x==ans or x==(ans//10)
# UT
print(Solution().isPalindrome2(101))

10. 回文串验证（忽略标点/空格符）

class Solution:
    # 筛选判断：O(N) O(N)
    def isPalindrome(self, s: str) -> bool:
        sgood = "".join(ch.lower() for ch in s if ch.isalnum())
        return sgood == sgood[::-1]
    # 双指针原地判断：O(N) O(1)
    def isPalindrome2(self, s: str) -> bool:
        n = len(s)
        left, right = 0, n - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if left < right:
                if s[left].lower() != s[right].lower():
                    return False
                left, right = left + 1, right - 1

        return True

11. 回文串排列（是否存在）

# 位元算
a, b = 1<<2, 1<<4
c = a ^ b # c必然不是2的N次方
print(a&a-1,b&b-1,c&c-1) # 判断是否是2的N次方
# 是否存在回文排列（思路和是否存在单独的奇数次一样）
class Solution:
    # 方法一：异或（思路：2的N次方）
    def canPlalindrome(self, s: str) -> bool:
        n = 0
        for i in s:
            n ^= 1<<ord(i) # 2的i次方
        # 如果存在多个异或未抵消的数,1<<ord(A) ^ 1<<ord)(B)肯定不是2的n次方
        return n & n - 1 == 0 # 二进制判断是否是2的n次方(n & n - 1)
    # 方法二：Counter（奇数次数数量<=1）
    def canPlalindrome2(self, s: str) -> bool:
        import collections
        return sum(1 for k, v in collections.Counter(s).items() if v % 2 != 0) <= 1
    # 方法三：Set（与方法二一样）
    def canPlalindrome3(self, s: str) -> bool:
        my_set = set()
        for ch in s:
            if ch in my_set:
                my_set.remove(ch)
            else:
                my_set.add(ch)
        return len(my_set) <= 1
# UT
print(Solution().canPlalindrome2('aba'))

12. 有效括号

def isValid(s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        dic = {")": "(","]": "[","}": "{"}
        stack = []
        for i in s:
            if stack and i in dic: # 如果栈不空，且i为有效右括号
                if stack[-1] == dic[i]: # 如果栈顶为对应的左括号，则弹出
                    stack.pop()
                else:
                    return False # 如果栈顶不是对应的左括号，则不匹配
            else:
                stack.append(i) # 如果i为左括号（非右括号都会），入栈
        return not stack

def isValid2(s: str) -> bool:
    arr = ['{}', '[]', '()']
    l = len(s) // 2
    print(l)
    i = 0
    while i < l:
        s = s.replace(arr[0], '').replace(arr[1], '').replace(arr[2], '')
        i += 1
    return len(s) == 0
# UT
s = '({()[]})'
print(isValid(s))

13. 罗马数字转整数

def roman2int(s: str) -> int:
    dic = {'I': 1, 'IV': 4, 'V': 5, 'IX': 9, 'X': 10, 'XL': 40, 'L': 50,
           'XC': 90, 'C': 100, 'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}
    su = []
    i = 0
    while i < len(s):
        v = s[i:i+2]
        if v in dic:
            su.append(dic[v])
            i += 2
        else:
            su.append(dic[s[i]])
            i += 1
    return sum(su)
# UT
print(roman2int('MCMXC'))

14. 删除有序列表中重复元素后的新列表长度

from typing import List
def removeDuplicates(nums: List[int]) -> int:
    if not nums:
        return 0
    i = 0
    for j in range(1, len(nums)):
        if nums[i] != nums[j]:
            i += 1
            nums[i] = nums[j]
    return i + 1

a = [0,1,1,2,3,3,4]
print(removeDuplicates(a))

15. 列表中移除某元素

from typing import List

def removeElement(nums: List[int], val: int):
    # 倒序遍历，避免pop()后取值索引-1导致的取值问题
    for i in range(len(nums) - 1, -1, -1):
        if nums[i] == val:
            nums.pop(i)
    return len(nums)
# UT
nums, val = [3, 2, 2, 3, 5, 7], 3
print(removeElement(nums, val))

16. 矩阵转置

from typing import List

class Solution:
    def transpose(self, arr: List[List[int]]) -> List[List[int]]:
        return [(i) for i in zip(*arr)]

arr = [[1, 2, 3], [4, 5, 6]]
print(Solution().transpose(arr)) # [(1, 4), (2, 5), (3, 6)]