697. 数组的度
题目描述
给定一个非空且只包含非负数的整数数组
nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。你的任务是在
nums中找到与nums拥有相同大小的度的最短连续子数组，返回其长度。示例 1：
输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
示例 2：
输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。
解题思路
这个题目的难点在于如果出现多个次数相同的元素，到底哪一个是最优解。首先给自己提个醒，如果涉及到列表中元素需要数个数，那么一定要先用set去除重复项，要不然很容易报超时错误！主要是用字典将元素及其属性相关联，根据值查找键所用的方法为[k for (k,v) in sic.items() if v == value]，这样可以将所有最高项生成一个列表，然后遍历这个列表中的元素，index获取第一个出现的元素，将列表倒序，第一个出现的索引即为原列表该元素最后一次出现的索引。将这两个作差，最小值即为待求元素。最后就很简单了，做一个列表切割，返回最终结果就可以了。
解题代码
1. def findShortestSubArray(nums): 2. if len(nums) == 1: 3. return 1 4. # 问题的关键在于如果最高次出现了多项，怎么确定哪一项才是真正的最优解 5. num_dic = {} 6. # 元素作为键，出现次数作为值 7. set_dic_1 = {} 8. for i in list(set(nums)): 9. set_dic_1[i] = nums.index(i) 10. for i in list(set(nums)): 11. num_dic[i] = nums.count(i) 12. max_ci = max(list(num_dic.values())) 13. max_list = [k for (k,v) in num_dic.items() if v == max_ci] 14. temp = {} 15. for num in max_list: 16. for i in range(len(nums) - 1, 0, -1): 17. if nums[i] == num: 18. end = i 19. temp[end-set_dic_1[num]] = num 20. break 21. max_num = temp[min(list(temp.keys()))] 22. 23. l_index = nums.index(max_num) 24. r_index = 0 25. for i in range(len(nums)-1,0,-1): 26. if nums[i]== max_num: 27. r_index = i 28. break 29. return len(nums[l_index:r_index+1])
728. 自除数
题目描述
自除数 是指可以被它包含的每一位数整除的数。
- 例如，
128是一个 自除数 ，因为128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。自除数 不允许包含 0 。
给定两个整数
left和right，返回一个列表，列表的元素是范围[left, right]内所有的 自除数 。示例 1：
输入：left = 1, right = 22
输出：[1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
示例 2:
输入：left = 47, right = 85
输出：[48,55,66,77]
解题思路
这题的关键在找到每位数，用字符串切片的方式会方便很多，然后就是while循环，以及判断最后一个，一定要注意边界问题。将目标元素添加到目标列表中，最终返回目标列表。
解题代码
1. def selfDividingNumbers(left: int, right: int): 2. result = [] #盛放结果的列表 3. for i in range(left,right+1): 4. count = 0 5. temp_str = str(i) 6. if "0" not in temp_str: 7. while count <= len(temp_str) - 1: 8. if i % int(temp_str[count]) != 0: 9. break 10. if count == len(temp_str)-1: 11. result.append(i) 12. count +=1 13. else: 14. pass 15. 16. return result
821. 字符的最短距离
题目描述
给你一个字符串
s和一个字符c，且c是s中出现过的字符。返回一个整数数组
answer，其中answer.length == s.length且answer[i]是s中从下标i到离它 最近 的字符c的 距离 。两个下标
i和j之间的 距离 为abs(i - j)，其中abs是绝对值函数。示例 1：
输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。
示例 2：
输入：s = "aaab", c = "b"
输出：[3,2,1,0]
解题思路
这题可以从左到右遍历一遍再从右到左遍历一遍，如果i为c的话count就为0，否则count累加，将结果储存一下。两次遍历取最小值就可以了。注意开始的时候，如果s[0]就等于c的话，好办，直接开始遍历就可以了。如果不等于c要把开始到c第一次出现之间的count进行倒叙，再添加到列表中。从右到左列表需要[::-1]变为正序，最后遍历两个列表，取相应位置的最小值，添加到目标列表中，最终返回这个目标列表。
解题代码
1. def shortestToChar(s: str, c: str): 2. # 从左到右遍历一遍，再从右到左遍历一遍，比较对应位置，选择最小的最为最终结果 3. l_r = [] 4. r_l = [] 5. temp_1 = [] 6. temp_2 = [] 7. result = [] 8. count = 0 9. if s[0]==c: 10. for i in s: 11. if i == c: 12. count = 0 13. else: 14. count += 1 15. l_r.append(count) 16. else: 17. for i in s[:s.index(c):]: 18. if i == c: 19. count = 0 20. else: 21. count += 1 22. temp_1.append(count) 23. l_r.extend(temp_1[::-1]) 24. for i in s[s.index(c)::]: 25. if i == c: 26. count = 0 27. else: 28. count += 1 29. l_r.append(count) 30. s = s[::-1] 31. 32. if s[0] == c: 33. for i in s: 34. if i == c: 35. count = 0 36. else: 37. count += 1 38. r_l.append(count) 39. else: 40. for i in s[:s.index(c):]: 41. if i == c: 42. count = 0 43. else: 44. count += 1 45. temp_2.append(count) 46. r_l.extend(temp_2[::-1]) 47. for i in s[s.index(c)::]: 48. if i == c: 49. count = 0 50. else: 51. count += 1 52. r_l.append(count) 53. r_l = r_l[::-1] # 颠倒回来 54. for i in range(len(r_l)): 55. result.append(min(r_l[i],l_r[i])) 56. 57. return result
