1. 顺序查找：O(N) O(1)

from typing import List
def seq_search(nums:List[int],n):
    for i,v in nums:
        if n == v:
            return i
    return -1

2. 二分查找一维数组

def b_search(nums:List[int],X):
    def binarySearch(arr, l, r, x):
        if l <= r:
            mid = (l + r) // 2
            if(arr[mid] < x):
                return binarySearch(arr, mid+1, r, x)
            elif arr[mid] > x: 
                return binarySearch(arr, l, mid-1, x)
            else: 
                return mid 
        else:
            return -1
    return binarySearch(nums,0,len(nums)-1,X)
# 测试代码
arr = [1,5,8,9]
X = 8
print(b_search(arr,X))

3. 二分查找二维数组

from typing import List
class Solution:
    # 二分查找
    def binarySearch2D(self, nums: List[List[int]], target: int) -> bool:
        if not nums or len(nums) == 0 or not nums[0] or len(nums[0]) == 0:
            return False
        m, n = len(nums), len(nums[0])
        i, j = 0, n - 1
        while (i < m and j >= 0):
            if target < nums[i][j]:
                j -= 1
            elif target > nums[i][j]:
                i += 1
            else:
                return True
        return False

4. 找出只出现一次的元素

from functools import reduce
from typing import List
import random

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)
#测试代码
lst = [i for i in range(101)]
lst.extend(lst);lst.remove(20);random.shuffle(lst)
print(Solution().singleNumber(lst))

5. 找出重复出现的元素

from typing import List
import random
class Solution:
    # 1.异或法:O(N) O(1) 需要前提条件 
    # 异或法控制了空间复杂度O(1)
    # 1-100的数，放在101位数组中，多出的一位是重复元素，找出该元素。A^A^B = B
    # 此方法全部计算后才能得到结果，而其他方法可以在中途找到直接return
    # 重要条件:因为所有的B都必须异或一次，所以要求1-100的数字都必须出现
    def findRepeatNumber(self,nums: List[int]) -> int:
        tmp = nums[0]
        for i in enumerate(nums[1:]):
            tmp ^= (i[0] ^ i[1])
        return tmp

    # 2.下标定位之元素交换法:O(N)O(1) 
    # 数组元素交换控制了空间复杂度O(1)
    # 但是也导致了前提条件：数组中元素的最大值必须小于数组的长度。(MAX<=len-1)
    # 特别说明(因为用了原地):元素值必须小于列表长
    def findRepeatNumber2(self, nums: List[int]) -> int:
        for i,v in enumerate(nums):
            if v != i:
                if nums[v] == v:
                    return v
                nums[v] , nums[i] = v , nums[v]
        return -1
    # 3.哈希表中介法:O(N)O(N) 
    def findRepeatNumber3(self,nums:List[int]) -> int:
        _dict = {}
        for v in nums:
            if v in _dict:
                return v
            _dict[v] = ''
        return -1
    # 4.排序判断法:O(NlogN)O(1) 
    def findRepeatNumber4(self, nums):
        nums.sort()
        pre = nums[0]
        for index in range(1, len(nums)):
            if pre == nums[index]:
                return pre
            pre = nums[index]

# 测试代码
lst = [i for i in range(101)]
lst.append(10);random.shuffle(lst)
print(Solution().findRepeatNumber(lst))
print(Solution().findRepeatNumber2(lst))
print(Solution().findRepeatNumber3(lst))
print(Solution().findRepeatNumber4(lst))

6. 有序数组中最小数

from typing import List
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left, right = 0, len(numbers) - 1
        while left < right:
           mid = left + (right-left) // 2
           if numbers[mid] > numbers[right]:
               left = mid + 1
           elif numbers[mid] < numbers[right]:
               right = mid
           else:
               right -= 1
        return numbers[left]

print(Solution().minArray([23,40,90,12]))

7. 相邻元素之后最大(最小)的元素序号

import sys
import random
from typing import List

def search_near_diff(nums:List[tuple]):
    pre, max_diff, max_idx= nums[0][1], 0, 0 # 最大
    # pre, max_diff, max_idx= nums[0][1],sys.maxsize , 0 # 最小
    for idx,_ in enumerate(nums[1:]):
        tmp = abs(_[1] - pre)
        if max_diff < tmp:
        # if max_diff > tmp: # 最小
            max_diff, max_idx = tmp, idx
        pre = _[1]
    return nums[max_idx][0],nums[max_idx+1][0]
