当前位置：网站首页>LeetCode热题 HOT52-100
LeetCode热题 HOT52-100
2022-07-23 20:36:00 【A snicker】
146、LRU 缓存
class LRUCache {
int capacity;
LinkedHashMap<Integer, Integer> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return cache.size() > capacity;
}
};
}
public int get(int key) {
return cache.getOrDefault(key, -1);
}
public void put(int key, int value) {
cache.put(key, value);
}
}
148、排序链表
自顶向下的归并排序。先用快慢指针的方法，找到链表的中间点。然后通过归并排序的思想，分开对两个子链表进行排序，然后合并。
class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null){
return head;
}
ListNode fast = head;
ListNode slow = head;
ListNode pre = head;
while(fast!=null && fast.next!=null){
pre = slow;
fast = fast.next.next;
slow = slow.next;
}
pre.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
return sort(l1,l2);
}
ListNode sort(ListNode l1,ListNode l2){
ListNode p = new ListNode();
ListNode l = p;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
p.next = l1;
l1 = l1.next;
} else{
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if(l1!=null){
p.next = l1;
}
if(l2!=null){
p.next = l2;
}
return l.next;
}
}
152、乘积最大子数组
因为数组中的数有正有负，所以要设立两个值，imax和imin。当数为负数的时候，imax和imin的值互换。真正的最大值max是imax和imin的最大值。
class Solution {
public int maxProduct(int[] nums) {
int max = Integer.MIN_VALUE;
int imax = 1, imin = 1;
for(int i=0;i<nums.length;i++){
if(nums[i]<0){
int tmp = imax;
imax = imin;
imin = tmp;
}
imax = Math.max(imax*nums[i],nums[i]);
imin = Math.min(imin*nums[i],nums[i]);
max = Math.max(max,imax);
}
return max;
}
}
155、最小栈
A为基本栈，B为辅助栈。当B为空或者B的peek值大时，向B入栈。
class MinStack {
Stack<Integer> A,B;
public MinStack() {
A=new Stack<>();
B=new Stack<>();
}
public void push(int val) {
A.add(val);
if(B.empty() || B.peek()>=val){
B.add(val);
}
}
public void pop() {
if(A.pop().equals(B.peek())){
B.pop();
}
}
public int top() {
return A.peek();
}
public int getMin() {
return B.peek();
}
}
160、相交链表
建立一个判断链表节点是否相等的方法。然后操作head1和head2的链表在同一长度起步。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode l1 = headA;
ListNode l2 = headB;
int size1 = 0,size2 = 0;
while(l1!=null){
l1 = l1.next;
size1++;
}
while(l2!=null){
l2 = l2.next;
size2++;
}
if(size1>=size2){
while(size1>size2){
headA = headA.next;
size1--;
}
}
else{
while(size1<size2){
headB = headB.next;
size2--;
}
}
while(headA!=null && headB!=null){
if(headA != headB){
headA = headA.next;
headB = headB.next;
}
else{
if(dis(headA,headB) == true){
return headA;
}
else{
headA = headA.next;
headB = headB.next;
}
}
}
return null;
}
boolean dis(ListNode headA,ListNode headB){
if(headA==null){
return true;
}
if(headA == headB){
return dis(headA.next,headB.next);
}
else{
return false;
}
}
}
169、多数元素
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
int size = nums.length;
for(int i=0;i<size;i++){
if(nums[i] == nums[i+size/2]){
return nums[i];
}
}
return -1;
}
}
198、打家劫舍
动态规划，偷窃第k个房间，就不能偷第k-1个房间。所以就比较第k-1个房间的dp值，和第k-2个房间的dp值加上第k个房间的值。
class Solution {
public int rob(int[] nums) {
int l = nums.length;
int[] dp = new int[l];
if(l==1){
return nums[0];
}
if(l==2){
return Math.max(nums[0],nums[1]);
}
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<l;i++){
dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
}
return dp[l-1];
}
}
200、岛屿数量
深度优先搜索，如果位置为1，则对其为起始节点进行dfs，在dfs过程中将每个搜到的1都标记为0。
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i=0;i<grid.length;i++){
for(int j=0;j<grid[0].length;j++){
if(grid[i][j]=='1'){
bfs(grid,i,j);
count++;
}
}
}
return count;
}
void bfs(char[][] grid,int i,int j){
if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j]=='0'){
return;
}
grid[i][j]='0';
bfs(grid,i-1,j);
bfs(grid,i+1,j);
bfs(grid,i,j-1);
bfs(grid,i,j+1);
}
}
206、反转链表
迭代。遍历链表时，将当前节点的next指针改为指向前一个节点。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode temp = null;
while(cur!=null){
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
207、课程表
使用一个队列来进行广度优先搜索，初始时，把所有入度为0的节点都放入队列中。
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> edges = new ArrayList<List<Integer>>();
int[] indeg = new int[numCourses];
for(int i=0;i<numCourses;i++){
edges.add(new ArrayList<Integer>());
}
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()){
// 统计次数，如果为true，则次数应为总课程数，因为每个课程都要入一次队列
visited++;
int u = queue.poll();
for(int v : edges.get(u)){
// 以学会了课程u，把需要提取学习课程u的所有课程的indeg减一
indeg[v]--;
if(indeg[v]==0){
queue.offer(v);
}
}
}
return visited == numCourses;
}
}
208、实现 Trie (前缀树)
字典树。
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;
}
}
215、数组中的第K个最大元素
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
221、最大正方形
动态规划。dp数组中表示以（i，j）为右下角的最大正方形的边长，然后通过dp*dp来比较获得最大值。
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int maxSide = 0;
int dp[][] = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(matrix[i][j]=='0'){
dp[i][j] = 0;
} else{
if(i==0 || j==0){
dp[i][j] = 1;
} else{
dp[i][j] = Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j]) + 1;
}
}
maxSide = Math.max(maxSide,dp[i][j]*dp[i][j]);
}
}
return maxSide;
}
}
226、翻转二叉树
递归
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode left1 = invertTree(root.right);
TreeNode right1 = invertTree(root.left);
root.left = left1;
root.right = right1;
return root;
}
}
234、回文链表
通过快慢指针来取到中间节点。在通过hashmap存储节点的值。
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head;
ListNode slow = head;
ListNode head1 = head;
Map<Integer,Integer> hsp = new HashMap<>();
int i = 0;
int n = 0;
while(head1 != null){
head1 = head1.next;
n++;
}
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
while(slow != null){
i++;
hsp.put(i,slow.val);
slow = slow.next;
}
while(i>0){
int temp = hsp.get(i);
if(temp != head.val){
return false;
}
i--;
head = head.next;
}
return true;
}
}
236、二叉树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
if(root==p || root==q){
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){
return right;
} else{
return left;
}
}
}
238、除自身以外数组的乘积
记录左右乘积的数组，每个除自身以外的数组乘积都是：左乘积数组*右乘积数组。
class Solution {
public int[] productExceptSelf(int[] nums) {
int size = nums.length;
int[] left = new int[size];
int[] right = new int[size];
left[0] = 1;
right[size-1] = 1;
for(int i=1;i<size;i++){
left[i] = nums[i-1]*left[i-1];
}
for(int i=size-1;i>0;i--){
right[i-1] = nums[i]*right[i];
}
for(int i=0;i<size;i++){
nums[i] = left[i]*right[i];
}
return nums;
}
}
239、滑动窗口最大值
双端队列手动实现单调队列
首先定义一个双端队列deque
当数组为非空 并且 头结点的范围 不在 [i - k + 1, i] 内时，将队列头弹出 执行deque.peek()
当队列非空，并且队列尾部索引对应数组元素的元素小于nums[i]的时候，将队列尾部弹出，执行deque.peekLast()
将此时的i加入到deque中 执行deque.offer(i)
class Solution {
// 双端队列手动实现单调队列
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n-k+1];
int idx = 0;
for(int i=0;i<n;i++){
// 保证当前的要装的i，比队列第一个的差小于k。即队列最多有3个数
while(!deque.isEmpty() && deque.peek()<i-k+1){
deque.poll();
}
// 保证当前的nums[i]的值如果比当前队列末尾的值大的话，直接删除。
while(!deque.isEmpty() && nums[deque.peekLast()]<nums[i]){
deque.pollLast();
}
deque.offer(i);
if(i>=k-1){
res[idx++] = nums[deque.peek()];
}
}
return res;
}
}
240、搜索二维矩阵 II
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int x = 0;
int y = n-1;
while(x<m && y>=0){
if(matrix[x][y] == target){
return true;
} else if(matrix[x][y]>target){
y--;
} else{
x++;
}
}
return false;
}
}
279、完全平方数
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、移动零
class Solution {
public void moveZeroes(int[] nums) {
int m = 0;
int l = nums.length;
for(int i=0;i<l;i++){
if(nums[i] != 0){
nums[m++] = nums[i];
}
}
while(m<l){
nums[m++] = 0;
}
}
}
287、寻找重复数
class Solution {
public int findDuplicate(int[] nums) {
Set<Integer> hst = new HashSet<>();
for(int i=0;i<nums.length;i++){
if(hst.contains(nums[i])){
return nums[i];
}
hst.add(nums[i]);
}
return -1;
}
}
297、二叉树的序列化与反序列化
public class Codec {
public String serialize(TreeNode root) {
return rserialize(root,"");
}
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;
}
}
300、最长递增子序列
动态规划。两重for循环，第一次for循环是循环nums的每一个i，第二次for循环是循环nums中的每个小于i的所有数j。
dp[i] = Math.max(dp[i],dp[j]+1);
class Solution {
public int lengthOfLIS(int[] nums) {
// 动态规划，把所有的dp都置为一
int[] dp = new int[nums.length];
dp[0] = 1;
int max = 1;
for(int i=1;i<nums.length;i++){
dp[i] = 1;
// 循环i之前的所有元素，如果比他们大，比较是当前的dp大还是他们的dp加1大
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i] = Math.max(dp[i],dp[j]+1);
}
}
max = Math.max(max,dp[i]);
}
return max;
}
}
301、删除无效的括号
广度优先搜索，每一轮都删除字符串中的1个括号，直到出现合法匹配的字符串为止。
我们进行广度优先搜索时，每次保存上一轮搜索的结果，然后对上一轮已经保存的结果中的每一个字符串尝试所有可能的删除一个括号的方法，然后将保存的结果进行下一轮搜索。在保存结果时，我们可以利用哈希表对上一轮生成的结果去重，从而提高效率。
class Solution {
public List<String> removeInvalidParentheses(String s) {
List<String> result = new ArrayList<>();
if(s.equals("")){
result.add(s);
return result;
}
Deque<String> queue = new ArrayDeque<>();
queue.offer(s);
HashSet<String> set = new HashSet<>();
boolean isFound = false;
// bfs 广度优先
while(!queue.isEmpty()){
String curr = queue.poll();
// 对符合要求的字符串进行入result
if(isValid(curr)){
result.add(curr);
isFound = true;
}
if(isFound){
continue;
}
// 对不符合要求的字符串，将每个只删一个 ( 或者 ) 的字符串进行入队列queue
for(int i=0;i<curr.length();i++){
if(curr.charAt(i) == '(' || curr.charAt(i) == ')'){
String str;
if(i == curr.length()-1){
str = curr.substring(0,curr.length()-1);
} else{
str = curr.substring(0,i) + curr.substring(i+1);
}
if(set.add(str)){
queue.offer(str);
}
}
}
}
if(result.isEmpty()){
result.add("");
}
return result;
}
// 检验字符串是否符合要求
private static boolean isValid(String s){
int left = 0;
for(int i=0;i<s.length();i++){
int curr = s.charAt(i);
if(curr == '('){
left++;
} else if(curr == ')'){
if(left != 0){
left--;
} else{
return false;
}
}
}
return left == 0;
}
}
309、最佳买卖股票时机含冷冻期
class Solution {
public int maxProfit(int[] prices) {
int size = prices.length;
if(size < 2){
return 0;
}
int[][] f = new int[size][3];
f[0][0] = -prices[0];
for(int i=1;i<size;i++){
// 有股票
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[size-1][1],f[size-1][2]);
}
}
312、戳气球
i不断缩小，j不断扩大，k在i和j之间。dp[i，j]的意思是在数组i到j的范围内，k为分割戳点的左右加自身的最大数量。
class Solution {
public int maxCoins(int[] nums) {
int n = nums.length;
int[] res = new int[n + 2];
for(int i = 0; i < n + 2; i++){
if(i == 0 || i == n + 1){
res[i] = 1;
}else{
res[i] = nums[i - 1];
}
}
int[][] dp= new int[n+2][n+2];
for(int i=n+1;i>=0;i--){
for(int j=i+1;j<n+2;j++){
for(int k=i+1;k<j;k++){
dp[i][j] = Math.max(dp[i][j],dp[i][k]+dp[k][j]+res[i]*res[k]*res[j]);
}
}
}
return dp[0][n+1];
}
}
322、零钱兑换
动态规划：求从1开始到最终零钱的dp值，然后再把每种硬币类型都考虑一遍。
dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,amount+1);
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 ? -1 : dp[amount];
}
}
递归：
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount<1){
return 0;
}
return dfs(coins,amount,new int[amount]);
}
int dfs(int[] coins,int amount,int[] counts){
if(amount<0){
return -1;
}
if(amount==0){
return 0;
}
if(counts[amount-1]!=0){
return counts[amount-1];
}
int min = Integer.MAX_VALUE;
for(int coin : coins){
int res = dfs(coins,amount-coin,counts);
if(res>=0 && res<min){
min = 1 + res;
}
}
counts[amount-1] = (min == Integer.MAX_VALUE) ? -1:min;
return counts[amount-1];
}
}
337、打家劫舍 III
当 node 被选中时，node 的左右孩子都不能被选中。
当 node 不被选中时，node 的左右孩子可以被选中，也可以不被选中。
class Solution {
Map<TreeNode,Integer> f = new HashMap<>(); //被选中
Map<TreeNode,Integer> g = new HashMap<>(); //不被选中
public int rob(TreeNode root) {
dfs(root);
return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
}
void dfs(TreeNode node){
if(node == null){
return;
}
dfs(node.left);
dfs(node.right);
f.put(node,node.val + g.getOrDefault(node.left,0) + g.getOrDefault(node.right, 0));
g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0))
+ Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
}
}
338、比特位计数
class Solution {
public int[] countBits(int n) {
int[] res = new int[n+1];
for(int i=0;i<=n;i++){
res[i] = res[i >> 1] + (i & 1);
}
return res;
}
}
347、前 K 个高频元素
重点：通过map中的value的大小进行排序，根据排序结果取出前k个key。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Arrays.sort(nums);
int size = nums.length;
Map<Integer,Integer> hsp1 = new HashMap<>();
hsp1.put(nums[0],1);
for(int i=1;i<size;i++){
if(nums[i] == nums[i-1]){
hsp1.put(nums[i],hsp1.get(nums[i])+1);
} else{
hsp1.put(nums[i],1);
}
}
Set<Integer> set=hsp1.keySet();
hsp1.entrySet();
List<Map.Entry<Integer,Integer>> list = new ArrayList(hsp1.entrySet());
Collections.sort(list, (o1, o2) -> (o2.getValue() - o1.getValue()));
int[] res = new int[k];
int i=0;
while(i<k){
res[i] = list.get(i).getKey();
i++;
}
return res;
}
}
394、字符串解码
边栏推荐
- KubeVela离线安装
- Jetson nano烧录踩坑记（一定可以解决你的问题）
- Read the five flow indicators of R & D efficiency insight
- 太全了，建议收藏！SAP究竟可以为企业带来什么？
- 不用MQTT C库就能实现MQTT连接、订阅和发布
- 高数下|二重积分的计算3|高数叔|手写笔记
- Unity解决动画不可用:The AnimationClip ‘XXX‘ used by the Animation component ‘XXX‘ must be marked as Legacy.
- CDR插件开发之Addon插件002 - 用1分钟编写一个可双击运行的EXE程序
- STM32c8t6驱动激光雷达（一）
- Go to the square for dinner
猜你喜欢
随机推荐
Unity解决动画不可用:The AnimationClip ‘XXX‘ used by the Animation component ‘XXX‘ must be marked as Legacy.
[kernel] platform bus model for driving development and learning
【力扣】最接近的三数之和
华泰证券低佣金开户链接安全吗，怎么办理低佣金
win7-vs2012下安装.net frame work 的过程图文详解
解决1秒钟内，用户快速点击，重复请求的问题
[100 cases of scratch drawing] Figure 46-scratch drawing flowers children's programming scratch programming drawing case tutorial grade examination competition drawing training case
我，AI博士生，在线众筹研究主题
太全了，建议收藏！SAP究竟可以为企业带来什么？
If the order is not paid within 30 minutes, it will be automatically cancelled
Trial record of ModelBox end cloud collaborative AI development kit (rk3568) (II)
prime_series_level-1
AB team score flow chart, get the names of the players who score three consecutive times and the names of the players who catch up with and surpass the opponents each time (PDD)
微软网站上关于在Edge浏览器中打开或关闭smartScreen的说明有误
el-upload实现上传文件预览
Detailed explanation of MSTP protocol for layer 3 switch configuration [Huawei ENSP experiment]
Lyscript plug-in command return encapsulation
STM32C8t6 驱动激光雷达实战（二）
视觉slam学习|基础篇01
模块化开发