YoungForest's blog

LeetCode weekly contest 152

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

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
111 / 5333	YoungForest	18	1:11:49	0:11:56 1	0:21:44 1	0:37:27	1:01:49

本期比赛由于粗心，第一题忘记考虑corner case，0的排列是1；第二题干脆upper lower写反了。获得2次罚时。否则应该可以进入前100的。题目比较简单，都是常规题目，之前的原题改改就行。

1175. Prime Arrangements

筛法求素数 + 排列组合。

时间复杂度: O(N),
空间复杂度: O(N).

class Solution {
    using ll = long long;
    const int modulo = 1e9 + 7;
    unordered_map<int, ll> memo;
    ll A(int x) {
        if (x == 0)
            return 1;
        if (x == 1)
            return 1;
        if (memo.find(x) == memo.end()) {
            memo[x] = (x * A(x - 1)) % modulo;
        }
        return memo[x];
    }
public:
    int numPrimeArrangements(int n) {
        vector<bool> a(n + 1, true);
        int count = 0;
        for (int i = 2; i < n + 1; ++i) {
            if (a[i]) {
                ++count;
                for (int j = 2; j * i < n + 1; ++j) {
                    a[j * i] = false;
                }
            }
        }
        return (A(count) * A(n - count)) % modulo;
    }
};

1176. Diet Plan Performance

简单的滑动窗口。竟然因为粗心错了一次。

时间复杂度: O(N),
空间复杂度: O(N).

class Solution {
public:
    int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {
        if (k > calories.size())
            return 0;
        int sum = accumulate(calories.begin(), calories.begin() + k, 0);
        int ans = 0;
        if (sum > upper)
            ++ans;
        else if (sum < lower)
            --ans;
        for (int i = k; i < calories.size(); ++i) {
            sum = sum + calories[i] - calories[i - k];
            if (sum > upper)
                ++ans;
            else if (sum < lower)
                --ans;
        }
        return ans;
    }
};

阅读全文 »

LeetCode weekly contest 151

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

这周去字节跳动参加夏令营了，周日还需要上课，所以就鸽了周赛。那你怎么能参加kick start呢？毕竟本月的round E是所谓的黄金轮次，对面试获取名额很重要，所以我选择翘掉夏令营。

夏令营结束后，按约补题。不得不说，LeetCode比Kick start的难度还是要低不少的。感觉Kick start的签到题难度是Medium，后2题是Hard。

1169. Invalid Transactions

考察字符串处理。由于transactions.lenght < 1000, 所以及时是暴力方法也是可以的。事实上，我实现的优化方法在最坏情况下，并没有变好。

时间复杂度: O(N^2).
空间复杂度: O(N).

class Solution {
public:
    vector<string> invalidTransactions(vector<string>& transactions) {
        unordered_map<string, vector<tuple<int, int, string>>> name_trasactions;
        for (const auto& s : transactions) {
            stringstream ss(s);
            string tmp;
            vector<string> v;
            while (getline(ss, tmp, ',')) {
                v.push_back(tmp);
            }
            name_trasactions[v[0]].push_back({stoi(v[1]), stoi(v[2]), v[3]});
        }
        unordered_set<string> ans;
        for (auto& p : name_trasactions) {
            sort(p.second.begin(), p.second.end());
            int l = 0, r = 0;
            for (; r < p.second.size(); ++r) {
                if (get<1>(p.second[r]) > 1000) {
                    ans.insert(p.first + "," + to_string(get<0>(p.second[r])) + "," + to_string(get<1>(p.second[r]))+ "," + get<2>(p.second[r]));
                }
                while (get<0>(p.second[r]) - get<0>(p.second[l]) > 60) {
                    ++l;
                }
                for (int i = l; i < r; ++i) {
                    if (get<2>(p.second[r]) != get<2>(p.second[i])) {
                        ans.insert(p.first + "," + to_string(get<0>(p.second[r])) + "," + to_string(get<1>(p.second[r]))+ "," + get<2>(p.second[r]));
                        ans.insert(p.first + "," + to_string(get<0>(p.second[i])) + "," + to_string(get<1>(p.second[i]))+ "," + get<2>(p.second[i]));
                    }
                }
            }
        }
        return vector<string>(ans.begin(), ans.end());
    }
};

1170. Compare Strings by Frequency of the Smallest Character

