leetcode_OJ WC106 解題心得
- 題意：依照奇數偶數排序陣列
- 想法：水題直接做即可
- 分析：Time complexity O(N), Space complexity O(1)
class Solution
{
public:
vector<int> sortArrayByParityII(vector<int>& A)
{
int n = A.size();
int odd[n]={0};
int even[n]={0};
int optr = 0, eptr = 0;
for(int i = 0; i < n; i++)
{
if(A[i] & 1)
{
odd[optr++] = A[i];
}
else
{
even[eptr++] = A[i];
}
}
optr = 0, eptr = 0;
for(int i = 0; i < n; i++)
{
if(i & 1)
{
A[i] = odd[optr++];
}
else
{
A[i] = even[eptr++];
}
}
return A;
}
};
- 題意：給左右括號字串，問至少要加上幾個左右括號才能使括號配對成功，例如
((( 欠缺三個、()))(( 欠缺四個（左二右二）
- 想法：遇到左括號表示欠配對，將to_match 變數加起來，遇到又括號再將其遞減，倘若to_match又太多了代表右括號過多，再用第二個變數lack表示
- 分析：Time complexity O(N), Space complexity O(1)
class Solution
{
public:
int minAddToMakeValid(string S)
{
int n = S.size(), lack = 0, to_match = 0;
for (int i = 0; i < n; i++)
{
if (S[i] == '(')
{
to_match++;
}
else if (S[i] == ')')
{
if (to_match >= 1)
{
to_match--;
}
else
{
lack++;
}
}
}
return to_match + lack;
}
};
- 題意：給一個數字於陣列中，取三個不重複的數字a b c但是a b c數值不一定要相異，再給定一目標target，問 a + b + c = target 之組合情形
- 想法：本以為這題有點像背包問題，但沒有那麼難，較近似數學組合問題
- 首先用map將各個數字的數量存起來
- 由於數字最多到101，因此可以利用 101 * 101暴力搜尋（不用到第三個回圈，只要看map中是否存在即可，亦即
if(my[thr] == 0 || my[it2] == 0) //unable to use
{
continue;
}
- 為了防止重複，我們會希望數字是遞增的（但不必嚴格增，否則 2 + 2 + 3 = 7 這種就找不到了），亦即
if(!(fir <= sec && sec <= thr)) //maLLain the order to prevent duplicated
{
continue;
}
- 在查看各種方法的組合數： C(a,1) * C(b,1) * C(c,1) or C(a,2) * C(b,1) or C(a,3)
- 分析：Time complexity O(101^2), Space complexity O(1)
#define LL long long
const int MOD = 1e9 + 7;
class Solution
{
public:
int threeSumMulti(vector<int>& A, int target)
{
unordered_map<LL, LL>my;
LL n = A.size();
LL res = 0;
for(LL i = 0; i < n; i++)
{
my[A[i]]++;
}
for(LL it1 = 0; it1 < 101; ++it1)
{
if(my[it1] == 0)
{
continue;
}
for(LL it2 = it1; it2 < 101; ++it2)
{
LL fir = it1;
LL sec = it2;
LL thr = target - fir - sec;
if(my[thr] == 0 || my[it2] == 0) //unable to use
{
continue;
}
if(!(fir <= sec && sec <= thr)) //maLLain the order to prevent duplicated
{
continue;
}
if((fir == sec) && (fir == thr))
{
res +=cnr(my[fir], 3) % MOD;
}
else if((fir == sec) && (fir != thr)) //2 and 1
{
res +=( cnr(my[fir], 2) % MOD ) * ( cnr(my[thr], 1) % MOD );
}
else if((fir == thr) && (fir != sec)) //2 and 1
{
res +=( cnr(my[fir], 2) % MOD ) * ( cnr(my[sec], 1) % MOD );
}
else if((thr == sec) && (fir != thr)) //2 and 1
{
res +=( cnr(my[sec], 2) % MOD ) * ( cnr(my[fir], 1) % MOD );
}
else //all different
{
res +=( cnr(my[fir], 1) % MOD ) * ( cnr(my[sec], 1) % MOD ) * ( cnr(my[thr], 1) % MOD );
}
res %= MOD;
}
}
return (int)(res % MOD); //test
}
LL cnr( LL n, LL k )
{
if (k > n) return 0;
if (k * 2 > n) k = n-k;
if (k == 0) return 1;
LL result = n;
for( LL i = 2; i <= k; ++i ) {
result *= (n-i+1);
result /= i;
}
return result;
}
};
- 題意：給圖中的數個點，問哪一個點出發開始做DFS可以連通最多點
- 思路：每一個點都DFS一次，比較出能聯通最多點的起點，並且找出ID最小的（從後面找回來即可）
- 分析：Time complexity O(N^2), Space complexity O(N)
class Solution {
public:
int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial)
{
//check which node be removed will remove the most connection
int n = initial.size(), m = graph.size();
sort(initial.begin(), initial.end());
vector<int> color_cnt(m,0); //do not use n, otherwise runtime error will occurred such as [0,9] will out of the array bound with length 2
//count how much nodes can be traversed from the starting point
for(int i = 0; i < n; ++i)
{
int each_cnt = 0;
vector<bool> traversed(m, false);
DFS(graph, initial[i], traversed, each_cnt);
color_cnt[initial[i]] = each_cnt;
}
int res = INT_MAX, max_color = 0;
for(int i = n - 1; i >= 0; --i)
{
if(color_cnt[initial[i]] >= max_color)
{
res = initial[i];
max_color = color_cnt[initial[i]];
}
}
return res;
}
void DFS(vector<vector<int>>& graph, int cur_node, vector<bool>& traversed, int& each_cnt)
{
if(traversed[cur_node]) //traversed node, return
{
return;
}
traversed[cur_node] = true;
each_cnt++;
for(int i = 1; i < graph[cur_node].size(); ++i)
{
if(graph[cur_node][i]) //traversable and not traversed, travese it
{
DFS(graph, i, traversed, each_cnt);
}
}
return; //end traverse of current node
}
};