按照leetcode标签排序做题

1、两个数组的交集

解析

观察题目，求两个数组的交集，并且结果中每个元素不重复，立刻想到集合set求交集insection。 python构造集合set() 求交集 1.set1 & set2 2.set.insection(set1,set2) 最后转成list输出

解答

class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: set1 = set(nums1) set2 = set(nums2) return list(set.intersection(set1,set2))#或者return list(set1 & set2)

2.按奇偶排序数组II

解析：题目的含义就是，奇数序号放奇数，偶数序号放偶数，且数量相等

答案1:

遍历一次将其中的偶数和奇数分出来，再将两个数组的元素轮流加入新数组

class Solution: def sortArrayByParityII(self, A: List[int]) -> List[int]: Res1,Res2,Res = [],[],[] for a in A: if a % 2 == 0: Res1.append(a) else: Res2.append(a) for i in range(0,len(Res1)): Res.append(Res1[i]) Res.append(Res2[i]) return Res

答案2：不额外使用内存，仅在原数组进行排序，使用双指针。

一个j指向序号奇数，一个i指向偶数序号，注意只有当指针对应位置上的数字符合规则，才移动指针，例如这里将while换成if语句，则不能保证A【j】为奇数就指向下一个点了。

class Solution: def sortArrayByParityII(self, A: List[int]) -> List[int]: i = 0 for j in range(1,len(A),2): while A[j] % 2 == 0: A[i],A[j] = A[j],A[i] i += 2 return A

3、数组的相对排序

解析：这道题主要可拆分成两步，一个是按arr2顺序，一个是按升序，因此主要思路是在arr1提取出arr2中的元素排序后再对剩余的排列

答案：

1.

// 遍历arr2中每个元素，如果arr1中存在，则加到结果中 // 每次arr1中加一个后就移除它 // 最后剩余元素sort一下 class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: res = [] for i in arr2: while i in arr1: res.append(i) //remove() 函数用于移除列表中某个值的第一个匹配项。 arr1.remove(i) arr1.sort() return res + arr1

2.

//将arr1中多余的数通过集合的元素唯一性，提出完成排序并加入arr2 //此时arr2中元素的顺序正确，只是确少重复元素， //因此，通过按照arr2元素的索引号，对arr1进行排列 class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: arr2 += sorted(set(arr1) - set(arr2)) arr1.sort(key=arr2.index) return arr1

3.计数排序

// 第一步遍历arr1中元素，并计数每个元素，索引即元素值，得到的arr相当于一个直方图 // 第二步遍历arr2，值即为arr中下标，如果arr对应元素的值不为0，则表明arr中还有该值，添加后减一 // 第三步遍历剩余的arr，从0到最后，如果某个值得个数不为0，添加并减一直至0 class Solution: def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: arr = [0 for i in range(0,1001)] res = [] for i in arr1: arr[i] += 1 for i in arr2: while (arr[i]): res.append(i) arr[i] -= 1 for i in range(len(arr)): while(arr[i]): res.append(i) arr[i] -= 1 return res

4、距离顺序排列矩阵单元格

解析：这道题的意思就是求矩阵其他元素位置上中离某一个元素值的距离，的排序

答案

class Solution: def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]: # 把所有元素的位置组成一个列表 res = [] for i in range(R): for j in range(C): res.append([i,j]) # 按关键字是元素的对应距离升序 # lambda中计算每个位置上的距离，按距离升序，将对应的元素位置排列好 res.sort(key = lambda x: abs(x[0] - r0) + abs(x[1]-c0)) return res

5、有效的字母异位词

解析：对两个字符串排序后比较不同即可

答案、

// collections.Counter()可以计数并返回元素及其个数的列表 class Solution: def isAnagram(self, s: str, t: str) -> bool: return collections.Counter(s) == collections.Counter(t) // 直接排序 return sorted(s) == sorted(t)

6、三角形的最大周长

解析：该题就是找满足a+b > c 的最大的三个值，排序后从大到小遍历即可

答案1、排序后遍历

class Solution: def largestPerimeter(self, A: List[int]) -> int: A.sort(reverse=True) for i in range(2,len(A)): if A[i] + A[i-1] > A[i-2]: return A[i-1] + A[i-2] + A[i] return 0

答案2、冒泡排序

摘自leetcode评论区的解法，通过冒泡的写法, 因为我们没必要全部把数组排序完, 再去比较 两边之和大于第三边冒泡排序, 每排一轮, 就会选出个最大值放在后边, 当排三轮后, 我们就可以比较了,如果现在出现了符合三角情况的, 就直接返回, 不继续排序了,如果还没出现, 就再来一轮，用python实现

class Solution: def largestPerimeter(self, A: List[int]) -> int: for i in range(0,len(A)): for j in range(0,len(A)-i-1): if A[j+1] < A[j]: A[j],A[j+1] = A[j+1],A[j] if i>=2: if A[-i-1] + A[-i] > A[-i+1]: return A[-i] + A[-i-1] + A[-i+1] return 0

7、两个数组的交集II

解析：有重复的输出两个列表的交集

基本想法就是求两个的交集，并将有交集中的元素，在哪个列表里出现次数最少，就添加几个到最后结果

答案

1.（自己的解法）计数

class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: n1 = collections.Counter(nums1) n2 = collections.Counter(nums2) result = [] for i in n1: if i in n2: for j in range(0,min(n1[i],n2[i])): result.append(i) return result

2.用集合的元素唯一性

class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: inter = set(nums1) & set(nums2) result = [] for i in inter: result += [i] * min(nums1.count(i),nums2.count(i)) return result

3.一行流

求得两个计数字典的交集，再展开形成列表

class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: return [*(collections.Counter(nums1) & collections.Counter(nums2)).elements()]

4.双指针法：排序两个数组，用两个指针同时遍历，移动小那个值的指针

class Solution: def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1.sort() nums2.sort() result = [] i,j = 0,0 while (i<len(nums1) and j<len(nums2)): if nums1[i] == nums2[j]: result.append(nums1[i]) i,j = i+1,j+1 elif nums1[i]<nums2[j]: i += 1 else: j += 1 return result

8、排序链表

解析，没学过链表，用了一个蠢办法，提取进列表，排序后，再建立一个列表

答案

# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def sortList(self, head: ListNode) -> ListNode: if head == None: return None h = head res = [] while(h.next != None): res.append(h.val) h = h.next res.append(h.val) res.sort() h = ListNode(res[0]) x = h for i in res[1:]: x.next = ListNode(i) x = x.next return h

9