这里总结了一些非常有意思的、非常规的题目，多是一些数学、通信领域的实际问题。

这里总结了一些非常规的算法思想

相关LeetCode题目

LeetCode 60. 第k个排列（中）

直觉

利用阶乘系统，构建输入和输出的映射关系，实际上阶乘系统经常在密码学中被应用。

关键代码

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factorials, nums = [1], ['1']  # 声明保存阶层数的变量factorials，factorials[0]就是1，以及存储从 1 到 N 的数字的变量nums，nums[0]是'1'。
        
        for i in range(1, n):
            # 计算从 0 到 (N - 1)!的所有阶乘数。
            factorials.append(factorials[i - 1] * i)
            # 生成输入数组，存储从 1 到 N 的数字。
            nums.append(str(i + 1))

        k -= 1  # 数组排序是从0开始的，所以要在输入的k上减去1
        
        output = []  # 声明保存结果的output
        # 开始循环计算k的阶乘表示，循环范围从n - 1到0。
        for m in range(n - 1, -1, -1):
            # 计算 k 的阶乘表示，使用阶乘系数构造排列。
            # 已知 k = k_m * m! + ... + k_1 * 1! + k_0 * 0!
            k_m = k // factorials[m]  # 计算计算当前阶乘 m! 对应的阶乘系数 k_m，从后往前计算。
            k -= k_m * factorials[m]  # 更新k
            output.append(nums[k_m])  # 将阶乘系数对应的数选中放入output中
            del nums[k_m]  # 再从nums中删除这次被选中的数字
        
        return ''.join(output)  # 返回选中的排列字符串output的字符串形式。

题解 **

LeetCode 60. 第k个排列（中）

LeetCode 89. 格雷编码（中）

题目

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。 给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

直觉

1、先翻转 0 1，得到长度为 n 的排列 0 1 1 0 （n=4）。
2、在前 n/2 个数字不变，在后 n/2 个排列前加 1。组成新排列，以此类推。

这个解法也可以理解成动态规划，状态转移方程就是：

dp[j] += dp[j-1] | 1 << i

关键代码

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = [0]
        for i in range(n):
            size = len(res)
            # 为啥要从后面往前循环，因为是镜像的，由0 1得到1 0，所以必须从后往前循环。
            for j in range(size-1, -1, -1):
                res.append(res[j] | (1 << i))
        return res

题解

LeetCode 89. 格雷编码（中）

剑指offer 面试题43. 1～n整数中1出现的次数（中）

题目

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

直觉

不要试图遍历 [1, 2, 3, ..., n] 的list，而是直接从分析 n 入手，以求解出1出现的次数。

关键代码

while high != 0 or cur != 0:
    if cur == 0: res += high * digit
    elif cur == 1: res += high * digit + low + 1
    else: res += (high + 1) * digit
    low += cur * digit
    cur = high % 10
    high //= 10
    digit *= 10

题解

剑指offer-面试题43-1～n整数中1出现的次数（中）

剑指offer 面试题62-圆圈中最后剩下的数字（易）

题目

经典的约瑟夫环问题，此题的难点在于求解状态转移方程。

直觉

用链环解决在 \(O(n \times m)\) 的时间复杂度内解决问题的思路很简单，但是要想在 \(O(n)\) 的时间复杂度内解决问题就不容易了。

关键代码

class Solution:
    def lastRemaining(self, n: int, m: int) -> int:
        if n < 1 or m < 1:
            return -1
        last = 0
        for i in range(1, n+1):
            last = (last + m) % i
        return last

题解

剑指offer-面试题62-圆圈中最后剩下的数字（易）