21天养成编程习惯：Leetcode刷题第十五天

火币交易所 2022年10月21日 11:02 98 Connor

「青少年编程竞赛交流群」已成立（适合6至18周岁的青少年），公众号后台回复【Scratch】或【Python】，即可进入，如果加入了之前的社群不需要重复加入。进群之后大家可以参与每周日晚20:00的升级打怪活动以及每个月的青少年编程组队学习活动。

本期训练营根据孩子们对知识的掌握情况分成两个打卡群（Leetcode简单打卡群、Leetcode中等打卡群），每个打卡群针对不同需求的孩子，这就使得本次活动更具有针对性，对孩子学习编程帮助更大。

活动的时间从9月1日至9月21日，每天一道编程题。

参与的小朋友可以，让他邀请你到本次相应的打卡群并把本次的打卡题目发给你。

微信号：ProgrammingAssistant

Day15：169_求众数

难度：简单

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入：nums = [ 3, 2, 3]

输出： 3

示例 2:

输入：nums = [ 2, 2, 1, 1, 1, 2, 2]

展开全文

输出： 2

提示：

n == nums.length

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

实现

第一种：利用排序的方法

C# 语言

publicclassSolution

publicintMajorityElement( int[] nums)

nums = nums.OrderBy(a => a).ToArray;

returnnums[nums.Length / 2];

Python 语言

classSolution(object):

defmajorityElement(self, nums):

:type nums: List[int]

:rtype: int

nums.sort

returnnums[len(nums) // 2]

第二种：利用 Boyer-Moore 投票算法

寻找数组中超过一半的数字，这意味着数组中其他数字出现次数的总和都是比不上这个数字出现的次数。即如果把该众数记为 +1 ，把其他数记为 −1 ，将它们全部加起来，和是大于 0 的。

C# 语言

publicclassSolution

publicintMajorityElement( int[] nums)

intcandidate = nums[ 0];

intcount = 1;

for( inti = 1; i < nums.Length; i++)

if(count == 0)

candidate = nums[i];

count += (nums[i] == candidate) ? 1: - 1;

returncandidate;

Python 语言

classSolution(object):

defmajorityElement(self, nums):

:type nums: List[int]

:rtype: int

candidate = nums[ 0]

count = 1

fori inrange( 1, len(nums)):

ifcount == 0:

candidate = nums[i]

ifcandidate == nums[i]:

count += 1

else:

count += -1

returncandidate

Day15：95_不同的二叉搜索树II

难度：中等

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。

示例1：

输入：n = 3

输出：[[ 1,null, 2,null, 3],[ 1,null, 3, 2],[ 2, 1, 3],[ 3, 1,null,null, 2],[ 3, 2,null, 1]]

示例2：

输入：n = 1

输出：[[ 1]]

提示：

1 <= n <= 8

思路：递归。

如果将 i 作为根节点，那么 [1, i-1] 为 i 的左子树节点， [i+1, n] 为右子树节点。

问题就被拆分为两个子问题了：

求左区间构成的所有二叉搜索树作为 i 的左子树

求右区间构成的所有二叉搜索树作为 i 的右子树

求左区间构成的所有二叉搜索树作为 i 的左子树

求右区间构成的所有二叉搜索树作为 i 的右子树

递归终止条件：

区间为空，返回null。

区间的左右端点相同，即只包含一个数，返回该数构成的根结点。

区间为空，返回null。

区间的左右端点相同，即只包含一个数，返回该数构成的根结点。

以上就是利用递归求解该问题的思路。

C# 语言

* Definition for a binary tree node.

* public class TreeNode {

* public int val;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int x) { val = x; }

publicclassSolution

publicIList<TreeNode> GenerateTrees( intn)

if(n == 0)

returnnewList<TreeNode>;

returnGenerateTrees( 1, n);

publicList<TreeNode> GenerateTrees( intstart, intend)

List<TreeNode> lst = newList<TreeNode>;

//此时没有数字，将 null 加入结果中

if(start > end)

lst.Add( null);

returnlst;

//只有一个数字，当前数字作为一棵树加入结果中

if(start == end)

TreeNode tree = newTreeNode(start);

lst.Add(tree);

returnlst;

//尝试每个数字作为根节点

for( inti = start; i <= end; i++)

//得到所有可能的左子树

List<TreeNode> leftTrees = GenerateTrees(start, i - 1);

//得到所有可能的右子树

List<TreeNode> rightTrees = GenerateTrees(i + 1, end);

//左子树右子树两两组合

foreach (TreeNode leftTree in leftTrees)

foreach (TreeNode rightTree in rightTrees)

TreeNode root = newTreeNode(i);

root.left = leftTree;

root.right = rightTree;

//加入到最终结果中

lst.Add(root);

returnlst;

Python 语言

# Definition for a binary tree node.

# class TreeNode(object):

# def __init__(self, val=0, left=None, right=None):

# self.val = val

# self.left = left

# self.right = right

classSolution(object):

defgenerateTrees(self, n):

:type n: int

:rtype: List[TreeNode]

ifn == 0:

returnlist

returnself.generate( 1, n)

defgenerate(self, start, end):

lst = list

ifstart > end:

lst.append( None)

returnlst

ifstart == end:

tree = TreeNode(start)

lst.append(tree)

returnlst

fori inrange(start, end + 1):

leftTrees = self.generate(start, i - 1)

rightTrees = self.generate(i + 1, end)

forleftTree inleftTrees:

forrightTree inrightTrees:

tree = TreeNode(i)

tree.left = leftTree

tree.right = rightTree

lst.append(tree)

returnlst

青少年编程升级打怪计划

把电子学会的青少年编程能力等级测评作为游戏的关卡，带着小朋友们升级打怪。

每周日晚20:00，利用腾讯会议进行直播分享，之后安排一个测试（与等级测评的题目数量一致）考察小朋友们对知识的掌握情况。

为了，让各个阶段的小朋友都能参与到学习中，我们每个月都会组织Scratch、Python、C++的青少年编程学习活动，为小朋友们三助力，即学习编程助力、实践知识助力、结识伙伴助力。

一键三连，一起学习⬇️

innodb 是如何存数据的？

4 行代码写 3 个NPE异常

发表评论

21天养成编程习惯：Leetcode刷题第十五天

innodb 是如何存数据的？

4 行代码写 3 个NPE异常

最新留言

标签列表