力扣刷题记录——205.同构字符串、217. 存在重复元素、283. 移动零

2023-01-30 89

版权

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

简介： 力扣刷题记录——205.同构字符串、217. 存在重复元素、283. 移动零

205.同构字符串

题目描述

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:

输入：s = "egg", t = "add"

输出：true

示例 2：

输入：s = "foo", t = "bar"

输出：false

解题思路

看到映射关系，首先想到的是字典的对应关系，所以这一题我们能够拿字典来处理。遍历s,建立与t的映射关系，以此来生成映射中的t，同样遍历t,建立与s的映射关系，生成映射中的s，比较生成的与实际的是否相等，如果都相等说明是同构字符串，返回True，否则返回False。整体的思路还是比较简单的。

解题代码

1. def isIsomorphic(s: str, t: str):
2. if len(s) != len(t):
3. return False
4. else:
5.         s_dic = {}
6.         t_dic = {}
7.         s_str = ""
8.         t_str = ""
9. for i in range(0,len(s)):
10.             s_dic[s[i]] = t[i]
11.             t_dic[t[i]] = s[i]
12. for i in s:
13.             s_str += s_dic[i]
14. for j in t:
15.             t_str += t_dic[j]
16. if s_str == t and t_str == s:
17. return True
18. else:
19. return False

217. 存在重复元素

题目描述

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]

输出：true

示例 2：

输入：nums = [1,2,3,4]

输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]

输出：true

解题思路

这题放之前我肯定遍历列表用count来数了，现在第一想法就是用set转成集合，set有一个天然优势，那就是会去除重复元素，这样我们只需要比较转换前和转化后的长度就可以了，大大减少了代码量，一次通过！

解题代码

1. def containsDuplicate( nums):
2.     list_set  = list(set(nums))
3. if len(list_set) == len(nums):
4. return False
5. else:
6. return True

283. 移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]

输出:[1,3,12,0,0]

示例 2:

输入: nums = [0]

输出:[0]

解题思路

分为两步走吧，第一步找出0的索引，第二步将0与后面的数交换，及冒泡排序，这里注意要从后面的索引开始交换，这样才不影响前面列表的顺序，所有涉及到列表的倒序操作。

解题过程

1. def moveZeroes(nums):
2.     zero_list = []
3. for i in range(0,len(nums)):
4. if nums[i] == 0:
5.             zero_list.append(i)
6.     zero_list = zero_list[::-1]
7. for ind_p in zero_list:
8. while ind_p != len(nums)-1:
9.             nums[ind_p],nums[ind_p+1] = nums[ind_p+1],nums[ind_p]
10.             ind_p +=1
11. return nums

可惜，有一个算例超出时间了，看来时间复杂度还是太高了，需要优化自己的代码，要低于O(n^2)。上面我用到的是冒泡排序，可以更换其他的排序算法以降低时间复杂度。

1. def moveZeroes(nums):
2.     length_1 = len(nums)
3.     nums_tep = nums[::-1]
4. for i in nums_tep:
5. if i == 0:
6.             nums.remove(i)
7.     length_2 = len(nums)
8.     count = 0
9. while count != length_1-length_2:
10.         nums.append(0)
11.         count+=1
12. return nums

虽然通过了，但是好像复制了数组，不符合题目要求！看看其他大神的解答：

1. class Solution:
2. def moveZeroes(self, nums: List[int]) -> None:
3. """
4.         Do not return anything, modify nums in-place instead.
5.         """
6. for i in range(len(nums)-1,-1,-1):    
7. if nums[i]==0:
8.                 nums.append(nums.pop(i))