数据结构与算法解题-20240421

---

一、278. 第一个错误的版本

简单
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：
输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：
输入：n = 1, bad = 1
输出：1

class S278:
    def func(self, n):
        start = 1
        end = n
        while start <= end:
            mid = (start + end) // 2
            if isBadVersion(mid):
                # todo 若 mid是错误版本，则最后一个正确版本一定在闭区间 [i, m - 1]
                end = mid - 1
            else:
                # todo 若 mid是正确版本，则首个错误版本一定在闭区间 [m + 1, j]
                start = mid + 1
        return start  #todo start 指向首个错误版本，end 指向最后一个正确版本

r=S278()
n=5
print(r.func(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二、541. 反转字符串 II

简单
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，
就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：
输入：s = “abcdefg”, k = 2
输出：“bacdfeg”

示例 2：
输入：s = “abcd”, k = 2
输出：“bacd”

abcdefgz 反转 cbadefzg
abcdefgzjj 反转 cbadef jzgj
解题思路
1.python的range可以设置步长，实现2k的循环
2.当最后一步剩余元素小于2k，超过k时，因为循环的是i，而且都是处理i后元素，i在循环不满足条件结束之前，便处理了反转k个元素
3.当最后剩余元素小于k时，ss[i: i+k]只会表达到ss截止的地方，不会继续往后查找，就像ss[:]表示的是从最开始项到最后项一样

class S:
    def func(self,s,k):
        ss=[i for i in s]
        n=len(ss)
        for i in range(0,n,2*k):
            ss[i:i+k]=ss[i:i+k][::-1]
        return ''.join(ss)

1
2
3
4
5
6
7
8

三、右旋字符串

卡码网题目链接(opens new window)
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。
输入：输入共包含两行，
第一行为一个正整数 k，代表右旋转的位数。
第二行为字符串 s，代表需要旋转的字符串。
输出：输出共一行，为进行了右旋转操作后的字符串。

class S17:
    def func(self,s,k):
        n=len(s)
        s=s[n-k:]+s[:n-k]
        return s

r=S17()
s="abcdefg"
k=2
print(r.func(s, k))

1
2
3
4
5
6
7
8
9
10
11

四、替换数字

卡码网题目链接(opens new window)
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。
例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”
输入：一个字符串 s,s 仅包含小写字母和数字字符。
输出：打印一个新的字符串，其中每个数字字符都被替换为了number
样例输入：a1b2c3
样例输出：anumberbnumbercnumber
数据范围：1 <= s.length < 10000。

class S18:
    def func(self,s):
        lst=list(s)   #todo Python里面的string也是不可改的，所以也是需要额外空间的。空间复杂度：O(n)
        for i in range(len(lst)):
            if lst[i].isdigit():
                lst[i]='number'
        return ''.join(lst)


1
2
3
4
5
6
7
8
9

五、977.有序数组的平方

力扣题目链接(opens new window)

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

暴力法

# todo 暴力法
class S19:
    def func(self,nums):
        for i in range(len(nums)):
            nums[i]*=nums[i]
        nums.sort()
        return nums
1
2
3
4
5
6
7