当前位置:网站首页>Li Kou daily question 1 (2)
Li Kou daily question 1 (2)
2022-07-06 08:50:00 【Baby paper d】
Persimmons should always be picked up and pinched soft , The daily question must also be written from the simplest . Probably just because it started , Just don't want to give up . Simple though , Stick to it, too , Is it just an effort to show yourself ? Perhaps my so-called insistence is also quite ridiculous .
It's just , How happy how to come .
One 、5.28 Remove the outermost bracket
The main idea of the topic : A set of strings , It consists of several characters , It contains several sets of parentheses , The requirement of this question is to delete the outermost parentheses of each group in the string , Output the remaining string .
analysis : It matches the parentheses almost , You need to use a stack to save parentheses , You also need another string to hold the output .
class Solution:
def removeOuterParentheses(self, s: str) -> str:
stack = []
res = ''
for i in s:
# First judge whether there is a right bracket , If you have any , Then output its left bracket
if i == ')':
stack.pop()
# If the stack is not empty , It means that it is not the outermost character , Is added to the result string
if stack:
res += i
# If left parenthesis , Add to the stack
if i == '(':
stack.append(i)
return res
Two 、5.25 The unique substring in the surround string
The main idea of the topic : Given a set of strings p, Judgment string p in a-z-a-z The number of non empty substrings in the circular string , namely p The substring of is in the circular string . Involving dynamic programming , Nor is it simply seeking the longest substring , Because we just find the number of non empty substrings .
I still don't understand dynamic planning , We can't draw inferences from one instance , Just remember that this problem is solved like this , My understanding ability is not good , Have a chance , Have a chance to have a good look , It is important to understand the process of Dynamic Planning . And sliding windows .
class Solution:
def findSubstringInWraproundString(self, p: str) -> int:
dp = defaultdict(int)
# k Used to record the number of consecutive characters
k = 0
for i, ch in enumerate(p):
# The difference between characters is 1 or -25
if i > 0 and (ord(ch) - ord(p[i - 1])) % 26 == 1:
k += 1
else:
k = 1
# dp Is used to record the longest substring ending with the current character
dp[ch] = max(dp[ch], k)
# That's going to be dp All values in add up , It's just a string p Number of all substrings in
return sum(dp.values())
3、 ... and 、5.24 Single valued binary trees
The main idea of the topic : Determine whether all values of the binary tree are the same , If the same , return True, otherwise False.
analysis : Breadth first search BFS, Depth-first search DFS Fine , Just traverse the binary tree once .
Breadth first search : You need to complete the search with the help of queues .
There is no need to determine which layer to traverse :
# 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;
# Traverse the nodes of the current layer
q.append(cur.left)
q.append(cur.right)
return True
Depth-first search : There are three kinds of , The first sequence traversal 、 In the sequence traversal 、 After the sequence traversal , Let's take preorder traversal as an example
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)
Four 、 In the length of 2N To find out the repetition N Secondary elements
The main idea of the topic : Given an array , The length is 2N, Among them is N+1 Elements , And just one element repeats N Time , Ask for repetition N The next element .
analysis : There's a repetition of an element N Time , And there are N+1 Elements , The length is 2N, Then other elements only appear once . Traverse one side of the array to count and find . Or use hash table ( It is a set of key value structures ), Count .
class Solution:
def repeatedNTimes(self, nums: List[int]) -> int:
# # Traversal count
# 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
# Hash
found = set()
for i in nums:
if i in found:
return i
found.add(i)
边栏推荐
- C语言双指针——经典题型
- [MySQL] limit implements paging
- UML图记忆技巧
- Crash problem of Chrome browser
- Cesium draw points, lines, and faces
- R language ggplot2 visualization: place the title of the visualization image in the upper left corner of the image (customize Title position in top left of ggplot2 graph)
- Hutool gracefully parses URL links and obtains parameters
- LeetCode:剑指 Offer 03. 数组中重复的数字
- LeetCode:498. 对角线遍历
- Marathon envs project environment configuration (strengthen learning and imitate reference actions)
猜你喜欢
Alibaba cloud server mining virus solution (practiced)
被破解毁掉的国产游戏之光
游戏解包的危害及资源加密的重要性
Fairguard game reinforcement: under the upsurge of game going to sea, game security is facing new challenges
Detailed explanation of dynamic planning
visdom可视化实现与检查介绍
PC easy to use essential software (used)
Simple use of promise in uniapp
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Excellent software testers have these abilities
随机推荐
What are the common processes of software stress testing? Professional software test reports issued by companies to share
Tdengine biweekly selection of community issues | phase III
电脑清理,删除的系统文件
FairGuard游戏加固:游戏出海热潮下,游戏安全面临新挑战
广州推进儿童友好城市建设,将探索学校周边200米设安全区域
View computer devices in LAN
Computer cleaning, deleted system files
自动化测试框架有什么作用?上海专业第三方软件测试公司安利
个人电脑好用必备软件(使用过)
C語言雙指針——經典題型
Esp8266-rtos IOT development
Current situation and trend of character animation
【ROS】usb_cam相机标定
[NVIDIA development board] FAQ (updated from time to time)
Simple use of promise in uniapp
Problems in loading and saving pytorch trained models
优秀的软件测试人员,都具备这些能力
Hutool gracefully parses URL links and obtains parameters
LeetCode:26. 删除有序数组中的重复项
Navicat Premium 创建MySql 创建存储过程