Q:无序列表，如何去重

ids=[1,2,3,4,3,2,5] 
new_ids=list(set(ids)) 
print(new_ids)

Q:字符串转为数字，比如 str="1234"，变成 int 1234，并测试这个程序。

def stoi(sr):
    current = 0
    for i in sr:
        sum = ord(i) - ord('0')
        current = current * 10 + sum
    return current

assert type(stoi('1234')) == int
assert stoi('1234') == 1234

Q:99乘法表

for i in range(1, 10):
    for j in range(1, i+1):
        print('{}x{}={}\t'.format(j, i, i*j), end='')
    print()

Q:实现阶乘函数

def factorial(num):
    if num <=1:
        return 1
    else:
        return num*factorial(num-1)

Q:算出 100-1000 的质数

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数.

data = []
for i in range(100, 1000):
    for j in range(2, i):
        if i % j == 0:
            break
    else:
        data.append(i)

Q:字符串反转，如果字符串有多个空格也需要处理

ss = 'SJD EJJF EJEF'
ss = re.sub(r'\s', '', ss)
print(ss[::-1])

ss = 'SJD EJJF EJEF'
ss = re.sub(r'\s', '', ss)
a = ''.join(reversed(ss))
print(a)

def rev(str):
    l = list(str)
    newstr = ""
    while len(l) > 0:
        newstr += l.pop()
    return newstr

Q: 找出第一个非重复字符在字符串中的位置

举例：‘Google’返回l,4

def first_char(string):
    dict1 = {}
    for i in string:
        # 累计字符的出现次数
        if i in dict1:
            dict1[i] += 1
        # 只出现一次，key对应的value就记1次
        else:
            dict1[i] = 1
    for i in range(len(string)):
        if dict1[string[i]] == 1:
            return string[i], i

Q:实现斐波那契数列(⽣成器方式)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1)+fib(n-2)
for i in range(1, 20):
    print(fib(i), end=',')

Q:字符串中找出连续最长的数字串。

import re
print(max(re.findall(r"\d*", input()), key=len))

def longest_continuous_digits(input_str):
    max_digit = ''
    current_digit = ''
    
    for char in input_str:
        if char.isdigit():
            current_digit += char
        else:
            if len(current_digit) > len(max_digit):
                max_digit = current_digit
            current_digit = ''

    # 检查最后一个数字串
    if len(current_digit) > len(max_digit):
        max_digit = current_digit

    if max_digit:
        return max_digit
    else:
        return "没有找到数字串"

Q:leetcode-409. 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

