【算法】算法题-20231117

一、搜索插入位置（35）

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

def erfen_search_insert(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (right + left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            right = mid - 1
        else:
            left = mid + 1
    return left
1
2
3
4
5
6
7
8
9
10
11
12
13

二、字符串相乘（43）

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:
输入: num1 = “2”, num2 = “3”
输出: “6”

示例 2:
输入: num1 = “123”, num2 = “456”
输出: “56088”

def test11(nums1, nums2):
    res = 0
    for i, v in enumerate(nums1[::-1]):
        for j, u in enumerate(nums2[::-1]):
            res += int(v) * int(u) * (10 ** (i + j))
    return str(res)


res = test11('123', '456')
print(res)
1
2
3
4
5
6
7
8
9
10

三、两个相同字符之间的最长子字符串（1624）

给你一个字符串 s，请你返回 两个相同字符之间的最长子字符串的长度 ，
计算长度时不含这两个字符。如果不存在这样的子字符串，返回 -1 。

子字符串 是字符串中的一个连续字符序列。

示例 1：
输入：s = “aa”
输出：0
解释：最优的子字符串是两个 ‘a’ 之间的空子字符串。

示例 2：
输入：s = “abca”
输出：2
解释：最优的子字符串是 “bc” 。

示例 3：
输入：s = “cbzxy”
输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。

示例 4：
输入：s = “cabbac”
输出：4
解释：最优的子字符串是 “abba” ，其他的非最优解包括 “bb” 和 “” 。

思路：
遍历所有的字符
当这个字符在字符串中出现两次时，计算第一个索引和最后一个索引中间的子字符串的数量

def max_value(strs):
    n=-1
    for i in set(strs):
        if strs.count(i)>1:
            n=max(n,strs.rfind(i)-strs.find(i)-1)
    return n
s = "cabbac"
r=max_value(s)
print(r)
1
2
3
4
5
6
7
8
9

四、给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度

例如：“”、“()()”、“()(()())” 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 “)(” 、“(()” 都不是 有效括号字符串 。
给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度

示例 1：
输入：s = “(1+(2*3)+((8)/4))+1”
输出：3
解释：数字 8 在嵌套的 3 层括号中。
示例 2：
输入：s = “(1)+((2))+(((3)))”
输出：3

思路：
python 栈思想
核心思路其实就是统计最大的连续左括号的数量。
遍历整个字符串，遇到左括号，总数+1，遇到右括号总数-1。
实时更新最大连续左括号的数量。

def test(strs):
    res=0
    ret=0
    for i in strs:
        if i =="(":
            ret+=1
            res=max(ret,res)
        elif i==")":
            ret-=1
    return res
s = "(1)+((2))+(((3)))"
r=test(s)
print(r)
1
2
3
4
5
6
7
8
9
10
11
12
13