【算法】算法题-20231111-CSDN博客

一、409. 最长回文串

简单

给定一个包含大写字母和小写字母的字符串 s 返回 通过这些字母构造成的 最长的回文串 。
在构造过程中请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。

示例 1:
输入:s = “abccccdd”
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:
输入:s = “a”
输出:1

示例 3
输入:s = “aaaaaccc”
输出:7

def func12(s):
    res = 0
    center = 0
    from collections import Counter
    s_1 = Counter(s)
    for i in s_1:
        if s_1[i] % 2 == 0:
            res += s_1[i]
        else:
            center = 1
            res += s_1[i] - 1
    return res + center


s = "abccccdd"
print(func12(s))

二、392. 判断子序列

简单

给定字符串 s 和 t 判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些也可以不删除字符而不改变剩余字符相对位置形成的新字符串。例如"ace"是"abcde"的一个子序列而"aec"不是。

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

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

示例 2
输入s = “axc”, t = “ahbgdc”
输出false

解题思路
设置双指针 i , j 分别指向字符串 s , t 的首个字符遍历字符串 t
当 s[i] == t[j] 时代表匹配成功此时同时 i++ , j++
进而若 i 已走过 s 尾部代表 s 是 t 的子序列此时应提前返回 true
当 s[i] != t[j] 时代表匹配失败此时仅 j++
若遍历完字符串 t 后字符串 s 仍未遍历完代表 s 不是 t 的子序列此时返回 false 。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s: 
        	return True
        i = 0
        for c in t:
            if s[i] == c:
                i += 1
                # 若已经遍历完 s 则提前返回 true
                if i == len(s):
                    return True
        return False

三、521. 最长特殊序列Ⅰ

简单

给你两个字符串 a 和 b请返回 这两个字符串中 最长的特殊序列 的长度。如果不存在则返回 -1 。
「最长特殊序列」 定义如下该序列为 某字符串独有的最长子序列即不能是其他字符串的子序列 。
字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。
例如“abc” 是 “aebdc” 的子序列因为删除 “aebdc” 中斜体加粗的字符可以得到 “abc” 。 “aebdc” 的子序列还包括 “aebdc” 、 “aeb” 和 “” (空字符串)。

示例 1
输入: a = “aba”, b = “cdc”
输出: 3
解释: 最长特殊序列可为 “aba” (或 “cdc”)两者均为自身的子序列且不是对方的子序列。

示例 2
输入a = “aaa”, b = “bbb”
输出3
解释: 最长特殊序列是 “aaa” 和 “bbb” 。

示例 3
输入a = “aaa”, b = “aaa”
输出-1
解释: 字符串 a 的每个子序列也是字符串 b 的每个子序列。同样字符串 b 的每个子序列也是字符串 a 的子序列。

def fun0(a, b):
    if a == b:
        return -1
    elif len(a) == len(b):
        return len(a)
    else:
        return max(len(a), len(b))


a = "aba"
b = "aa"
print(fun0(a, b))

四、628. 三个数的最大乘积

简单
给你一个整型数组 nums 在数组中找出由三个数组成的最大乘积并输出这个乘积。

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

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

示例 3
输入nums = [-1,-2,-3]
输出-6

def f(nums):
    v1 = nums[0] * nums[1] * nums[2]
    v2 = nums[-1] * nums[-2] * nums[-3]
    return max(v1, v2)

nums = [-1, -2, -3]
print(f(nums))