简单的二分查找。

时间复杂度: O(queries.length * queries[i].length * log words.length),
空间复杂度: O(queries.length + words.length).

class Solution {
    int f(const string& s) {
        char mi = 'z' + 1;
        int count = 0;
        for (char c : s) {
            if (c == mi) {
                ++count;
            } else if (c < mi) {
                mi = c;
                count = 1;
            }
        }
        return count;
    }
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> a;
        for (const auto& w : words) {
            a.push_back(f(w));
        }
        sort(a.begin(), a.end());
        vector<int> ans;
        for (const auto& q : queries) {
            int c = f(q);
            auto it = upper_bound(a.begin(), a.end(), c);
            ans.push_back(distance(it, a.end()));
        }
        return ans;
    }
};

阅读全文 »

kick start 2019 round E

发表于 2019-08-29 更新于 2026-04-28 分类于 KickStart Disqus：

Cherries Mesh

Minimum spanning tree.
尤其要注意Union-find的实现中，find要采用path compression的方法才能实现O(1).
否则会超时。

#include <iostream>
#include <vector>

using namespace std;

struct UF {
	vector<int> parents;
	UF(int n) {
		parents.resize(n);
		for (int i = 0; i < n; ++i) {
			parents[i] = i;
		}
	}

	int find(int x) {
		return parents[x] == x ? x : (parents[x] = find(parents[x]));
	}

	void unio(int x, int y) {
		int px = find(x);
		int py = find(y);
		parents[px] = py;
	}
};

int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		int N, M;
		cin >> N >> M;
		UF uf(N);
		int ans = 0;
		for (int j = 0; j < M; ++j) {
			int l, r;
			cin >> l >> r;
			--l;
			--r;
			if (uf.find(l) == uf.find(r)) {
				continue;
			}
			uf.unio(l, r);
			ans += 1;
		}
		ans += (N - 1 - ans) * 2;
		cout << "Case #" << i + 1 << ": " << ans << endl;
	}
	return 0;
}

Code-Eat Switcher

Test set 1:

S = 1 或 2。列不等式就可以求解。
当S = 2时，有2个变量，不等式求解过程类似线性规划。

比赛的时候思路是对的，但是因为S = 1时，返回值写错了，一直没有AC。当时一直在调S = 2时的逻辑，完全没有想到S = 1时会出错。

#include <vector>
#include <iostream>
#include <unordered_map>
#include <map>
#include <cmath>

using namespace std;

bool solve(const vector<pair<int, int>>& energy, const int S, double code, double eat) {
    if (S == 1) {
        double Ci = energy[0].first;
        double Ei = energy[0].second;
        return code / Ci + eat / Ei <= 1;
    } else if (S == 2) {
        double C1 = energy[0].first, C2 = energy[1].first;
        double E1 = energy[0].second, E2 = energy[1].second;
        if (C1 / C2 == E1 / E2) {
            vector<pair<int, int>> tmp = {make_pair(energy[0].first + energy[1].first, energy[0].second + energy[1].second)};
            return solve(tmp, 1, code, eat);
        }
        double C = code, E = eat;
        double x = (C / C2 - 1 + E / E2 - E1 / E2) / (C1 / C2 - E1 / E2);
        double y = C / C2 - x * C1 / C2;
        // cout << "result: " << x << ", " << y << "|" << x * C1 + y * C2 << ", " << (1 - x) * E1 + (1 - y) * E2 << " | " << 
        // 1 - E / E2 + E1 / E2 - x * E1 / E2
        // << endl;
        if (x > 1) {
            return 1 - E / E2 + E1 / E2 - 1 * E1 / E2 >= C / C2 - 1 * C1 / C2;
        }
        if (y > 1) {
            return (1 - E / E2 + E1 / E2 - 1) * (E2 / E1) >= (C / C2 - 1) * (C2 / C1);
        }
        if (x < 0) {
            return 1 - E / E2 + E1 / E2 >= C / C2;
        }
        if (y < 0) {
            return (1 - E / E2 + E1 / E2) * (E2 / E1) >= (C / C2) * (C2 / C1);
        }
        return true;
        // return x >= 0 && y >= 0 && x <= 1 && y <= 1;
    } else {
        return false;
    }
}

