HHOT 100（61~80）
前言
2023-7-2 10:25:40
推荐
HOT 100（1~20）【LeetCode】
HOT 100（21~40）【LeetCode】
HOT 100（41~60）【LeetCode】
207. 课程表【中等】
- 课程表
提示
中等
1.6K
相关企业
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的
。
提示：
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
拓扑排序
BFS
class Solution {
List<List<Integer>> edges;//有向图
int [] indeg;//入度
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges=new ArrayList<List<Integer>>();
for(int i=0;i<numCourses;i++){
edges.add(new ArrayList<Integer>());
}
indeg=new int[numCourses];
for(int[] info:prerequisites){
edges.get(info[1]).add(info[0]);
indeg[info[0]]++;
}
//拓扑排序
Queue<Integer> queue = new LinkedList<Integer>();
for(int i=0;i<numCourses;i++){
if(indeg[i]==0){
queue.offer(i);
}
}
//广度优先搜索
int visited=0;
while(!queue.isEmpty()){
visited++;
int u=queue.poll();
for(int v:edges.get(u)){
indeg[v]--;
if(indeg[v]==0){
queue.offer(v);
}
}
}
return visited==numCourses;
}
}
参考
dfs
class Solution {
List<List<Integer>> edges;//有向图
int[] visited;
boolean valid=true;
public boolean canFinish(int numCourses, int[][] prerequisites) {
edges=new ArrayList<List<Integer>>();
for(int i=0;i<numCourses;i++){
edges.add(new ArrayList<Integer>());
}
visited=new int[numCourses];
for(int[] info:prerequisites){
edges.get(info[1]).add(info[0]);
}
for(int i=0;i<numCourses&&valid;i++){
if(visited[i]==0){
dfs(i);
}
}
return valid;
}
public void dfs(int u){
visited[u]=1;
for(int v:edges.get(u)){
if(visited[v]==0){
dfs(v);
if(!valid){
return;
}
}else if(visited[v]==1){
valid=false;
return;
}
}
visited[u]=2;
}
}
208. 实现 Trie (前缀树)【中等】
208.实现 Trie (前缀树)
中等
1.5K
相关企业
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 True
trie.search("app"); // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app"); // 返回 True
提示：
1 <= word.length, prefix.length <= 2000
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
官方
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
215. 数组中的第K个最大元素【中等】
215.数组中的第K个最大元素
中等
2.2K
相关企业
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104
HashMap
class Solution {
public int findKthLargest(int[] nums, int k) {
Map<Integer, Integer> map = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < nums.length; i++) {
int pre = map.getOrDefault(nums[i], 0);
map.put(nums[i], ++pre);
}
Integer[] keys = new Integer[map.size()];
Integer[] values = new Integer[map.size()];
map.values().toArray(values);
map.keySet().toArray(keys);
int res = 0;
// int c = 0;
// for (int i = 0; i < values.length; i++) {
// if (c >= k) {
// break;
// }
// while (values[i] > 0) {
// values[i]--;
// c++;
// res = keys[i];
// }
// }
int sum=0;
int i=0;
for (i=0;i<values.length;i++){
sum+=values[i];
//刚好超过的临界值
if(sum>=k&&sum-values[i]<=k){
break;
}
}
res=keys[i];
return res;
}
}
221. 最大正方形【中等】
221.最大正方形
中等
1.5K
相关企业
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4
示例 2：
输入：matrix = [["0","1"],["1","0"]]
输出：1
示例 3：
输入：matrix = [["0"]]
输出：0
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’
参考
class Solution {
//暴力解法
public int maximalSquare(char[][] matrix) {
int rows=matrix.length;
int columns=matrix[0].length;
if(rows==0||columns==0){
return 0;
}
int maxSide=0;
for(int i=0;i<rows;i++){
for(int j=0;j<columns;j++){
//左上角=1
if(matrix[i][j]=='1'){
maxSide=Math.max(maxSide,1);
//可能的最大正方形边长
int currentMaxSide=Math.min(rows-i,columns-j);
for(int k=1;k<currentMaxSide;k++){
boolean flag=true;
//右下角
if(matrix[i+k][j+k]=='0'){
break;
}
//外一环
for(int m=0;m<k;m++){
if(matrix[i+k][j+m]=='0'||matrix[i+m][j+k]=='0'){
flag=false;
break;
}
}
if(flag){
maxSide=Math.max(maxSide,k+1);
}else{
break;
}
}
}
}
}
int maxSquare=maxSide*maxSide;
return maxSquare;
}
}
参考
动态规划文章来源：https://www.toymoban.com/news/detail-523705.html
class Solution {
//动态规划
public int maximalSquare(char[][] matrix) {
int rows=matrix.length;
int columns=matrix[0].length;
if(rows==0||columns==0){
return 0;
}
int maxSide=0;
int[][] dp=new int[rows][columns];
for(int i=0;i<rows;i++){
for(int j=0;j<columns;j++){
if(matrix[i][j]=='1'){
if(i==0||j==0){
dp[i][j]=1;
}else{
dp[i][j]=Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1]))+1;
}
maxSide=Math.max(maxSide,dp[i][j]);
}
}
}
int maxSquare=maxSide*maxSide;
return maxSquare;
}
}
226. 翻转二叉树【简单】
226.翻转二叉树
简单
1.6K
相关企业
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
C语言
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct TreeNode* left = invertTree(root->left);
struct TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
递归
/**
* 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 TreeNode invertTree(TreeNode root) {
if (root==null){
return null;
}
TreeNode tmp=root.left;
root.left=root.right;
root.right=tmp;
invertTree(root.left);
invertTree(root.right);
return root;
}
}
234. 回文链表【简单】
- 回文链表
简单
1.7K
相关企业
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
转为List 左右指针
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
//转换为数组
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> list=new ArrayList();
while(head!=null){
list.add(head.val);
head=head.next;
}
int left=0;
int right=list.size()-1;
while(left<=right){
if(list.get(left)!=list.get(right)){
return false;
}
left++;
right--;
}
return true;
}
}
236. 二叉树的最近公共祖先【中等】
- 二叉树的最近公共祖先
中等
2.3K
相关企业
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
参考
dfs
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private TreeNode ans;
public Solution(){
this.ans=null;
}
//递归
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
this.dfs(root,p,q);
return this.ans;
}
public boolean dfs(TreeNode root,TreeNode p, TreeNode q){
if(root==null){
return false;
}
boolean lson=dfs(root.left,p,q);
boolean rson=dfs(root.right,p,q);
if((lson&&rson)||((root.val==p.val||root.val==q.val)&&(lson||rson))){
ans=root;
}
return lson||rson||(root.val == p.val || root.val == q.val);
}
}
238. 除自身以外数组的乘积【中等】
238.除自身以外数组的乘积
中等
1.5K
相关企业
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
自己
判断数组中有几个0
class Solution {
public int[] productExceptSelf(int[] nums) {
int [] answer=new int[nums.length];
int product=1;
int zeroCount=0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
zeroCount++;
}else{
product*=nums[i];
}
}
for(int i=0;i<nums.length;i++){
if(zeroCount>0){
if(nums[i]!=0){
answer[i]=0;
}else{
if(zeroCount>1){
answer[i]=0;
}else{
answer[i]=product;
}
}
}else{
answer[i]=product/nums[i];
}
}
return answer;
}
}
参考
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] L=new int[nums.length];
int[] R=new int[nums.length];
L[0]=1;
R[nums.length-1]=1;
for(int i=0,j=nums.length-1;i<nums.length&&j>=0;i++,j--){
if(i!=0){
L[i]=L[i-1]*nums[i-1];
}
if(j!=nums.length-1){
R[j]=R[j+1]*nums[j+1];
}
}
int[] res=new int[nums.length];
for(int i=0;i<nums.length;i++){
res[i]=L[i]*R[i];
}
return res;
}
}
239. 滑动窗口最大值【困难】
239.滑动窗口最大值
提示
困难
2.4K
相关企业
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
参考
堆（优先队列）
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n=nums.length;
//优先队列 存储[元素和下标]
PriorityQueue<int []>pq=new PriorityQueue<int []>(new Comparator<int []>(){
public int compare(int[] pair1,int[] pair2){
return pair1[0]!=pair2[0]?pair2[0]-pair1[0]:pair2[1]-pair1[1];
}
});
//初始优先队列 初始窗口的值
for(int i=0;i<k;i++){
pq.offer(new int[]{nums[i],i});
}
int[] ans=new int[n-k+1];
ans[0]=pq.peek()[0];
for(int i=k;i<n;i++){
pq.offer(new int[]{nums[i],i});//加入
while(pq.peek()[1]<=i-k){//出现在滑动窗口的最左侧
pq.poll();//弹出
}
ans[i-k+1]=pq.peek()[0];
}
return ans;
}
}
参考
单调队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n=nums.length;
Deque<Integer> deque=new LinkedList<Integer>();
//初始化 初始窗口
for(int i=0;i<k;i++){
//当前遍历的值大于队尾，逐出
while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){
deque.pollLast();//直到递增
}
//加入目前递减队列
deque.offerLast(i);
}
int[] ans=new int[n-k+1];
ans[0]=nums[deque.peekFirst()];//初始窗口的最大值
for(int i=k;i<n;i++){
//当前遍历的值大于队尾，逐出
while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){
deque.pollLast();//直到递增
}
//加入目前递减队列
deque.offerLast(i);
//最大值到了窗口的最左边了
while(deque.peekFirst()<=i-k){
deque.pollFirst();
}
ans[i-k+1]=nums[deque.peekFirst()];
}
return ans;
}
}
240. 搜索二维矩阵 II【中等】
240.搜索二维矩阵 II
中等
1.3K
相关企业
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109
https://yzhyaa.blog.csdn.net/article/details/114109714
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
// 得到右上角位置，i行j列
int i = 0, j = n - 1;
while (i < m && j >= 0) {
if(target<matrix[i][j]) j--;
else if(target==matrix[i][j]) return true;
else i++;
}
return false;
}
}
253. 会议室 II【中等】
Plus
279. 完全平方数【中等】
- 完全平方数
中等
1.7K
相关企业
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
官方
动态规划
class Solution {
public int numSquares(int n) {
int[] f=new int[n+1];
for(int i=1;i<=n;i++){
int minn=Integer.MAX_VALUE;
for(int j=1;j*j<=i;j++){
minn=Math.min(minn,f[i-j*j]);
}
f[i]=minn+1;
}
return f[n];
}
}
283. 移动零【简单】
283.移动零
简单
2K
相关企业
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
进阶：你能尽量减少完成的操作次数吗？
class Solution {
public void moveZeroes(int[] nums) {
int n=nums.length;
int j=0;
for(int i=0;i<n;i++){
if(nums[i]!=0){
nums[j++]=nums[i];
}
}
for(;j<n;j++){
nums[j]=0;
}
}
}
双指针
class Solution {
public void moveZeroes(int[] nums) {
int n=nums.length;
int left=0;
int right=0;
while(right<n){
if(nums[right]!=0){
swap(nums,left,right);
left++;
}
right++;
}
}
public void swap(int[] nums,int left,int right){
int tmp=nums[left];
nums[left]=nums[right];
nums[right]=tmp;
}
}
287. 寻找重复数【中等】
给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
提示：
1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
自己-计数器
class Solution {
public int findDuplicate(int[] nums) {
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int pre=map.getOrDefault(nums[i],0);
map.put(nums[i],++pre);
}
for (Map.Entry<Integer, Integer> integerIntegerEntry : map.entrySet()) {
if(integerIntegerEntry.getValue()>1){
return integerIntegerEntry.getKey();
}
}
return 0;
}
}
自己-优化
class Solution {
public int findDuplicate(int[] nums) {
HashMap<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++){
int pre=map.getOrDefault(nums[i],0);
if(pre!=0){
return nums[i];
}
map.put(nums[i],++pre);
}
return 0;
}
}
参考
双指针
静态链表
class Solution {
//快慢指针--Floyd 判圈算法
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
//直到相遇
do {
slow = nums[slow];//跳一步
fast = nums[nums[fast]];//跳两步
} while (slow != fast);
//起点出发
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
297. 二叉树的序列化与反序列化【困难】
297.二叉树的序列化与反序列化
困难
1.1K
相关企业
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
提示：
树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000
参考
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return rserialize(root,"");
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] dataArray=data.split(",");
List<String> dataList=new LinkedList<String>(Arrays.asList(dataArray));
return rdeserialize(dataList);
}
public String rserialize(TreeNode root,String str) {
if(root==null){
str+="None,";
}else{
str+=str.valueOf(root.val)+",";
str=rserialize(root.left,str);
str=rserialize(root.right,str);
}
return str;
}
public TreeNode rdeserialize(List<String> dataList) {
if(dataList.get(0).equals("None")){
dataList.remove(0);
return null;
}
TreeNode root=new TreeNode(Integer.valueOf(dataList.get(0)));
dataList.remove(0);
root.left=rdeserialize(dataList);
root.right=rdeserialize(dataList);
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
300. 最长递增子序列【中等】
300.最长递增子序列
中等
3.2K
相关企业
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?
参考
动态规划
class Solution {
public int lengthOfLIS(int[] nums) {
int len=nums.length;
int[] dp=new int[len];
dp[0]=1;
int maxans=1;
for(int i=1;i<len;i++){
dp[i] = 1;
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
}
}
maxans=Math.max(maxans,dp[i]);
}
return maxans;
}
}
301. 删除无效的括号【困难】
301.删除无效的括号
困难
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1：
输入：s = "()())()"
输出：["(())()","()()()"]
示例 2：
输入：s = "(a)())()"
输出：["(a())()","(a)()()"]
示例 3：
输入：s = ")("
输出：[""]
提示：
1 <= s.length <= 25
s 由小写英文字母以及括号 ‘(’ 和 ‘)’ 组成
s 中至多含 20 个括号
class Solution {
private List<String> res = new ArrayList<String>();
public List<String> removeInvalidParentheses(String s) {
int lremove = 0;
int rremove = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
lremove++;
} else if (s.charAt(i) == ')') {
if (lremove == 0) {
rremove++;
} else {
lremove--;
}
}
}
helper(s, 0, 0, 0, lremove, rremove);
return res;
}
private void helper(String str, int start, int lcount, int rcount, int lremove, int rremove) {
if (lremove == 0 && rremove == 0) {
if (isValid(str)) {
res.add(str);
}
return;
}
for (int i = start; i < str.length(); i++) {
if (i != start && str.charAt(i) == str.charAt(i - 1)) {
continue;
}
// 如果剩余的字符无法满足去掉的数量要求，直接返回
if (lremove + rremove > str.length() - i) {
return;
}
// 尝试去掉一个左括号
if (lremove > 0 && str.charAt(i) == '(') {
helper(str.substring(0, i) + str.substring(i + 1), i, lcount, rcount, lremove - 1, rremove);
}
// 尝试去掉一个右括号
if (rremove > 0 && str.charAt(i) == ')') {
helper(str.substring(0, i) + str.substring(i + 1), i, lcount, rcount, lremove, rremove - 1);
}
if (str.charAt(i) == ')') {
lcount++;
} else if (str.charAt(i) == ')') {
rcount++;
}
// 当前右括号的数量大于左括号的数量则为非法,直接返回.
if (rcount > lcount) {
break;
}
}
}
private boolean isValid(String str) {
int cnt = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
cnt++;
} else if (str.charAt(i) == ')') {
cnt--;
if (cnt < 0) {
return false;
}
}
}
return cnt == 0;
}
}
309. 最佳买卖股票时机含冷冻期【中等】
309.最佳买卖股票时机含冷冻期
中等
1.5K
相关企业
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:
输入: prices = [1]
输出: 0
提示：
1 <= prices.length <= 5000
0 <= prices[i] <= 1000
参考
动态规划
class Solution {
//动态规划-参考
public int maxProfit(int[] prices) {
int n=prices.length;
int f[][]=new int[n][3];
for(int i=0;i<n;i++){
for(int j=0;j<3;j++){
if(i==0){
f[i][0]=-prices[0];
f[i][1]=0;
f[i][2]=0;
}else{
f[i][0]=Math.max(f[i-1][0],f[i-1][2]-prices[i]);
f[i][1]=f[i-1][0]+prices[i];
f[i][2]=Math.max(f[i-1][1],f[i-1][2]);
}
}
}
return Math.max(f[n-1][1],f[n-1][2]);
}
}
312. 戳气球【困难】
312.戳气球
困难
1.3K
相关企业
有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
求所能获得硬币的最大数量。
示例 1：
输入：nums = [3,1,5,8]
输出：167
解释：
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins = 3*1*5 + 3*5*8 + 1*3*8 + 1*8*1 = 167
示例 2：
输入：nums = [1,5]
输出：10
提示：
n == nums.length
1 <= n <= 300
0 <= nums[i] <= 100
参考
递归
class Solution {
public int[][] rec;//记忆化搜索，结果保存 相当于缓存
public int[] val;
public int maxCoins(int[] nums) {
//初始化
int n=nums.length;
val=new int[n+2];
for(int i=1;i<=n;i++){
val[i]=nums[i-1];
}
val[0]=val[n+1]=1;
rec=new int[n+2][n+2];
for(int i=0;i<=n+1;i++){//赋值-1 没有计算出结果
Arrays.fill(rec[i],-1);
}
return solve(0,n+1);
}
//二分法递归
public int solve(int left,int right){
if(left>=right-1){
return 0;
}
//没有记忆
if(rec[left][right]!=-1){
return rec[left][right];
}
//进行计算
for(int i=left+1;i<right;i++){
int sum=val[left]*val[i]*val[right];
sum+=solve(left,i)+solve(i,right);
rec[left][right]=Math.max(rec[left][right],sum);
}
return rec[left][right];
}
}
参考
动态规划
class Solution {
public int[][] rec;//记忆化搜索，结果保存 相当于缓存
public int[] val;
public int maxCoins(int[] nums) {
//初始化
int n=nums.length;
val=new int[n+2];
for(int i=1;i<=n;i++){
val[i]=nums[i-1];
}
val[0]=val[n+1]=1;
rec=new int[n+2][n+2];
//动态规划
for(int i=n-1;i>=0;i--){//从前往后
for(int j=i+2;j<=n+1;j++){//从后往前
for(int k=i+1;k<j;k++){//遍历中间
int sum=val[i]*val[k]*val[j];
sum+=rec[i][k]+rec[k][j];
rec[i][j]=Math.max(rec[i][j],sum);
}
}
}
return rec[0][n+1];
}
}
322. 零钱兑换【中等】
322.零钱兑换
中等
2.5K
相关企业
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
参考
动态规划
class Solution {
public int coinChange(int[] coins, int amount) {
int max=amount+1;
int[] dp=new int[amount+1];
Arrays.fill(dp,max);
//初始化
dp[0]=0;
for(int i=1;i<=amount;i++){
for(int j=0;j<coins.length;j++){
if(coins[j]<=i){
dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount]>amount?-1:dp[amount];
}
}
最后
2023-7-2 10:43:44文章来源地址https://www.toymoban.com/news/detail-523705.html
到了这里，关于HOT 100（61~80）【LeetCode】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
