392. 判断子序列
题目描述
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace" 是"abcde" 的一个子序列，而"aec" 不是）。 示例 1： 输入：s = "abc", t = "ahbgdc" 输出：true 示例 2： 输入：s = "axc", t = "ahbgdc" 输出：false
解题思路
定义两个指针，分别去指向s和t，当两个指针所指内容相等时，两个指针分别加一，如果不相等，t指针加一，退出循环的条件就是某一个指针达到了对应字符串的长度。最后判断s指针是不是达到了s的长度即可解决问题。击败率还是蛮高的，挺满意的。
解题代码
1. def isSubsequence(s: str, t: str): 2. # s = "abc", t = "ahbgdc" 3. # 定义两个指针去指向s和t 4. s_p = 0 5. t_p = 0 6. while s_p < len(s) and t_p < len(t): 7. if s[s_p] == t[t_p]: 8. s_p += 1 9. t_p += 1 10. else: 11. t_p += 1 12. if s_p == len(s): 13. return True 14. else: 15. return False
401. 二进制手表
题目描述
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。例如，下面的二进制手表读取 "3:25" 。
（图源： WikiMedia - Binary clock samui moon.jpg ，许可协议： Attribution-ShareAlike 3.0 Unported (CC BY-SA 3.0) 给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。 小时不会以零开头：例如，"01:00" 是无效的时间，正确的写法应该是 "1:00" 。 分钟必须由两位数组成，可能会以零开头：例如，"10:2" 是无效的时间，正确的写法应该是 "10:02" 。 示例 1： 输入：turnedOn = 1输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"] 示例 2： 输入：turnedOn = 9输出：[]
解题思路
拿到这个题目的时候还是没有什么思路，想的还是暴力枚举法，虽然我知道时间复杂度肯定很高，不管了，能抓住老鼠的都是好猫。思路就是for循环去枚举，小时列表中一次选出i个，分钟列表中选出turnedOn-i，用到了itertools这个内置库，可以在指定的列表中选择指定的个数。之后就是求和判断符不符合规则，符合规则的转化格式存到列表中，最终返回这个最终列表。
解题代码
1. import itertools 2. class Solution: 3. def readBinaryWatch(self, turnedOn: int) -> List[str]: 4. # turnedOn = 5 5. hour_list = [8,4,2,1] 6. min_list = [32,16,8,4,2,1] 7. target_list = [] 8. for i in range(turnedOn+1): 9. # 在hour_list 里面选i个，在min_List选turnedOn-i个，之后求和判断，看有没有超出限制，没有的话添加到目标列表中，最后返回这个目标列表 10. on_list = list(itertools.permutations(hour_list, i)) 11. down_list = list(itertools.permutations(min_list,turnedOn-i)) 12. for m in on_list: 13. for n in down_list: 14. if sum(m) <=11 and sum(n) <=59: 15. if len(str(sum(n)))==1: 16. target_str = "{0}:0{1}".format(sum(m),sum(n)) 17. else: 18. target_str = "{0}:{1}".format(sum(m), sum(n)) 19. target_list.append(target_str) 20. target_list = list(set(target_list)) 21. return target_list
409.最长回文串
题目描述
给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1: 输入:s = "abccccdd" 输出:7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。 示例 2: 输入:s = "a" 输入:1 示例 3： 输入:s = "aaaaaccc" 输入:7
解题思路
这一题思路还是比较清晰的，还是用set把列表中的每一个元素提取出来，如果只有一个元素的话，那么直接返回字符串的长度就可以了。之后设置一个开关target，判断列表中是否有出现次数对2取模还余1的，如果有的话，target就要变成1。我们之后对单独对target进行一次判断，如果target发生变化，说明回文串中间还能再加一个数，所以最终结果+1。中间用一个for循环去数每一个元素出现的次数，我们只记录大于等于2的，并且只取2的整数倍。用一个count去记录，最终返回count的值。
解题代码
1. def longestPalindrome(s: str): 2. s_list = [i for i in s] 3. s__set_list = list(set(s)) 4. count = 0 5. target = 0 6. if len(s__set_list)==1: 7. return len(s) 8. for i in s__set_list: 9. if s_list.count(i)%2 == 1: 10. target = 1 11. if s_list.count(i) >= 2: 12. count += (s_list.count(i)//2)*2 13. 14. if target == 1: 15. return count+1 16. else: 17. return count
