ARTS #26

Algorithm

本周选择的算法题是：Next Permutation

规则如下：

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

`1,2,3` → `1,3,2`
`3,2,1` → `1,2,3`
`1,1,5` → `1,5,1

Solution

我实现的方案：

Runtime：40 ms，快过 91.17%。

Memory：12.6 MB，低于 100%。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        if length <= 1: return
        
        def reverse(start: int, end: int):
            """
            反转指定的区间
            """
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        
        index = None
        for i in range(length-2, -1, -1):
            if nums[i] < nums[i+1]:
                index = i
                break

        # 降序时，反转成升序
        if index is None:
            reverse(0, length - 1)
            return

        smallest = index + 1
        for i in range(smallest+1, length):
            if nums[i] <= nums[index]:
                break
            else:
                smallest = i
        
        nums[index], nums[smallest] = nums[smallest], nums[index]
        reverse(index + 1, length - 1)

这题算法并不复杂，难的是理解 next permutation。

附上一个对该问题的解释：

Review

Getting Started with GraphQL

前段时间在搭建公司内部系统时，采用了 GraphQL 作为前后端的数据通讯方式，使用下来觉得好处很多：

解耦 - 前端需要的数据字段不用后端手动提供，避免了频繁更新、部署接口
结构一致 - 数据返回的结构和请求时的结构一样
自描述 - 字段名、字段类型、对象之间的组合、继承关系在写 Query 的过程中可以直观看到

缺点就是前期存在一定的学习成本，以及初始环境的搭建。

Tip

找出当前机器正在使用指定端口的进程：

lsof -i :23515 -t
# lsof = list open files

找出文件然后执行指定的命令：

find . -exec echo {} \;

Image Lazy Loading

新的属性 loading，可以很容易实现图片的懒加载：

<img src="path/to/logo.png" loading="lazy"  onload="alert('Loaded!');">

期待它在兼容性上有更好的表现。

Algorithm

Solution

Review

Tip

Share