Yitao's Blog

1998. GCD Sort of an Array Description Solution Because we are using gcd to transfer numbers, so the number which shares the same factor should in the same set. So we could use Union-Find to mark numbers. There is also a tricky point that how to get the prime factor of one number. https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/ Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546const int N = 1E5+1;class Solution { i ...

1894. Find the Student that Will Replace the Chalk Description Solution presum + binary search Code 12345678910111213class Solution {public: int chalkReplacer(vector<int>& chalk, int k) { if(chalk[0] > k) return 0; for(int i = 1; i < chalk.size(); i++){ chalk[i] += chalk[i-1]; if(chalk[i] > k) return i; } k %= chalk.back(); int pos = upper_bound(chalk.begin(), chalk.end(), k) - chalk.begin() ...

502. IPO Description Solution Fix capital then find maximal profit by priority_queue Code 1234567891011121314151617181920212223242526class Solution { static bool cmp(pair<int,int>a, pair<int,int>b){ return a.second < b.second; }public: int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) { //find the maximal profit under current capital priority_queue<int, vector<int> ...

678. Valid Parenthesis String Description Solution Using a list to store the availiable number of * scaned forward. If we meet a ‘)’ and there is no ‘(‘ in the stack, then we gonna use * to match. As for mismatched ‘(‘, we should use * following to match it. Code 1234567891011121314151617181920212223242526272829class Solution {public: bool checkValidString(string s) { stack<int> stk; vector<int> count(s.size()+1, 0); for(int i = 0; i < s.siz ...

629. K Inverse Pairs Array Description Solution The tricky point is how to get the recurrence relation. We could ituitively give dp[i][j] as for i length array, the number of k’s inverse pairs. Then let’s figure out the recurrence relation Assume we already have dp[n][k], then we add one item afterwards. We have 12[1 2 3 4 5] 6↑ ↑ ↑ ↑ ↑ ↑ We can insert 6 into 6 slot to get more 5,4,3,2,1,0 more inverse pairs. so dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + ... + dp[n-1][k - (n-1)] Then we could ...

链表中倒数第k个节点 Description Solution Using fast-slow pointers, let fast pointer firstly walk k step then slow and fast walk togerther. Code 123456789101112131415161718192021/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* getKthFromEnd(ListNode* head, int k) { ListNode *fast = head, *slow = head; for(int i = 0; i &l ...

1681. Minimum incompatibility Description Solution We firstly compute the cost[i] , which i should be the mask of the elements in one set. Then we compute dp[mask] , and the recurrence relation is : 1dp[mask] = min(dp[mask ^ subset] + cost[subset]) Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546class Solution {public: int minimumIncompatibility(vector<int>& nums, int k) { int n = nums.size(); if(n % k) return ...

1987. Number of Unique Good Subsequences Description Solution Refer to Distinct Subsequences We calculate the different subsequence end with ith index. 12345678dp0[i] -> stands for from begin to ith index, subsequence number end with 0dp1[i] -> stands for from begin to ith index, subsequence number end with 1dp1[i] = dp1[i-1] + dp0[i-1] + 1 (for ith is 1)dp1[i] = dp1[i-1] (for ith is 0)dp0[i] = dp1[i-1] + dp0[i-1] (for ith is 0)dp0[i] = dp0[i-1] (for ith is 1) Code 123456789101112 ...

1986. Minimum Number of Work Sessions to Finish the Tasks Description Solution State Compress + DP 12firstly compute cost[mask].dp[mask] = min(dp[subset] + cost[mask ^ subset] <= TimeSession ? 1 : 0) Code 12345678910111213141516171819202122class Solution {public: int minSessions(vector<int>& tasks, int sessionTime) { int n = tasks.size(); vector<int> dp(1 << n, 15); vector<int> cost(1 << n); for(int i = 0; i & ...

881. Boats to Save People Description Solution Greedy, because every boat is required to save most 2 people, so we could greedily let every boat loads 2 people. But a tricky point is, intuitively we should let each boat takes as heavier as possible, but actually, if we could putpeople[-1] with people[1] instead of people[-1] with people[0], we still could let people[-2] with people[1], so just let first and last together and we will get the correct answer. Code 123456789101112131415161718cl ...

1000. Minimum Cost to Merge Stones Description Solution Using DP to solve the problem, we have 1dp[i][j][k] = from ith to jth, the cost to form k's piles So we have 1dp[i][j][k] = min(dp[i][p][1] + dp[p+1][j][k-1]) (p from i to j-1, step is k-1) Code 123456789101112131415161718192021222324252627282930class Solution {public: int mergeStones(vector<int>& stones, int k) { if((stones.size()-1) % (k-1) != 0) return -1; int n = stones.siz ...

295. Find Median from Data Stream Description Solution Because we are handling a stream problem, if we need resort the array each time it is a costy solution. So if we could have a self-balance binary search tree, we could use the top of the tree as the answer, but just writing a AVL or RBT is not very troublesome. A better solution is to use two priority queue, one is min heap and other is max heap. Code 123456789101112131415161718192021222324252627282930class MedianFinder {public: ...

790. Domino and Tromino Tiling Description Solution Check the dp state illustrated in picture Code 1234567891011121314151617class Solution { static const int MOD = 1E9 + 7;public: int numTilings(int n) { if(n == 1) return 1; vector<vector<long long>> dp(2, vector<long long>(1+n,0)); dp[0][1] = 1; dp[1][2] = 2; dp[0][2] = 2; for(int i = 3; i <= n; i++){ dp[0][i] = (dp[0][i-1] + dp[1][i ...

787. Cheapest Flights Within K Stops Description Solution BFS+cost[] array Ignore the vertex with more step && more cost, just to prune Code 1234567891011121314151617181920212223class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: adjacent = defaultdict(list) cost = [sys.maxsize] * n queue = [src] cost[src] = 0 step = 0 for f in flights: adjacent[f[0]].append((f[1 ...

479. Largest Palindrome Product Description Solution Because two n-digits intergers’ product are range from 2n-1 digits to 2n digits. Our strategy is constructing palindrome by str + reverse(str) . Then we detect from highest n-digits interger to sqrt(palin) to see if it can be divided into 2 n digits numbers. Code 12345678910111213141516class Solution: def largestPalindrome(self, n: int) -> int: def getPalin(i): s = str(i) s += s[::-1] return ...