Leetcode Notes

资料库

leetcode 1370 上下字符串

index 从后往前遍历的时候 千万要注意 删除操作 对于index的位移

290. 单词规律

如果我们有 两个对象 他们必须一一对应 我们最好创建两个哈希表

实现这种一一对应的关系

1
2
3
4
5
6
7
8
    //assume A is char and B is int | C is char too
    //simulate A => B and C also => B
    unordered_map<int, char> dict;
    char A = 'A', C = 'C';
    int B = 17;
    dict[B] = A;
    dict[B] = C;     //只有 hash key是被保护的对象 被保护对象不可以重复
// 如果两者都是被保护对象 那只能建立两个hash table

  • 我们将环岛划分为 n 个结点，要走过所有的结点，会漏下一段，想要求最短行进距离，只要漏下的最长即可

leetcode 387 找到第一个唯一字符

如题 我们要在一个字符串里找到第一个 不和后面任何字符重复的唯一出现一次的字符

  • 队列 + 延迟删除(每次检测到出现重复字符都会触发一个循环删除操作(当然 这其实挺慢的))

由于队列的 FIFO属性 如果想找到第一个符合要求的元素 使用队列是方便的

2021. 2. 7｜665 非递减序列

1
2
3
4
5
6
// 4 2 5
// 1 4 2 5
// 3 4 2 5  3种情况
// 当我们发现nums[i] < nums[i-1] 时 应该优先调整num[i-1]的值 因为nums[i]变大会影响之后的判断
// 所以我们只需要知道 nums[i-1]最小能变到多小 显然，就是nums[i-2]的大小。
// 但如果nums[i]比nums[i-2]更小， 这意味着我们不得不调整nums[i]的值使得它和nums[i-1]一样。

2.7｜5674 构造字典序最大的合并字符串

总之两边每次都拿最大的那个，问题在于 如果说两个字符串的头都一样大，应当拿的是子字符串最大的那个 「使用 substr(i)」

2.8｜978最长湍流子数组 和交替子序列比起来，这个是要求连续最长的 需要进行互相继承 优化了dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int maxTurbulenceSize(vector<int>& arr) {
        // 摆动上升记为up，摆动下降记为down  这个其实是动态规划的优化版本
        int up = 1, down = 1, n = arr.size(), res = 1;
        for (int i = 1; i < n; i ++) {
            // 我们应当注意的是 虽然up好像被清零了，但实际上它的值被继承到了down里，它们两个是交替继承到
            // 建议先完全理解动态规划方法解决这个问题
            if (arr[i] == arr[i-1]) {
                up = 1;
                down = 1;
            }
            else if (arr[i] > arr[i-1]) {
                up = down + 1;
                down = 1;
            }
            else {
                down = up + 1;
                up = 1;
            }
            res = max(res, max(up, down));
        }
        return res;
    }

2.11｜703 数据流中的第K大元素 「不断的添加数据到一个数组中，我们每次都要第k大的元素」

只关注前K大，我们用数组中==前k大的元素组成一个最小堆，并且维持堆的大小为K==(堆顶的就是目前第k大的元素)。

之后每次添加元素val，如果val比目前的堆顶小，那么它将被pop掉，如果它比堆顶要大，那么堆顶将被pop掉，第K大元素将会发生变更。

初始数据 4 5 8 2 ｜ 第3大

我们的堆中存有 4 5 8 ，add 3的时候，3比4还小，所以它不会影响到第K大元素， 它会被放在堆顶，直接被pop掉

如果add 的是5， 那么4会在堆顶，它现在已经不是第3大的元素了，4被pop掉。

2.13｜448 找到1-n之中所有消失的数字

题：数组大小为n，它理应包含从1-n的连续不同的数字。

但是有一些数字出现了多次，我们现在需要用一个数组返回数组中缺失的 范围在1-n之间的数字

关键在于 ==数的范围和下标的范围差不多 构建的直接就是下标对应的联系==

nums[i] 的出现 直接将 nums[nums[i]-1] + n (%n 可以把+n去掉，可能本来就已经加上了)

3.2 | 304. 二维区域和检索 - 矩阵不可变

多次调用了矩阵的前缀和,我们可以一开始就全给他算出来,改成前缀模式 这样比较省时间.

