刷题地址：https://leetcode-cn.com/study-plan/lcof/?progress=xcewnbs
文章目录
- 总结
- 2021.08.06 第 1 天 整数
- 2021.08.07 第2天 整数
- 2021.08.08 第3天 数组
- 2021.08.09 第4天 数组
- [10 剑指 Offer II 010. 和为 k 的子数组](https://leetcode-cn.com/problems/QTMn0o/)
- [11 剑指 Offer II 011. 0 和 1 个数相同的子数组](https://leetcode-cn.com/problems/A1NYOS/)
- [12 剑指 Offer II 012. 左右两边子数组的和相等](https://leetcode-cn.com/problems/tvdfij/)
- [13 剑指 Offer II 013. 二维子矩阵的和](https://leetcode-cn.com/problems/O4NDxx/)
- 2021.08.10 第5天 数组
- 2021.08.11 第6天 字符串
- 2021.08.12 第7天 链表
- 2021.08.13 第8天 链表
- 2021.08.14 第9天 链表
- [27 剑指 Offer II 027. 回文链表](https://leetcode-cn.com/problems/aMhZSa/)
- [28 剑指 Offer II 028. 展平多级双向链表](https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/solution/bian-ping-hua-duo-ji-shuang-xiang-lian-biao-by-lee/)
- [29 剑指 Offer II 029. 排序的循环链表](https://leetcode-cn.com/problems/4ueAj6/)
- 2021.08.15 第10天 哈希表
- 2021.08.16 第11天 哈希表
- 2021.08.17 第12天 栈
- 2021.08.18 第13 天 栈
- 2021.08.19 第14 天 对列
- 2021.08.20 第15 天队列
- 2021.08.21 第16天 树
- 2021.08.22第17天 树
- 2021.08.23 第18天 树
- 2021.08.24 第19天树
- 2021.08.25 第20天 堆
总结
找链表中间节点的时候，用快慢指针，当快慢指针初始都指向head,结束条件不能是
while(fast!=null&&fast.next!=null)
因为这样的话，判断出来比如 1 2 3 1 ，就找到的是3 ，[3,4]找到的就是4,我的解决方法是将快指针初始指向头结点的下一个节点
ListNode fast=head.next;
ListNode slow=head;
如果hashMap的value值是List,怎么把所有的value赋值给List<List>
new ArrayList<List<String>>(map.values());
用数组模拟栈的时候，记得把栈顶置为-1；
list反转，Collections.reverse();
获取队列的队头元素
queue.peek()/queue.element()
java数组转list
int temp1[]=queue.poll();
List<Integer> list1 = Arrays.asList(temp1[0],temp1[1]);
list.add(list1);
2021.08.06 第 1 天 整数
1 剑指 Offer II 001. 整数除法
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’ 。
class Solution {
public int divide(int a, int b) {
if(a==0x80000000&&b==-1)//溢出的情况，-2^31/-1
return 0x7FFFFFFF;
int positive=2;//标记正数的个数
if(a>0){
positive--;
a=-a;
}
if(b>0){
positive--;
b=-b;
}
int result=0;
//计算两个负数相除
while(a<=b){
a=a-b;
result++;
}
return positive==1?-result:result;
}
}
优化
问题分析：当被除数很大但除数很小，减法操作会执行次数很多。例如，2^31/1 执行2^31次减法。
当被除数大于除数时，继续比较判断被除数是否大于除数的2倍。如果是，继续判断被除数是否大于除数的4倍，8倍，16倍，……如果被除数最多大于除数的2k倍，那么将被除数减去除数的2k倍，然后将剩余的被除数重复前面的步骤。
为了求得15/2的商，先从15里减去8 (2^3) ，得到7；再从7里减去4(2^2), 得到3；再从3里减去2(2^1),得到1，此时1小于2，因此商是3+2+1=7
class Solution {
public int divide(int dividend, int divisor) {
//-2^31/ -1 = 2^31 溢出
if(dividend == 0x80000000 && divisor == -1){
return 0x7FFFFFFF;
}
int negative = 2;//用于记录正数个数
//由于负数转为正数 -2^31 -> 2^31 越界，所以采用正数转为负数
if(dividend > 0){
negative --;
dividend = -dividend;
}
if(divisor > 0){
negative --;
divisor = -divisor;
}
//计算两个负数相除
int result = 0;
while(dividend <= divisor){
int value = divisor;//统计减数
int quotient = 1;//统计商
while(value > 0xc0000000 && value + value >= dividend){//value > 0xc0000000 防止value*2溢出
quotient += quotient;//如果可以用乘法 quotient*=2
value += value;//如果可以用乘法 value*=2
}
result += quotient;
dividend -= value;
}
return negative == 1 ? -result : result;
}
}
0xc0000000表示32位int型最小负整数的一半(-2^31)/2。，因为除数和被除数都已经转成负数了，所以上面判断的形式是除数大于被除数。
方法2：
位运算快速除
class Solution {
public int divide(int a, int b) {
int signBit = 0x80000000;
long ans = 0, x = a, y = b;
//不直接使用Math.abs()是为了避免除数或被除数为-2^31的情况，此时Math.abs()返回将出错
x = x < 0 ? -x : x;
y = y < 0 ? -y : y;
//示例：60/8=(60-32)/8+4=(60-32-16)/8+2+4=(60-32-16-8)/8+1+2+4=1+2+4=7
while (x >= y) {
long cnt = 1, base = y;
while (x > (base << 1)) {
cnt <<= 1;
base <<= 1;
}
ans += cnt;
x -= base;
}
ans = (((a ^ b) & signBit) == 0) ? ans : -ans;
return (int) ((Integer.MAX_VALUE < ans || ans < Integer.MIN_VALUE) ? Integer.MAX_VALUE : ans);
}
}
2 剑指 Offer II 002. 二进制加法
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
class Solution {
public String addBinary(String a, String b) {
int len1=a.length();
int len2=b.length();
//如果字符串长度不一样，在较短的字符串前面补0
if(len1>len2){
for(int i=0;i<len1-len2;i++)
{
b="0"+b;
}
}
if(len1<len2)
{
for(int i=0;i<len2-len1;i++)
{
a="0"+a;
}
}
len1=a.length();
len2=b.length();
int len3=len1+1;
int arr[]=new int[len3];//相加的结果可能比原来的字符串多一位
int carry=0;
len3=len3-1;
len1=len1-1;
len2=len2-1;
while(len1>=0&&len2>=0){
if( a.charAt(len1)=='1'&&b.charAt(len2)=='1')
{
if(carry==1)//进位为1的情况
arr[len3]=1;
else
arr[len3]=0;
carry=1;//计算完之后，进位为1
}
else if(a.charAt(len1)=='0'&&b.charAt(len2)=='0')
{
arr[len3]=carry;
carry=0;//计算完之后，进位为0
}
else{
if(carry==1)
arr[len3]=0;
else
arr[len3]=1;
//计算完之后，进位不会改变
}
len1--;
len2--;
len3--;
}
arr[0]=carry;//把进位加到arr的第一个元素
String str="";
if(arr[0]==1) str="1";
for(int i=1;i<arr.length;i++)//拼接字符串
str+=arr[i];
return str;
}
}
解法二：道理都一样，只是非常简洁
参考：二进制求和
class Solution {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer();
int n = Math.max(a.length(), b.length()), carry = 0;
for (int i = 0; i < n; ++i) {
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
ans.append((char) (carry % 2 + '0'));
carry /= 2;
}
if (carry > 0) {
ans.append('1');
}
ans.reverse();
return ans.toString();
}
}
3 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
class Solution {
public int[] countBits(int n) {
int[] res = new int[n+1];
for(int i=1;i<n+1;i++)
res[i] = res[i>>1] + (i%2);
return res;
}
}
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/counting-bits/solution/bi-te-wei-ji-shu-by-leetcode-solution-0t1i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 0; i <= n; i++) {
bits[i] = countOnes(i);
}
return bits;
}
public int countOnes(int x) {
int ones = 0;
while (x > 0) {
x &= (x - 1);
ones++;
}
return ones;
}
}
2021.08.07 第2天 整数
4 剑指 Offer II 004. 只出现一次的数字
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
思路1：哈希表，用map存储元素和该元素出现的次数，最后遍历即可
思路2：位运算
如果是一个数出现了一次，其他书都出现了两次，那么我们可以对整个数组的元素做异或运算，得到的结果即为只出现一次的数
现在其他数字出现了3次，我们可以考虑分别把所有数的每一个二进制位都相加
因为3个重复的数，他们的二进制位是相同的，加起来要么是0，要么是3，如果再加上不重复那个数的二进制位，可能变成0，或者是4，我们对3取一个模就是不重复数的二进制位了
怎么取出每一个数的第n个二进制位？
可以考虑把这个数右移一位，再与1相与（比如1011，取第二个二进制位，注意，最右边为第一个二进制位，1011右移1位变成0101,0101&0001=1，就把这个二进制位取出来了
所以，取出一个数的第n个二进制位的公式
x>>(n-1)&1
得到取模后的值之后怎么计算？
把result初始化为0，比如计算出来,第1位二进制位是1，那么只需要把result与1左移0位的值相或就可以了，相或的意思就是保留所有二进制为1的为
记算出来,第3位二进制位是1，那么只需要把result与1左移2位的值（0100）相或就可以
class Solution {
public int singleNumber(int[] nums) {
int result=0;
for(int i=0;i<32;i++) {
int temp=0;
for(int j=0;j<nums.length;j++)
{
temp+=(nums[j]>>i)&1;
}
if(temp%3!=0)
result|=(1<<i);
}
return result;
}
}
5 剑指 Offer II 005. 单词长度的最大乘积
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
思路1：暴力枚举（会超时），对于每一个字符串，都枚举它和它后面的字符串的组合，看是否有重复字符，没有则计算两者的长度乘积
class Solution {
public int maxProduct(String[] words) {
int max=0;
for(int i=0;i<words.length;i++){
for(int j=i;j<words.length;j++){
if(!isSame(words[i],words[j])){
max=Math.max(max,words[i].length()*words[j].length());
}
}
}
return max;
}
public boolean isSame(String a,String b){
for(int i=0;i<a.length();i++){
for(int j=0;j<b.length();j++){
if(a.charAt(i)==b.charAt(j))
return true;
}
}
return false;
}
}
思路2：位运算
考虑怎么降低比较两个字符串有没有相同字符的复杂度，可以把字符串转化为整数，比如
出现a,那么转成整数就是result|=1<<0
出现z,就是result|=1<<25
比较两个字符串有没有相同字符就可以转化成比较两个字符串对应的整数相与是否为0，相与为0，说明两者包含的字符没有重复的（在二进制位看就是二进位为1的数刚好错开了）
public static int maxProduct2(String[] words) {
int length = words.length;
int[] ints = new int[length];
for (int i = 0; i < length ; i++) {
for (char c : words[i].toCharArray()){
ints[i] |= (1 << (c - 97));//使用整型数代表word中的一个字符串
}
}
int re = 0;
for (int i = 0; i < length -1 ; i++) {//进行整型数的比较并得出最大长度
int pre1 = ints[i];
for (int j = i + 1; j < length; j++) {
int pre2 = ints[j];
if ((pre1 & pre2) == 0){//与运算
int te = words[i].length() * words[j].length();
re = re >= te ? re : te;
}
}
}
return re;
}
作者：closes
链接：https://leetcode-cn.com/problems/maximum-product-of-word-lengths/solution/qiao-miao-di-shi-yong-zheng-xing-shu-de-vec14/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
6 剑指 Offer II 006. 排序数组中两个数字之和
解题思路：双指针指向头尾
头+尾<target 说明加数不够，把i后移
头+尾>target 说明加数有多，把j前移
class Solution {
public int[] twoSum(int[] numbers, int target) {
int i=0;int j=numbers.length-1;
while(i<j){
if(numbers[i]+numbers[j]<target)
i++;
else if (numbers[i]+numbers[j]>target)
j--;
else
return new int[]{i,j};
}
return null;
}
}
思路二：二分查找
在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; ++i) {
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return new int[]{-1, -1};
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/solution/liang-shu-zhi-he-ii-shu-ru-you-xu-shu-zu-by-leet-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2021.08.08 第3天 数组
7 剑指 Offer II 007. 数组中和为 0 的三个数
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请找出所有和为 0 且 不重复 的三元组。
思路 ：注意是要找不重复的三元组，如果用暴力遍历，必然会找到重复的元组，
所以我们考虑先将数组排序
首先在外循环每次定位一个数字，内循环就是相当于排序数组的twoSum，用双指针，为了避免重复，外循环每次应该跳过相同的元素
总体来说是先固定第一位加数，然后固定第二位加数，第3位加数用双指针来解
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result=new ArrayList();
for(int i=0;i<nums.length;i++) {
if(i>0&&nums[i]==nums[i-1])
continue; //跳过相同的数
int k=nums.length-1;
for(int m=i+1;m<nums.length;m++){
if(m>i+1&&nums[m]==nums[m-1])
continue; //跳过相同的数
while(m<k){
if(nums[m]+nums[k]>0-nums[i])
k--;///相加较大，右指针前移
else if(nums[m]+nums[k]<0-nums[i])
break; //因为我们是固定了左指针，左指针不能动，相加较小的情况不合题意，直接break
else{
List<Integer>list=new ArrayList();//注意list创建的位置
list.add(nums[i]);
list.add(nums[m]);
list.add(nums[k]);
result.add(list);
break;
}
}
}
}
return result;
}
}
官方的解法还是会快一点
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚举 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚举的数不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList();
int len = nums.length;
if(nums == null || len < 3) return ans;
Arrays.sort(nums); // 排序
for (int i = 0; i < len ; i++) {
if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
int L = i+1;
int R = len-1;
while(L < R){
int sum = nums[i] + nums[L] + nums[R];
if(sum == 0){
ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
while (L<R && nums[L] == nums[L+1]) L++; // 去重
while (L<R && nums[R] == nums[R-1]) R--; // 去重
L++;
R--;
}
else if (sum < 0) L++;
else if (sum > 0) R--;
}
}
return ans;
}
}
去重之后的L++和R–是因为此时L和R指向的数字还是与前一个数字相同
真的太绝了。请收下我的膝盖
8 剑指 Offer II 008. 和大于等于 target 的最短子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路1：当得到的和满足条件>= target之后，记录当前的长度，然后把左指针右移，看看是否还满足，直到不满足，再把右指针后移
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int min = nums.length + 1;
int sum = nums[left];
if (sum > target) return 1;
for (int i = 1; i <= nums.length - 1; i++) {
sum += nums[i];
while (sum >= target) {
min = Math.min(min, i - left + 1);
sum = sum - nums[left];
left++;
}
}
return min>nums.length?0:min;
}
}
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int lo = 0, hi = 0, sum = 0, min = Integer.MAX_VALUE;
while (hi < nums.length) {
sum += nums[hi++];
while (sum >= s) {
min = Math.min(min, hi - lo);
sum -= nums[lo++];
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
思路二：暴力解决
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum >= s) {
ans = Math.min(ans, j - i + 1);
break;
}
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/chang-du-zui-xiao-de-zi-shu-zu-by-leetcode-solutio/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
9 剑指 Offer II 009. 乘积小于 K 的子数组
给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
思路：从左到右遍历累乘，乘积小于k，则继续乘，大于k，则将成绩置为1，左指针后移一位，从左指针开始乘
比如输入: nums = [10,5,2,6], k = 100，就依次遍历的是 10 、10*5 、10 * 5 * 2、 5、 5 * 2、 5 * 2 *6
2 、2 * 6 、 6 符合条件的有8个
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int lo=1;int hi=0; int n=nums.length;int product=1;
int result=0;
while(hi<n){
product*=nums[hi++];
if(product<k){
result++;
if(hi==n){//hi到达最后了，需要处理，否则不满足循环条件，循环结束
product=1;
hi=lo++;
}
}
else{
product=1;
hi=lo++;
}
}
return result;
}
}
思路2：考虑以每一个数组元素结尾的子数组的个数，它们相加
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0;
int prod = 1, ans = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
prod *= nums[right];
while (prod >= k) prod /= nums[left++];
ans += right - left + 1;
}
return ans;
}
}
2021.08.09 第4天 数组
10 剑指 Offer II 010. 和为 k 的子数组
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
思路：想用滑动窗，但是细节太多了，写了一堆废代码
看看别人的吧
1 暴力
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for (int start = 0; start < nums.length; start++) {
int sum = 0;
for (int end = start; end >= 0; end--) {
sum += nums[end];
if (sum == k) {
count++;
}
}
}
return count;
}
}
2 前缀和 + 哈希表优化
public class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap < Integer, Integer > mp = new HashMap < > ();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (mp.containsKey(pre - k)) {
count += mp.get(pre - k);
}
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
}
11 剑指 Offer II 011. 0 和 1 个数相同的子数组
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
前缀和 啊啊啊
12 剑指 Offer II 012. 左右两边子数组的和相等
13 剑指 Offer II 013. 二维子矩阵的和
2021.08.10 第5天 数组
14 剑指 Offer II 014. 字符串中的变位词
解题思路：滑动窗口，用两个数组存储滑动窗内字符的出现次数，每滑动一次就比较一次两个数组是否相等
class Solution {
public boolean checkInclusion(String s1, String s2) {
if(s1.length()>s2.length())
return false;
int nums1[]=new int [26];
int nums2[]=new int[26];
for(int i=0;i<s1.length();i++)
nums1[s1.charAt(i)-'a']+=1;
int left=0;
int right=s1.length()+left-1;
for(int i=0;i<=right;i++)
nums2[s2.charAt(i)-'a']+=1;
if(isEqual(nums1,nums2))
return true;
while(right<s2.length()){
nums2[s2.charAt(left++)-'a']--;
right++;
if(right==s2.length())
return false;
nums2[s2.charAt(right)-'a']++;
if(isEqual(nums1,nums2))
return true;
}
return false;
}
public boolean isEqual(int nums1[],int nums2[]){
for(int i=0;i<nums1.length;i++){
if(nums1[i]!=nums2[i])
return false;
}
return true;
}
}
15 剑指 Offer II 015. 字符串中的所有变位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
思路，就是把第14题的代码改了一下，符合条件的地方把left索引加list
class Solution {
List<Integer>list=new ArrayList();
public List<Integer> findAnagrams(String s, String p) {
return find(p,s);
}
public List<Integer> find(String s1,String s2){
if(s1.length()>s2.length())
return list;
int nums1[]=new int [26];
int nums2[]=new int[26];
for(int i=0;i<s1.length();i++)
nums1[s1.charAt(i)-'a']+=1;
int left=0;
int right=s1.length()+left-1;
for(int i=0;i<=right;i++)
nums2[s2.charAt(i)-'a']+=1;
if(isEqual(nums1,nums2))
list.add(left);
while(right<s2.length()){
nums2[s2.charAt(left++)-'a']--;
right++;
if(right==s2.length())
break;
nums2[s2.charAt(right)-'a']++;
if(isEqual(nums1,nums2))
list.add(left);
}
return list;
}
public boolean isEqual(int nums1[],int nums2[]){
for(int i=0;i<nums1.length;i++){
if(nums1[i]!=nums2[i])
return false;
}
return true;
}
}
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int n = s.length(), m = p.length();
List<Integer> res = new ArrayList<>();
if(n < m) return res;
int[] pCnt = new int[26];
int[] sCnt = new int[26];
for(int i = 0; i < m; i++){
pCnt[p.charAt(i) - 'a']++;
sCnt[s.charAt(i) - 'a']++;
}
if(Arrays.equals(sCnt, pCnt)){
res.add(0);
}
for(int i = m; i < n; i++){
sCnt[s.charAt(i - m) - 'a']--;
sCnt[s.charAt(i) - 'a']++;
if(Arrays.equals(sCnt, pCnt)){
res.add(i - m + 1);
}
}
return res;
}
}
我悟了
需要注意的是，在匹配之后，left指针不能马上移动到right指针之后，因为可能就left和right同时移动1个或者2个位置就又能匹配了
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int n = s.length(), m = p.length();
List<Integer> res = new ArrayList<>();
if(n < m) return res;
int[] pCnt = new int[26];
int[] sCnt = new int[26];
for(int i = 0; i < m; i++){
pCnt[p.charAt(i) - 'a'] ++;
}
int left = 0;
for(int right = 0; right < n; right++){
int curRight = s.charAt(right) - 'a';
sCnt[curRight]++;
while(sCnt[curRight] > pCnt[curRight]){
int curLeft = s.charAt(left) - 'a';
sCnt[curLeft]--;
left++;
}
if(right - left + 1 == m){
res.add(left);
}
}
return res;
}
}
16 剑指 Offer II 016. 不含重复字符的最长子字符串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
下面写的滑动窗口的方法，没有考虑到
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length()==0)
return 0;
int left=0;
int nums[]=new int[128];
int max=0;
for(int right=0;right<s.length();right++){
int cur=s.charAt(right)-32;
nums[cur]++;
if(nums[cur]>1){//出现了重复字符
max=Math.max(max,right-left);//保留当前出现重复字符前的长度
while(nums[cur]>1){//左指针后移，直到left和right区间内没有重复字符
int remove=s.charAt(left)-32;//32是空格space的ASCII嘛，也就是说所有字符的ascii码都在32之后
nums[remove]--;//左指针移动后，相应字符映射到数组中的位置对应的值减1
left++;//左指针后移
}
}
}
max=Math.max(max,s.length()-left);//这是右指针移动到最后也没有出现重复字符的情况，单独讨论一下
return max;
}
}
其他解法，参考：leetcode 3. 无重复字符的最长子串
2021.08.11 第6天 字符串
17 剑指 Offer II 017. 含有所有字符的最短字符串
18 剑指 Offer II 018. 有效的回文
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。
解题思路 ：双指针
class Solution {
public boolean isPalindrome(String s) {
int n = s.length();
int left = 0, right = n - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
++left;
}
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
--right;
}
if (left < right) {
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
++left;
--right;
}
}
return true;
}
}
19 剑指 Offer II 019. 最多删除一个字符得到回文
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
class Solution {
int del = 0; //记录删除的字符次数
public boolean validPalindrome(String s) {
int i = 0,j = s.length()-1;
while(i < j){
if(s.charAt(i) == s.charAt(j)){
i++;
j--;
}else{
//不相等的话，若没有删除字符，则删除左边或右边的字符再判断；若删除过一次，则不是回文串
if(del == 0){
del++;
return validPalindrome(s.substring(i,j)) || validPalindrome(s.substring(i+1,j+1));
}
return false;
}
}
return true;
}
}
20 剑指 Offer II 020. 回文子字符串的个数
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
思路
分别计算以i为中心向外扩散的回文串的个数和以(i,i+1)为中心的向外扩散的回文串的个数，然后相加
class Solution {
public int countSubstrings(String s) {
int result=0;
for(int i=0;i<s.length();i++)
result+=palindrome( s, i)+palindrome(s, i,i+1);
return result;
}
public int palindrome(String s,int i){//以i为中心的回文串
int count=1;//单个字符也是回文
int left=i-1;
int right=i+1;
while(left>=0&&right<s.length()&&(s.charAt(left)==s.charAt(right))){
left--;
right++;
count++;
}
return count;
}
public int palindrome(String s,int i,int j){//以i,j为中心的回文串
if(j>=s.length()||s.charAt(i)!=s.charAt(j))
return 0;
int count=1;//s.charAt(i)=s.charAt(j)时，也是一个回文
int left=i-1;
int right=j+1;
while(left>=0&&right<s.length()&&(s.charAt(left)==s.charAt(right))) {
left--;
right++;
count++;
}
return count;
}
}
可以简化，只用一个中心扩展函数
class Solution {
public int countSubstrings(String s) {
int result=0;
for(int i=0;i<s.length();i++)
result+=palindrome( s, i,i)+palindrome(s, i,i+1);
return result;
}
public int palindrome(String s,int i,int j){//以i,j为中心的回文串
if(j>=s.length()||s.charAt(i)!=s.charAt(j))
return 0;
int count=1;//s.charAt(i)=s.charAt(j)时，也是一个回文
int left=i-1;
int right=j+1;
while(left>=0&&right<s.length()&&(s.charAt(left)==s.charAt(right))) {
left--;
right++;
count++;
}
return count;
}
}
差不多，更简洁一点
public class Solution {
public int countSubstrings(String s) {
int ans = 0;
for(int i=0;i<s.length();i++)
ans+=CountSubstringsInternal(s,i,i)+CountSubstringsInternal(s,i,i+1);
return ans;
}
public int CountSubstringsInternal(String s, int l, int r)
{
int cnt=0;
while(l>=0&&r<s.length())
{
if(s.charAt(l--)!=s.charAt(r++)) break;
cnt++;
}
return cnt;
}
}
思路二：动态规划
public int countSubstrings(String s) {
int length = s.length();
boolean[] dp = new boolean[length];
int count = 0;//回文串的数量
for (int j = 0; j < length; j++) {
for (int i = 0; i <= j; i++) {
if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1])) {
dp[i] = true;
count++;
} else {
dp[i] = false;
}
}
}
return count;
}
作者：sdwwld
链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/shu-ju-jie-gou-he-suan-fa-dong-tai-gui-h-3bms/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2021.08.12 第7天 链表
21 剑指 Offer II 021. 删除链表的倒数第 n 个结点
思路1：利用递归
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int num=help( head,n);
return num==n?head.next:head;
}
public int help(ListNode head,int n){
if(head==null)
return 0;//倒数第0个节点
int num= help(head.next,n);//head.next是倒数第几个节点
if(num==n)
head.next=head.next.next;//删除倒数n个结点，n已经说了大于0，这里不用考虑空指针
return 1+num;
}
}
思路2:迭代，迭代写过很多次了，用快慢指针，快指针先走n步，然后两个指针一起走，快指针走到终点时两个指针都走了length-n步，局可以删除慢指针指向的节点的下一个节点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast=head;
ListNode slow=head;
while(n>0){
fast=fast.next;
n--;
}
if(fast==null)//要删除的是头结点
return head.next;
while(fast.next!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return head;
}
}
可以利用假的头结点简化代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode fast=head;
ListNode slow=dummy;
while(n>0){
fast=fast.next;
n--;
}
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
slow.next=slow.next.next;
return dummy.next;
}
}
22 剑指 Offer II 022. 链表中环的入口节点
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
解题思路：快慢指针
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(slow==fast){//快慢指针相遇，说明有环
fast=head;
while(fast!=slow){//让快指针指向头结点，然后快慢指针同时移动，再次相遇的点就是入环点
fast=fast.next;
slow=slow.next;
}
return fast;
}
}
return null;
}
}
思路2 ：哈希表，将访问过的节点存入Set,第一个被重复放进去的节点就是入环点
23 剑指 Offer II 023. 两个链表的第一个重合节点
给定两个单链表的头节点 headA 和 headB ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路1：双指针
一个指针从headA开始走，为空了，就从headB开始走
另一个指针从headB开始走，为空了，就从headA开始走
这样相遇时走过的路程是一样的
需要注意的是，如果两个链表没有交点，那么第二遍走完两个指针都指向null,也会退出循环
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempA=headA;
ListNode tempB=headB;
while( tempA!=tempB){
tempA=(tempA!=null)?tempA.next:headB;
tempB=(tempB!=null)?tempB.next:headA;
}
return tempA;
}
}
思路二：哈希表
把一个链表全部入Set，然后入第二个链表的节点，第一个重复的就是交点，没有重复的节点就返回Null
思路三：暴力两层while循环，依次在一个链表中比较另一个链表的每一个节点
2021.08.13 第8天 链表
24 剑指 Offer II 024. 反转链表
思路一：迭代
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
ListNode next=null;
while(cur!=null){
next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
迭代+假头
class Solution {
public ListNode reverseList(ListNode head) {
ListNode dummy=new ListNode(0);
//dummy.next=head;
ListNode temp=dummy;
ListNode end=null;
while(head!=null){
ListNode next=head.next;
end=temp.next;
temp.next=head;
head.next=end;
head=next;
}
return dummy.next;
}
}
思路3：递归
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode p=reverseList(head.next);
head.next.next=head;
head.next=null;
return p;
}
}
public ListNode reverseList(ListNode head) {
// 上一个节点，到最后会变成头节点
ListNode last = null;
while(head!=null){
// 临时保存下一个节点
ListNode next = head.next;
// 下一个节点指向上一个节点
head.next = last;
// 执行完，记录一下当前节点
last = head;
// 下一个节点
head = next;
}
return last;
}
作者：felix-he
链接：https://leetcode-cn.com/problems/UHnkqh/solution/fan-zhuan-lian-biao-xiang-jie-ban-by-fel-tyu5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
25 剑指 Offer II 025. 链表中的两数相加
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
可以假设除了数字 0 之外，这两个数字都不会以零开头。
解题思路：先把两个链表反转，然后就变成了力扣第二道题两数相加，然后相加反转后的链表，把得到的结果再进行反转就可以了
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1= reverseList(l1);
l2= reverseList(l2);
ListNode node=addTwoNumbers(l1, l2,0);
return reverseList(node);
}
public ListNode reverseList(ListNode head){
if(head==null||head.next==null)
return head;
ListNode p=reverseList(head.next);
head.next.next=head;
head.next=null;
return p;
}
public ListNode addTwoNumbers(ListNode l1, ListNode l2,int a){
if(l1==null&&l2==null)
return a==0?null:new ListNode(a);//链表都走到最后一个，但是有进位的情况
if(l1!=null){
a+=l1.val;
l1=l1.next;
}
if(l2!=null){
a+=l2.val;
l2=l2.next;
}
ListNode node=new ListNode(a%10);
node.next=addTwoNumbers(l1, l2,a/10);
return node;
}
}
思路2：使用栈
本题的主要难点在于链表中数位的顺序与我们做加法的顺序是相反的，为了逆序处理所有数位，我们可以使用栈：把所有数字压入栈中，再依次取出相加。计算过程中需要注意进位的情况。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new LinkedList<Integer>();
Deque<Integer> stack2 = new LinkedList<Integer>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode ans = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int a = stack1.isEmpty() ? 0 : stack1.pop();
int b = stack2.isEmpty() ? 0 : stack2.pop();
int cur = a + b + carry;
carry = cur / 10;
cur %= 10;
ListNode curnode = new ListNode(cur);
curnode.next = ans;
ans = curnode;
}
return ans;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/add-two-numbers-ii/solution/liang-shu-xiang-jia-ii-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
26 剑指 Offer II 026. 重排链表
思路：利用栈，把链表节点全部入栈，然后接下的操作就相当于在原来链表的基础上，每次从栈中取出一个元素插入到链表中，4个元素需要弹出2次，7个元素需要弹出3次，弹出次数为链表长度除以2
class Solution {
public void reorderList(ListNode head) {
Stack<ListNode>stack=new Stack();
ListNode temp=head;
int count=0;
while(temp!=null){
stack.push(temp);
temp=temp.next;
count++;
}
temp=head;
int mod=count/2;//栈最多弹出这么多次
while(mod>0){
ListNode next=temp.next;
temp.next=stack.pop();
temp=temp.next;
temp.next=next;
temp=next;
mod--;
}
temp.next=null;
}
}
可以再合并一下
2021.08.14 第9天 链表
27 剑指 Offer II 027. 回文链表
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
解题思路1：把节点的值全部存入栈，然后从头结点开始遍历，看每一个值是否和栈顶相等
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer>stack=new Stack();
ListNode temp=head;
while(temp!=null){
stack.push(temp.val);
temp=temp.next;
}
temp=head;
while(temp!=null){
if(temp.val!=stack.pop())
return false;
temp=temp.next;
}
return true;
}
}
思路2 ：找到中间节点，反转链表的后半部分，然后比较
需要注意的是，如果链表的长度为奇数，那么前部分比后半部分长度多一个
如果链表的长度为偶数，那么前部分和后半部分长度相等
所以遍历的时候，如果后半部分遍历完毕，就停止遍历
class Solution {
public boolean isPalindrome(ListNode head) {
//解题思路2，找到中间节点，反转后一半链表
if(head==null||head.next==null)
return true;
ListNode mid= finMid(head);
ListNode reverse=reverseList(mid.next);//后半段反转之后的头结点
while(reverse!=null){
if(head.val!=reverse.val)
return false;
head=head.next;
reverse=reverse.next;
}
return true;
}
public ListNode finMid(ListNode head){
ListNode fast=head.next;
ListNode slow=head;
if(head.next.next==null) {
return slow;
}
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
public ListNode reverseList(ListNode head){
if(head==null||head.next==null)
return head;
ListNode p= reverseList(head.next);
head.next.next=head;
head.next=null;
return p;
}
}
上面是先找到中点再反转，也可以找中点的过程中，一边遍历，一边反转
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
ListNode pre = head, prepre = null;
while(fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
pre.next = prepre;
prepre = pre;
}
if(fast != null) {
slow = slow.next;
}
while(pre != null && slow != null) {
if(pre.val != slow.val) {
return false;
}
pre = pre.next;
slow = slow.next;
}
return true;
}
}
思路3 把元素放到数组里面，然后用双指针
class Solution {
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 将链表的值复制到数组中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用双指针判断是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
思路4 递归
class Solution {
private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) {
return false;
}
if (currentNode.val != frontPointer.val) {
return false;
}
frontPointer = frontPointer.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
frontPointer = head;
return recursivelyCheck(head);
}
}
28 剑指 Offer II 028. 展平多级双向链表
多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。
思路1 递归
class Solution {
private Node node;
public Node flatten(Node head) {
if(head == null) {
return null;
}
if(node != null) {
node.next = head;
head.prev = node;
node.child = null;
}
node = head;
//开始遍历child时（比如3, 7)，next会被改变，所以用nextNode保存一下
Node nextNode = head.next;
flatten(head.child);
flatten(nextNode);
return head;
}
}
迭代
class Solution {
public Node flatten(Node head) {
if (head == null) return head;
Node pseudoHead = new Node(0, null, head, null);
Node curr, prev = pseudoHead;
Deque<Node> stack = new ArrayDeque<>();
stack.push(head);
while (!stack.isEmpty()) {
curr = stack.pop();
prev.next = curr;
curr.prev = prev;
if (curr.next != null) stack.push(curr.next);
if (curr.child != null) {
stack.push(curr.child);
// don't forget to remove all child pointers.
curr.child = null;
}
prev = curr;
}
// detach the pseudo node from the result
pseudoHead.next.prev = null;
return pseudoHead.next;
}
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list/solution/bian-ping-hua-duo-ji-shuang-xiang-lian-biao-by-lee/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
29 剑指 Offer II 029. 排序的循环链表
class Solution {
public Node insert(Node head, int insertVal) {
if(head==null)//原始链表为空，根据题意，新建一个链表，并且形成环
{
head = new Node(insertVal);
head.next=head;
return head;
}
Node cur = head,max=null;//max用来处理插入值小于当前最小值和大于当前最大值的情况
while(cur.next!=head)
{
//找大于等于当前值，小于等于下一个值的插入点。
if(cur.val<=insertVal&&cur.next.val>=insertVal) break;
//顺便把升序的尾部找到
if(cur.val>cur.next.val) max=cur;
cur=cur.next;
}
//遍历完没找到升序的尾部，那它肯定就是head的前一个Node，也就是现在的cur
if(max==null) max=cur;
//成功找到大于等于当前值，小于等于下一个值的插入点，那么进行插入即可
if(cur.val<=insertVal&&cur.next.val>=insertVal)
{
var nn = new Node(insertVal,cur.next);
cur.next=nn;
}
//没找到插入点，那么不管是比最大值大还是比最小值小，都是插到当前最大值的之后（同时肯定也是当前最小值之前）
else
{
var nn = new Node(insertVal,max.next);
max.next=nn;
}
return head;
}
}
2021.08.15 第10天 哈希表
30 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器
HashMap+ArrayList
想在数组中实现O(1)的删除，那么用末尾数据交换要删除数据，然后删除末尾数据。
HashMa的key存储元素值，val存储元素的索引
class RandomizedSet {
// 解法1
// HashMap + ArrayList
private Random random;
private Map<Integer, Integer> map;
private List<Integer> list;
/** Initialize your data structure here. */
public RandomizedSet() {
random = new Random();
// map存集合中元素在list中的位置
map = new HashMap<>();
list = new ArrayList<>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
map.put(val, list.size());
list.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int size = list.size();
int idx = map.get(val);
// 如果要移除的元素不是列表中最后一项, 将最后一项的元素移动至要移除的位置
if (idx < size - 1) {
int lastItem = list.get(size - 1);
list.set(map.get(val), lastItem);
map.put(lastItem, idx);
}
list.remove(size - 1);
map.remove(val);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
本题最主要的要求是要达到三种操作都是o(1)的复杂度，首先插入的复杂度达到o(1)大多数数据结构都能达到，难点就在于随机访问和删除。其实对于删除的时间复杂度我们很容易想到哈希表，而随机访问我们又十分容易联想到数组利用下标访问。
参考：
添加链接描述https://leetcode-cn.com/problems/FortPu/solution/java-ti-jie-by-cuncun-cun-cun-cun-gpx3/
public class RandomizedSet {
private class Node{
Node pre;
Node next;
int val;
public Node(Node pre, Node tail, int val) {
this.pre = pre;
this.next = tail;
this.val = val;
}
public Node() {
}
public Node(int val) {
this.val = val;
}
}
Node head;
Node tail;
Map<Integer,Node> map;
ArrayList<Node> list;
public RandomizedSet() {
head=new Node();
tail=new Node();
map=new HashMap<>();
list=new ArrayList<>();
head.next=tail;
tail.pre=head;
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val))
return false;
Node node=new Node(val);
tail.pre.next=node;
node.pre=tail.pre;
node.next=tail;
tail.pre=node;
list.add(node);
map.put(val,node);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val))
return false;
Node node=map.get(val);
node.pre.next=node.next;
node.next.pre=node.pre;
map.remove(val);
list.remove(node);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
int index=(int)(Math.random()*list.size());
return list.get(index).val;
}
}
31 剑指 Offer II 031. 最近最少使用缓存
这是我自己写的代码
首先基础架构是利用HashMap和双向链表，hashMap插入和查找元素都非常快，但是不是有序的，双向链表插入和删除快，且有序，但是定位到要删除的元素就比较耗费时间，所以把两者结合起来
利用双向链表和HashMap,HashMap的key就存储传入的key，Value存储封装了key和value的Node类型
我们定义一个删除节点的函数和在链表头部插入节点的函数
删除：根据传入的key，去hashMap里面检查有没有对应的Key,没有，则直接返回-1，如果有，把这个节点从当前位置删除，因为是双向链表，所以，删除元素设计当前元素的前后节点的指针改变指向
插入头部：可以使用一个假头，相当于在头结点之后插入一个节点，很简单
class LRUCache {
private int cap;
private int count=0;//计数当前存了多少个元素
private Map<Integer,Node>map=new HashMap();
Node head=null;//记录双向链表的头结点
Node tail=null;//记录双向链表的尾结点
public LRUCache(int capacity) {
this.cap=capacity;
}
public int get(int key) {
if(map.containsKey(key)){
Node node=map.get(key);
delete(node.key);
addToFirst(node);//然后加入到链表头部
return node.val;
}
return -1;
}
public void put(int key, int value) {
Node node=new Node(key,value);
if(map.containsKey(key)){
delete(key);//如果map中有当前key，先移除这个key，
addToFirst(node);//然后加入到链表头部
}
else {
if(count==cap){
delete(tail.key);
addToFirst(node);//然后加入到链表头部
}
else{
addToFirst(node);//然后加入到链表头部
}
}
}
public void delete(int key){
Node node=map.get(key);
if(node==head){//是第一个节点
if(head.next!=null){//不只有一个节点
head.next.pre=null;
head=head.next;
}
else{//只有一个节点的情况
head=null;
tail=null;
}
}
else if(node==tail){//是最后一个节点
if(tail.pre!=null)//不只有一个节点
tail.pre.next=null;
tail=tail.pre;//只有一个节点也会执行
}
else{
node.pre.next=node.next;
node.next.pre=node.pre;
}
map.remove(key);
count--;
}
public void addToFirst(Node node){
if(head==null)//当前没有元素
head=tail=node;
else {//当前链表有元素
node.next=head;
head.pre=node;
head=node;
}
count++;
map.put(node.key,node);
}
}
class Node{
int key;
int val;
Node pre;
Node next;
public Node(int key,int val){
this.key=key;
this.val=val;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
看到一个题解，跟我的思路差不多，不过比我的见简洁
class ListNode {
//成员变量
int key;
int value;
ListNode next;
ListNode prev;
//构造方法
public ListNode(int key, int value){
this.key = key;
this.value = value;
}
}
class LRUCache {
//成员变量
private ListNode head;//虚拟头结点
private ListNode tail;//虚拟尾节点
private Map<Integer, ListNode> numToNode;//哈希表的键是缓存的键
private int capacity;
public LRUCache(int capacity) {
numToNode = new HashMap<>();
//初始化双向链表
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.prev = head;
this.capacity = capacity;
}
public int get(int key) {
if(!numToNode.containsKey(key)){
return -1;
}
ListNode node = numToNode.get(key);
moveToTail(node, node.value);
return node.value;
}
public void put(int key, int value) {
if(numToNode.containsKey(key)){//哈希表包含键
moveToTail(numToNode.get(key), value);
}else{//哈希表不包含键
if(numToNode.size() == capacity){//缓存达到容量上限
ListNode node = head.next;
deleteNode(node);//双向链表删除最近最少使用节点
numToNode.remove(node.key);//哈希表（缓存）删除最近最少使用节点
}
//缓存未达到容量上限
ListNode node = new ListNode(key, value);
insertToTail(node);//双向链表插入节点
numToNode.put(key, node);//哈希表（缓存）插入节点
}
}
//将节点移动到双向链表的尾部
private void moveToTail(ListNode node, int newValue){
deleteNode(node);
node.value = newValue;//如果是插入一个键值对，键相同，值不同，要将节点值更新移动要双向链表结尾
insertToTail(node);
}
//删除节点
private void deleteNode(ListNode node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
//将节点插入到双向链表的尾部
private void insertToTail(ListNode node){
tail.prev.next = node;
node.prev = tail.prev;
node.next = tail;
tail.prev = node;
}
}
class LRUCache {
class Node {
int k, v;
Node l, r;
Node(int _k, int _v) {
k = _k;
v = _v;
}
}
int n;
Node head, tail;
Map<Integer, Node> map;
public LRUCache(int capacity) {
n = capacity;
map = new HashMap<>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.r = tail;
tail.l = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
refresh(node);
return node.v;
}
return -1;
}
public void put(int key, int value) {
Node node = null;
if (map.containsKey(key)) {
node = map.get(key);
node.v = value;
} else {
if (map.size() == n) {
Node del = tail.l;
map.remove(del.k);
delete(del);
}
node = new Node(key, value);
map.put(key, node);
}
refresh(node);
}
// refresh 操作分两步：
// 1. 先将当前节点从双向链表中删除（如果该节点本身存在于双向链表中的话）
// 2. 将当前节点添加到双向链表头部
void refresh(Node node) {
delete(node);
node.r = head.r;
node.l = head;
head.r.l = node;
head.r = node;
}
// delete 操作：将当前节点从双向链表中移除
// 由于我们预先建立 head 和 tail 两位哨兵，因此如果 node.l 不为空，则代表了 node 本身存在于双向链表（不是新节点）
void delete(Node node) {
if (node.l != null) {
Node left = node.l;
left.r = node.r;
node.r.l = left;
}
}
}
这是我自己代码的改进版本，加了头尾哨兵，减少头结点和尾节点的判断
class LRUCache {
private int cap;
private int count=0;//计数当前存了多少个元素
private Map<Integer,Node>map=new HashMap();
Node head=null;//记录双向链表的头结点
Node tail=null;//记录双向链表的尾结点
public LRUCache(int capacity) {
this.cap=capacity;
head=new Node(-1,-1);
tail=new Node(-1,-1);
head.next=tail;
tail.pre=head;
}
public int get(int key) {
if(!map.containsKey(key))
return -1;
Node node=map.get(key);
delete(node.key);
addToFirst(node);//然后加入到链表头部
return node.val;
}
public void put(int key, int value) {
Node node=new Node(key,value);
if(map.containsKey(key)){
delete(key);//如果map中有当前key，先移除这个key，
addToFirst(node);//然后加入到链表头部
}
else {
if(count==cap)
delete(tail.pre.key);
addToFirst(node);//然后加入到链表头部
}
}
public void delete(int key){
Node node=map.get(key);
node.pre.next=node.next;
node.next.pre=node.pre;
map.remove(key);
count--;
}
public void addToFirst(Node node){
node.next=head.next;
node.pre=head;
head.next.pre=node;
head.next=node;
count++;
map.put(node.key,node);
}
}
class Node{
int key;
int val;
Node pre;
Node next;
public Node(int key,int val){
this.key=key;
this.val=val;
}
}
用LinkedHashMap实现
class LRUCache {
int cap;
LinkedHashMap<Integer,Integer> cache=new LinkedHashMap<>();
public LRUCache(int capacity) {
this.cap = capacity;
}
public int get(int key) {
if(!cache.containsKey(key))
return -1;
// 将 key 变为最近使用
makeRecently(key);
return cache.get(key);
}
public void put(int key, int value) {
if (cache.containsKey(key)) {
cache.put(key, value);// 修改 key 的值
makeRecently(key); // 将 key 变为最近使用
return;
}
if (cache.size() >= this.cap) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
cache.put(key, value); // 将新的 key 添加链表尾部
}
private void makeRecently(int key)
{
int val= cache.get(key);
cache.remove(key); // 删除 key，重新插入到队尾
cache.put(key,val);
}
}
32 剑指 Offer II 032. 有效的变位词
给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。
注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
首先本题可以通过排序来判断
解题思路：比较两个字符串中各个字符出现次数，用数组存储，第一个字符串的字符使得数组中对应的值加1，第二个字符串的字符使得数组中对应的值减1，最后数组中的值应该都是0；如果不是，返回false
class Solution {
public boolean isAnagram(String s, String t) {
int n1=s.length();
int n2=t.length();
if(n1!=n2)
return false;
if(s.equals(t))
return false;
int arr[]=new int [128];
for(int i=0;i<n1;i++)
arr[s.charAt(i)-32]++;
for(int i=0;i<n2;i++){
arr[t.charAt(i)-32]--;
if(arr[t.charAt(i)-32]<0)
return false;
}
for(int i=0;i<128;i++){
if(arr[i]%2!=0)
return false;
}
return true;
}
}
题目中要求对Unicode 字符进行处理，那么我们可以考虑使用哈希表来处理
对于进阶问题，Unicode 是为了解决传统字符编码的局限性而产生的方案，它为每个语言中的字符规定了一个唯一的二进制编码。而 Unicode中可能存在一个字符对应多个字节的问题，为了让计算机知道多少字节表示一个字符，面向传输的编码方式的 UTF−8 和 UTF−16 也随之诞生逐渐广泛使用，具体相关的知识读者可以继续查阅相关资料拓展视野，这里不再展开。
回到本题，进阶问题的核心点在于「字符是离散未知的」，因此我们用哈希表维护对应字符的频次即可。同时读者需要注意 Unicode 一个字符可能对应多个字节的问题，不同语言对于字符串读取处理的方式是不同的。
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
if(s.equals(t))
return false;
Map<Character, Integer> table = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
table.put(ch, table.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
table.put(ch, table.getOrDefault(ch, 0) - 1);
if (table.get(ch) < 0) {
return false;
}
}
return true;
}
}
2021.08.16 第11天 哈希表
33 剑指 Offer II 033. 变位词组
解题思路：
两个字符串互为字母异位词，当且仅当两个字符串包含的字母相同。同一组字母异位词中的字符串具备相同点，可以使用相同点作为一组字母异位词的标志，使用哈希表存储每一组字母异位词，哈希表的键为一组字母异位词的标志，哈希表的值为一组字母异位词列表。
遍历每个字符串，对于每个字符串，得到该字符串所在的一组字母异位词的标志，将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后，哈希表中的每个键值对即为一组字母异位词。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>>map=new HashMap();
List<List<String>> list;
for(String s:strs){
char[]arr=s.toCharArray();
Arrays.sort(arr);
String temp=new String(arr);
if(map.containsKey(temp)){
map.get(temp).add(s);
}else{
map.put(temp,new ArrayList());
map.get(temp).add(s);
}
}
return new ArrayList<List<String>>(map.values());
}
}
思路2：计数
太绝了，统计每个字母的出现次数，将字母和出现次数一起拼接成字符串作为HashMap的键值，太绝了，然后value还是一个链表，只要是变位词组，那么按字母顺序和次数拼接出来的字符串就一定相等
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
int[] counts = new int[26];
int length = str.length();
for (int i = 0; i < length; i++) {
counts[str.charAt(i) - 'a']++;
}
// 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 26; i++) {
if (counts[i] != 0) {
sb.append((char) ('a' + i));
sb.append(counts[i]);
}
}
String key = sb.toString();
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode-solut-gyoc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
(待)34 剑指 Offer II 034. 外星语言是否排序
35 剑指 Offer II 035. 最小时间差
给定一个 24 小时制（小时:分钟 “HH:MM”）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。
示例 1：
输入：timePoints = [“23:59”,“00:00”]
输出：1
示例 2：
输入：timePoints = [“00:00”,“23:59”,“00:00”]
输出：0
解题思路：先把所有的时间都转化成分钟数的整数值，一天最多24 * 60=1440分钟，所以如果列表的长度超过1440，直接返回0
分钟数计算出来之后，进行排序，然后依次计算相邻元素之间的差值，取最小值，还需要取最小值和最大值之间的时间差，比如23:59和00:01之间的时间差，与最小值进行比较
class Solution {
private int parseMinute(String str) {
return str.charAt(0) * 600 + str.charAt(1) * 60 + str.charAt(3) * 10 +str.charAt(4);
}
public int findMinDifference(List<String> timePoints) {
int len = timePoints.size();
if (len < 2 || len > 1440) {
return 0;
}
int[] times = new int[len];
for(int i = 0; i < len; i++) {
times[i] = parseMinute(timePoints.get(i));
}
Arrays.sort(times);
int min = Integer.MAX_VALUE;
for(int i = 0; i < len - 1; i++) {
min = Math.min(min, times[i+1] - times[i]);
if (min == 0) return 0;
}
return Math.min(min, 1440 - times[len-1] + times[0]);
}
}
2021.08.17 第12天 栈
36 剑指 Offer II 036. 后缀表达式
解题思路：遇到操作数就压入栈中，遇到运算符就取出两个操作数，由后取出的元素做第一个操作数
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer>stack=new Stack();
int a=0;int b=0;
for(int i=0;i<tokens.length;i++){
String s =tokens[i];
switch(s){
case "+":
a=stack.pop();
b=stack.pop();
stack.push(a+b);
break;
case "-":
a=stack.pop();
b=stack.pop();
stack.push(b-a);
break;
case "*":
a=stack.pop();
b=stack.pop();
stack.push(b*a);
break;
case "/":
a=stack.pop();
b=stack.pop();
stack.push(b/a);
break;
default:
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
学习一下，不用那么多弹出
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<Integer>();
int n = tokens.length;
for (int i = 0; i < n; i++) {
String token = tokens[i];
if (isNumber(token)) {
stack.push(Integer.parseInt(token));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
switch (token) {
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
default:
}
}
}
return stack.pop();
}
public boolean isNumber(String token) {
return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
}
}
膜拜一下100%的代码
class Solution {
public int evalRPN(String[] tokens) {
int[] stack = new int[tokens.length];
int top = -1;
for (String token : tokens) {
switch (token) {
case "+":
stack[top - 1] += stack[top];
top--;
break;
case "-":
stack[top - 1] -= stack[top];
top--;
break;
case "*":
stack[top - 1] *= stack[top];
top--;
break;
case "/":
stack[top - 1] /= stack[top];
top--;
break;
default:
stack[++top] = Integer.valueOf(token);
}
}
return stack[top];
}
}
37 剑指 Offer II 037. 小行星碰撞
解题思路，都在代码中了
正数入栈，等负数来碰，一直比较栈顶，栈顶为正，且当前非负数和栈顶相加小于0，弹出栈顶，循环比较
上面的步骤不再弹出时，可能是栈为空，也可能是栈顶已经是负数，那我们直接把当前负数入栈
也可能是当前元素和栈顶相加为0，那么直接弹出栈顶
class Solution {
public int[] asteroidCollision(int[] nums) {
int n=nums.length;
int i=0; //标记左边的小于0的行星,i左边全部小于0
Stack<Integer>stack=new Stack();
while(i<=n-1&&nums[i]<0){
stack.push(nums[i]);//把开头的负数全部加入stack,因为他们不会发生碰撞
i++;
}
for(int cur=i;cur<n;cur++){
if(nums[cur]>0)//正数直接入栈
stack.push(nums[cur]);
else{ //负数
while(!stack.isEmpty()&&stack.peek()>0&&nums[cur]+stack.peek()<0){//相加小于0，且栈顶是正数,就一直弹出栈顶元素
stack.pop();
}
if(stack.isEmpty()||(!stack.isEmpty()&&stack.peek()<0)){//栈为空或者栈顶为负数，入栈
stack.push(nums[cur]);
}
else {//栈不为空，栈顶也不是负数
if(stack.peek()>0&&nums[cur]+stack.peek()==0){//相加等于0，弹出栈顶
stack.pop();
}
}
}
}
int size=stack.size();
int arr[]=new int[size];
for(int k=size-1;k>=0;k--){
arr[k]=stack.pop();
}
return arr;
}
}
看看人家的代码，太优雅了
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int[] stack = new int[asteroids.length];
int top = -1;
for(int a:asteroids){
while(a<0&&top>=0&&stack[top]>0&&stack[top]<-a){
top--;
}
if(a<0&&top>=0&&stack[top]>=-a){
if(stack[top]==-a) top--;
continue;//当前负数被抵消，不入栈
}
stack[++top] = a;
}
int[] res = new int[top+1];
for(int i = 0;i<=top;i++) res[i] = stack[i];//这是因为++top这个操作会导致最后多一个元素
return res;
}
}
38 剑指 Offer II 038. 每日温度
请根据每日 气温 列表 temperatures ，重新生成一个列表，要求其对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。
解题思路：运用单调栈，比那里数组，把当前没有匹配到的后一个较高的数都存进栈，匹配到当前数组元素比栈顶大，那么栈顶元素的对应的需要等待的天数就是当前数组元素的索引减去栈顶元素的索引
怎么找到栈顶元素的索引?
我是把每个各元素的数据和索引封装成一个节点加入栈中，这样就能很方便得到该元素的索引。
其实也可以用一个一维数组存储
最后当数组遍历完，那么栈中剩余元素对应的需要等待的天数就为0
class Solution {
public int[] dailyTemperatures(int[] nums) {
//运用单调栈，但是怎么匹配索引,我把索引和数据封装成一个节点加入栈中？
Stack<Node>stack=new Stack();
stack.push(new Node(nums[0],0));
for(int i=1;i<nums.length;i++){
while(!stack.isEmpty()&&nums[i]>stack.peek().val){
int index=stack.pop().index;
nums[index]=i-index;
}
stack.push(new Node(nums[i],i));
}
//最后当数组遍历完，那么栈中剩余元素对应的需要等待的天数就为0
while(!stack.isEmpty()){
nums[stack.pop().index]=0;
}
return nums;
}
}
class Node{
int val;
int index;
Node(int val,int index){
this.val=val;
this.index=index;
}
}
我是hanpi吗，存进栈的时候就存索引呗。。。。。。。。
class Solution {
public int[] dailyTemperatures(int[] nums) {
//运用单调栈，但是怎么匹配索引,我把索引和数据封装成一个节点加入栈中？
Stack<Integer>stack=new Stack();
stack.push(0);
for(int i=1;i<nums.length;i++){
while(!stack.isEmpty()&&nums[i]>nums[stack.peek()]){
int index=stack.pop();
nums[index]=i-index;
}
stack.push(i);
}
//最后当数组遍历完，那么栈中剩余元素对应的需要等待的天数就为0
while(!stack.isEmpty()){
nums[stack.pop()]=0;
}
return nums;
}
}
思路2：动态规划
从后往前推，如果当前nums[i]比nums[j]小，那么直接得到对应的j-i，否则就调到比nums[j]大的那个数比较，这就是j=j += res[j],res[j]为0，说明nums[j]后面没有比nums[j]大的数
来一个快的
顺序遍历 其实并不能特别高效的利用之前计算的结果 还是一个个找的（逆序就很简单 相当于预知未来 所以直接跳转就行）
参考：https://leetcode-cn.com/problems/daily-temperatures/solution/dpde-si-wei-by-ryaninnerpeace-9ib3/
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
res[temperatures.length - 1] = 0;
for (int i = temperatures.length - 2; i >= 0; i--) {
for (int j = i + 1; j < temperatures.length; j += res[j]) {
if (temperatures[i] < temperatures[j]) {
res[i] = j - i;
break;
} else if (res[j] == 0) {
res[i] = 0;
break;
}
}
}
return res;
}
}
2021.08.18 第13 天 栈
39 剑指 Offer II 039. 直方图最大矩形面积
解题思路1：暴力枚举
能够了出来的最大直方图的面积必然是以某个柱子的高度作为高度的，我们就以每一个柱子为高度能够了出来的最大直方图，找出最大值，
class Solution {
public int largestRectangleArea(int[] nums) {
int n=nums.length;
Stack<Node>stack=new Stack();
stack.push(new Node(-1,0));//先把第一个元素入栈
int max=0;
//大概思路就是枚举每一根柱子作为矩形的高，求每一个矩形的面积，然后去最大值
//求面积还需要知道宽度，宽度就是当前柱子的前一个比它小的元素和后一个比它小的元素之间的距离
for(int i=1;i<n;i++){
if(!stack.isEmpty()&&nums[i]<nums[stack.peek().index]){
while(!stack.isEmpty()&&nums[i]<nums[stack.peek().index]){//可能是前面多个元素的后一个较小元素
Node node=stack.pop();
int tempArea=nums[node.index]*(i-node.smallerIndex-1);//我们计算的是以当前nums[i]为高的矩形的面积
max=Math.max(max,tempArea);
}
if(stack.isEmpty()){//栈空了，说明当前这个点太小了，把前面的都淘汰了，前一个比它小的元素索引就是-1
stack.push(new Node(-1,i));
}else{
int smallerIndex= (nums[i]==nums[stack.peek().index])?stack.peek().smallerIndex:stack.peek().index;
stack.push(new Node(smallerIndex,i));//这个smallerIndex怎么找?while结束，栈不为空，当前元素要么大于栈顶要么等于栈顶，所以上面分两钟情况
}
}
else if(!stack.isEmpty()&&nums[i]>nums[stack.peek().index]){
stack.push(new Node(stack.peek().index,i));//如果大于当前栈顶，那么当前栈顶就是它的前一个比它小的数
}
else if(!stack.isEmpty()&&nums[i]==nums[stack.peek().index]){//如果和栈顶相等，那么他们的前一个更小的元素相等
stack.push(new Node(stack.peek().smallerIndex,i));
}
}
while(!stack.isEmpty()){
//如果栈不为空，那么剩下的元素其后都没有比它小的元素，我们需要知道，剩下的栈的栈顶肯定是原来数组的最后一个元素，因为没人能淘汰它
//那么栈中剩下的元素都能延伸到最后
Node node=stack.pop();
int tempArea=nums[node.index]*(n-node.smallerIndex-1);
max=Math.max(max,tempArea);
}
return max;
}
//我们可以考虑把当前索引和它前面第一个比它小的元素的索引封装成一个结点
class Node{
int smallerIndex;
int index;
Node(int smallerIndex,int index){
this.smallerIndex=smallerIndex;
this.index=index;
}
}
}
数组模拟栈，太优雅了
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] stack = new int[n];
int top = -1;
int res = 0;
for(int i = 0;i<n;i++){
while(top>=0&&heights[stack[top]]>heights[i]){
int r = i;
int l = top>=1?stack[top-1]+1:0;
res = Math.max(res,(r-l)*heights[stack[top]]);
top--;
}
stack[++top] = i;
}
while(top>=0){
int r = n;
int l = top>=1?stack[top-1]+1:0;
res = Math.max(res,(r-l)*heights[stack[top]]);
top--;
}
return res;
}
}
40 剑指 Offer II 040. 矩阵中最大的矩形
2021.08.19 第14 天 对列
41 剑指 Offer II 041. 滑动窗口的平均值
解题思路：初始化容器容量大小，当队列中的元素数量超过了指定的容器容量，就弹出队头元素
class MovingAverage {
/** Initialize your data structure here. */
int size;
Queue<Integer>queue=new LinkedList();
double curSum=0.0;
public MovingAverage(int size) {
this.size=size;
}
public double next(int val) {
queue.add(val);
curSum+=val;
if(queue.size()>size){
curSum-=queue.poll();
}
return (double)curSum/(double)queue.size();
}
}
42 剑指 Offer II 042. 最近请求次数
class RecentCounter {
Queue<Integer>queue=new LinkedList();
public RecentCounter() {
}
public int ping(int t) {
queue.offer(t);
while(queue.peek()+3000<t){
queue.poll();
}
return queue.size();
}
}
43 剑指 Offer II 043. 往完全二叉树添加节点
解题思路：
class CBTInserter {
TreeNode root;
Deque<TreeNode> deque;
public CBTInserter(TreeNode root) {
this.root = root;
deque = new LinkedList();
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
// BFS to populate deque
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left == null || node.right == null)
deque.offerLast(node);
if (node.left != null)
queue.offer(node.left);
if (node.right != null)
queue.offer(node.right);
}
}
public int insert(int v) {
TreeNode node = deque.peekFirst();
deque.offerLast(new TreeNode(v));
if (node.left == null)
node.left = deque.peekLast();
else {
node.right = deque.peekLast();
deque.pollFirst();
}
return node.val;
}
public TreeNode get_root() {
return root;
}
}
2021.08.20 第15 天队列
44 剑指 Offer II 044. 二叉树每层的最大值
解题思路：层序遍历，记录每一层的最大值，先写在这，这个题要是还能用dfs我就，，，算了
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer>list=new ArrayList();
Queue<TreeNode>queue=new LinkedList();
if(root==null)
return list;
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
int tempMax=0;
for(int i=0;i<size;i++){
TreeNode temp=queue.poll();
if(i==0)
tempMax=temp.val;
else{
tempMax=Math.max(tempMax,temp.val);
}
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
}
list.add(tempMax);
}
return list;
}
}
class Solution {
public List<Integer> largestValues(TreeNode root) {
//队列
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
if(root != null){
queue.add(root);
}
while(!queue.isEmpty()){
int max = Integer.MIN_VALUE;
int levelSize = queue.size();
for(int i = 0; i < levelSize; i++){
TreeNode node = queue.poll();
max = Math.max(max, node.val);
if(node.left != null){
queue.add(node.left);
}
if(node.right != null){
queue.add(node.right);
}
}
res.add(max);
}
return res;
}
}
思路2 ：深度优先搜索
太强了呀，如果遍历到当前深度，list的大小没跟上，直接把当前节点的值放入list，否则，就比较当前值和已经发那个如list中对应位置那个值的大小。就是我们要明确list的大小和二叉树的最大深度是一样的
class Solution {
ArrayList<Integer> res = new ArrayList<>();
public List<Integer> largestValues(TreeNode root) {
dfs(root,0);
return res;
}
public void dfs(TreeNode root , int d){
if(root == null){
return;
}
if(d == res.size()){
res.add(root.val);
}else if(root.val > res.get(d)){
res.set(d,root.val);
}
dfs(root.left , d+1);
dfs(root.right , d+1);
}
}
45 剑指 Offer II 045. 二叉树最底层最左边的值
解题思路1：广度优先搜索，每一层出队前暂存出队的第一个节点，等到队列为空，直接返回最后暂存的这个节点值就可以了
class Solution {
public int findBottomLeftValue(TreeNode root) {
List<Integer>list=new ArrayList();
Queue<TreeNode>queue=new LinkedList();
int result=0;
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
TreeNode temp=queue.poll();
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
if(i==0){
result=temp.val;
}
}
}
return result;
}
}
这个层序遍历不是更清晰简洁？直接反着装，最后一个弹出对垒的节点就是最后一层的最左边那个节点
class Solution {
public int findBottomLeftValue(TreeNode root) {
if (root.left == null && root.right == null) {
return root.val;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
TreeNode temp = new TreeNode(-100);
while (!queue.isEmpty()) {
temp = queue.poll();
if (temp.right != null) {
// 先把右节点加入 queue
queue.offer(temp.right);
}
if (temp.left != null) {
// 再把左节点加入 queue
queue.offer(temp.left);
}
}
return temp.val;
}
}
思路2，深度优先，线把二叉树的最大深度求出来，然后找出第一个深度等于最大深度的节点，，，
我的代码只有当最后一层只有一个节点的时候才正确，否则会找到最后一个节点
class Solution {
int result=0;
public int findBottomLeftValue(TreeNode root) {
int maxDepth=GetMaxDepth(root);
helper (root,1,maxDepth);
return result;
}
public int GetMaxDepth(TreeNode root){
if(root==null)
return 0;
return 1+Math.max( GetMaxDepth(root.left), GetMaxDepth(root.right));
}
public void helper (TreeNode root,int depth,int maxDepth){
if(root==null)
return ;
if( depth==maxDepth){
result=root.val;
return ;
}
helper (root.left,depth+1,maxDepth);
helper (root.right,depth+1,maxDepth);
}
}
再看看别人的代码
class Solution {
int maxHeight = -1;
int left = 0;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 0);
return left;
}
void dfs(TreeNode root,int height) {
if(root.left == null && root.right == null) {
if(height > maxHeight) {
maxHeight = height;
left = root.val;
}
return;
}
if(root.left != null) dfs(root.left, height + 1);
if(root.right != null) dfs(root.right, height + 1);
}
}
46 剑指 Offer II 046. 二叉树的右侧视图
解题思路1：广度优先搜索，每次取每一层的最后一个节点放入list
class Solution {
public List<Integer> rightSideView(TreeNode root) {
//解题思路，取每一层的最右边的节点
List<Integer>list=new ArrayList();
Queue<TreeNode>queue=new LinkedList();
if(root==null)
return list;
queue.offer(root);
while(!queue.isEmpty()){
int size=queue.size();
for(int i=0;i<size;i++){
TreeNode temp=queue.poll();
if(temp.left!=null)
queue.offer(temp.left);
if(temp.right!=null)
queue.offer(temp.right);
if(i==size-1){
list.add(temp.val);
}
}
}
return list;
}
}
解题思路2：深度优先搜索
我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。
我们可以存储在每个深度访问的第一个结点，一旦我们知道了树的层数，就可以得到最终的结果数组
class Solution {
List<Integer> res=new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root,0);
return res;
}
public void dfs(TreeNode root,int depth){
if(root==null) return ;
if(depth==res.size()){
res.add(root.val);
}
dfs(root.right,depth+1);
dfs(root.left,depth+1);
}
}
解题思路3:用栈
把左节点先入栈，右节点后入栈，这样就会先遍历右子树
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;
Stack<TreeNode> nodeStack = new Stack<TreeNode>();
Stack<Integer> depthStack = new Stack<Integer>();
nodeStack.push(root);
depthStack.push(0);
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.pop();
int depth = depthStack.pop();
if (node != null) {
// 维护二叉树的最大深度
max_depth = Math.max(max_depth, depth);
// 如果不存在对应深度的节点我们才插入
if (!rightmostValueAtDepth.containsKey(depth)) {
rightmostValueAtDepth.put(depth, node.val);
}
nodeStack.push(node.left);
nodeStack.push(node.right);
depthStack.push(depth + 1);
depthStack.push(depth + 1);
}
}
List<Integer> rightView = new ArrayList<Integer>();
for (int depth = 0; depth <= max_depth; depth++) {
rightView.add(rightmostValueAtDepth.get(depth));
}
return rightView;
}
}
2021.08.21 第16天 树
49 剑指 Offer II 049. 从根节点到叶节点的路径数字之和
解题思路，就递归遍历，找到叶子结点就把当前的字符串拼接上叶子结点，然后加入到List，最后对list中的字符串转成整数求和
class Solution {
List<String>list=new ArrayList();
public int sumNumbers(TreeNode root) {
helper( root,"");
int result=0;
for(int i=0;i<list.size();i++){
result+=Integer.valueOf(list.get(i));
}
return result;
}
public void helper(TreeNode root,String s){
if(root==null){
return ;
}
if(root.left==null&&root.right==null){
list.add(s+root.val);
}
helper( root.left,s+root.val);
helper( root.right,s+root.val);
}
}
优化，直接带着整数递归
class Solution {
List<Integer>list=new ArrayList();
public int sumNumbers(TreeNode root) {
helper( root,0);
int result=0;
for(int i=0;i<list.size();i++){
result+=list.get(i);
}
return result;
}
public void helper(TreeNode root,int s){
if(root==null){
return ;
}
if(root.left==null&&root.right==null){
list.add(s*10+root.val);
}
helper( root.left,s*10+root.val);
helper( root.right,s*10+root.val);
}
}
不用list
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int prevSum) {
if (root == null) {
return 0;
}
int sum = prevSum * 10 + root.val;
if (root.left == null && root.right == null) {
return sum;
} else {
return dfs(root.left, sum) + dfs(root.right, sum);
}
}
}
广度优先遍历
class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
int sum = 0;
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> numQueue = new LinkedList<Integer>();
nodeQueue.offer(root);
numQueue.offer(root.val);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.poll();
int num = numQueue.poll();
TreeNode left = node.left, right = node.right;
if (left == null && right == null) {
sum += num;
} else {
if (left != null) {
nodeQueue.offer(left);
numQueue.offer(num * 10 + left.val);
}
if (right != null) {
nodeQueue.offer(right);
numQueue.offer(num * 10 + right.val);
}
}
}
return sum;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/solution/qiu-gen-dao-xie-zi-jie-dian-shu-zi-zhi-he-by-leetc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
2021.08.22第17天 树
50 剑指 Offer II 050. 向下的路径节点之和
解题思路：利用前缀和，计算到当前节点，查看之前有没有前缀和为curSum-target
参考：前缀和，递归，回溯
class Solution {
int result;
Map<Integer,Integer>map=new HashMap();
public int pathSum(TreeNode root, int targetSum) {
if(root==null)
return 0;
map.put(0,1); //千万别忘了，不然会少算
helper(root,targetSum,0);
return result;
}
public void helper(TreeNode root,int targetSum,int curSum){
if(root==null)
return ;
curSum+=root.val;
result+=map.getOrDefault(curSum-targetSum,0);//注意不能和下面这句话换位置，不然[1],0这种例子就通不过
map.put(curSum,map.getOrDefault(curSum,0)+1);
helper(root.left, targetSum, curSum);
helper(root.right, targetSum, curSum);
map.put(curSum,map.get(curSum)-1);
}
}
52 剑指 Offer II 052. 展平二叉搜索树
解题思路1：把所有节点按中序遍历取出来（递归，迭代），然后放在一个list里面，之后依次把他们取出来
解题思路2：递归，创建一个假的头结点，在中序遍历的过程中，不断把遍历到的节点加入到假头后面
class Solution {
TreeNode head = new TreeNode(-1);
TreeNode pre = head;
public TreeNode increasingBST(TreeNode root) {
inorder(root);
return head.right;
}
public void inorder(TreeNode node) {
if (node == null) {
return;
}
inorder(node.left);
pre.right = node;
pre = node;
pre.left = null;
inorder(node.right);
}
}
2021.08.23 第18天 树
2021.08.24 第19天树
56 剑指 Offer II 056. 二叉搜索树中两个节点之和
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
示例 1：
输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12
示例 2：
输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点
解题思路：中序遍历，同时用set保存遍历过的结点值
class Solution {
Set<Integer>set=new HashSet();
public boolean findTarget(TreeNode root, int k) {
if(root==null){
return false;
}
if(set.contains(k-root.val)){
return true;
}
set.add(root.val);
return findTarget( root.left, k)||findTarget( root.right, k);
}
}
57 剑指 Offer II 057. 值和下标之差都在给定的范围内
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
解题思路1：暴力，无法解决
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int n=nums.length;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
long a=Math.abs((long)nums[i] - (long)nums[j]);
if((a <= t)&& Math.abs(i - j) <= k)
return true;
}
}
return false;
}
}
解题思路2：参考【宫水三叶】一题双解：「滑动窗口 & 二分」&「桶排序」解法
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int n = nums.length;
TreeSet<Long> ts = new TreeSet<>();
for (int i = 0; i < n; i++) {
Long u = nums[i] * 1L;
// 从 ts 中找到小于等于 u 的最大值（小于等于 u 的最接近 u 的数）
Long l = ts.floor(u);
// 从 ts 中找到大于等于 u 的最小值（大于等于 u 的最接近 u 的数）
Long r = ts.ceiling(u);
if(l != null && u - l <= t) return true;
if(r != null && r - u <= t) return true;
// 将当前数加到 ts 中，并移除下标范围不在 [max(0, i - k), i) 的数（维持滑动窗口大小为 k）
ts.add(u);
if (i >= k) ts.remove(nums[i - k] * 1L);
}
return false;
}
}
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int len = nums.length;
int[][] data = new int[len][2];
for (int i = 0; i < len; i++) data[i] = new int[]{nums[i], i};
Arrays.sort(data, Comparator.comparingInt(a -> a[0])); // 按照元素值的大小升序排列
for (int i = 0; i < len - 1; i++) {
// 固定住第一个数
for (int j = i + 1; j < len; j++) {
if ((long) data[j][0] - data[i][0] > t) break;
if (Math.abs(data[j][1] - data[i][1]) <= k) return true;
}
}
return false;
}
}
2021.08.25 第20天 堆
59 剑指 Offer II 059. 数据流的第 K 大数值
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
示例：
输入：
[“KthLargest”, “add”, “add”, “add”, “add”, “add”]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]
解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jBjn9C
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
写了半天，还是优先队列好用啊
class KthLargest {
int nums[];
int k;
int max=Integer.MIN_VALUE;
public KthLargest(int a, int[] arr) {
nums=new int[k];
for(int i=0;i<k;i++){
nums[i]=arr[i];
}
k=a;
buildHeap(nums,k);
for(int i=k;i<nums.length;i++){
if(nums[i]>nums[0]){
swap(nums,0,i);
heaplify( nums,0,k);
}
}
}
public int add(int val) {
if(nums.length<k){
return Math.max(max,val);
}
if(val>nums[0]){
nums[0]=val;
heaplify(nums,0,k);
}
return nums[0];
}
public void buildHeap(int nums[],int k){
for(int i=nums.length/2-1;i>=0;i--){
heaplify(nums,i,k);
}
}
public void heaplify(int nums[],int i,int k){
int minIndex=i;
while(true){
if(i*2+1<k&&nums[i*2+1]<nums[minIndex]) minIndex=i*2+1;
if(i*2+2<k&&nums[i*2+2]<nums[minIndex]) minIndex=i*2+2;
if(i==minIndex) break;
swap(nums,i,minIndex);
i=minIndex;
}
}
public void swap(int nums[],int i,int j){
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
真的绝
class KthLargest {
PriorityQueue<Integer> pq;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
pq = new PriorityQueue<Integer>();
for (int x : nums) {
add(x);
}
}
public int add(int val) {
pq.offer(val);
if (pq.size() > k) {
pq.poll();
}
return pq.peek();
}
}
60 剑指 Offer II 060. 出现频率最高的 k 个数字
给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前 k 高的元素。可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
解题思路：
class Solution {
Map<Integer,Integer>map=new HashMap();
//解题思路，哈希表+堆，哈希表统计数字出现次数，堆维护出现次数最高的k个数字
public int[] topKFrequent(int[] nums, int k) {
for(int i=0;i<nums.length;i++){
map.put(nums[i],map.getOrDefault(nums[i],0)+1);
}
Set entrySet=map.entrySet();
Map.Entry entry[]=new Map.Entry [k];
int cur=0;
for(Object ent:entrySet){
if(cur<k)
entry[cur++]= (Map.Entry)ent;
else
break;
}
buildHeap(entry,k);//先创建一个大小为k的堆
cur=0;
for(Object ent:entrySet){
if(cur>=k){
Map.Entry m=(Map.Entry)ent;
if((int)m.getValue()>(int)entry[0].getValue()){
entry[0]=m;
heapify(entry, 0, k);
}
}
cur++;
}
int res[]=new int[k];
for(int i=0;i<k;i++){
res[i]=(int)entry[i].getKey();
}
return res;
}
public void buildHeap(Map.Entry entry[], int k){
for(int i=k/2-1;i>=0;i--){
heapify(entry,i,k);
}
}
public void heapify(Map.Entry entry[],int i,int k){
int minIndex=i;
while(true){
if(i*2+1<k&&(int)entry[i*2+1].getValue()<(int)entry[minIndex].getValue()) minIndex=i*2+1;
if(i*2+2<k&&(int)entry[i*2+2].getValue()<(int)entry[minIndex].getValue()) minIndex=i*2+2;
if(minIndex==i) break;
swap(entry,i,minIndex);
i=minIndex;
}
}
public void swap( Map.Entry entry[],int i,int j){
Map.Entry temp=entry[i];
entry[i]=entry[j];
entry[j]=temp;
}
}
优先队列
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
for (int num : nums) {
occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
int num = entry.getKey(), count = entry.getValue();
if (queue.size() == k) {
if (queue.peek()[1] < count) {
queue.poll();
queue.offer(new int[]{num, count});
}
} else {
queue.offer(new int[]{num, count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; ++i) {
ret[i] = queue.poll()[0];
}
return ret;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
61 剑指 Offer II 061. 和最小的 k 个数对
给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。
示例 1:
输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
示例 2:
输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
示例 3:
输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qn8gGX
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路，用优先队列,大根堆
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//解题思路，优先队列构造大根堆
List<List<Integer>>list=new ArrayList();
PriorityQueue<int[]>queue=new PriorityQueue<int[]>((int []a,int[]b)->(b[0]+b[1])-(a[0]+a[1]));//注意比较器的书写，默认是小根堆，构造大根堆需要定义构造器
for(int i=0;i<nums1.length;i++){
for(int j=0;j<nums2.length;j++){
int temp[]=new int[]{nums1[i],nums2[j]};
if(queue.size()<k){
queue.offer(temp);
}else{
if(temp[0]+temp[1]<queue.peek()[0]+queue.peek()[1]){
queue.poll();
queue.offer(temp);
}else{
break;//注意说了是升序
}
}
}
}
//int size=queue.size();
for(int i=0;i<k;i++){
if(!queue.isEmpty()){
int temp1[]=queue.poll();
List<Integer> list1 = Arrays.asList(temp1[0],temp1[1]);
list.add(list1);
}
}
return list;
}
}
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> res = new ArrayList<>();
PriorityQueue<int[]> pq = new PriorityQueue<>(k, (o1, o2)->(o2[0] + o2[1] - o1[0] - o1[1]));
for(int i = 0; i < Math.min(nums1.length, k); i++){
for(int j = 0; j < Math.min(nums2.length, k); j++){
if(pq.size() == k && nums1[i] + nums2[j] >= pq.peek()[0] + pq.peek()[1]) break;
if(pq.size() == k) pq.poll();
pq.offer(new int[]{nums1[i], nums2[j]});
}
}
for(int i = 0; i < k && pq.size() > 0; i++){
int[] temp = pq.poll();
List<Integer> list = new ArrayList<>();
list.add(temp[0]);
list.add(temp[1]);
res.add(list);
}
return res;
}
}