目录
- 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=child
return 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)-1
while l<=r:
mid=(l+r)//2
if target==nums[mid]:
return mid
if nums[l]<=nums[mid]: # 左半部分有序
if nums[l]<=target<nums[mid]:
r=mid-1
else:
l=mid+1
else: # 右半部分有序
if nums[mid]<target<=nums[r]:
l=mid+1
else:
r=mid-1
return -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=0
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j]=='1':
res+=1
dfs(i,j) # 将与其连接的陆地都标记为True（已经访问过）
return res
BFS 解法
class Solution:
from collections import deque
def numIslands(self, grid: List[List[str]]) -> int:
def bfs(x,y):
q=deque()
q.append((x,y))
visited[x][y]=True
while 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]=True
m,n=len(grid),len(grid[0])
visited=[[False]*n for _ in range(m)]
dirs=[(-1,0),(1,0),(0,-1),(0,1)] # 上下左右
res=0
for i in range(m):
for j in range(n):
if not visited[i][j] and grid[i][j]=='1':
res+=1
bfs(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 False
dic={
")":"(",
"}":"{",
"]":"["
}
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-1
tail=m+n-1
while p1>=0 or p2>=0:
if p1==-1:
nums1[tail]=nums2[p2]
p2-=1
elif p2==-1:
nums1[tail]=nums1[p1]
p1-=1
elif nums1[p1]<=nums2[p2]:
nums1[tail]=nums2[p2]
p2-=1
else:
nums1[tail]=nums1[p1]
p1-=1
tail-=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 = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow,fast=head,head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
return True
return 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]=True
backtracing(nums,used)
used[i]=False
path.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 = None
class 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 root
elif not left and right:
return right
elif not right and left:
return left
else:
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使用符号 &&（逻辑与）和 ||（逻辑或）来执行逻辑运算。
