YoungForest's blog

LeetCode weeekly contest 125

发表于 2019-02-24 更新于 2026-04-28 分类于 LeetCode Disqus：

本周末真是忙炸，为自己的拖延和懒惰付出了代价。事情都堆在了一起，周日的deadline超级多。早上10点和老板开会，商量怎么出本科计算机组成原理补考试题的事儿。开完会回到实验室，contest已经开始了。在短暂犹豫是否按计划参加contest，还是先完成出补考题的任务后，我开始了本周的weekly contest。也算是自己这2个月来坚持的为数不多的事情，继续坚持下去对我来说不仅是提高算法能力的事情了，更是对掌控自己生活的信心的一种极大鼓舞。

阅读全文 »

Queue and Stack

发表于 2019-02-17 更新于 2026-04-28 分类于 Programming Disqus：

今天我们一起学习2种重要的数据结构：队列和栈。
本文根据LeetCode上的Explore教程 Introduction to Data Structure - Queue & Stack 整理而成。

Introduction

最常用的Collection是数组(Array)，其最常使用的获取数据的操作是随机获取(Random access), 在C++中一般称作 subscribe。
但是有时，我们想要限制处理数据的顺序。最常见的限制是：先进先出(First in first out), 后进先出(Last in first out)。分别对应2种数据结构队列(Queue) 和栈(Stack)。

我们从定义、实现和每种数据结构的内置操作分别学习队列和栈。
学习目标：

理解数据处理顺序FIFO和LIFO的原则；
手动实现数据结构；
熟悉语言内置的Queue和Stack；
解决基础的Queue-related问题，尤其是BFS；
解决基础的Stack-related问题；
理解系统的栈如何帮助你，在解决dfs和其他递归问题的时候。

Queue: First-in-first-out Data Structure

定义

先进先出最普遍的比喻是排队(也就是队列), 最早进入队列的人最早被服务到。
所以队列总共只有2个modify 方法：

enqueue
dequeue

实现

阅读全文 »

LeetCode weekly contest 124

发表于 2019-02-17 更新于 2026-04-28 分类于 LeetCode Disqus：

今天是开工后第一次参加LeetCode weekly contest，共作出3道题目，排名为772 / 4174。看着每次排名从200+落到了700+，心情蛮失落的。我认为排名掉落的原因有：1. 排名为200是状态和运气都比较好的情况，之前大多数时候也是700左右。2. 第3题虽然为Hard，最后提交TLE了。但我认为如果再多给半个小时就可以AC了。之所以后面时间不够了，与第2、4题花了比较多时间调试直接相关。还是很多实现不够熟悉，比如bfs, backtracking，不能灵活地默写出来。甚至在做第4题的时候，还需要现场查C++的API，对语言的熟悉程度也不够。

993. Cousins in Binary Tree

在一棵二叉树上找表兄弟。所谓“表兄弟”的定义为，2个节点在同一层，但父节点不同。

Intuition: 递归地找节点的父亲和层数，比较2个节点的父亲和层数是否相同。也即，dfs遍历2遍二叉树。

时间复杂度：O(N),
空间复杂度: 平均O(Log N)，最差O(N), 因为需要递归栈。

由于春节假期期间看了LeetCode上的递归专题Introduction to Algorithms - Recursion I。10min搞定该签到题。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    // parent, depth
    pair<int, int> findNode(TreeNode* root, int value, int parent, int depth) {
        if (!root) return {0, depth + 1};
        if (root->val == value) return {parent, depth + 1};
        auto left = findNode(root->left, value, root->val, depth + 1);
        auto right = findNode(root->right, value, root->val, depth + 1);
        if (left.first != 0) return left;
        if (right.first != 0) return right;
        return {0, depth + 1};
    }
public:
    bool isCousins(TreeNode* root, int x, int y) {
        auto xNode = findNode(root, x, 0, 0);
        auto yNode = findNode(root, y, 0, 0);
        if (xNode.first != yNode.first && xNode.second == yNode.second)
            return true;
        return false;
    }
};

994. Rotting Oranges

给定一个网格，每个格子有3种状态

什么也没有
好橘子
坏橘子
每天坏橘子会将临近的好橘子变成坏橘子，求所有橘子变坏的天数。如果无穷大的话，返回-1.

阅读全文 »

recursion

发表于 2019-02-11 更新于 2026-04-28 分类于 Programming Disqus：

