2024.4.27——LeetCode 高频题复盘

2024-04-28 20:12
文章标签 leetcode 27 复盘 高频 2024.4

本文主要是介绍2024.4.27——LeetCode 高频题复盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 102. 二叉树的层序遍历
  • 33. 搜索旋转排序数组
  • 121. 买卖股票的最佳时机
  • 200. 岛屿数量
  • 20. 有效的括号
  • 88. 合并两个有序数组
  • 141. 环形链表
  • 46. 全排列
  • 236. 二叉树的最近公共祖先

102. 二叉树的层序遍历


题目链接

Python

方法一

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []res=[]queue=[root]while queue:level_value=[]for _ in range(len(queue)):node=queue.pop(0)level_value.append(node.val)if node.left:queue.append(node.left)if node.right:queue.append(node.right)res.append(level_value)return res

方法二

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:if not root:return []res=[]parent=[root]while parent:res.append([node.val for node in parent])child=[]for node in parent:if node.left:child.append(node.left)if node.right:child.append(node.right)parent=childreturn res

Java

方法一

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<>();queue.add(root);while (!queue.isEmpty()) {List<Integer> levelValue = new ArrayList<>();int levelSize = queue.size();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll(); levelValue.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}res.add(levelValue);}return res;}
}

方法二

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();if (root == null) {return res;}Queue<TreeNode> currentLevel = new LinkedList<>();currentLevel.add(root);while (!currentLevel.isEmpty()) {List<Integer> levelValues = new ArrayList<>();Queue<TreeNode> nextLevel = new LinkedList<>();while (!currentLevel.isEmpty()) {TreeNode node = currentLevel.poll();levelValues.add(node.val);if (node.left != null) {nextLevel.add(node.left);}if (node.right != null) {nextLevel.add(node.right);}}res.add(levelValues);currentLevel = nextLevel;}return res;}
}

33. 搜索旋转排序数组


题目链接

Python

class Solution:def search(self, nums: List[int], target: int) -> int:l,r=0,len(nums)-1while l<=r:mid=(l+r)//2if target==nums[mid]:return midif nums[l]<=nums[mid]: # 左半部分有序if nums[l]<=target<nums[mid]:r=mid-1else:l=mid+1else: # 右半部分有序if nums[mid]<target<=nums[r]:l=mid+1else:r=mid-1return -1

Java

public class Solution {public int search(int[] nums, int target) {int l = 0, r = nums.length - 1;while (l <= r) {int mid = l + (r - l) / 2;if (nums[mid] == target) {return mid;}if (nums[l] <= nums[mid]) {if (nums[l] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[r]) {l = mid + 1;} else {r = mid - 1;}}}return -1; }
}

121. 买卖股票的最佳时机


题目链接

Python

class Solution:def maxProfit(self, prices: List[int]) -> int:# 每一天的股票都有两种状态：dp[i][0]不持有,dp[i][1]持有dp=[[0,0] for _ in range(len(prices))]dp[0][1]=-prices[0]for i in range(1,len(prices)):dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]) # 不持有dp[i][1]=max(dp[i-1][1],-prices[i]) # 持有return dp[len(prices)-1][0]

Java

public class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];dp[0][1] = -prices[0];  for (int i = 1; i < n; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 不持有dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);              // 持有}// 最后一天不持有股票的情况即为最大利润return dp[n - 1][0];}
}

200. 岛屿数量


题目链接

Python

DFS 解法

class Solution:def numIslands(self, grid: List[List[str]]) -> int:def dfs(x,y):visited[x][y]=True # 核心for d in dirs:nx=x+d[0]ny=y+d[1]if 0<=nx<m and 0<=ny<n and not visited[nx][ny] and grid[x][y]=='1':dfs(nx,ny)m,n=len(grid),len(grid[0])visited=[[False]*n for _ in range(m)]dirs=[(-1,0),(1,0),(0,-1),(0,1)] # 上下左右res=0for i in range(m):for j in range(n):if not visited[i][j] and grid[i][j]=='1':res+=1dfs(i,j) # 将与其连接的陆地都标记为True（已经访问过）return res

BFS 解法