int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		int D, S;
        cin >> D >> S;
        string ans;
        vector<pair<int, int>> energy(S);
        for (int i = 0; i < S; ++i) {
            cin >> energy[i].first >> energy[i].second;
        }
        for (int i = 0; i < D; ++i) {
            int A, B;
            cin >> A >> B;
            bool yes = solve(energy, S, A, B);
            if (yes) {
                ans.push_back('Y');
            } else {
                ans.push_back('N');
            }
        }
		cout << "Case #" << i + 1 << ": " << ans << endl;
	}
	return 0;
}

Test Set 2

观察有，对于每个slot，每获得1份eating能量，就会少收获 $C_i / E_i$ 份coding能量。所以如果 $C_i / E_i < C_j / E_j$ 的话，更好的选择永远时i。
根据这个观察，我们把slot根据 $C_i / E_i$ 排序，计算E的前缀和和C的后缀和。每天使用二分查找找到满足eating的分界点，再判断是否满足coding。

阅读全文 »

LeetCode biweekly contest 7

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

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
106 / 1901	YoungForest	18	1:01:13	0:05:46	0:27:13	0:35:34	1:01:13

本周参加字节跳动的夏令营，周六开幕，所以本次的双周赛是在五星级酒店的床上完成的。好不舒服，比赛结果也还能看下去。
由于第二天上午要参加夏令营的课程，所以周赛就鸽掉了。不过下午的kick start round E还是参加了，翘掉了夏令营的课程。谁让我非常想去谷歌呢？

双周赛题目不难，感觉像是其他OJ上类似的beginner定位。

1165. Single-Row Keyboard

考察hash table的应用, 建立字母和index的反向映射即可。

时间复杂度: O(N)
空间复杂度: O(N)

class Solution {
public:
    int calculateTime(string keyboard, string word) {
        vector<int> location(26);
        for (int i = 0; i < keyboard.size(); ++i) {
            location[keyboard[i] - 'a'] = i;
        }
        int ans = 0;
        int current = 0;
        for (char c : word) {
            ans += std::abs(location[c - 'a'] - current);
            current = location[c - 'a'];
        }
        return ans;
    }
};

1166. Design File System

考察基本的数据结构（树）和字符串处理。
对路径进行建树，每个文件或目录是一个节点，节点上有value。查找和增长的过程都是类似字典树。
时间复杂度: O(N).
空间复杂度: O(N).

class FileSystem {
    struct Node {
        unordered_map<string, shared_ptr<Node>> children;
        int value;
        Node(int v) : value(v) {}
    };
    vector<string> split(const string& path) {
        string tmp;
        vector<string> stk;
        stringstream ss(path);
        while(getline(ss,tmp,'/')) {
            stk.push_back(tmp);
        }
        return stk;
    }
    shared_ptr<Node> m;
public:
    FileSystem() {
        m = make_shared<Node>(0);
    }
    
    bool create(string path, int value) {
        auto words = split(path);
        auto current = m;
        for (int i = 1; i < words.size() - 1; ++i) {
            const auto& word = words[i];
            if (current->children.find(word) == current->children.end()) {
                return false;
            } else {
                current = current->children[word];
            }
        }
        if (current->children.find(words.back()) != current->children.end()) {
            return false;
        }
        current->children[words.back()] = make_shared<Node>(value);
        return true;
    }
    
    int get(string path) {
        auto words = split(path);
        auto current = m;
        for (int i = 1; i < words.size(); ++i) {
            const auto& word = words[i];
            if (current->children.find(word) == current->children.end()) {
                return -1;
            } else {
                current = current->children[word];
            }
        }
        return current->value;
    }
};

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem* obj = new FileSystem();
 * bool param_1 = obj->create(path,value);
 * int param_2 = obj->get(path);
 */

阅读全文 »

LeetCode weekly contest 150

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

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (7)
476 / 5091	YoungForest	19	1:31:13	0:03:52	0:09:23	1:16:13 2	0:50:16 1

本次比赛效果同样不佳，排名在400+。直接原因是第3题的搜索剪枝花费了太长时间，没有一步到位。根本原因是最近2周好不容易放假在家，放松了练习，刷题基本停止了，自然手上的功夫就荒废了。真应了那句“业精于勤荒于嬉”呀。上周的排名同样很差。

1160. Find Words That Can Be Formed by Characters

