1. 螺旋矩阵 II
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
1 <= n <= 20
代码：
class Solution(object): def generateMatrix(self, n): """ :type n: int :rtype: List[List[int]] """ res = [[0] * n for _ in range(n)] pos = [0, 0] move = (0, 1) for index in range(1, n * n + 1): res[pos[0]][pos[1]] = index if res[(pos[0] + move[0]) % n][(pos[1] + move[1]) % n] > 0: move = (move[1], -1 * move[0]) pos[0] = pos[0] + move[0] pos[1] = pos[1] + move[1] return res if __name__ == '__main__': s = Solution() print (s.generateMatrix(3)) print (s.generateMatrix(1))
输出：
[[1, 2, 3], [8, 9, 4], [7, 6, 5]]
[[1]]
2. 排列序列
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
示例 1：
输入：n = 3, k = 3
输出："213"
示例 2：
输入：n = 4, k = 9
输出："2314"
示例 3：
输入：n = 3, k = 1
输出："123"
提示：
1 <= n <= 9
1 <= k <= n!
代码：
class Solution(object): def getPermutation(self, n, k): """ :type n: int :type k: int :rtype: str """ import math res = [""] def generate(s, k): n = len(s) if n <= 2: if k == 2: res[0] += s[::-1] else: res[0] += s return step = math.factorial(n - 1) yu = k % step if yu == 0: yu = step c = k // step - 1 else: c = k // step res[0] += s[c] generate(s[:c] + s[c+1:], yu) return s = "" for i in range(1, n + 1): s += str(i) generate(s, k) return res[0] if __name__ == '__main__': s = Solution() print(s.getPermutation(3, 3)) print(s.getPermutation(4, 9)) print(s.getPermutation(3, 1))
输出：
213
2314
123
3. 数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
示例 2：
输入：n = 0
输出：0
提示：
0 <= n <= 10^9
代码：
class Solution: def countDigitOne(self, n: int) -> int: res, i = 0, 1 while i <= n: res += n // (i * 10) * i x = (n // i) % 10 res += i if x > 1 else (n % i + 1) * x i *= 10 return res if __name__ == '__main__': s = Solution() print(s.countDigitOne(13)) print(s.countDigitOne(0))
输出：
6
0
附录
排列与组合
是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。
基本原理
⑴加法原理和分类计数法
⒈加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+…+mn种不同方法。
⒉第一类办法的方法属于集合A1，第二类办法的方法属于集合A2，……，第n类办法的方法属于集合An，那么完成这件事的方法属于集合A1UA2U…UAn。
⒊分类的要求 ：每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同（即分类不重）；完成此任务的任何一种方法，都属于某一类（即分类不漏）。
⑵乘法原理和分步计数法
⒈ 乘法原理：
做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法。
⒉合理分步的要求
任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。
3.与后来的离散型随机变量也有密切相关。
著名问题
计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。
地图着色问题
对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。
船夫过河问题
船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。
中国邮差问题
由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。
任务分配问题
有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。
