当前位置:网站首页>力扣每日一题(二)
力扣每日一题(二)
2022-07-06 08:45:00 【孩纸D】
柿子总要捡软的捏,每日一题肯定也要从最简单的写起。大概只是因为开始了,就不想放弃罢了。虽然简单,也在坚持吧,是只给自己看的努力吗?或许自己所谓的坚持也蛮可笑的吧。
罢了罢了,怎么开心怎么来吧。
一、5.28删除最外层的括号
题目大意:一组字符串,由若干字符组成,其中包含若干组括号,而本题的要求就是将字符串中每组的最外围括号删除,输出剩下的字符串。
解析:跟括号匹配差不多,需要采用栈来保存括号,也需要另一个字符串来保存要输出的结果。
class Solution:
def removeOuterParentheses(self, s: str) -> str:
stack = []
res = ''
for i in s:
# 先判断是否有右括号,若有,则将其左括号输出
if i == ')':
stack.pop()
# 若栈不为空,则说明不是最外层字符,则添加到结果字符串中
if stack:
res += i
# 若为左括号,则添加到栈中
if i == '(':
stack.append(i)
return res
二、5.25环绕字符串中唯一的子字符串
题目大意:给定一组字符串p,判断字符串p中a-z-a-z循环字符串中非空子串的数量,即p的子串是在循环字符串中的。涉及到动态规划的,也不是单一的求最长子串,因为只是求非空子串的数量。
对于动态规划还是不那么理解的,不能举一反三,只是记着这个题是这样的解法,我的理解能力不行,有机会吧,有机会好好看看吧,理解动态规划的过程还是很重要的。还有滑动窗口。
class Solution:
def findSubstringInWraproundString(self, p: str) -> int:
dp = defaultdict(int)
# k用于记录连续字符的数量
k = 0
for i, ch in enumerate(p):
# 字符之差为 1 或 -25
if i > 0 and (ord(ch) - ord(p[i - 1])) % 26 == 1:
k += 1
else:
k = 1
# dp是用于记录以当前字符的结尾的最长子串
dp[ch] = max(dp[ch], k)
# 那就是将dp中的所有值加起来,就是字符串p中的所有子串数量
return sum(dp.values())
三、5.24单值二叉树
题目大意:判断二叉树是否所有值都相同,若相同,返回True,否则False。
解析:广度优先搜索BFS,深度优先搜索DFS都可以,只是遍历一遍二叉树。
广度优先搜索:需要借助于队列来完成搜索。
不需要确定遍历到哪一层:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isUnivalTree(self, root: TreeNode) -> bool:
q = deque()
q.append(root)
val = root.val
while q:
cur = q.popleft()
if not cur:
continue
if val != cur.val:
return False;
# 遍历当前层的节点
q.append(cur.left)
q.append(cur.right)
return True
深度优先搜索:有三种,先序遍历、中序遍历、后序遍历,下面以先序遍历为例
class Solution:
def isUnivalTree(self, root: TreeNode) -> bool:
return self.dfs(root, root.val)
def dfs(self, root, val):
if not root:
return True
if val != root.val:
return False
return self.dfs(root.left, val) and self.dfs(root.right, val)
四、在长度为2N的数组种找出重复N次的元素
题目大意:给定一个数组,长度为2N,其中有N+1个元素,且恰有一个元素重复了N次,要求找出重复N次的那个元素。
解析:有一个元素重复了N次,而且有N+1个元素,长度又为2N,那么其他元素都只出现了一次。遍历一边数组进行计数就找到了。或则采用哈希表(就是一组键值结构),进行计数。
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
# #遍历计数
# n = len(nums)/2
# flag = [0 for i in range(0, max(nums)+1)]
# for j in nums:
# flag[j] += 1
# if flag[j] == n:
# return j
# 哈希
found = set()
for i in nums:
if i in found:
return i
found.add(i)
边栏推荐
- C语言双指针——经典题型
- Roguelike game into crack the hardest hit areas, how to break the bureau?
- LeetCode:162. 寻找峰值
- R language ggplot2 visualization, custom ggplot2 visualization image legend background color of legend
- Generator parameters incoming parameters
- JVM quick start
- MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
- marathon-envs项目环境配置(强化学习模仿参考动作)
- egg. JS directory structure
- Crash problem of Chrome browser
猜你喜欢
JVM performance tuning and practical basic theory - Part 1
Tcp/ip protocol
ROS编译 调用第三方动态库(xxx.so)
C language double pointer -- classic question type
Deep anatomy of C language -- C language keywords
View computer devices in LAN
sublime text中conda环境中plt.show无法弹出显示图片的问题
Process of obtaining the electronic version of academic qualifications of xuexin.com
LeetCode:124. 二叉树中的最大路径和
Computer graduation design PHP Zhiduo online learning platform
随机推荐
FairGuard游戏加固:游戏出海热潮下,游戏安全面临新挑战
pcd转ply后在meshlab无法打开,提示 Error details: Unespected eof
LeetCode:394. 字符串解码
R language ggplot2 visualization, custom ggplot2 visualization image legend background color of legend
LeetCode:26. 删除有序数组中的重复项
poi追加写EXCEL文件
Restful API design specification
China's high purity aluminum target market status and investment forecast report (2022 Edition)
Sublime text using ctrl+b to run another program without closing other runs
Marathon envs project environment configuration (strengthen learning and imitate reference actions)
vb.net 随窗口改变,缩放控件大小以及保持相对位置
Guangzhou will promote the construction of a child friendly city, and will explore the establishment of a safe area 200 meters around the school
TDengine 社区问题双周精选 | 第三期
Visual implementation and inspection of visdom
JVM quick start
Hutool gracefully parses URL links and obtains parameters
MySQL learning records 12jdbc operation transactions
View computer devices in LAN
Modify the video name from the name mapping relationship in the table
ROS编译 调用第三方动态库(xxx.so)