手撸

• 排序链表 148
• 数组 topK 215
• 判断两个链表是否相交。
• 求一个数列中两个元素的最大和，找到这个两个元素。（Top K 问题）

简单计算器

描述

用户输入一个类似这样 3*( 4+ 50 )-(( 100 + 40 )5/2- 32* 2/4+9)((( 3 + 4)-4)-4) 这样的表达式，假设表达式里面除了包含空格、’+’、’-‘、’‘、’/‘和括号再无其他特殊符号，然后自己动手写代码解析其中的表达式，实现加减乘除，最后得出的结果与真实的计算机所算的结果必须一致。

代码

# -*- coding:utf-8 -*-
"""
    @Time  : 2021/10/13  14:22
    @Author: Feng Lepeng
    @File  : test.py
    @Desc  :
"""
import re


def multiply_divide(s):
    # 计算一个不含括号的最小乘除单元，用split分隔*或/然后计算
    ret = float(s.split('*')[0]) * float(s.split('*')[1]) if '*' in s else float(s.split('/')[0]) / float(
        s.split('/')[1])
    return ret


def remove_md(s):
    if '*' not in s and '/' not in s:
        return s                        # 没有乘除的话递归结束
    else:                               # 匹配一个最小乘除单元，调用multiply_divide计算，将结果拼接成一个新的表达式进行递归处理
        k = re.search(r'-?[\d\.]+[*/]-?[\d\.]+', s).group()
        # ret = multiply_divide(k)
        # r = '+' + str(ret) if len(re.findall(r'-', k)) == 2 else str(ret)
        # s = s.replace(k, r)
        s = s.replace(k, '+' + str(multiply_divide(k))) if len(re.findall(r'-', k)) == 2 else s.replace(k, str(
            multiply_divide(k)))
        return remove_md(s)


def add_sub(s):
    l = re.findall('([\d\.]+|-|\+)', s) # 将表达式转换成列表，
    if l[0] == '-':                     # 如果第一个数是负数，对其进行处理
        l[0] = l[0] + l[1]
        del l[1]

    sum = float(l[0])
    print(l)
    for i in range(1, len(l), 2):          # 循环计算结果
        if l[i] == '+' and l[i + 1] != '-':
            sum += float(l[i + 1])
        elif l[i] == '+' and l[i + 1] == '-':
            sum -= float(l[i + 2])
        elif l[i] == '-' and l[i + 1] == '-':
            sum += float(l[i + 2])
        elif l[i] == '-' and l[i + 1] != '-':
            sum -= float(l[i + 1])
    return sum


def basic_operation(s):                 # 计算一个基本的4则运算
    s = s.replace(' ', '')
    return add_sub(remove_md(s))        # 调用前面定义的函数，先乘除，后加减


def calculate(expression):
    if not re.search(r'\([^()]+\)', expression):  # 匹配最里面的括号，如果没有的话，直接进行运算，得出结果
        return basic_operation(expression)
    k = re.search(r'\([^()]+\)', expression).group()  # 将匹配到的括号里面的表达式交给basic_operation处理后重新拼接成字符串递归处理
    expression = expression.replace(k, str(basic_operation(k[1:len(k) - 1])))
    return calculate(expression)


if __name__ == '__main__':
    s = '1 - 2 * ( (60-30 +(-40/5) * (9-2*5/3 + 7 /3*99/4*2998 +10 * 568/14 )) - (-4*3)/ (16-3*2) )'
    print(calculate(s))

判断一个点是否在给定五角星内部

思路

判断一个散点是否在多边形内部的主要依据有如下几点：

1、过散点做X轴平行线，与多边形相交。

2、左边交点数为基数，在内部，偶数在外面

3、散点在多边形上的情况 算成内部

手撕NMS

二分查找

用Python实现一个二分查找的函数。

二分查找算法：简单的说，就是将一个列表先排序好，比如按照从小到大的顺序排列好，当给定一个数据，比如3，查找3在列表中的位置时，可以先找到列表中间的数li[middle]和3进行比较，当它比3小时，那么3一定是在列表的右边，反之，则3在列表的左边，比如它比3小，则下次就可以只比较[middle+1, end]的数，继续使用二分法，将它一分为二，直到找到3这个数返回或者列表全部遍历完成（3不在列表中）

优点：效率高，时间复杂度为O(logN)；
缺点：数据要是有序的，顺序存储。

li = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 
def search(someone, li):
    l = -1
    h = len(li)
 
    while l + 1 != h:
        m = int((l + h) / 2)
        if li[m] < someone:
            l = m
        else:
            h = m
    p = h
    if p >= len(li) or li[p] != someone:
        print("元素不存在")
    else:
        str = "元素索引为%d" % p
        print(str)
 
 
search(3, li)  # 元素索引为2