【算法】二分查找-20231121

一、344. 反转字符串

提示
简单
865
相关企业
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = [“h”,“e”,“l”,“l”,“o”]
输出：[“o”,“l”,“l”,“e”,“h”]
示例 2：

输入：s = [“H”,“a”,“n”,“n”,“a”,“h”]
输出：[“h”,“a”,“n”,“n”,“a”,“H”]

class Solution:

    def func(self,nums):
        left=0
        right=len(nums)-1
        self.reverse(nums,left,right)

    def reverse(self,nums,start,end):
        while start<end:
            nums[start],nums[end]=nums[end],nums[start]
            start+=1
            end-=1

nums=["h","e","l","l","o"]
ss=Solution()
ss.func(nums)
print(nums)

二、392. 判断子序列

简单

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = “abc”, t = “ahbgdc”
输出：true
示例 2：

输入：s = “axc”, t = “ahbgdc”
输出：false

def test4(s,t):

    j=0
    for i in t:
        if s[j]==i:
            j+=1

            if j==len(s)-1:
                return True
    return False

s="axc"
t="ahbgdc"
print(test4(s, t))

三、581. 最短无序连续子数组

中等
1.1K
相关企业
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：

输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：

输入：nums = [1,2,3,4]
输出：0
示例 3：

输入：nums = [1]
输出：0

思路：
1、我们将数据进行排序
2、然后左右指针从0和len(nums)-1开始向中间靠拢
3、找到左右第一个与原数组不相同的下标终止即可

def test5(nums):
    new_nums=sorted(nums)
    left=0
    right=len(nums)-1
    while left<len(nums):
        if nums[left]!=new_nums[left]:
            break
        left+=1

    while right>left:
        if nums[right]!=new_nums[right]:
            break
        right-=1

    return right-left+1

nums=[1]
print(test5(nums))

四、680. 验证回文串 II

简单

给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入：s = “aba”
输出：true
示例 2：

输入：s = “abca”
输出：true
解释：你可以删除字符 ‘c’ 。
示例 3：

输入：s = “abc”
输出：false

def test5(s):
    left=0
    right=len(s)-1
    while left<right:
        if s[left]==s[right]:
            left+=1
            right-=1
        else:
            return s[left:right]==s[left:right][::-1] or s[left+1:right+1]==s[left+1:right+1][::-1]

    return True

s='abca'
print(test5(s))