Python每日一练(20230228)
目录
1. 螺旋矩阵 II ★★
2. 排列序列 ★★★
3. 数字 1 的个数 ★★★
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完全问题,存在多项式复杂度算法:先求出度为奇数的点,用匹配算法算出这些点间的连接方式,然后再用欧拉路径算法求解。这也是图论的问题。
任务分配问题
有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少?这是线性规划的问题。
相关阅读
相关文章
- 【水水水文章】用 Python 发邮件
- 羊了个羊,但是Python简(li)单(pu)版
- pycharm自带python环境吗_Python IDE环境之 新版Pycharm安装详细教程[通俗易懂]
- pycharm打包python项目_Python怎么打包
- pycharm将python程序打包_python 程序打包
- python setattr函数_Python内置函数(53)——setattr
- Python 时间运算函数timedelta与relativedelta
- python怎样读取文件夹里的图片_python图片处理及识别
- python的特点和优势_Java与Python异同
- python分析人口出生率代码_国家统计局居然也能用的上Python?人口数据Python脚本了解一下?…[通俗易懂]
- python语言关键字是_Python 关键字
- python如何生成随机数_Python生成50个随机数
- Python基础-4 使用函数减少重复操作
- 【7】python_matplotlib 输出(保存)矢量图方法;画图时图例说明(legend)放到图像外侧;Python_matplotlib图例放在外侧保存时显示不完整问题解决
- python 堆排序算法
- Python中的继承
- python-Python与SQLite数据库-SQLite数据库的基本知识(二)
- python批量抓取美女图片详解编程语言
- Linux下安装Python的指南(linux下安装python)
- 安装Python MySQL驱动之快速指南(python安装mysql驱动)
- Python玩转Redis:提升缓存效率(python使用redis)
- Python在MSSQL中的应用实践(python与mssql)
- Linux下的Python开发技术之旅(linux下python开发)
- Python常见文件操作的函数示例代码
- python类定义的讲解
- 使用python分析gitlog日志示例