leetcode-排序一

发表于 | 分类于 | 页面访问量 次
字数统计: 1.7k 字 | 阅读时长 ≈ 7 分钟

总结：今天的效率还可以。不过，又出现钻牛角尖的情况。简单的问题卡了好久。好在最后迎刃而解。有时候需要暂时搁置，效率优先。

1030. 距离顺序排列矩阵单元格（C+）

分析：看了一下别人的思路，大致就是广度遍历，深度遍历。题意很好理解。就是构建矩阵，然后根据原点求距离排序。 矩阵用遍历，原点距离用abs（），排序用sorted。优答：使用了lambda感觉简明不少。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        def distance(p1,p2):
            return int(abs(p1[0]-p2[0])+abs(p1[1]-p2[1]))
        
        dic = []
        for i in range(R):
            for j in range(C):
                dic.append([distance([i,j],[r0,c0]),[i,j]])
        dic = sorted(dic,key=(lambda x:x[0]))
        for i in range(len(dic)):
            dic[i] = dic[i][1]
        return dic

扩展：

  • sorted用法。与sort区别，不影响结构。

    sorted返回一个有序的副本，并且类型总是列表。

    sort对原列表进行排序，无返回值。

  • sort/sorted方法还有两个可选参数：key和reverse

    • key在使用时必须提供一个排序过程总调用的函数：
    • reverse实现降序排序，需要提供一个布尔值：True为倒序排列，False为正序排列
    1
    2
    3
    4
    5
    6
    7
    8
    >>> f = [{'name':'abc','age':20},{'name':'def','age':30},{'name':'ghi','age':25}]     #列表中的元素为字典 
        >>> def age(s): 
               return s['age'] 
        >>> ff = sorted(f,key = age)      #自定义函数按列表f中字典的age从小到大排序  
         
        [{'age': 20, 'name': 'abc'}, {'age': 25, 'name': 'ghi'}, {'age': 30, 'name': 'def'}] 
         
        >>> f2 = sorted(f,key = lambda x:x['age'])    #如果觉得上面定义一个函数代码不美观，可以用lambda的形式来定义函数,效果同上

148. 排序链表（B+）

分析：应该算是很经典的题了吧。一开始想的很简单。后来发现不对，没那么容易。简单的讲就是归并的思想。先把所有链表都分开，然后排序，再拼接。排序时使用了快慢针。快针分链表时计数，慢针来记录中间指针位置。然后从首中开始向后比较。

递归归并问题卡了我1个多小时。就是想不通，为什么分开之后排序了。终于灵光一现。先分化到底端。然后排序，然后往回找。想通之后，发现就是最基础的归并。

1342》13，42》1，3 2，4》13， 24》1234

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution:
    def sortList(self, head):
        """
        主要是使用归并的思路 先分再合
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        return self.minute(head)

    def minute(self, head):
        """
        这个方法主要是实现分的操作
        分的过程用快慢指针实现
        :param head:
        :return:
        """
        if head.next is None:
            return head
        quick, slow, temp = head, head, head
        while quick is not None and quick.next is not None:
            temp = slow
            slow = slow.next
            quick = quick.next.next
        temp.next = None  # 这一步就是将整个链表从中间分开 失去这一步 后面将无限循环

        i = self.minute(head)
        j = self.minute(slow)
        return self.Combined(i, j)

    def Combined(self, i, j):
        """
        这个方法主要实现合的操作
        合的过程就是从i 和 j开始比较 就是从开头和中间开始比较 将两个相比小的排在head后
        最后返回head即可
        :param i:ListNode
        :param j:ListNode
        :return:
        """
        TempNode = ListNode(0)
        temp = TempNode
        while i is not None and j is not None:
            if i.val <= j.val:
                temp.next = i
                i = i.next
            else:
                temp.next = j
                j = j.next
            temp = temp.next
        if i is not None:
            temp.next = i
        if j is not None:
            temp.next = j
        return TempNode.next

324. 摆动排序 II（C+）

分析：题意简单，但是思考出最优解还是需要细心和耐心的。参考答案，很棒~直接贴出来。

来自StefanPochmann

先对数组排序，分为大数部分和小数部分，再穿插排序。 注意顺序，例如[1，2，4，4，4，6]这个数组，通过降序穿插得到[4,6,2,4,1,4]。 如果顺序排列，则会得到[1,4,2,4,4,6]不满足要求。 这里是因为我们想尽量将小数部分的最大数放在边上，这样只用靠近一个大数部分的最大数。

1
2
3
4
5
6
7
8
class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        half = len(nums[::2])
        nums[::2], nums[1::2] = nums[:half][::-1],nums[half:][::-1]

75. 颜色分类（C）

分析：题意，0，1，2排序。不可以使用sort。

要求：一个直观的解决方案是使用计数排序的两趟扫描算法。首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。

思考仅使用常数空间的一趟扫描算法！

0，1，2 排序。一次遍历，如果是0，则移动到表头，如果是2，则移动到表尾，不用考虑1。0和2处理完，1还会有错吗？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        
        i = 0
        j = n - 1            #取末尾位置,计数往前添加.
        while i <= j:
            if nums[i] == 0:
                nums.pop(i)
                nums.insert(0,0)
                i += 1
            elif nums[i] == 2:
                nums.pop(i)
                nums.insert(j,2)
                j -= 1
            else:
                i += 1

710. 黑名单中的随机数（A-）

分析：感觉无从下手~直接借鉴思路。关键点在于黑名单的映射分类.

思路：

  • 黑名单长度为s，我们从[0, N-s)中取随机值，这个随机值有可能在黑名单中，怎么办？
  • [0, N-s)内的元素，如果有i个在黑名单中，那么在[N-s, N)中，必定有i个元素不在黑名单中
  • 对[0, N-s)中的黑名单元素和[N-s, N)中不在黑名单中的元素做映射m，必定可以一一对应，怎么对应倒是无所谓
  • 从[0, N-s)中取随机值r，如果r不在黑名单中，直接返回；如果r在黑名单中，则m[r]一定不在黑名单，返回m[r]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from random import randint       #生成随机整数.有界限.

class Solution:

    def __init__(self, N, blacklist):
        
        self.s = N - len(blacklist)
      
        b_lt_s = {i for i in blacklist if i < self.s}   # 小于s的黑名单元素集合
 
        w_gt_s = {i for i in range(self.s, N)} - set(blacklist) # 大于s的非黑名单元素集合
       
        self.m = {k: v for k,v in zip(b_lt_s, w_gt_s)}    # 做映射，使用zip方便一点

    def pick(self):
        """
        :rtype: int
        """
        r = randint(0, self.s-1)
        return r if r not in self.m else self.m[r]
0%
undefined