class Solution:from collections import dequedef numIslands(self, grid: List[List[str]]) -> int:def bfs(x,y):q=deque()q.append((x,y))visited[x][y]=Truewhile q:x,y=q.popleft()for d in dirs:nx,ny=x+d[0],y+d[1]if 0<=nx<m and 0<=ny<n and not visited[nx][ny] and grid[x][y]=='1':q.append((nx,ny))visited[nx][ny]=Truem,n=len(grid),len(grid[0])visited=[[False]*n for _ in range(m)]dirs=[(-1,0),(1,0),(0,-1),(0,1)] # 上下左右res=0for i in range(m):for j in range(n):if not visited[i][j] and grid[i][j]=='1':res+=1bfs(i,j) # 将与其连接的陆地都标记为True（已经访问过）return res

Java

DFS 解法

public class Solution {public int numIslands(char[][] grid) {int m = grid.length;int n = grid[0].length;boolean[][] visited = new boolean[m][n];int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右int res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == '1') {res++;dfs(grid, visited, i, j, dirs);}}}return res;}private void dfs(char[][] grid, boolean[][] visited, int x, int y, int[][] dirs) {visited[x][y] = true;int m = grid.length;int n = grid[0].length;for (int[] d : dirs) {int nx = x + d[0];int ny = y + d[1];if (0 <= nx && nx < m && 0 <= ny && ny < n && !visited[nx][ny] && grid[nx][ny] == '1') {dfs(grid, visited, nx, ny, dirs);}}}
}

BFS 解法

public class Solution {public int numIslands(char[][] grid) {int m = grid.length;int n = grid[0].length;boolean[][] visited = new boolean[m][n];int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右int res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (!visited[i][j] && grid[i][j] == '1') {res++;bfs(grid, visited, i, j, dirs);}}}return res;}private void bfs(char[][] grid, boolean[][] visited, int x, int y, int[][] dirs) {int m = grid.length;int n = grid[0].length;Queue<int[]> queue = new LinkedList<>();queue.add(new int[]{x, y});visited[x][y] = true;while (!queue.isEmpty()) {int[] point = queue.poll();int curX = point[0];int curY = point[1];for (int[] d : dirs) {int nx = curX + d[0];int ny = curY + d[1];if (0 <= nx && nx < m && 0 <= ny && ny < n && !visited[nx][ny] && grid[nx][ny] == '1') {queue.add(new int[]{nx, ny});visited[nx][ny] = true;}}}}
}

20. 有效的括号


题目链接

class Solution:def isValid(self, s: str) -> bool:if len(s)%2!=0:return Falsedic={")":"(","}":"{","]":"["}stack=[]for c in s:# 右括号都看栈里面是否有相应的左括号if c in dic:# 栈里面没有对应的左括号if not stack or stack[-1]!=dic[c]:return False# 栈里面有对应的左括号，成对的左右括号相消else:stack.pop()# 左括号都入栈else:stack.append(c)return not stack

Java

class Solution {public boolean isValid(String s) {if (s.length()%2!=0){return false;}HashMap<Character,Character> hashmap=new HashMap<>();hashmap.put(')','(');hashmap.put('}','{');hashmap.put(']','[');Stack<Character> stack=new Stack<>();for (char c:s.toCharArray()){if (hashmap.containsKey(c)){if (stack.isEmpty() || stack.peek()!=hashmap.get(c)){return false;}else{stack.pop();}}else{stack.push(c);}}return stack.isEmpty();}
}

88. 合并两个有序数组


题目链接

Python

class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""p1,p2=m-1,n-1tail=m+n-1while p1>=0 or p2>=0:if p1==-1:nums1[tail]=nums2[p2]p2-=1elif p2==-1:nums1[tail]=nums1[p1]p1-=1elif nums1[p1]<=nums2[p2]:nums1[tail]=nums2[p2]p2-=1else:nums1[tail]=nums1[p1]p1-=1tail-=1

Java

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int p1=m-1;int p2=n-1;int tail=m+n-1;while (p1>=0 || p2>=0){if (p1==-1){nums1[tail]=nums2[p2];p2-=1;}else if (p2==-1){nums1[tail]=nums1[p1];p1-=1;}else if (nums1[p1]<=nums2[p2]){nums1[tail]=nums2[p2];p2-=1;}else{nums1[tail]=nums2[p1];p1-=1;}tail-=1;}}
}