本文根据LeetCode上的教程 Introduction to Algorithms - Recursion I 整理而成。目的在于帮助笔者自己更熟悉“递归”这一重要的编程概念，如果能够同时对他人产生帮助，那更好不过了。

本文的结构和LeetCode上的完全相同，分为简介、递归原则、复现关系、备忘录、复杂度分析、总结 6个部分。

简介

本Card的目的，回答以下问题：

什么是递归？递归如何工作？
如何递归地解决一个问题？
如何分析一个递归算法的时间复杂度和空间复杂度？
如何以一种更好的方式应用递归？

递归的原理

每次递归函数调用自身，都将给定问题变为子问题。递归过程一直继续指导子问题可以不通过进一步递归就可以直接解决。

递归函数避免无限递归的必要属性：

递归结束条件(base cases)
一套规则(recurrence relation)，可以将所有其他的cases规约为base cases。

递归函数中可以有多个地方调用本身。

阅读全文 »

LeetCode weekly contest 123

发表于 2019-02-10 更新于 2026-04-28 分类于 LeetCode Disqus：

本次比赛是春节后的第一次。

Add to Array-Form of Integer

思路：模拟笔算过程，一位一位地相加。（Solution中有个很形象的名字：Schoolbook Addition）
时间复杂度：O(max(N, M)), 其中N, M分别表示A，K的长度。
空间复杂度：O(M-N), 即deque所用的空间。

class Solution {
public:
    vector<int> addToArrayForm(vector<int>& A, int K) {
        int index = A.size() - 1;
        while (K > 0 && index >= 0) {
            int last_digit = K % 10;
            K /= 10;
            A[index] += last_digit;
            int carry = A[index] / 10;
            K += carry;
            A[index] %= 10;
            index--;
        }
        
        deque<int> result;
        while (K > 0) {
            result.push_front(K % 10);
            K /= 10;
        }
        
        A.insert(A.begin(), result.begin(), result.end());
        
        return A;
    }
};

990. Satisfiability of Equality Equations

思路：使用并查集存储相等的关系，再遍历所有的不等关系是否在不同的集之间。

时间复杂度：O(N),
空间复杂度：O（N）。

class Solution {
    array<char, 26> parents;
    void union_variables(char a, char b) {
        char a_parent = find_root(a);
        char b_parent = find_root(b);
        parents[a_parent - 'a'] = b_parent;
    }
    char find_root(char a) {
        while (parents[a - 'a'] != a)
            a = parents[a - 'a'];
        return a;
    }
public:
    Solution() {
        for (int i = 0; i < 26; i++) {
            parents[i] = 'a' + i;
        }
    }
    bool equationsPossible(vector<string>& equations) {
        for(const string & s : equations) {
            if (s[1] == '=') {
                union_variables(s[0], s[3]);
            }
        }
        
        for(const string & s : equations) {
            if (s[1] == '!') {
                if (find_root(s[0]) == find_root(s[3]))
                    return false;
            }
        }
        
        return true;
    }
};

991. Broken Calculator

思路：一旦X大于Y，就只能通过减一的操作来达到Y。
如果X小于Y，则可以DOUBLE，也可以Decrement。
这时候如何选择呢？可以发现Double, Decrement, Decrement 和 Decrement, Double得到的结果相同。
这样，我们可以看出，
如果Y是奇数，则必须Double, Decrement才能得到。
如果Y是偶数，则必须Double才能得到(Decrement的操作次数更多)。

阅读全文 »

LeetCode weekly contest 122

发表于 2019-02-04 更新于 2026-04-28 分类于 LeetCode Disqus：

由于宅在家里过节，竟然忘记了每天是星期几，只知道农历腊月几日。今天才发现已经到了周一了，错过了每周一度的weekly contest。在此除夕之夜，和家人一起看春晚之前，Forest携全家人一起祝大家新年快乐！快些刷完这4道比赛题目，好安心吃年夜饭。

由于比赛不能用官方的Notes, 写在blog上还是蛮方便的一种替代品。

985. Sum of Even Numbers After Queries

第一题直接模拟即可。每个query有2个动作：

add val to A[index];
sum the even values of A.

模拟的时间复杂度为：
O(K * N)
其中，N为数组长度，K为queries长度。

因为题目中K，N都不大于10000，所以总的规模在10^8 < 10^9, 是可以AC的。

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        vector<int> results;
        for (const vector<int>& query : queries) {
            A[query[1]] += query[0];
            int total = 0;
            for (int a : A) {
                if (a % 2 == 0) total += a;
            }
            results.push_back(total);
        }
        
        return results;
    }
};

