Yitao's Blog

5852. Minimize the Difference Between Target and Chosen Elements Description Solution DFS + memorize visited + pruning Code 1234567891011121314151617181920212223242526272829303132class Solution { vector<vector<int>> visited; int res = INT_MAX;public: int minimizeTheDifference(vector<vector<int>>& mat, int target) { int m = mat.size(), n = mat[0].size(); for(int i = 0; i < m; i++) sort(mat[i].begin(), mat[i].end()); ...

5853. Find Array Given Subset Sums Description Solution Firstly, let’s think about a easier question—If sums‘s elements are all positive, how would you solve this? Obviously, the minimum one m is the front one in the ans array. How to find the next answers? Delete all subset in sums from ans array, which should be $2^{ans.size()-1}$ elements to be deleted How to do this in programming? In each iteration, use a mask to mark the combination of ans‘s numbers, note that we just need to dele ...

650. 2 Keys Keyboard Description Solution O(n^2), search from 1 to i-1 to find the smallest operation number for dp[i] O(sqrt(n)), all the operations sequences are like : CPPPCPPPPCP..., can be divided into groups (CPPP)(CPP)(CP)…. .If we have each group’s length like g1, g2,g3..., so after first group, there are g1 A’s, after second group g1 * g2 A’s… We want have N = g1 * g2 * g3...*gn A’s, if gi can be divided into product of other two numbers, denote as gi = p * q, so it can be divide ...

212. Word Search II Description Solution A classic usage of Trie Tree(prefix tree). Template: 123456789class Trie{ Trie *next[26]; bool isEnd; Trie(){ for(int i = 0; i< 26; i++) next[i] = nullptr; isEnd = false; }}; Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162class Trie{public: Trie* next[26]; bool isEnd; Trie(){ for(int i = ...

CS5234 --Algorithm at Scale Lec1 mainly talked about two toy problem solving by sampling. Array all 0's ? Given the algorithm, 1234Repeat s times: Choose random i in [1,n] if A[i] = 1 then return Falsereturn True We’d like to guarantee the following statement: if all 0’s : return true if $\ge \epsilon n$ 1’s : return false (We can promise that >= 2/3 probability to return false and we can adjust the probability by adjusting the sampling times) otherwise: return true or false Proof: if t ...

481. Magical String Description Solution Use a pointer to record current occurrence of next segment of s. The new added segment’s consecutive number should be different from back of s. Code 1234567891011121314151617181920class Solution: def magicalString(self, n: int) -> int: if n <= 3: return 1 s = "122" freq,size,res = 2, 3, 1 #freq postion pointer while size < n: f = int(s[freq]) c = 1 if s[len(s)- ...

553. Optimal Division Description Solution To get the maxium value in the nums, we can fix the numerator and get minium denominator in the lefted numbers. So just let each number divided by later to generate a minium denominator. Code 1234567891011121314151617class Solution: def optimalDivision(self, nums: List[int]) -> str: res = "" if len(nums) == 1: res = str(nums[0]) return res elif len(nums) == 2: res = str(nums[0]) ...

992. Subarrays with K Different Integers Description Solution Quite tricky solution using two pointers, that we can fix the right pointer then move the left pointer to check the subarrays with less equals k elements. Then we can get subarray number by number of array with less equals k+1 elemens - number of array with less equals k+1 elemens. Code 1234567891011121314151617181920212223242526class Solution {public: int subarraysWithKDistinct(vector<int>& nums, int k) { ...

959. Regions Cut By Slashes Description Solution Two solutions both work: DFS, like find connected components in a island-sea question, but we need to deal with the slashes because we can not DFS a half-block. So we can zoom up the grid into 3 * 3 array then map the slash into it. Use union-find to union the plots and edges. First, each plot are in its own set, four edges are in one set We note that once slash connect two points from the same set, we can get 1 new region. Once points are ...

501. Find Mode in Binary Search Tree Description Solution Imagine how we find mode in an array [1 2 2 4 5 6 6 7], we just scan over then use some variables recording the most frequent number. In this BST, we can use inorder-traversal to get this sorted array. Code 1234567891011121314151617181920212223242526272829303132333435class Solution {public: int maxfreq, prev, curfreq; vector<int> res; vector<int> findMode(TreeNode* root) { dfs(root); retu ...

1012. Numbers With Repeated Digits Description Solution The most important tricky point, just find integers have no repeated digit!!! Then use DFS to solve the problem A naive way is to find the permutation -> TLE To speed up, we can directly compute permutation that has less digits than n‘s, then use DFS to compute the combination whose digit equals to n Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution {pub ...

552. Student Attendance Record II Description Solution A typical finite-state machine problem + dp. Just draw a state transfer graph. Code 1234567891011121314151617181920212223242526272829class Solution { static const int MOD = 1E9 + 7;public: int checkRecord(int n) { long long p1, p2, l11, l21, l12, l22, a; p1 = l11 = a = 1; p2 = l12 = l21 = l22 = 0; for(int i = 1; i <n; i++){ long long np1, np2, nl11, nl21, nl12, nl22, na; ...

282. Expression Add Operators Description Solution Use tricky DFS to solve it. The most important trick: Because we need to give each expression that leads to the target, so we need to record current string. Then, for+ and -, in fact we just need to record the exep value in previous expression. But to treat * rightly, we need record one more variable – lastValue to calculate the expression rightly. So if we have, for example 1 2 3 4 5 6 7 8 11 + 2 * 3 DFS(45678) ​ ↑ To treat ...

526. Beautiful Arrangement Description Solution Naively do backtracking DP + State Compression use mask to record first num ‘s integer’s combinations, for example 0101 means 1 and 3 are in the first 2 slots of the array. 1dp[mask] = sum of dp[mask^i], which i is suitable for popcount(mask) slot Code 12345678910111213141516171819202122232425262728class Solution {public: int countArrangement(int n) { vector<unordered_set<int>> suitable(n+1); for(int ...

388. Longest Absolute File Path Description Solution Recollection the use of stringstream: http://www.cplusplus.com/reference/sstream/stringstream/ Code 123456789101112131415161718192021222324252627282930313233343536373839class Solution {public: int lengthLongestPath(string input) { stringstream ss(input); string token; vector<string> paths; int res = 0; while(getline(ss, token, '\n')){ int layer = 0; ...