141. 环形链表


题目链接

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def hasCycle(self, head: Optional[ListNode]) -> bool:slow,fast=head,headwhile fast and fast.next:slow=slow.nextfast=fast.next.nextif slow==fast:return Truereturn False

Java

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow=head;ListNode fast=head;while (fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;if(slow==fast){return true;}}return false;}
}

注意：在Java中，while (fast != null && fast.next != null)不能写成 while (fast && fast.next) 这种语法。Java 对布尔表达式的要求是明确且严格的，它要求表达式明确地返回一个布尔值。

46. 全排列


题目链接

Python

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:path=[]res=[]def backtracing(nums,used):if len(path)==len(nums):res.append(path[:])for i in range(len(nums)):if not used[i]:path.append(nums[i])used[i]=Truebacktracing(nums,used)used[i]=Falsepath.pop()used=[False]*(len(nums))backtracing(nums,used)return res

Java

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();boolean[] used =new boolean[nums.length];backtracking(nums,used,path,res);return res;}public void backtracking(int[] nums,boolean[] used, List<Integer> path,List<List<Integer>> res){if (path.size()==nums.length){res.add(new ArrayList<>(path));}for(int i=0;i<nums.length;i++){if (!used[i]){path.add(nums[i]);used[i]=true;backtracking(nums,used,path,res);used[i]=false;path.remove(path.size()-1);}}}
}

注意：Java写法中 path.remove(path.size()-1);不能写成 path.remove(nums[i]);。因为nums[i]是基本类型，Java 实际上会将 nums[i] 视为一个整数，并尝试将其作为索引来移除 path 列表中对应索引处的元素。如果确实需要根据值来移除元素，并且该值是一个对象（这里是 Integer）path.remove(Integer.valueOf(nums[i])); // 创建一个Integer对象，并尝试移除这个对象

236. 二叉树的最近公共祖先


题目链接

Python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root or p==root or q==root:return root# 后序遍历left=self.lowestCommonAncestor(root.left,p,q)right=self.lowestCommonAncestor(root.right,p,q)if left and right:return rootelif not left and right:return rightelif not right and left:return leftelse:return

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root==null || p==root || q==root){return root;}TreeNode left = lowestCommonAncestor(root.left,p,q);TreeNode right = lowestCommonAncestor(root.right,p,q);if (left!=null && right!=null){return root;}else if (left!=null && right==null){return left;}else if (left==null && right!=null){return right;}else{return null;}}
}

注意：在Java中，不能使用 and 和 or 这样的关键字来表示逻辑运算。Java使用符号 &&（逻辑与）和 ||（逻辑或）来执行逻辑运算。

这篇关于2024.4.27——LeetCode 高频题复盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/944149。

相关文章

SpringBoot启动报错的11个高频问题排查与解决终极指南

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突：NoSuchMethodError 的终极解法2. Bean注入失败：No qu
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
leetcode-24Swap Nodes in Pairs

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L
阅读更多...
leetcode-23Merge k Sorted Lists

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists
阅读更多...
C++ | Leetcode C++题解之第393题UTF-8编码验证

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目： 题解： class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
【JavaScript】LeetCode：16-20

【JavaScript】LeetCode：16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i，右指针j，从头遍历数组，若j指针指向的元素不在set中，则加入该元素，否则更新结果res，删除集合中i指针指向的元素，进入下一轮循环。 /*** @param
阅读更多...
树莓派5_opencv笔记27：Opencv录制视频（无声音）

树莓派5_opencv笔记27：Opencv录制视频（无声音）

今日继续学习树莓派5 8G：（Raspberry Pi，简称RPi或RasPi）  本人所用树莓派5 装载的系统与版本如下:  版本可用命令 (lsb_release -a) 查询: Opencv 与 python 版本如下： 今天就水一篇文章，用树莓派摄像头，Opencv录制一段视频保存在指定目录... 文章提供测试代码讲解，整体代码贴出、测试效果图 目录 阶段一：录制一段
阅读更多...
LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

LeetCode：64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵，找出只包含 1 的最大正方形，并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2