不过Solution中给到一种复杂度为O(N+K)的。
思想是：每次计算sum时，我们可以利用上一个query的结果。
如果add后，
A中数值从奇数变为偶数了，sum = last_sum + 新偶数；
if 偶数 -> 奇数，sum = last_sum - 旧偶数;
if 偶数 -> 偶数，sum = last_sum + 新偶数 - 旧偶数;
if 奇数 -> 奇数，sum = last_sum.

class Solution {
public:
    vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {
        vector<int> results;
        int total = 0;
        for (int a : A) {
            if (a % 2 == 0) total += a;
        }
        
        for (const vector<int>& query : queries) {
            if (A[query[1]] % 2 == 0) total -= A[query[1]];
            A[query[1]] += query[0];
            if (A[query[1]] % 2 == 0) total += A[query[1]];
            results.push_back(total);
        }
        
        return results;
    }
};

阅读全文 »

LeetCode weekly contest 121

发表于 2019-01-27 更新于 2026-04-28 分类于 LeetCode Disqus：

今天放假回家，下午3点半的火车。不过我还是百忙之中抽出时间参加了每周例行的weekly contest。结果因为回家不够专注，效果很差，只做出一道签到题。第二题TLE(结果把一个变量改成引用就可以了，也算是吸取了教训，能用引用就用引用)，第3题没有足够的时间完成了(直到下午坐上火车，心无旁骛地终于独立完成了第三题。其实思路从一开始就是对的，只不过没有时间调试细节)。第四题干脆连题干都没有时间看完。

984. String Without AAA or BBB

Intution: 由于不能出现连续的a或b，我们可以试着直接构造出符合要求的字符串。多的字符出现2次，即插入一个少的字符，当剩余的2个字符一样多的时候，就一个出现一次就可以了。

class Solution {
public:
    string strWithout3a3b(int A, int B) {
        string result;
        char large, small;
        int bigger, smaller;
        if (A > B) {
            large = 'a';
            small = 'b';
            bigger = A;
            smaller = B;
        } else {
            large = 'b';
            small = 'a';
            bigger = B;
            smaller = A;
        }
        for (; bigger > 0 && smaller > 0 && bigger > smaller; bigger-=2, smaller--) {
            result.push_back(large);
            result.push_back(large);
            result.push_back(small);
        }
        for (; bigger > 0 && smaller > 0; bigger--, smaller--) {
            result.push_back(large);
            result.push_back(small);
        }
        while (bigger > 0) {
            result.push_back(large);
            bigger--;
        }
        while (smaller > 0) {
            result.push_back(small);
            small--;
        }
        
        return result;
    }
};

981. Time Based Key-Value Store

Intution:
使用hashmap存储<key, vector<pair<int, string>> value>,
每次查找到key对应的vector后，针对pair的第一个值使用二分查找upper_bound timestamp.

注意：用引用，千万不要用普通变量存储hashmap[key]。

class TimeMap {
private:
    /** Intution:
        使用hashmap存储<key, vector<pair<int, string>> value>,
        每次查找到key对应的vector后，针对pair的第一个值使用二分查找upper_bound timestamp
    */
    unordered_map<string, vector<pair<int, string>>> hashmap;
    class Cmp {
        public:
        bool operator() (pair<int, string> a, pair<int, string> b) {
            return a.first < b.first;
        }
    };
public:
    /** Initialize your data structure here. */
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        hashmap[key].push_back({timestamp, value});
    }
    
    string get(string key, int timestamp) {
        auto& values = hashmap[key];    // 注意：用引用，千万不要用普通变量存储
        if (values.size() == 0) return "";
        auto val = upper_bound(values.begin(), values.end(), make_pair(timestamp, ""), Cmp());
        if (val == values.begin()) return "";
        return (--val)->second;
    }
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */

983. Minimum Cost For Tickets

Intution: 最优化问题，最优解依赖子问题的解，首先想到dp。
最优解结构：f(x) = min(f(x-1) + cost[0], f(x-7) + cost[1], f(x-30) + cost[2]),
其中，f(x)表示天数为x时的最小花费，由于x可能不存在于days中，此时，f(x)表示比x恰好大的天的最小花费。

阅读全文 »

LeetCode weekly contest 120

发表于 2019-01-20 更新于 2026-04-28 分类于 LeetCode Disqus：

