力扣刷题记录——697. 数组的度、728. 自除数、821. 字符的最短距离

2023-01-30 75

版权

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

简介： 力扣刷题记录——697. 数组的度、728. 自除数、821. 字符的最短距离

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