# 测试代码
NUM, MAX = 5, 100
lands = [(i,random.randint(0,MAX)) for i in range(1,NUM+1)]
print(lands)
print(search_near_max_diff(lands))

8. 最长公共前缀

from typing import List
def longestCommonPrefix(strs: List[str]) -> str:
    ans = ''
    for i in zip(*strs):
        # 去重后等于1，说明三个列字符一样
        if len(set(i)) == 1:
            ans += i[0]
        else:
            break
    return ans
cmn = longestCommonPrefix(['ab', 'abc', 'abcd'])
print(cmn)

9. 两数之和(数组中两元素和为某数的所有组合)

from typing import List
class Solttion:
    # O(N) 哈希键存储
    def sum(self, nums: List[int], target: int) -> List[int]:
        hash = {}
        for i, num in enumerate(nums):
            if target - num in hash:
                return (hash[target - num], i)
            hash[nums[i]] = i
        return ()
    # 暴力 O(NN) 
    def sum2(self, nums: List[int], target: int) -> List[int]:
        for _,i in enumerate(nums):
            for __,j in enumerate(nums[_:]):
                if i+j == target:
                    return _,_+__
# O(N)
print(Solttion().sum([1,5,6,8],9))
# O(n*n)
print(Solttion().sum2([1,5,6,8],9))

10. 3数/N数之和(数组中N个元素和为某数的所有组合)

from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 解决nSum问题
        if len(nums) <= 2:
            return []
        nums.sort()
        return self.nSum(nums, 3, 0)

    def nSum(self, nums, n, target):
        """注意，此函数的nums应是排序后的数组，否则每层递归都要对nums排序，效率极低"""
        if len(nums) < n:
            return []
        res = []

        # twoSum
        if n == 2:
            left, right = 0, len(nums)-1
            while left < right:
                if nums[left] + nums[right] == target:
                    res.append([nums[left], nums[right]])
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif nums[left] + nums[right] > target:
                    right -= 1
                else:
                    left += 1
            return res
        else:
            for first_idx in range(len(nums)):
                if first_idx > 0 and nums[first_idx] == nums[first_idx-1]:
                    continue
                subres = self.nSum(nums[first_idx+1:], n-1, target-nums[first_idx])
                for i in range(len(subres)):
                    res.append([nums[first_idx]]+subres[i])
            return res

    def threeSum2(self, nums: List[int]) -> List[List[int]]:
        """三数之和，暴力列举的话，时间复杂度为O(n^3)，该解法为O(n^2)"""
        # 因为是计算三数之和，因此输入数组的长度必须大于等于3，否则返回[]
        # 因此首先进行长度判断
        n = len(nums)
        if n < 3: return []
        # 特况判定后，对输入数组进行快排，直接使用sort()
        # 为之后的有序查找奠定基础
        nums.sort()
        res = []
        # 因为最后我们需要得到索引，因此按照索引遍历数组
        for i in range(n):
            # 因为需要找到三数之和为0，又因为数组有序，我们设计的双指针都在i的右侧，即大于nums[i]
            # 所以一旦nums[i]>0则之后不需要再进行判断，直接返回结果即可
            if nums[i] > 0: return res
            # 因为题目要求，不需要重复答案，因此如果nums[i]与之前相同则跳过
            # 这里注意不能从第一个开始跳过的，因为[0, 0, 0]都跳过变成[]
            if(i>0 and nums[i]==nums[i-1]):
                continue
            # 好，这些特殊情况处理之后，我们定义双指针
            # left从当前索引的下一个索引开始
            L = i+1
            # right从最后一个索引开始
            R = n-1
            # 双指针结束条件为L<R
            while L < R:
                # 如果双指针对应的值加上当前遍历值和为0，则满足条件
                if nums[i] + nums[L] + nums[R] == 0:
                    # 将结果装入res中
                    res.append([nums[i], nums[L], nums[R]])
                    # 一旦出现匹配结果，仍然要保证结果不重复，
                    # 也就是左右指针的下一个值如果和上一个相同需要一直移动
                    # 而且要控制移动后L<R
                    # L指针向右，R指针向左
                    while(L<R and nums[L]==nums[L+1]):
                        L += 1
                    while(L<R and nums[R]==nums[R-1]):
                        R -= 1
                    # 当然如果并没有重复，那么指针就按照正常情况进行移动
                    L += 1
                    R -= 1
                # 如果我们发现三数之和大于0，因为数组有序，只需移动R指针即可
                elif (nums[i]+nums[L]+nums[R] > 0):
                    R -= 1
                # 否则移动左指针
                else:
                    L += 1
        return res
