1、剑指 Offer 48. 最长不含重复字符的子字符串
https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/
2、剑指 Offer 09. 用两个栈实现队列
class CQueue {
Deque<Integer> stack1;
Deque<Integer> stack2;
public CQueue() {
stack1 = new LinkedList<Integer>();//压入栈
stack2 = new LinkedList<Integer>();//弹出栈
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(stack2.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
if(stack2.isEmpty()){
return -1;
}else{
return stack2.pop();
}
}
}
剑指 Offer 30. 包含min函数的栈
调用 min、push 及 pop 的时间复杂度都是 O(1)。
https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/
class MinStack {
Deque<Integer> stack;
Deque<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new ArrayDeque<Integer>();
minStack = new LinkedList<Integer>();
}
public void push(int x) {
stack.push(x);
if(minStack.isEmpty() || x<=min()){
minStack.push(x);
}
}
public void pop() {
if(stack.pop() == min()){
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int min() {
return minStack.peek();
}
}
3、二叉树的中序遍历
4、面试题 16.25. LRU 缓存
LRU(最近最少使用)缓存结构
import java.util.*;
public class Solution {
Map<Integer,Integer> map;
int capacity;
public Solution(int capacity) {
// write code here
this.capacity = capacity;
// LinkedHashMap可以保证插入有序
map = new LinkedHashMap<>(capacity);
}
public int get(int key) {
// write code here
Integer value = map.get(key);
if(value!=null){
if(map.size()>1){
map.remove(key);
map.put(key,value); // 存入最后(最后表示最新使用过的)
}
}else{
return -1;
}
return value;
}
public void set(int key, int value) {
// write code here
if(map.containsKey(key)){
map.remove(key);
}
if(map.size()>=capacity){
//这中相当于有一个指针，指向第一个数的前面 keySet() 返回key的集合
//next() 取出下一个数，指针指向下一位
Integer firstKey = map.keySet().iterator().next();
map.remove(firstKey);
}
map.put(key,value);
}
}
最不经常使用算法（LFU）
import java.util.*;
public class Solution {
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
Map<Integer, Integer> map = new LinkedHashMap<>();
public int[] LFU(int[][] operators, int k) {
int m = operators.length;
if (m == 0) {
return null;
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < m; i++) {
int[] nums = operators[i];
if (nums[0] == 1) {
set(nums[1], nums[2], k);
} else {
list.add(get(nums[1]));
}
}
int[] res = new int[list.size()];
int index = 0;
for (Integer i : list) {
res[index++] = i;
}
return res;
}
public int get(int key) {
Integer value = map.get(key);
if (value != null) {
if (map.size() > 1) {
map.remove(key);
map.put(key, value); // 存入最后(最后表示最新使用过的)
}
} else {
return -1;
}
return value;
}
public void set(int key, int value, int k) {
// write code here
if (map.containsKey(key)) {
map.remove(key);
}
if (map.size() >= k) {
//这中相当于有一个指针，指向第一个数的前面 keySet() 返回key的集合
//next() 取出下一个数，指针指向下一位
Integer firstKey = map.keySet().iterator().next();
map.remove(firstKey);
}
map.put(key, value);
}
}
5、剑指 Offer 40. 最小的k个数
1、用快排最最最高效解决 TopK 问题：O(N)O(N)
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 最后一个参数表示我们要找的是下标为k-1的数
return quickSearch(arr, 0, arr.length - 1, k - 1);
}
private int[] quickSearch(int[] nums, int lo, int hi, int k) {
// 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
int j = partition(nums, lo, hi);
if (j == k) {
return Arrays.copyOf(nums, j + 1);
}
// 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
}
// 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
private int partition(int[] nums, int lo, int hi) {
int v = nums[lo];
int i = lo, j = hi + 1;
while (true) {
while (++i <= hi && nums[i] < v);
while (--j >= lo && nums[j] > v);
if (i >= j) {
break;
}
int t = nums[j];
nums[j] = nums[i];
nums[i] = t;
}
nums[lo] = nums[j];
nums[j] = v;
return j;
}
}
2、大根堆(前 K 小) / 小根堆（前 K 大),Java中有现成的 PriorityQueue，实现起来最简单：O(NlogK)
// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
// 1. 若目前堆的大小小于K，将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
// 反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 默认是小根堆，实现大根堆需要重写一下比较器。
Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int num: arr) {
if (pq.size() < k) {
pq.offer(num);
} else if (num < pq.peek()) {
pq.poll();
pq.offer(num);
}
}
// 返回堆中的元素
int[] res = new int[pq.size()];
int idx = 0;
for(int num: pq) {
res[idx++] = num;
}
return res;
}
}
3、二叉搜索树也可以 O(NlogK)O(NlogK)解决 TopK 问题哦
- BST 相对于前两种方法没那么常见，但是也很简单，和大根堆的思路差不多～要提的是，与前两种方法相比，BST 有一个好处是求得的前K大的数字是有序的。
- 因为有重复的数字，所以用的是 TreeMap 而不是 TreeSet
- TreeMap的key 是数字，value 是该数字的个数。
- 我们遍历数组中的数字，维护一个数字总个数为 K 的 TreeMap：
- 1.若目前 map 中数字个数小于 K，则将 map 中当前数字对应的个数 +1；
- 2.否则，判断当前数字与 map 中最大的数字的大小关系：若当前数字大于等于 map 中的最大数字，就直接跳过该数字；若当前数字小于 map 中的最大数字，则将 map 中当前数字对应的个数 +1，并将 map 中最大数字对应的个数减 1。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// TreeMap的key是数字, value是该数字的个数。
// cnt表示当前map总共存了多少个数字。
TreeMap<Integer, Integer> map = new TreeMap<>();
int cnt = 0;
for (int num: arr) {
// 1. 遍历数组，若当前map中的数字个数小于k，则map中当前数字对应个数+1
if (cnt < k) {
map.put(num, map.getOrDefault(num, 0) + 1);
cnt++;
continue;
}
// 2. 否则，取出map中最大的Key（即最大的数字), 判断当前数字与map中最大数字的大小关系：
// 若当前数字比map中最大的数字还大，就直接忽略；
// 若当前数字比map中最大的数字小，则将当前数字加入map中，并将map中的最大数字的个数-1。
Map.Entry<Integer, Integer> entry = map.lastEntry();
if (entry.getKey() > num) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (entry.getValue() == 1) {
map.pollLastEntry();
} else {
map.put(entry.getKey(), entry.getValue() - 1);
}
}
}
// 最后返回map中的元素
int[] res = new int[k];
int idx = 0;
for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
int freq = entry.getValue();
while (freq-- > 0) {
res[idx++] = entry.getKey();
}
}
return res;
}
}
4、数据范围有限时直接计数排序就行了：O(N)O(N)
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 统计每个数字出现的次数
int[] counter = new int[10001];
for (int num: arr) {
counter[num]++;
}
// 根据counter数组从头找出k个数作为返回结果
int[] res = new int[k];
int idx = 0;
for (int num = 0; num < counter.length; num++) {
while (counter[num]-- > 0 && idx < k) {
res[idx++] = num;
}
if (idx == k) {
break;
}
}
return res;
}
}
7、剑指 Offer 48. 最长不含重复字符
8、环形链表
9、最长公共子序列
https://blog.nowcoder.net/n/f0aeb5e68fb340e5a6346fc9edea42f2
10、剑指 Offer 12. 矩阵中的路径
https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
回溯法
class Solution {
public boolean exist(char[][] board, String word) {
int row = board.length;
int col = board[0].length;
char[] words = word.toCharArray();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(dfs(board,words,i,j,0)){
return true;
}
}
}
return false;
}
public boolean dfs(char[][] board, char[] words,int i,int j,int index) {
if(i>=board.length || i<0 || j>=board[0].length || j<0 || words[index] != board[i][j]){
return false;
}
if(index == words.length-1){
return true;
}
char temp = board[i][j];
board[i][j] = '.';// 把当前值保存起来，避免重复
boolean res = dfs(board,words,i+1,j,index+1) || dfs(board,words,i,j+1,index+1) || dfs(board,words,i-1,j,index+1) || dfs(board,words,i,j-1,index+1);
// 回溯
board[i][j] = temp;
return res;
}
}
11、三数之和
https://leetcode-cn.com/problems/3sum/
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
//先对数组进行排序
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int i=0;i<nums.length-2;i++){
//过滤掉重复的
if(i>0&&nums[i] == nums[i-1]){
continue;
}
//因为是排序的，如果第一个数字大于0，那么后面的也都
//大于0，他们三个数字的和不可能等于0
if(nums[i]>0){
break;
}
int left = i+1;//左指针
int right = nums.length-1;//右指针
int target = -nums[i];
while(left < right){
//左右指针的和
int sum = nums[left]+nums[right];
if(sum == target){
//找到了一组，把他们加入到集合list中
res.add(Arrays.asList(nums[i],nums[left],nums[right]));
while(left<right&&nums[left]==nums[left+1]){
left++;
}
while(left<right&&nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}else if(sum<target){
left++;
}else{
right--;
}
}
}
return res;
}
}
12、判断二叉树是否对称
class Solution {
public boolean isSymmetric(TreeNode root) {
return isMirror(root,root);
}
public static boolean isMirror(TreeNode root1,TreeNode root2){
if(root1 == null && root2 == null)
return true;
if((root1 == null && root2 != null)||(root1 != null && root2 == null))
return false;
if(root1.val == root2.val){
return isMirror(root1.left,root2.right)&&isMirror(root1.right,root2.left);
} else{
return false;
}
}
}
13、跳跃游戏 II
贪心算法，通过局部最优解得到全局最优解
从前向后
- 如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置。
- 如下图，然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以下次跳到 4 的位置。
class Solution {
public int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++){
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);
if( i == end){ //遇到边界，就更新边界，并且步数加一
end = maxPosition;
steps++;
}
}
return steps;
}
}
- 时间复杂度：O(n)。
- 空间复杂度：O(1)。
- 这里要注意一个细节，就是 for 循环中，i < nums.length - 1，少了末尾。因为开始的时候边界是第 0 个位置，steps 已经加 11 了。如下图，如果最后一步刚好跳到了末尾，此时 steps 其实不用加 1 了。如果是 i < nums.length，i 遍历到最后的时候，会进入 if 语句中，steps 会多加 1。
从后向前
- 我们知道最终要到达最后一个位置，然后我们找前一个位置，遍历数组，找到能到达它的位置，离它最远的就是要找的位置。然后继续找上上个位置，最后到了第 0 个位置就结束了。
- 至于离它最远的位置，其实我们从左到右遍历数组，第一个满足的位置就是我们要找的。
public int jump(int[] nums) {
int position = nums.length - 1; //要找的位置
int steps = 0;
while (position != 0) { //是否到了第 0 个位置
for (int i = 0; i < position; i++) {
if (nums[i] >= position - i) {
position = i; //更新要找的位置
steps++;
break;
}
}
}
return steps;
}
- 时间复杂度：O(n²)，因为最坏的情况比如 1 1 1 1 1，position 会从 5 更新到 0，并且每次更新都会经历一个 for 循环。
- 空间复杂度：O(1)。
14、编辑距离
https://blog.nowcoder.net/n/f43c7c112507453ab53ad1047818c4c8
public int editDistance (String str1, String str2) {
// write code here
int len1 = str1.length();
int len2 = str2.length();
if(len1 == 0 || len2 == 0){
return len1 == 0?len2:len1;
}
// dp[i][j]表示把str1的前i个字符变为str2的前j个字符所需要的最少编辑距离
int[][] dp = new int[len1+1][len2+1];
for(int i=0;i<=len1;i++){
for(int j=0;j<=len2;j++){
if(i == 0){ // 初始化，相当于word1的添加操作
dp[i][j] = j;
}else if(j == 0){// 初始化，相当于word1的删除操作
dp[i][j] = i;
}else if(str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}else{
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]))+1;
}
}
}
return dp[len1][len2];
}
15. 一个数组，除了某个数字只出现一次，其它都只出现两次，
https://leetcode-cn.com/problems/skFtm2/submissions/
思路：
1、排序
2、HashMap记录
class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])){
map.put(nums[i],map.get(nums[i])+1);
}else{
map.put(nums[i],1);
}
}
Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
while(it.hasNext()){
Map.Entry<Integer, Integer> entry = it.next();
if(entry.getValue().equals(1)){
return entry.getKey();
}
}
return -1;
}
}
3、异或操作
class Solution {
public int singleNonDuplicate(int[] nums) {
int res = nums[0];
for(int i=1;i<nums.length;i++){
res = res ^ nums[i];
}
return res;
}
}
16. 一个数组，除了某个数字只出现一次，其它都只出现三次
https://leetcode-cn.com/problems/WGki4K/solution/
最简单的方法，HashMap，同上，但是时间复杂度太高
所以采用位运算
- 答案的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。
- 对于数组中非答案的元素，每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，它们的和都是 3 的倍数（即和为 0 或 3）。
- 因此：答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。
- 对于数组中的每一个元素 x，我们使用位运算(x >> i) & 1 得到 x 的第 i 个二进制位，并将它们相加再对 3 取余，得到的结果一定为 0 或 1，即为答案的第 i 个二进制位。
class Solution {
//将所有整数按照位置加起来，然后对3取余，若结果为0，则待求数字在该位上是0；
//若结果为1，则待求数字在该位上是1.
/**
nums : [2,2,3,2]
二进制数组：[10,10,11,10]
各个位相加：[4,1]
对3取余：ans = 0
ans = ans | (1 << 0) = 00 | 01 = 01;
ans = ans | (1 << 1) = 01 | 11 = 11;
*/
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int num: nums) {
total += ((num >> i) & 1);
}
if (total % 3 != 0) {
ans = ans | (1 << i);
}
}
return ans;
}
}
- 时间复杂度：O(nlogC)，其中 n 是数组的长度，C 是元素的数据范围，在本题中 logC=log 2^{32} = 32，也就是我们需要遍历第 0\∼31 个二进制位。
- 空间复杂度：O(1)。
17、判断树 B 是否是树 A 的子树
https://leetcode-cn.com/problems/subtree-of-another-tree/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (t == null) return true; // t 为 null 一定都是 true
if (s == null) return false; // 这里 t 一定不为 null, 只要 s 为 null，肯定是 false
return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
}
/**
* 判断两棵树是否相同
*/
public boolean isSameTree(TreeNode s, TreeNode t){
if (s == null && t == null) return true;
if (s == null || t == null) return false;
if (s.val != t.val) return false;
return isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
}
}
18、将一个链表按奇偶序号分成两个链表，按序号而不是值。
https://leetcode-cn.com/problems/odd-even-linked-list/
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode p=head,q=head.next;
ListNode ouHead = q;//偶数的头节点
while(q!=null && q.next!=null){
p.next = q.next;
p = q.next;
q.next = p.next;
q = p.next;
}
p.next = ouHead;
return head;
}
}
19、二叉树中一个节点的左右子节点可以进行互换，问两个二叉树能不能通过这种操作变成一样的？
二叉树的镜像
https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
class Solution {
/**
这是一道很经典的二叉树问题。显然，我们从根节点开始，递归地对树进行遍历，
并从叶子节点先开始翻转得到镜像。如果当前遍历到的节点 root 的左右两棵子树
都已经翻转得到镜像，那么我们只需要交换两棵子树的位置，即可得到以 root
为根节点的整棵子树的镜像。
*/
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
翻转等价二叉树
https://leetcode-cn.com/problems/flip-equivalent-binary-trees/
class Solution {
public boolean flipEquiv(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null){//都为空
return true;
}
if(root1 == null || root2 == null){//只有一个为空
return false;
}
if(root1.val == root2.val){
return (flipEquiv(root1.left,root2.left)&&flipEquiv(root1.right,root2.right)) ||
(flipEquiv(root1.left,root2.right)&&flipEquiv(root1.right,root2.left));
}else{
return false;
}
}
}
20、接雨水
接雨水
https://leetcode-cn.com/problems/trapping-rain-water/
接雨水 II
https://leetcode-cn.com/problems/trapping-rain-water-ii/
盛水最多的容器
https://www.nowcoder.com/practice/3d8d6a8e516e4633a2244d2934e5aa47
21、统计数组中每个元素出现的个数，不能用map，set，时间复杂度 O(n),空间 O(1)
public class Char_Number_Of_String_2 {
public static void main(String[] args) {
String str = "www.hellohahaha.com";
//定义字符数组chars存放字符串中的每种字符,定义一个count变量用于循环就解决疑惑了
int count = 0;
char[] chars = new char[26];
//定义一个整型数组，用来统计字符串中每种字符出现的次数
int[] nums = new int[26];
//将str中的每种字符存放到chars数组中
for (int i = 0; i < str.length() ; i++) {
//定义一个标志位
int index = -1;
//在chars数组中查找是否已经存在字符c
char c = str.charAt(i);
for (int j = 0; j < count; j++) {
//如果chars数组中存在字符c
if(c == chars[j]){
index = j;
}
}
//判断chars数组中是否存在字符c
//如果没有找到
if(index == -1){
chars[count] = c;
nums[count]++;
count++;
}else{
//如果找到了
nums[index]++;
}
}
//输出结果
System.out.println(Arrays.toString(chars));
System.out.println(Arrays.toString(nums));
}
}
[w, ., h, e, l, o, a, c, m, , , , , , , , , , , , , , , , , ]
[3, 2, 4, 1, 2, 2, 3, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
22、实现一个阻塞队列，考虑到多线程并发的情况，要求有put,get,isEmpty, isFull方法。
https://jishuin.proginn.com/p/763bfbd573ea
- 阻塞队列是一个具备先进先出特性的队列结构，从队列末尾插入数据，从队列头部取出数据。而阻塞队列与普通队列的最大不同在于阻塞队列提供了阻塞式的同步插入、取出数据的功能（阻塞入队put/阻塞出队take）。
- 使用put插入数据时，如果队列空间已满并不直接返回，而是令当前操作的线程陷入阻塞态（生产者线程），等待着阻塞队列中的元素被其它线程（消费者线程）取走，令队列重新变得不满时被唤醒再次尝试插入数据。使用take取出数据时，如果队列空间为空并不直接返回，而是令当前操作的线程陷入阻塞态（消费者线程），等待其它线程（生产者线程）插入新元素，令队列非空时被唤醒再次尝试取出数据。
- 阻塞队列主要用于解决并发场景下消费者线程与生产者线程处理速度不一致的问题。例如jdk的线程池实现中，线程池核心线程（消费者线程）处理速度一定的情况下，如果业务方线程提交的任务过多导致核心线程处理不过来时，将任务暂时放进阻塞队列等待核心线程消费（阻塞队列未满）；由于核心线程常驻的原因，当业务方线程提交的任务较少，核心线程消费速度高于业务方生产速度时，核心线程作为消费者会阻塞在阻塞队列的take方法中，避免无谓的浪费cpu资源。
- 由于阻塞队列在内部实现了协调生产者/消费者的机制而不需要外部使用者过多的考虑并发同步问题，极大的降低了生产者/消费者场景下程序的复杂度。
/**
* 阻塞队列
* 1. 首先是一个先进先出的队列
* 2. 提供特别的api，在入队时如果队列已满令当前操作线程阻塞；在出队时如果队列为空令当前操作线程阻塞
* 3. 单个元素的插入、删除操作是线程安全的
*/
public interface MyBlockingQueue<E> {
/**
* 插入特定元素e，加入队尾
* 队列已满时阻塞当前线程，直到队列中元素被其它线程删除并插入成功
* */
void put(E e) throws InterruptedException;
/**
* 队列头部的元素出队(返回头部元素，将其从队列中删除)
* 队列为空时阻塞当前线程，直到队列被其它元素插入新元素并出队成功
* */
E take() throws InterruptedException;
/**
* 队列是否为空
* */
boolean isEmpty();
}
23、字符串转ip地址(回溯算法)
https://leetcode-cn.com/problems/restore-ip-addresses/
24、三数之和
public List<List<Integer>> threeSum(int[] num) {
//先对数组进行排序
Arrays.sort(num);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < num.length - 2; i++) {
//过滤掉重复的
if (i > 0 && num[i] == num[i - 1])
continue;
//因为是排序的，如果第一个数字大于0，那么后面的也都
//大于0，他们三个数字的和不可能等于0
if (num[i] > 0)
break;
int left = i + 1;//左指针
int right = num.length - 1;//右指针
int target = -num[i];
while (left < right) {
//左右指针的和
int sum = num[left] + num[right];
if (sum == target) {
//找到了一组，把他们加入到集合list中
res.add(Arrays.asList(num[i], num[left], num[right]));
//过滤掉重复的
while (left < right && num[left] == num[left + 1])
left++;
while (left < right && num[right] == num[right - 1])
right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return res;
}
25、剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器
https://leetcode.cn/problems/FortPu/
方法一：变长数组 + 哈希表
- 变长数组可以在 O(1)O(1) 的时间内完成随机访问元素操作
- 哈希表可以在 O(1)O(1) 的时间内完成插入和删除操作
class RandomizedSet {
List<Integer> nums;
Map<Integer, Integer> indices;
Random random;
public RandomizedSet() {
nums = new ArrayList<Integer>();
indices = new HashMap<Integer, Integer>();
random = new Random();
}
public boolean insert(int val) {
if (indices.containsKey(val)) {
return false;
}
int index = nums.size();
nums.add(val);
indices.put(val, index);
return true;
}
public boolean remove(int val) {
if (!indices.containsKey(val)) {
return false;
}
int index = indices.get(val);
int last = nums.get(nums.size() - 1);
nums.set(index, last);
indices.put(last, index);
nums.remove(nums.size() - 1);
indices.remove(val);
return true;
}
public int getRandom() {
int randomIndex = random.nextInt(nums.size());
return nums.get(randomIndex);
}
}
26、观看不同视频个数的前5名
https://blog.csdn.net/u010003835/article/details/106536970
类似：部门工资前三高的所有员工
https://leetcode.cn/problems/department-top-three-salaries/
观看不同视频个数的前5名（不一定对，没有验证）
SELECT user_id, differ_video
FROM
(
SELECT user_id, COUNT(1) AS differ_video
FROM
(
SELECT user_id, video_id
FROM
(
SELECT *
FROM user_video_log
WHERE pt = '20200603'
) tmp
GROUP BY user_id, video_id
) tmp2
GROUP BY user_id
) tmp3
SORT BY differ_video DESC
LIMIT 5
;
部门工资前三高的所有员工
SELECT
d.Name AS 'Department', e1.Name AS 'Employee', e1.Salary
FROM
Employee e1
JOIN
Department d ON e1.DepartmentId = d.Id
WHERE
3 > (SELECT
COUNT(DISTINCT e2.Salary)
FROM
Employee e2
WHERE
e2.Salary > e1.Salary
AND e1.DepartmentId = e2.DepartmentId
)
;
公司里前 3 高的薪水意味着有不超过 3 个工资比这些值大。
京公网安备 11010502036488号