力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数

2023-01-30 134

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 力扣刷题记录——459.重复的字符串、461. 汉明距离、476. 数字的补数

459.重复的字符串

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。 示例 1: 输入: s = "abab" 输出: true 解释: 可由子串 "ab" 重复两次构成。 示例 2: 输入: s = "aba" 输出: false 示例 3: 输入: s = "abcabcabcabc" 输出: true 解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

解题思路

首先判断字符串长度是不是1，是的话直接返回False，否则用set获取字符串中的单一元素，在s中去数，如果数出来的结果一样，那么说明可以由重复的字符串构成。

解题过程

1. def repeatedSubstringPattern(s):
2. if len(s) == 1:
3. return False
4.     s_set = list(set(s))
5.     target_list = []
6. for i in s_set:
7.         target_list.append(s.count(i))
8. if len(set(target_list)) == 1:
9. return True
10. else:
11. return False

忽略了字符串的位置，虽然ab的数量一样，但是位置不一样也不能重复构成字符串。可以尝试用列表元素第一次出现的位置与第二次出现的位置进行切割列表。

1. def repeatedSubstringPattern(s):
2. if len(s) == 1:
3. return False
4. elif len(set(s)) == 1:
5. return True
6.     s_set = list(set(s))
7. for i in range(0,len(s_set)):
8.         list_a = ['a', 'b', 'c', 'a']
9. 
10.         first_index = s.index(s_set[i])
11. try:
12.             sed_indx = s.index(s_set[i], first_index + 1)
13. except ValueError:
14. return False
15. else:
16.             step = sed_indx - first_index  #０改成ｉ
17. print("第二次出现的索引",sed_indx)
18. print("第一次出现的索引",first_index)
19. print("步长",step)
20.             begin = s.find(s_set[i])
21. # print("begin",begin)
22. while begin+step <= len(s)-1:
23. if s[begin] == s[begin+step]:
24.                     begin += step
25. else:
26. return False
27. return True

忽略了组合中间还包括第一个元素的情况，头痛！用列表切割判断吧！

1. def repeatedSubstringPattern(s):
2. if len(s) == 1:
3. return False
4. elif len(set(s)) == 1:
5. return True
6.     s_set = list(set(s))
7. for i in range(2,int(len(s)/2)+1):
8.         target_str = "".join(s[:i])
9.         s_list= [j for j in s.split(target_str) if j != ""]
10. if s_list == []:
11. return True
12. return False

终于通过了！看看其他大佬的解答，直接震惊我！

1. class Solution:
2. def repeatedSubstringPattern(self, s: str) -> bool:
3. return True if s in (s + s)[1:-1] else False

如果s不包含重复子串，那么s自己就是一次重复的子串，那么把s + s去头去尾中就一定不包含s自己。

如果s包含重复子串，那么在s + s去头去尾中就一定能找到s自己,这样的做法真的很巧妙！记住了！

461. 汉明距离

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y ，计算并返回它们之间的汉明距离。 示例 1： 输入：x = 1, y = 4 输出：2 解释： 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。 示例 2： 输入：x = 3, y = 1 输出：1

解题思路

首先要将传入的整数转化为二进制，可以用bin函数，主要要进行切片，然后将两个二进制数字补齐，短的数字要在前面加0补齐，最后判断各位是否相等，不相等的话count需要进行+1，最后返回count的值。

解题代码

1. def hammingDistance(x: int, y: int):
2.     x_bin = bin(x)[2:]
3.     y_bin = bin(y)[2:]
4.     max_length = max(len(x_bin),len(y_bin))
5.     min_length = min(len(x_bin),len(y_bin))
6. if len(x_bin)>len(y_bin):
7.         y_list = [i for i in y_bin]
8. for i in range(max_length-min_length):
9.             y_list.insert(0,"0")
10.             y_bin = "".join(y_list)
11. elif len(x_bin)==len(y_bin):
12. pass
13. else:
14.         x_list = [i for i in x_bin]
15. for i in range(max_length-min_length):
16.             x_list.insert(0,"0")
17.             x_bin = "".join(x_list)
18.     count = 0
19. for i in range(0,len(x_bin)):
20. if x_bin[i] != y_bin[i]:
21.             count +=1
22. return count

476. 数字的补数

题目描述

对整数的二进制表示取反（0 变 1 ，1 变 0 ）后，再转换为十进制表示，可以得到这个整数的补数。例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。给你一个整数 num ，输出它的补数。 示例 1： 输入：num = 5 输出：2 解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。 示例 2： 输入：num = 1 输出：0 解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

解题思路

将整数用bin函数转化为2进制的数，遍历得到的字符串，判断其中的每一个数，得到它的补数，最后用int转化为整数就可以了，返回得到的整数。

解题代码

1. def findComplement(num: int):
2. # 转化为2进制
3.     num_bin = bin(num)[2:]
4.     fin_num = ""
5. for i in num_bin:
6. if i =="0":
7.             fin_num += "1"
8. else:
9.             fin_num += "0"
10.     result_num = int(fin_num,2)
11. return result_num