def cront(s):
  count = collections.Counter(s).values()
  x = sum([item//2*2 for item in count if(item//2>0)])
  return x if x==len(s)else x+1

Q:[-1,1,1,-2,3,-5,-6]⽤最少的时间、空间，将负数放在左边、正数放右边。

def sort_li(li):
    i = 0
    j = len(li) - 1
    while i <= j:
        if li[i] < 0:
            i += 1
        elif li[j] > 0:
            j -= 1
        else:
            li[i], li[j] = li[j], li[i]
    return li

Q: lintcode-144. 交错正负数

给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。
解题思路：先将负数放在左边，正数放在右边，然后隔一个数进行交换。（需考虑负数多，正数多和正负数一样多的情况）

def rerange(a):
    if a is None or len(a) == 0:
        return a
    start, end = 0, len(a)-1
    while start < end:
        if a[end] > 0:
            end -= 1
        elif a[start] < 0:
            start += 1
        else:
            a[start], a[end] = a[end], a[start]
    # 计算负数的个数
    if a[start] < 0:
        start += 1
    # 负数更少，两边应是正数
    if start < len(a)-start:
        start, end = 0, len(a)-2
    # 正数更少，两边应是负数
    elif start > len(a)-start:
        start, end = 1, len(a)-1
    # 正数负数相同
    else:
        start, end = 0, len(a)-1

    while start < end:
        if a[start] > 0 or a[end] < 0:
            break
        a[start], a[end] = a[end], a[start]
        start += 2
        end -= 2

    return a

Q:字符串中最小的整数

class Solution(object):
    def FindMaxinStr(self, s):
        if not s:
            return 0
        result = []
        current = 0
        for c in s:
            num = ord(c) - ord('0')
            if 0 <= num <= 9:
                current = current*10+num
                result.append(current)
            else:
                current = 0
        return min(result)

Q: 剑指 Offer 50. 第一个只出现一次的字符

在字符串s中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

def first(s: str):
    dic = {}
    for c in s:
        dic[c] = c not in dic
    for c in s:
        if dic[c]:
            return c
    return ''

Q:输⼊一个字符串然后去掉空格，在统计每个字⺟出现的次数

from collections import Counter
a = a.replace(' ', '')
b = Counter(a)

def str_count(a):
    a = a.replace(' ', '')
    b = {}
    i = 0
    while i < len(a):
        if a[i] in b:
            b[a[i]] += 1
        else:
            b[a[i]] = 1
        i += 1
    return b

Q：leetcode-88.合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

    n1 = len(nums1)
    n2 = len(nums2)
    k = n1 + n2 - 1
    i = n1 - 1
    j = n2 - 1
    for i in range(n2):
        nums1.append(0)
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    return nums1

Q:leetcode-704. 二分法查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            pivot = left + (right - left) // 2
            if nums[pivot] == target:
                return pivot
            if target < nums[pivot]:
                right = pivot - 1
            else:
                left = pivot + 1
        return -1

Q:leetcode-20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

def isvalid(self, s):
    stack = []
    mapping = {")": "(", "}": "{", "]": "["}
    for char in s:
        if char in mapping:
            top_element = stack.pop() if stack else '#'
            if mapping[char] != top_element:
                return False
        else:
            stack.append(char)
    return not stack

Q: 剑指Offer-40. 最小的k个数

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

def getLeastNumbers(arr: List[int], k: int):
    arr.sort()
    return arr[:k]

时间复杂度：O(n log n),其中 nn 是数组 arr 的长度.算法的时间复杂度即排序的时间复杂度。
空间复杂度：O(log n),排序所需额外的空间复杂度为O(logn)

def getLeastNumbers1(arr:List[int], k: int):
    if k == 0:
        return list()
    hp = [-x for x in arr[:k]]
    heapq.heapify(hp)
    for i in range(k,len(arr)):
        if -hp[0]>arr[i]:
            heapq.heappop(hp)
            heapq.heappush(hp, -arr[i])
    ans = [-x for x in hp]
    return ans

时间复杂度：O(nlogk)，其中 nn 是数组 arr 的长度。由于大根堆实时维护前 k小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
空间复杂度：O(k)，因为大根堆里最多 k个数。

Q: leetcode-347. 前 K 个高频元素

class Solution:
    def top(self,nums,k):
        lookup = Counter(nums)
        return [item[0] for item in lookup.most_common(k)]

def topKFrequent(nums, k):
    """
    给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
    :param nums:
    :param k:
    :return:
    """
    n = len(nums)
    dic = {}
    for i in range(n):
        if nums[i] not in dic:
            dic[nums[i]] = 1
        else:
            dic[nums[i]] += 1

    res = []
    while k > 0:
        tmp = 0
        for num in dic:
            if dic[num] > tmp:
                tmp = dic[num]
                cur = num
        dic[cur] = -1
        res.append(cur)
        k -= 1
    return res

Q:leetcode-560.和为K的子数组

class Solution:
    def subarraySum(self, nums, k: int):
        # num_times 存储某“前缀和”出现的次数，这里用collections.defaultdict来定义它
        # 如果某前缀不在此字典中，那么它对应的次数为0
        num_times = collections.defaultdict(int)
        num_times[0] = 1  # 先给定一个初始值，代表前缀和为0的出现了一次
        cur_sum = 0  # 记录到当前位置的前缀和
        res = 0
        for i in range(len(nums)):
            cur_sum += nums[i]  # 计算当前前缀和
            if cur_sum - k in num_times:  # 如果前缀和减去目标值k所得到的值在字典中出现，即当前位置前缀和减去之前某一位的前缀和等于目标值
                res += num_times[cur_sum - k]
            # 下面一句实际上对应两种情况，一种是某cur_sum之前出现过（直接在原来出现的次数上+1即可），
            # 另一种是某cur_sum没出现过（理论上应该设为1，但是因为此处用defaultdict存储，如果cur_sum这个key不存在将返回默认的int，也就是0）
            # 返回0加上1和直接将其置为1是一样的效果。所以这里统一用一句话包含上述两种情况
            num_times[cur_sum] += 1
        return res

Q:leetcode-434. 字符串中的单词数

class Solution:
    def countSegments(self, s):
        return len(s.split())

Q:字母统计并排序, 其中单词用空格分隔，统计出现最多的3个单词和它们出现的次数

def func(data):
    # 按空格对字符串进行切割
    data = data.split(' ')
    list_most=collections.Counter(data).most_common(3)
    print(list_most)

Q:快排

def quick_sort(li,start,end):
    if start >= end:
        return
    left = start
    right = end
    mid = li[left]
    while left < right:
        while left < right and li[right] >= mid:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] < mid:
            left += 1
        li[right] = li[left]
    li[left] = mid
    quick_sort(li, start, left-1)
    quick_sort(li, left+1, end)

Q:冒泡排序

def bubble_sort(arr):
    length = len(arr)
    while length > 0:
        for i in range(length-1):
            if arr[i] > arr[i+1]:
                current = arr[i]
                arr[i] = arr[i+1]
                arr[i + 1] = current
        length -= 1