【算法】算法题-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 = 0right = len(nums) - 1while left <= right:mid = (right + left) // 2if nums[mid] == target:return midelif nums[mid] > target:right = mid - 1else:left = mid + 1return left

二、字符串相乘（43）

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

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

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

def test11(nums1, nums2):res = 0for 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)

三、两个相同字符之间的最长子字符串（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=-1for 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)

四、给你一个 有效括号字符串 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=0ret=0for i in strs:if i =="(":ret+=1res=max(ret,res)elif i==")":ret-=1return res
s = "(1)+((2))+(((3)))"
r=test(s)
print(r)