3.4 | 1438. 绝对差不超过限制的最长连续子数组

「想要每次都拿出最大值和最小值 可以使用multiset」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    // ⚠️ 要求的子数组里 任意两个元素 的差 不能超过limit!! 不是相邻元素
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> count;   // 为什么使用 multiset ? 因为我们需要保证有序 而且同时需要最大和最小元素 「这意味着堆(priority_queue 是基于队列实现的 所以不支持拿最后尾元素)的不可使用」
        int n = nums.size(), left = 0, right = 0, res = 0;
        while (right < n) {
            count.insert(nums[right]); //默认是从小到大排序
            while (*count.rbegin() - *count.begin() > limit) {
                count.erase(count.find(nums[left++]));    // multiset -> erase 
            }
            res = max(right-left+1, res);
            right++;
        }
        return res;
    }
};

3.6 | 503. 下一个更大元素 II

1. 单调栈

对于每个数都需要找到下一个比它大的元素, 栈中存储的相当于一个降序的序列 只要出现一个更大的 栈中所有元素对应的下一个更大 都是它

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        stack<int> tedious;
        vector<int> res(n, -1);
        for (int i = 0; i < 2*n-1; ++i) {
            while (!tedious.empty() && nums[i % n] > nums[tedious.top()]) {
                res[tedious.top()] = nums[i % n];
                tedious.pop();
            }
            tedious.push(i % n);
        }
        return res;
    }

==⚠️ 可以通过「 % capacity」 来实现对于数组的逻辑拉长 「⚠️ i < 2*n-1 是省了一次 不是越界」==

3.6 | 快速幂 本质上讲 是利用了递归的 栈逻辑 x^n = x ^ n/2 * x ^ n/2 …

1
2
3
4
5
6
7
8
9
10
11
12
13
double myPow(double x, int n) {
        if (n == 0) return 1;
        long N = n;
        return n > 0 ? quickMulit(x, N) : 1.0/quickMulit(x, -N);
    }  
double quickMulit(double x, long n) {
        if (n == 1) return x;
        double y = quickMulit(x, n / 2);
        if (n & 1) { //为奇数
            return x * y * y;
        }
        return y * y;
    }

3.9 | 1047. 删除字符串中的所有相邻重复项

利用栈的性质解题 但注意的是 string 支持 pop_back() 和 back()操作 我们可以直接将其理解为一个栈来做 「同样的道理, 在a+b hard中, 我们也可以这样来用string 替代掉stack」

3.9 | 283 移动零 「把数组中某一特定值(此处是0)的元素 全部拿到队伍的末尾去」

「快慢指针」right指针一直前进,而left指针则停留在最后一个一定需要交换来解决问题的元素上 (⚠️ 在left 和right 都满足的时候, 两者就都自加)

1
2
3
4
5
6
7
void moveZero (vector<int>& nums ) {
  	int left = 0, right = 0;
  	while (right < nums.size()) {
      	if (nums[right]) swap(nums[right], nums[left ++]);
      	++ right;
    }
}

3.15 54. 螺旋矩阵 螺旋输出一个矩阵

考虑矩阵的四个角 「top right left bottom 」 用这四个变量标记它们

  • 此题由于输出的总数已经知道,我们应该设置一个恒定的标记 让它减少到0来判断是否应该结束循环,而不是加入超多的判断语句.

3.14 检查5张牌是否为顺子 「排序后,看最大和最小 差距大于等于5 就不行啦」

3.17 层序遍历,分层输出

分层的要点在于, 我们在原有的while循环里加入一个for循环, 对于原本就在队列中的n个结点,这个循环的目标就是把它们的孩子都加入队列, 同时把它们都pop出去.

3.17 股票的最大利润 「只可以买卖一次」「实际上就是求数组最大的元素差,其中大的元素一定要在小的后面」

minprice 保证了在位于 price处 时候, minprice一定是当前最小的那个值了. 而maxprice 则利用了这一点

1
2
3
4
for (int price: nums) {
      maxprofit = max(maxprofit, price - minprice);
      minprice = min(price, minprice);
}

3.20 | 150. 逆波兰表达式求值

逆波兰表达式的解法很简单, 数字直接入栈, 见运算符就把两个拿出来计算之后push回去. ⚠️ isdigit 是对字符生效的函数, 以及 stoi 字符串转int 函数. 值的注意的是 没有itos 哦!

