【算法】二分查找-20231120

一、75. 颜色分类

提示
中等

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

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

思路：快速排序

def fast_sort(nums):
    if len(nums) <= 1:
        return nums
    povit = nums[0]
    left = []
    right = []
    for i in range(1, len(nums)):
        if nums[i] < povit:
            left.append(nums[i])
        else:
            right.append(nums[i])
    return fast_sort(left) + [povit] + fast_sort(right)


nums = [2, 0, 2, 1, 1, 0]
print(fast_sort(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、80. 删除有序数组中的重复项 II

中等
932
相关企业
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

def test(nums):
    slow=2
    fast=2
    while fast<len(nums):
        if nums[fast]!=nums[slow-2]:
            nums[slow]=nums[fast]
            fast+=1
            slow+=1
        else:
            fast+=1
    return slow

nums=[0,0,1,1,1,1,2,3,3]
print(test(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14

三、125. 验证回文串

简单

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：
输入: s = “A man, a plan, a canal: Panama”
输出：true
解释：“amanaplanacanalpanama” 是回文串。
示例 2：
输入：s = “race a car”
输出：false
解释：“raceacar” 不是回文串。
示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 “” 。
由于空字符串正着反着读都一样，所以是回文串。

s = "A man, a plan, a canal: Panama"
res=s.replace(' ','').replace(',','').replace(':','').lower()
print(res)
def test2(s):
    left=0
    right=len(s)-1
    while left<=right:
        if s[left]==s[right]:
            left+=1
            right-=1
        else:
            return False
    return True
s="raceacar"
print(test2(s))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

四、189. 轮转数组

提示
中等

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

解题思路
三次翻转，先整体翻转，然后根据K的位置前后局部翻转。

class Solution:
    def rotate(self,nums,k):
        k=k%len(nums)
        self.reverse(nums,0,len(nums)-1)
        self.reverse(nums,0,k-1)
        self.reverse(nums,k,len(nums)-1)

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

nums=[1,2,3,4,5,6,7]
k=3
S=Solution()
S.rotate(nums, k)
print(nums)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18