前言

2023-7-2 09:52:04

推荐

HOT 100（1~20）【LeetCode】

HOT 100（21~40）【LeetCode】

HOT 100（41~60）

102. 二叉树的层序遍历【中等】

102.二叉树的层序遍历
中等
1.7K
相关企业
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：输入：root = [1]
输出：[[1]]
示例 3：输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

队列

/*** 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> list=new ArrayList<>();int count=queue.size();for (int i = 0; i<count ; i++) {TreeNode p = queue.poll();list.add(p.val);if (p.left != null) {queue.add(p.left);}if (p.right != null) {queue.add(p.right);}}res.add(list);}return res;}
}

104. 二叉树的最大深度【简单】

104.二叉树的最大深度
简单
1.6K
相关企业
给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，3/ \9  20/  \15   7
返回它的最大深度 3 。

递归

/*** 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 int maxDepth(TreeNode root) {if (root == null) {return 0;}return 1 + Math.max(maxDepth(root.left),maxDepth(root.right)) ;}
}

105. 从前序与中序遍历序列构造二叉树【中等】

105.从前序与中序遍历序列构造二叉树
中等
2K
相关企业
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列

官方

/*** 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 {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍历中的第一个节点就是根节点int preorder_root = preorder_left;// 在中序遍历中定位根节点int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根节点建立出来TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子树中的节点数目int size_left_subtree = inorder_root - inorder_left;// 递归地构造左子树，并连接到根节点// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 递归地构造右子树，并连接到根节点// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 构造哈希映射，帮助我们快速定位根节点indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
}

114. 二叉树展开为链表【中等】

114.二叉树展开为链表
中等
1.5K
相关企业
给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：输入：root = []
输出：[]
示例 3：输入：root = [0]
输出：[0]

提示：

树中结点数在范围 [0, 2000] 内
-100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

先序遍历

/*** 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 void flatten(TreeNode root) {List<TreeNode> list=new ArrayList<>();preorderTraversal(root,list);for(int i=1;i<list.size();i++){TreeNode pre=list.get(i-1);TreeNode cur=list.get(i);pre.left=null;pre.right=cur;}}public void preorderTraversal(TreeNode root,List<TreeNode> list){if(root!=null){list.add(root);preorderTraversal(root.left,list);preorderTraversal(root.right,list);}}
}

121. 买卖股票的最佳时机【简单】

121.买卖股票的最佳时机
简单
2.6K
相关企业
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

class Solution {public int maxProfit(int[] prices) {int minP=Integer.MAX_VALUE;int maxP=0;for(int i=0;i<prices.length;i++){if(prices[i]<minP){minP=prices[i];}if(maxP<prices[i]-minP){maxP=prices[i]-minP;}}return maxP;}
}

/*** 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 low=head;ListNode fast=head;while(fast!=null&&fast.next!=null){low=low.next;fast=fast.next.next;if(low==fast){return true;}}return false;}
}

环形链表 II

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode low=head;ListNode fast=head;while(fast!=null&&fast.next!=null){low=low.next;fast=fast.next.next;if(low==fast){ListNode node=head;while(node!=low){node=node.next;low=low.next;}return node;}}return null;}
}

快乐数

124. 二叉树中的最大路径和【困难】

124.二叉树中的最大路径和
困难
2K
相关企业
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
示例 2：输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 104]
-1000 <= Node.val <= 1000

参考
递归

/*** 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 {int maxSum=Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {maxGain(root);return maxSum;}public int maxGain(TreeNode node){if(node==null){return 0;}// 递归计算左右子节点的最大贡献值// 只有在最大贡献值大于 0 时，才会选取对应子节点int leftGain=Math.max(maxGain(node.left),0);int rightGain=Math.max(maxGain(node.right),0);     // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值int priceNewpath=node.val+leftGain+rightGain;// 更新答案maxSum=Math.max(maxSum,priceNewpath);// 返回节点的最大贡献值return node.val+Math.max(leftGain,rightGain);}
}

128. 最长连续序列【中等】

128.最长连续序列
中等
1.7K
相关企业
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

参考

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> num_set=new HashSet<>();for(int num:nums){num_set.add(num);}int longestStreak=0;for(int num:num_set){//只有当一个数是连续序列的第一个数的情况下才会进入内层循环if(!num_set.contains(num-1)){int currentNum=num;int currentStreak=1;//内层循环中匹配连续序列中的数while(num_set.contains(currentNum+1)){currentNum+=1;currentStreak+=1;}longestStreak=Math.max(longestStreak,currentStreak);}}return longestStreak;}
}

136. 只出现一次的数字【简单】

136.只出现一次的数字
简单
2.9K
相关企业
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：输入：nums = [2,2,1]
输出：1
示例 2 ：输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次。

异或

class Solution {public int singleNumber(int[] nums) {int single = 0;for (int num : nums) {single ^= num;}return single;}
}

哈希表

class Solution {public int singleNumber(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (int num : nums) {if (map.containsKey(num)){map.remove(num);} else {map.put(num, 1);}}Set<Integer> set = map.keySet();Iterator<Integer> iterator = set.iterator();return iterator.next();}
}

139. 单词拆分【中等】

139.单词拆分
中等
2.2K
相关企业
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。
示例 3：输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

官方

public class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> wordDictSet = new HashSet(wordDict);boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for (int i = 1; i <= s.length(); i++) {for (int j = 0; j < i; j++) {if (dp[j] && wordDictSet.contains(s.substring(j, i))) {dp[i] = true;break;}}}return dp[s.length()];}
}

141. 环形链表【简单】

141.环形链表
简单
1.9K
相关企业
给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

快慢指针

/*** 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 low=head;ListNode fast=head;while(fast!=null&&fast.next!=null){low=low.next;fast=fast.next.next;if(low==fast){return true;}}return false;}
}

142. 环形链表 II【中等】

142.环形链表 II
中等
2.1K
相关企业
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

哈希表

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if (head ==null){return null;}//哈希表Set<ListNode> set=new HashSet<>();ListNode cur=head;while (cur!=null){if (set.contains(cur)){return cur;}set.add(cur);cur=cur.next;}return null;}
}

前后指针

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if (head ==null){return null;}//前后指针ListNode slow= head;ListNode fast= head;while (fast!=null){slow=slow.next;if (fast.next != null) {  //小心空指针fast = fast.next.next;} else {return null;}//while(true) if(fast==null||fast.next == null) return null;if (fast==slow){//ptr和slow相遇就是入环点ListNode ptr = head;while (ptr != slow) {ptr = ptr.next;slow = slow.next;}return ptr;}}return null;}
}

快慢指针

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode low=head;ListNode fast=head;while(fast!=null&&fast.next!=null){low=low.next;fast=fast.next.next;if(low==fast){ListNode node=head;while(node!=low){node=node.next;low=low.next;}return node;}}return null;}
}

146. LRU 缓存【中等】

146.LRU 缓存
中等
2.5K
相关企业
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

参考
哈希表+双向链表

public class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key = _key; value = _value;}}private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 如果 key 存在，先通过哈希表定位，再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果 key 不存在，创建一个新的节点DLinkedNode newNode = new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode tail = removeTail();// 删除哈希表中对应的项cache.remove(tail.key);--size;}}else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}
}

Java的API：LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity; }
}

148. 排序链表

148.排序链表
中等
2K
相关企业
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

快排，超出时间限制

/*** 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 ListNode sortList(ListNode head) {quickSort(head,null);return head;}public void quickSort(ListNode head, ListNode end){if(head != end){ListNode p1 = head;ListNode p2 = head;while (p2 != end){if(p2.val < head.val){p1 = p1.next;int temp = p1.val;p1.val = p2.val;p2.val = temp;}p2 = p2.next;}//p1与基准交换if(p1 != head){int temp = p1.val;p1.val = head.val;head.val = temp;}quickSort(head,p1);quickSort(p1.next,end);}}}

参考-归并排序

/*** 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 ListNode sortList(ListNode head) {return sortList(head,null);}public ListNode sortList(ListNode head,ListNode tail){if(head==null){return head;}if(head.next==tail){head.next=null;return head;}//快慢指针找中点ListNode slow=head,fast=head;while(fast!=tail){slow=slow.next;fast=fast.next;if(fast!=tail){fast=fast.next;}}//分治ListNode mid=slow;ListNode list1=sortList(head,mid);ListNode list2=sortList(mid,tail);ListNode sorted=merge(list1,list2);return sorted;}//合并public ListNode merge(ListNode head1,ListNode head2){ListNode dummyHead=new ListNode(0);ListNode temp=dummyHead,temp1=head1,temp2=head2;while(temp1!=null&&temp2!=null){if(temp1.val<=temp2.val){temp.next=temp1;temp1=temp1.next;}else{temp.next=temp2;temp2=temp2.next; }temp=temp.next;}if(temp1!=null){temp.next=temp1;}else if(temp2!=null){temp.next=temp2;}return dummyHead.next;}}

152. 乘积最大子数组

152.乘积最大子数组
中等
2K
相关企业
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

参考-动态规划

class Solution {public int maxProduct(int[] nums) {int length=nums.length;int[] maxF=new int[length];int[] minF=new int[length];System.arraycopy(nums, 0, maxF, 0, length);System.arraycopy(nums, 0, minF, 0, length);for(int i=1;i<length;i++){maxF[i]=Math.max(maxF[i-1]*nums[i],Math.max(nums[i],minF[i-1]*nums[i]));minF[i]=Math.min(minF[i-1]*nums[i],Math.min(nums[i],maxF[i-1]*nums[i]));}int ans=maxF[0];for(int i=1;i<length;i++){ans=Math.max(ans,maxF[i]);}return ans;}
}

155. 最小栈

155.最小栈
提示
中等
1.6K
相关企业
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

示例 1:输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出：
[null,null,null,null,-3,null,0,-2]解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
参考

class MinStack {Deque<Integer> xStack;//辅助栈 同步操作Deque<Integer> minStack;public MinStack() {xStack = new LinkedList<Integer>();minStack = new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(val,minStack.peek()));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

160. 相交链表【简单】

简单
1.9K
相关企业
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

hash表

双指针

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA==null||headB==null){return null;}ListNode pA = headA, pB = headB;while (pA != pB) {pA = pA == null ? headB : pA.next;pB = pB == null ? headA : pB.next;}return pA;}
}

169. 多数元素【简单】

简单
1.6K
相关企业
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：输入：nums = [3,2,3]
输出：3
示例 2：输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

HashMap计数

class Solution {public int majorityElement(int[] nums) {HashMap<Integer,Integer> map=new HashMap<>();for(int i=0;i<nums.length;i++){if(map.containsKey(nums[i])){int count=map.get(nums[i]);map.put(nums[i],count+1);}else{map.put(nums[i],1);}}for(Integer i:map.keySet()){if(map.get(i)>nums.length/2){return i;}}return 0;}
}

排序返回[n/2]

同归于尽法

https://leetcode.cn/problems/majority-element/solution/javashi-pin-jiang-jie-xi-lie-majority-element-by-s/
“同归于尽消杀法” ：由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。遍历数组第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count 加一；如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力-1, 即使双方都死光，这块高地的旗帜 winner 不变，没有可以去换上自己的新旗帜。当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。就这样各路军阀一直厮杀以一敌一同归于尽的方式下去，直到少数阵营都死光，剩下几个必然属于多数阵营的，winner 是多数阵营。（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）

public int majorityElement(int[] nums) {int winner = nums[0];int count = 1;for (int i = 1; i < nums.length; i++) {if (winner == nums[i]) {count++;} else if (count == 0) {winner = nums[i];count++;} else {count--;}}return winner;
}

198. 打家劫舍【中等】

198.打家劫舍
中等
2.6K
相关企业
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

官方

class Solution {public int rob(int[] nums) {if (nums == null || nums.length == 0) {return 0;}int length = nums.length;if (length == 1) {return nums[0];}int first = nums[0], second = Math.max(nums[0], nums[1]);for (int i = 2; i < length; i++) {int temp = second;second = Math.max(first + nums[i], second);first = temp;}return second;}
}

200. 岛屿数量【中等】

200.岛屿数量
中等
2.2K
相关企业
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：输入：grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]
]
输出：1
示例 2：输入：grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

递归感染

class Solution {public int numIslands(char[][] grid) {int sum=0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j]=='1') {ganran(grid,i,j);sum++;}}}return sum;}//递归感染private static void ganran(char[][] grid, int i, int j) {//终止条件if (i<0||i>=grid.length||j<0||j>=grid[0].length){return;}if(grid[i][j]!='1') return;if (grid[i][j]=='1')grid[i][j]='2';ganran(grid,i-1,j);ganran(grid,i+1,j);ganran(grid,i,j-1);ganran(grid,i,j+1);}
}

206. 反转链表【简单】

206.反转链表
简单
3.2K
相关企业
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：输入：head = [1,2]
输出：[2,1]
示例 3：输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

/*** 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 ListNode reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;}
}

最后

2023-7-2 10:25:11