3.22 | 爬楼梯

456. 132 模式 「看数组里 是否有这样的三个元素 i j k 它们满足 i < j < k, 同时 nums[i] < nums[k] < nums[j]」

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    // i < j < k || nums[i] < nums[k] < nums[j]
    // 这个题的问题在于 我们只需要知道有没有即可, 我们是不需要提供下标的!
    // 不可以使用priorityqueue来存储k的所有可能性 想想为什么
   
    bool find132pattern(vector<int>& nums) {
        int left_min = nums[0], j = 1, n = nums.size();
        if (n < 3) return false;
        multiset<int> s;
        for (int i = 2; i < n; ++i) s.insert(nums[i]);
        while (!s.empty()) {
            if (left_min < nums[j]) {
                auto it = s.begin();
                while (it != s.end()) {
                    if (*it < nums[j] && *it > left_min) return true;
                    ++it;
                }
            }
            s.erase(s.find(nums[j+1])); //这里使用erase 会一次删除掉所有值为val的元素,
            // for (auto it = s.begin(); it != s.end(); ++it) {
            //     if (*it == nums[j+1]) {
            //         *it = 1e9+1;    
            //     }
            // }
            left_min = min(left_min, nums[j++]);
        }
        return false;
    }
};

==⚠️ 1. erase 如果里面直接给出元素, 会直接删除所有的该元素, 也可以使用find 这样只会删除第一个遇见的. 2.迭代器只是遍历工具, 我们是不能通过迭代器来修改容器内的值的!==

4.12 179. 最大数 「一个数组 把里面的数字拼成一个 字典序最大的字符串」

很容易想到在匿名函数里转字符串比较字典序.

但我们可以直接利用整数来尝试拼接.

[1738. 找出第K大的异或坐标值「要注意前缀和从0开始」][https://leetcode- cn.com/problems/find-kth-largest-xor-coordinate-value/]

关于二维前缀和的解释如下:

所以 prefix[i][j] = prefix[i][j-1]^prefix[i-1][j]^prefix[i-1][j-1]^matrix[i-1][j-1]

在342. 4的幂

1. 偶数位上是1的32位整形, 0xaaaaaaaa

杂项

  • accumulate 函数，到nums.begin()+k，是不包括下标k的！并且 accmulate 所需要的时间是很短的 使用accumulate来检测数组中是否只有0是一个可行的选择。

  • index 从后往前遍历的时候 千万要注意 删除操作 对于index的位移

  • 如何用队列实现栈? 「一个队列 每次push 都把队列转个圈」 如何用栈实现队列? 「两个栈(in / out) push全部进入输入栈, 每次执行pop或者top操作时如果输出栈为空就把输入栈的元素全部push进输出栈」

  • c++ 17 添加了新的特性 对于一个hashtable dist 「for (auto &[y, x] : dist」// 顺序和原来相同

  • 两个变量交换

    a = a - b; b = b - a; a = a + b; //法1

    a = a ^ b ; b = a ^ b; a = a ^ b; // 法2

·想要返回正确的double值，把被除数转成double型，而不是把结果转为double

1
return double(3/2) => 1        return double(3)/2 => 1.5

  • 字符与int之间的转化是简单的, 只需要加减'0' 就可以了, 字符串则可以通过 stoi 和 to_string 函数来实现!

  • 斐波那契数列 在n特别大时 采取矩阵快速幂的方法 能够求解 (滚动都太慢了)

  • -> 操作符 和 . 操作符的区别 「-> 左边是指针 . 左边是实体」 (p -> a() p是指针, p.a() p是实体)

  • nth_element(res.begin(), res.begin() + k, res.end(), greater<int>()). 寻找res中第k大的元素, 并将它放在第k个位置(默认是第k小) 「处理完之后, K之前的全都比他大, K之后的全部比它小(比排序快上一点)」

  • STL copy

    std::copy(start, end, container.begin()); // container 是复制到的那个容器的第一个元素， 因为复制到这个已有元素后更加高效

#Programming #Algorithm
Leetcode Notes
https://www.mementos.top/1976/04/01/LeetcodeNotes/
作者
Natsumi
发布于
1976年4月1日
许可协议