Alangy's Blog

分类 - LeetCode刷题记录

如何从40亿整数中找到不存在的一个
2023-04-07 20:54:07    110    0    0

https://article.itxueyuan.com/O0Pg3

参考类似二分查找的方法，每次选择按照二进制位统计，“更少”的那一堆。
当然了，这种方法要借助文件。每次，按照二进制位是0还是1，将其分为两部分。分好的结果可以append到文件中。
另一种方法：直接使用bitmap来统计，每个元素是否出现。复杂度O(N)，需要大约512M内存空间。

三个数的最大乘积
2023-03-18 21:06:01    56    0    0

给你一个整型数组 nums，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

https://leetcode.cn/problems/maximum-product-of-three-numbers/

分类讨论：三个正数|一个正数两个负数|两个正数一个负数|整个数组没有正数。

  • 三个正数：排序后最大的三个；
  • 一个正数两个负数：最小的两个负数*最大的正数；
  • 没有正数：最大的三个数；
  • 两正一负：如果只有这三个数，则就是最大三个数，如果还有一个正数或者负数，都能凑出更大的正数，因此不考虑。
    因此，需要找出最大的三个数和最小的两个数。
    寻找方法：一次扫描，然后暴力记录。
  1. int min1=INT_MAX, min2=INT_MAX;
  2.         int max1=INT_MIN, max2=INT_MIN, max3=INT_MIN;
  3.         for(int num:nums){
  4.             //先更新最小值
  5.             if(num<min1){
  6.                 min2=min1;
  7.                 min1=num;
  8.             }
  9.             else if(num<min2){
  10.                 min2=num;
  11.             }
  12.             //更新最大值
  13.             if(num>max1){
  14.                 max3=max2;
  15.                 max2=max1;
  16.                 max1=num;
  17.             }
  18.             else if(num>max2){
  19.                 max3=max2;
  20.                 max2=num;
  21.             }
  22.             else if(num>max3){
  23.                 max3=num;
  24.             }
  25.         }
  26.         return max(max1*max2*max3, min1*min2*max1);
滑动窗口-双指针类型题目
2023-03-04 19:53:59    87    0    0

基本概念

滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。

分类：窗口有两类，一种是固定大小类的窗口，一类是大小动态变化的窗口。

应用：什么情况可以用滑动窗口来解决实际问题呢？

  1. 一般给出的数据结构是数组或者字符串
  2. 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
  3. 该问题本身可以通过暴力求解

固定窗口大小：通常直接固定下窗口的长度，for循环只用关注最左边的点l，每次进入l+window.size，出栈l即可。
非固定窗口大小：扩张r, 直到符合要求，然后收缩l。

leetcode类型题目：
https://leetcode.cn/problems/minimum-window-substring
https://leetcode.cn/problems/find-all-anagrams-in-a-string/

主定理
2023-02-26 17:43:49    41    0    0

title

相交链表
2023-02-26 16:55:58    50    0    0

剑指 Offer 52. 两个链表的第一个公共节点

https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

虽然标为【简单】，但其实进阶做法较有技巧。其和链表成环一样，都能想到双指针。但是本题双指针的取巧性更强。

具体而言，假设链表A的私有部分长为a，链表B的私有部分长为b，二者的公共部分（如有）长度为c。

在aPtr走到尽头时，走了长度为a+c,此时只要将其接到B上继续往下走，走长度b时，总步数为a+c+b。而bPtr走到尽头时，接到A上继续往下走长度为a时，总步数也为a+c+b，即二者重合时【而且】此时二者都在第一个公共节点上。

  1. class Solution {
  2. public:
  3.     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
  4.         if (headA == nullptr || headB == nullptr) {
  5.             return nullptr;
  6.         }
  7.         ListNode *pA = headA, *pB = headB;
  8.         while (pA != pB) {
  9.             pA = pA == nullptr ? headB : pA->next;
  10.             pB = pB == nullptr ? headA : pB->next;
  11.         }
  12.         return pA;
  13.     }
  14. };
a>b Problem
2023-02-24 23:04:26    48    0    0

不允许使用任何比较运算符（例如>，<，?:等），判断语句，maxmin等函数，判断a和b的大小？

解法1：绝对值法：

return a+b+abs(a-b)/2

如果a比较大，返回a，如果b比较大，返回b

解法2：
计算a-b，取出最高位的元素，即r=(a-b)&0x8000_0000
res=r==1?a:n

接雨水
2023-02-17 19:52:17    50    0    0

难度：leetcode hard
给定 n 个非负整数表示每个宽度为 1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
原文地址：
https://leetcode.cn/problems/trapping-rain-water/
title