本周和好友“女声男”同时参加weekly contest。有同学共同竞争还是挺有压力的。因为我练习算法题已经有半年时间了，他还是新手，如若最后还败北了，岂不丢人。不过结果还好，没有丢自己的人。我在离比赛结束还有10min时全部AC，而且所有题目都是一遍过，略胜一筹。不得不说，这次的题比往届简单不少，之前我的水平一直维持在只做出2道题目，ranking 800左右，而本次ranking 为 356 / 3870。从排名上看有所进步。

下面我分享一下四道题目的思路。

977. Squares of a Sorted Array

给定一个数组，返回各个元素的平方数组，该数组是排好序的。直接brute force即可。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> square;
        
        for (auto a: A) {
            square.push_back(a * a);
        }
        
        sort(square.begin(), square.end());
        
        return square;
    }
};

时间复杂度：O(n log n)，因为有个排序。
空间复杂度：O(n)，因为要返回一个新的数组，除此之外，不实用额外空间。当然，你也可以使用传进来的数组所占的空间，更trick，但没有多大意义。

看过Solution后，惊奇地发现竟然还有种O(n)的解法。仔细一看，原来是自己没有注意到数组A本身是排好序的。问题可以转化为合并2个排好序的数组。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        vector<int> square;
        
        int j = 0;
        for (; j < A.size() && A[j] < 0; j++) ;
        
        int i = j - 1;
        while (i >= 0 && j < A.size()) {
            if (A[i]*A[i] < A[j]*A[j]) {
                square.push_back(A[i]*A[i]);
                i--;
            }
            else {
                square.push_back(A[j]*A[j]);
                j++;
            }
        }

        while (i >= 0) {
            square.push_back(A[i]*A[i]);
            i--;
        }
        
        while (j < A.size()) {
            square.push_back(A[j]*A[j]);
            j++;
        }
        
        return square;
    }
};

978. Longest Turbulent Subarray

给定一个数组，返回“升降子数组”的最大长度。所谓“升降子数组”，即相邻2个元素对大小变化的符号相反，比如[1, 2, 1, 2, 1]。画在坐标图上就是波浪状。

阅读全文 »

LeetCode weekly contest 119

发表于 2019-01-13 更新于 2026-04-28 分类于 LeetCode Disqus：

这次contest做的比较惨，排名大致是1486 / 3845。出现的问题有：

第二题，比较简单。由于是easy的题目，直接brute force了，结果TLE一次。之前由于粗心，for循环条件中的变量还写错了一次。导致2次罚时。
第三题，也不是很难，但最后并没有想到O(n)的解法。只想到了O(n ^ 2)的。想到了要算前缀和，也注意到了divisible这一关键词。但并没有联想到前缀和相等就可以这一关键点。
第四题，想到了dp。卡在了"找寻后面数组中刚刚大一点的数"这步，即没想到用TreeMap解决。归根结底是因为对基础的数据结构不熟悉。

973. K Closest Points to Origin

直接用C++中的Map即可，用key进行排序。

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        map<int, vector<vector<int>>> distance;
        for (const auto point: points) {
            distance[point[0]*point[0] + point[1]*point[1]].push_back(point);
        }
        vector<vector<int>> results;
        int i = 0;
        for (const auto d: distance) {
            for (const auto point: d.second) {
                results.push_back(point);
                i++;
                if (i >= K) {
                    return results;
                }
            }
        }
        
        return results;
    }
};

976. Largest Perimeter Triangle

只用找最大的3个可以组成三角形的数就可以了。

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        int result = 0;
        sort(A.begin(), A.end());
        for (int i = A.size() - 3; i >= 0; i--) {
            if (A[i] + A[i+1] > A[i+2]) {
                result = A[i] + A[i+1] + A[i+2];
                break;
            }
        }
        
        return result;
    }
};

974. Subarray Sums Divisible by K

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        unordered_map<int, int> prefix_sum;
        int sum = 0;
        int result = 0;
        prefix_sum[0] = 1;
        for (int i = 0; i < A.size(); i++) {
            sum = (sum + A[i] % K + K) % K;
            result += prefix_sum[sum];
            prefix_sum[sum]++;
        }
        
        return result;
    }
};

阅读全文 »

LeetCode weekly contest 118

发表于 2019-01-06 更新于 2026-04-28 分类于 LeetCode Disqus：

一周一度的LeetCode weekly contest 开始啦。本周着实比之前有所进步，首先是对C++更加熟悉了，之前都是用Python写的。答题过程也更流畅了，差点做出来3道题目。

阅读全文 »