常规的字母计数问题，用hashmap存储即可。需要注意的是，每次判断一个word的时候，需要获得一次拷贝。

时间复杂度: O(chars.size() + words.size() * word.size()),
空间复杂度: O(26)

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int ans = 0;
        vector<int> count(26);
        for (char c : chars) {
            ++count[c - 'a'];
        }
        for (const auto& s : words) {
            auto count_copy = count;
            for (char c : s) {
                --count_copy[c - 'a'];
                if (count_copy[c - 'a'] < 0) {
                    goto next;
                }
            }
            ans += s.size();
            next:
                ;
        }
        return ans;
    }
};

1161. Maximum Level Sum of a Binary Tree

先获得每一层的和，再取得最大值。

时间复杂度: O(N),
空间复杂度: O(N).

/**
 * 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 {
    vector<int> sum_of_level;
    void dfs(TreeNode* root, int depth) {
        if (root == nullptr)
            return;
        if (depth > sum_of_level.size()) {
            sum_of_level.push_back(0);
        }
        sum_of_level[depth-1] += root->val;
        dfs(root->left, depth + 1);
        dfs(root->right, depth + 1);
    }
public:
    int maxLevelSum(TreeNode* root) {
        dfs(root, 1);
        int ans = 0;
        for (int i = 1; i < sum_of_level.size(); ++i) {
            if (sum_of_level[i] > sum_of_level[ans]) {
                ans = i;
            }
        }
        return ans + 1;
    }
};

阅读全文 »

LeetCode weekly contest 149

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

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (9)
476 / 5091	YoungForest	15	1:00:14	0:10:21	0:42:14	1:00:14	null

惭愧的排名又落到400+了。最后一题有半个小时可以解决，一直试图用线段树来做。像kick start round D一样，沉迷于线段树而翻车。获得的教训是，不要纠结与区间问题一定要用线段树做，常常还有其他更简单的做法。

1154. Day of the Year

判断闰年，累加之前月份的日子。
时间复杂度: O(1),
空间复杂度: O(1).

class Solution {
    bool isLeap(int yy) {
        return (yy % 4 == 0 && yy % 100 != 0) || yy % 400 == 0;
    }
public:
    int dayOfYear(string date) {
        auto yy = stoi(date.substr(0, 4));
        auto mm = stoi(date.substr(5, 2));
        auto dd = stoi(date.substr(8, 2));
        vector<int> days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if (isLeap(yy)) {
            days[2] = 29;
        }
        int ans = 0;
        ans += accumulate(days.cbegin(), days.cbegin() + mm, 0);
        ans += dd;
        return ans;
    }
};

1155. Number of Dice Rolls With Target Sum

隔板插空，经典的排列组合问题。由于2个隔板之前的间隔不能大于骰子最大的数字，所以不能直接用数学公式求解。我采用了回溯法，使用了memorization，所以也算是DP。

时间复杂度: O(N ^ 2),
空间复杂度: O(d * bar).

class Solution {
    const int mod = 1e9 + 7;
    int f;
    map<pair<int, int>, int> memo;
    // [begin, end), the index of insert bar
    int backtracking(int begin, int end, int bar) {
        if (memo.find({begin, bar}) != memo.end()) {
            return memo[{begin, bar}];
        }
        if (bar == 0) {
            if (end - begin + 1 <= f)
                return 1;
            else
                return 0;
        }
        int ans = 0;
        for (int i = begin; i < end && i - begin + 1 <= f; ++i) {
            // insert in i
            ans += backtracking(i + 1, end, bar - 1);
            ans %= mod;
        }
        memo[{begin, bar}] = ans;
        return ans;
    }
public:
    int numRollsToTarget(int d, int f, int target) {
        this->f = f;
        int ans = backtracking(0, target - 1, d - 1);
        return ans;
    }
};

1156. Swap For Longest Repeated Character Substring

阅读全文 »

LeetCode weekly contest 148

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

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (6)	Q4 (8)
77 / 5319	YoungForest	23	0:56:45	0:09:51	0:24:02	0:41:20	0:56:45

本次比赛是我时隔3个月再次进入前100名，也是连续2次进入前200名，还是有些小开心的。算是一扫上周kick start 翻车的阴郁。
事实上，由于评测机的问题，我比赛刚结束时看到的排名是56名。后来官方有重新评测了最后一题，有些人的提交就可以过了，也没有罚时了。
本次比赛也是质量蛮高，题目不是很难，但考察的知识点很全面，难度分布也比较合理。

1144. Decrease Elements To Make Array Zigzag

因为只能减1嘛，所以是到Easy题目。如果题目改成加1或减1，会难的多。
只需要比较2种情况，选择小的即可。

时间复杂度: O(N),
空间复杂度: O(1).

class Solution {
    const int INF = 0x3f3f3f3f;
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int ans1 = 0;
        for (int i = 0; i < nums.size(); i += 2) {
            int neighbor = INF;
            if (i > 0) {
                neighbor = min(neighbor, nums[i - 1]);
            }
            if (i < nums.size() - 1) {
                neighbor = min(neighbor, nums[i + 1]);
            }
            if (neighbor != INF && neighbor <= nums[i]) {
                ans1 += nums[i] - neighbor + 1;
            }
        }
        int ans2 = 0;
        for (int i = 1; i < nums.size(); i += 2) {
            int neighbor = INF;
            if (i > 0) {
                neighbor = min(neighbor, nums[i - 1]);
            }
            if (i < nums.size() - 1) {
                neighbor = min(neighbor, nums[i + 1]);
            }
            if (neighbor != INF && neighbor <= nums[i]) {
                ans2 += nums[i] - neighbor + 1;
            }
        }
        return min(ans1, ans2);
    }
};

1145. Binary Tree Coloring Game

本题的难点在于理解题意。思路倒是十分直观，尽量选择最大的分支。如果大分支的数量大于一半，则必胜。
树的问题用递归，模版还是一个DFS。

时间复杂度: O(N), 遍历每个节点1次；
空间复杂度: O(N). 树的深度，最差为N。

/**
 * 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 {
    int l, r;
    // return the number of node in subtree
    int dfs(TreeNode* root, int x) {
        if (root == nullptr)
            return 0;
        int left = dfs(root->left, x);
        int right = dfs(root->right, x);
        if (root->val == x) {
            l = left;
            r = right;
        }
        return left + right + 1;
    }
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        dfs(root, x);
        if (n == l + r + 1) {
            return l != r;
        } else {
            int parent = n - l - r - 1;
            return parent - 1 > l + r || l - 1 > r + parent || r - 1 > l + parent;
        }
    }
};

阅读全文 »

LeetCode weekly contest 147

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

Rank	Name	Score	Finish Time	Q1 (2)	Q2 (5)	Q3 (7)	Q4 (7)
175 / 4906	YoungForest	21	1:14:32	0:08:18 1	0:27:17 1	0:41:32	1:04:32

昨天做了Biweekly contest，今天做了常规赛和下午的Google Kick D.
连续3场比赛，周末很充实。

1137. N-th Tribonacci Number

和 Fibonacci 类似。相同的解法应该都可以用在这里。
我采用了实现起来最方便的解法。

时间复杂度: O(N),
空间复杂度: O(N).

class Solution {
public:
    int tribonacci(int n) {
        vector<int> dp(max(n + 1, 3));
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }
        return dp[n];
    }
};

1138. Alphabet Boar

也是straight forward的解法。因为移动距离就是2点之间的曼哈顿距离，所以贪心地移就好了。
此处有坑，z的位置上不能向右移，uvwxy不能向下移。

时间复杂度: O(N).
空间复杂度: O(N).

class Solution {
public:
    string alphabetBoardPath(string target) {
        vector<pair<int, int>> locations(26);
        for (char c = 'a'; c <= 'z'; ++c) {
            int index = c - 'a';
            locations[index] = {index / 5, index % 5};
        }
        pair<int,int> current = {0, 0};
        string ans;
        auto special = locations.back();
        for (char c : target) {
            auto to = locations[c - 'a'];
            if (current != special) {
                if (to.second > current.second) {
                    ans.append(to.second - current.second, 'R');
                } else {
                    ans.append(current.second - to.second, 'L');
                }
                if (to.first > current.first) {
                    ans.append(to.first - current.first, 'D');
                } else {
                    ans.append(current.first - to.first, 'U');
                }
            } else {
                if (to.first > current.first) {
                    ans.append(to.first - current.first, 'D');
                } else {
                    ans.append(current.first - to.first, 'U');
                }
                if (to.second > current.second) {
                    ans.append(to.second - current.second, 'R');
                } else {
                    ans.append(current.second - to.second, 'L');
                }
            }
            ans.push_back('!');
            current = to;
        }
        return ans;
    }
};

阅读全文 »

kick start 2019 round D

发表于 2019-07-28 更新于 2026-04-28 分类于 KickStart Disqus：

排名: 765 / 1866.

X or What

本题是找规律的题目，考察最xor的熟悉程度。事实上，我曾经很接近于正确解法了。但一头心思钻到 interval 题目用线段树求解的经验上，试图寻找节点记录什么信息。结果越走越偏。

总结起来规律是这样的:
题目中给了xor-even的定义。
我们根据xor的性质有：

odd xor odd -> even
odd xor even -> odd
even xor even -> even

想要最后xor-even，interval中的odd必须是偶数个。一个非常直接的思路就出来了。统计odd的数量，如果是偶数，那么最长的interval就是整个数组的长度。如果是奇数，则去掉头或尾，找最长的。

#include <set>
#include <cstdio>

using namespace std;

const int N = 1e5 + 5;
int n, q;
int a[N], v[N];
int p[N];

int even(int i) {
  int count = 0;
  while (i > 0) {
    count += i % 2;
    i /= 2;
  }
  return count;
}

void read_input() {
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    a[i] = even(x) & 1;
  }
  for (int i = 0; i < q; ++i) {
      int x;
    scanf("%d %d", p+i, &x);
    v[i] = even(x) & 1;
  }
}

void solve() {
  set<int> idx[2];
  for (int i = 0; i < n; ++i) {
    idx[a[i]].insert(i);
  }
  for (int i = 0; i < q; ++i) {
    if (a[p[i]] != v[i]) {
      idx[a[p[i]]].erase(p[i]);
      a[p[i]] = v[i];
      idx[a[p[i]]].insert(p[i]);
    }
    if (i)
      printf(" ");
    if (idx[1].size() % 2 == 0) {
      printf("%d", n);
    }
    else {
      int ans = max(*idx[1].rbegin(), n-*idx[1].begin()-1);
      printf("%d", ans);
    }
  }
  printf("\n");
}

int main() {
#ifdef LOCAL
  time_t starttime = clock();
#endif
  int tt;
  scanf("%d", &tt);
  for (int tc = 1; tc <= tt; tc++) {
    printf("Case #%d: ", tc);
    read_input();
    solve();
#ifdef LOCAL
    cerr << "~ TC#" << tc << " done! execution time: " <<
      (double)(clock()-starttime) / CLOCKS_PER_SEC << " s" << endl;
#endif
  }
  return 0;
}

阅读全文 »

LeetCode biweekly contest 5

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

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (3)	Q3 (5)	Q4 (7)
98 / 1634	YoungForest	18	0:35:23	0:11:01	0:10:53	0:22:40	0:35:23

距离上次参加biweekly contest已经2个月了，编号也从1直接跳到5了。
本次contest十分简单，都是算法里的经典的题目，属于必会的。我做完4题后还有近1个小时。

1133. Largest Unique Number

签到题。遍历一遍数组，然后计数。然后从大向小找符合要求的数。

时间复杂度: O(N log N),
空间复杂度: O(N).

class Solution {
public:
    int largestUniqueNumber(vector<int>& A) {
        map<int, int> count;
        for (int a : A) {
            ++count[a];
        }
        for (auto it = count.crbegin(); it != count.crend(); ++it) {
            if (it->second == 1)
                return it->first;
        }
        return -1;
    }
};

1134. Armstrong Number

感觉还是一道Easy的题目。根据题意做即可，考察取数中每一个位。

时间复杂度: O(log N), N的位数。
空间复杂度: O(log N).

class Solution {
    int pow(int x, int y) {
        if (y == 0)
            return 1;
        else
            return x * pow(x, y - 1);
    }
public:
    bool isArmstrong(int N) {
        const int number = N;
        vector<int> digits;
        while (N > 0) {
            digits.push_back(N % 10);
            N /= 10;
        }
        int s = 0;
        int power = digits.size();
        for (auto digit : digits) {
            s += pow(digit, power);
        }
        
        return s == number;
    }
};

阅读全文 »