# UT
lst = [-1,0,1,2,-1,-4,8,-6,-2]
lst.sort()
print(Solution().nSum(lst,4,0))

11. 组合总数(列表中元素和为某数的所有组合)

from typing import List

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates = sorted(candidates)
        ans = []
        def find(s, use, remain):
            for i in range(s, len(candidates)):
                c = candidates[i]
                if c == remain:
                    ans.append(use + [c])
                if c < remain:
                    find(i, use + [c], remain - c)
                if c > remain:
                    return
        find(0, [], target)
        return ans

    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        dp = [[] for _ in range(target+1)]
        for i in sorted(candidates,reverse=True):
            for j in range(i,target+1):
                if j==i:dp[j] = [[i]];continue
                dp[j].extend([x+[i] for x in dp[j-i]])
                # print(dp)
        return dp[-1]

    def combinationSum3(self, candidates: List[int], target: int) -> List[List[int]]:
        dict = {}
        for i in range(1,target+1):
            dict[i]=[]

        for i in range(1,target+1):
            for j in candidates:
                if i==j:
                    dict[i].append([i])
                elif i>j:
                    for k in dict[i-j]:
                        x = k[:]
                        x.append(j)
                        x.sort() # 升序，便于后续去重
                        if x not in dict[i]:
                            dict[i].append(x)

        return dict[target]
# 测试代码
print(len(Solution().combinationSum([1,2,3,4],5)))
print(len(Solution().combinationSum2([1,2,3,4],5)))
print(len(Solution().combinationSum3([1,2,3,4],5)))

12. 查找TOP-K

from typing import List
import random


# 交换列表索引元素 复杂度O(N)
def swap(arr, a, b):
    arr[a], arr[b] = arr[b], arr[a]
    return arr

def findKLargest(arr: List[int], k: int) -> int:
    l = len(arr)
    target = l - k  # K大索引
    # 遍历区间:left、right
    left = 0
    right = l - 1
    while True:
        index = __partition(arr, left, right)
        if index == target:
            return arr[index]
        elif index < target:
            # 下一轮在 [index + 1, right] 里找
            left = index + 1
        else:
            # 下一轮在 [left,index - 1] 里找
            right = index - 1

def __partition(nums, left, right):
    # randint 是包括左右区间的
    random_index = random.randint(left, right)
    nums[random_index], nums[left] = nums[left], nums[random_index]

    pivot = nums[left]  # 中心点位置

    lt = left + 1
    rt = right

    while True:
        while lt <= rt and nums[lt] < pivot:
            lt += 1
        while lt <= rt and nums[rt] > pivot:
            rt -= 1

        if lt > rt:
            break
        swap(nums, lt, rt)
        lt += 1
        rt -= 1
    swap(nums, left, rt)
    return rt

# UT
print(findKLargest([1, 5, 7, 8, 3, 9], 4))

13. 字符串蕴含（包含）

def searchHas(input, target) -> list:
    res = []
    i = 0
    while i <= len(input) - len(target):
        j = 0
        while j < len(target):
            # print(j,input[i + j],target[j])
            if input[i + j] == target[j]:
                # print(j,target[j])
                if j == len(target) - 1:
                    res.append(i)
                j += 1
            else:
                break
        i += 1
    return res
# UT
print(search('helloworld', 'llo'))

14. 约瑟夫问题：间隔出列

# 长度n，间隔k，起始start
def josephus(n,k,start:int = 1):
    lista = list(range(1, n+1))
    i = start - 1
    for number in range(n, 0, -1):
        i = (i+k-1) % number
        person = lista.pop(i)
        yield person
# UT
result = [x for x in josephus(5,3)]
res = josephus(5,3)
result = [next(res) for _ in range(5)]
print(result)

15. 最大子序和

from typing import List
#子序：当前数和前一个数的和
def maxSubArray(nums: List[int]) -> int:
    for i in range(1, len(nums)):
        nums[i] = max(nums[i - 1] + nums[i], nums[i])
    return max(nums)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums)) # 6:[-2, 1, -2, 4, 3, 5, 6, 1, 5]