这道题的算法原理较好想到，其实就是确定任何一点的左右最大值，就可以得知这个点能够装到的最高的水。难在如果先做一遍遍历再将最大值存在数组中，无法做到从O(N)空间到O(1)的优化。
实际使用的方法是难点【双指针】。其实就是，维护left指针和right指针，如果当前left点的高度比right更低，那么left点的储水量就已知了（因为right向左移动，新值一定比right更大，因此，限制当前left点储水高度的，一定是left点的高度。）在求出left点的储水量后，向右边移动left即可。如此继续这个步骤，直到left==right。

这道题其实和leetcode medium中的盛水最多的容器很相似，从两端开始贪心，在找到当前限制条件（短板）后，提高短板到下一个极值点。

找出字符串中第一个匹配项的下标
2023-02-05 02:23:33    58    0    0

原始题目:
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

第一次学习KMP算法，参考的是改进版的动态规划算法。
https://zhuanlan.zhihu.com/p/83334559
其本质为一个有限状态机，通过needle构造出一个状态机，状态个数为needle的长度，然后不断输入heystack中的字符，处理状态机的改变。

状态机构造时的核心思路为：当无法继续向下匹配时，向影子状态，即代码中的X，即当前最长前缀所在的位置（X始终比当前遍历到的位置慢一步）询问下一个应该到达的状态。
本算法为了便于理解，在每个位置状态，多用了255个空间，但总的空间复杂度依旧保持不变。

  1. class Solution {
  2. public:
  3.     int strStr(string haystack, string needle) {
  4.         //字符串匹配？似乎有什么kmp算法？暴力匹配的话，最大复杂度为O(mn)
  5.         //直接使用kmp，首先构建next数组，本文选择二维的数组
  6.         //从haystack中查找needle
  7.         vector<vector<int>> dp(needle.length(), vector<int>(255, 0)); //char a的取值范围就是0-255
  8.         //初始状态为0
  9.         int X = 0; //标记上一个状态
  10.         dp[0][needle[0]] = 1; //只有这种情况下，才转移到1，其余情况都保留在0
  11.         for (int i = 1; i < needle.size(); i++) {
  12.             for (int c = 0; c < 255; c++) {
  13.
去除重复字母【hard】
red    2022-11-16 23:33:16    53    0    0

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
来源：https://leetcode.cn/problems/remove-duplicate-letters/

去掉一部分，使得字典序最大（最小），是一种很著名的单调栈题型。
其解法相对较为固定的部分是：保证单调栈是单调增加的。如果不单调增，则要删掉栈顶的那个“太大”的元素（往往有一定条件）
在本题中，其条件为：该字符在后面至少还有一次出现（否则就删没了）
此外，还需要考虑删除少了的情况。在本题中的方法为：如果前面已经出现过了这个元素，那么无条件删除后续要加进去的元素（相当于做了从后往前的删除）。有些时候，也可能是诸如“直接截断出前xxx个元素”

有一个对这类题型的很好归纳，见：https://leetcode.cn/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/

此外，有一点python上的技巧，例如末尾数组用stack[-1]。

  1. from functools import reduce
  2. from operator import add
  5. class Solution:
  6.     # //去掉一部分，使得字典序最大（最小），是一种很著名的单调栈题型。
  7.     # //其解法相对较为固定的部分是：保证单调栈是单调增加的。如果不单调增，则要删掉栈顶的那个“太大”的元素（往往有一定条件）
  8.     # //在本题中，其条件为：该字符在后面至少还有一次出现（否则就删没了）
  9.     # //此外，还需要考虑删除少了的情况。方法为：如果前面已经出现过了这个元素，那么无条件删除后续要加进去的元素（相当于做了从后往前的删除）
  10.     def removeDuplicateLetters(self, s: str) -> str:
  11.         stack = []
  12.         hasadd = set()
  13.         ccount = {}  # 到了当前位置后，“后面”还剩下
多数元素
2022-10-22 19:08:31    240    0    0

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

来源：https://leetcode.cn/problems/majority-element/

如果使用二分的快排方法，会在一个几乎全是1，2，3的长字符串TLE。
可以使用摩尔投票算法：维护一个候选人和投票。每次遇到支持者（等于候选人）时，将投票++，否则将投票--。当得票为0的时候，重新进行选举（直接选取当前遇到的元素）。

其正确性可以简单理解为：
不妨假设整个数组的众数记做a，则最初的数组中a的数量大于其余所有数。当采用count计数的时候有两种情况：

1）假设candidate等于a，则当count从1变为0的过程，此区间内a的数量等于其余数的数量，因此以count=0为分界线，数组右端部分的众数仍然为a

2）假设candidate不等于a，则当count从1变为0的过程， 此区间内a的数量小于等于其余数的数量，因此以count=0为分界线，数组右端部分的众数仍然为a

因此，以count=0可以将整个原始数组分为若干部分，count=0右端部分的数组中的众数永远是a，最终必然会筛选出a

1/4
Proudly powered by Leanote