python 刷 leetcode 题目(35)
程序员文章站
2024-03-21 17:15:40
...
75. 分类颜色
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
进阶:
- 一个直观的解决方案是使用计数排序的两趟扫描算法。
首先,迭代计算出0、1 和 2 元素的个数,然后按照0、1、2的排序,重写当前数组。 - 你能想出一个仅使用常数空间的一趟扫描算法吗?
代码如下;
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
#### the first method
# return nums.sort()
#### the second method
count0, count1, count2 = 0,0,0
for num in nums:
if num == 0:
count0 += 1
elif num == 1:
count1 += 1
else:
count2 += 1
for i in range(count0):
nums[i] = 0
for j in range(count1):
nums[count0 + j] = 1
for k in range(count2):
nums[count0 + count1 + k] = 2
生成括号
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
思路: 采用DFS方法进行递归 搜索
代码;
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
res = []
self.generate(n, n, "", res)
return res
def generate(self, left, right, str, res):
if left == 0 and right == 0:
res.append(str)
return
if left > 0:
self.generate(left - 1, right, str + '(', res)
if right > left:
self.generate(left, right - 1, str + ')', res)
推荐阅读
-
python 刷 leetcode 题目(35)
-
LeetCode刷题(90)~圆形赛道上经过次数最多的扇区【第203场周赛:题目一】
-
LeetCode刷题(0010)---9. 回文数,python
-
LeetCode 题目-671. 二叉树中第二小的节点/687.最长同值路径(python实现)
-
Leetcode---栈系列刷题(python3实现)----#20有效的括号
-
0223leetcode刷题5道python
-
[LeetCode][Python]刷题记录 1. 两数之和
-
荐 【小白用python刷Leetcode】32. 最长有效括号
-
【小白用python刷Leetcode】44.通配符匹配
-
力扣 (LeetCode)python刷题笔记8. 字符串转换整数 (atoi)