Problems
LeetCode : 372. Super Pow
[快速冪取模]
LeetCode : 843. Guess the Word
[game theory]
LeetCode : 2348. Number of Zero-Filled Subarrays
[math][array]
LeetCode : 2240. Number of Ways to Buy Pens and Pencils
[math]
LeetCode : 1954. Minimum Garden Perimeter to Collect Enough Apples
[math]
LeetCode : 2033. Minimum Operations to Make a Uni-Value Grid
[math][array]
LeetCode : 1276. Number of Burgers with No Waste of Ingredients
[math]
LeetCode : 2165. Smallest Value of the Rearranged Number
[math][sorting]
LeetCode : 2249. Count Lattice Points Inside a Circle
[math]
LeetCode : 2244. Minimum Rounds to Complete All Tasks
[math]
LeetCode : 963. Minimum Area Rectangle II
[math][geometry]
LeetCode : 447. Number of Boomerangs
[math][hash table]
LeetCode : 1033. Moving Stones Until Consecutive
[Math][Brainteaser]
LeetCode : 1513. Number of Substrings With Only 1s
[Math][String]
LeetCode : 2396. Strictly Palindromic Number
[Math]
LeetCode : 360. Sort Transformed Array
[Math]
LeetCode : 2413. Smallest Even Multiple
[Math]
LeetCode : 1785. Minimum Elements to Add to Form a Given Sum
[Math][Greedy][Array]
LeetCode : 1390. Four Divisors
[Math][Array]
LeetCode : 2446. Determine if Two Events Have Conflict
[Array][Math][String][Overlap Detection]
LeetCode : 2119. A Number After a Double Reversal
[Math]
LeetCode : 2481. Minimum Cuts to Divide a Circle
[Math]
LeetCode : 2495. Number of Subarrays Having Even Product
[Math][Array]
LeetCode : 899. Orderly Queue
[Math][Sort][String][Hard]
—
LeetCode 587. Erect the Fence
[geometry][convex hull]
LeetCode : 973. K Closest Points to Origin
LeetCode : 149. Max Points on a Line
LeetCode : 939. Minimum Area Rectangle
LeetCode : 1610. Maximum Number of Visible Points
LeetCode : 29. Divide Two Integers
LeetCode : 372. Super Pow
TODO :
效能太差，參考下其他人是怎麼做的
#define LL long long
#define MOD 1337class Solution {
private:
int firstNonZero = 0;
public:
bool divide2(vector<int> &b) {
bool res = false; for(int i = firstNonZero;i < b.size();i++) {
if(b[i] % 2 == 1) {
if(i == b.size() - 1) {
} else {
b[i + 1] += 10;
}
}
b[i] /= 2;
}
while(firstNonZero < b.size() && b[firstNonZero] == 0) {
firstNonZero += 1;
}
if(firstNonZero >= b.size()) {
return false;
}
return true;
}
int superPow(int a, vector<int>& b) {
if(a == 1) {
return 1;
}
LL base = a % MOD;
LL res = 1;
int firstNonZero = 0;
do {
if(b.back() & 1) {
res = res * base % MOD;
}
base = (base * base) % MOD;
} while(divide2(b));
return res;
}
};
LeetCode : 843. Guess the Word
雖然這一題評分不高，但這題蠻有趣的。可以看到同樣的複雜度下，如何用更少的次數來達到相同的效果。
這題蠻特別的，不求每次 submit 都 pass ，但需要很大機率能 pass。
推薦閱讀這一篇。
class Solution {
public:
int countScore(string &a, string &b) {
int score = 0;
for(int i = 0;i < a.size();i++) {
if(a[i] == b[i]) {
score++;
}
}
return score;
}
void findSecretWord(vector<string>& wordlist, Master& master) {
srand(time(NULL));
int guess = rand() % wordlist.size();
while(1) {
vector<string> candidate;
guess = rand() % wordlist.size();
string guessSt = wordlist[guess];
int res = master.guess(guessSt); if(6 == res) {
break;
} // 每一次的猜測都需要減少 candidate
for(int j = 0;j < wordlist.size();j++) {
if(countScore(guessSt, wordlist[j]) == res) {
candidate.push_back(wordlist[j]);
}
}
wordlist = candidate;
}
}
};
LeetCode : 2348. Number of Zero-Filled Subarrays
#define LL long long
class Solution {
public:
long long zeroFilledSubarray(vector<int>& nums) {
LL ans = 0;
LL n = 0;
for(int i = 0;i < nums.size();i++) {
if(0 == nums[i]) {
n++;
} else {
if(n > 0) {
ans += (1 + n) * n / 2;
}
n = 0;
}
}
if(n > 0) {
ans += (1 + n) * n / 2;
}
return ans;
}
};LeetCode : 2240. Number of Ways to Buy Pens and Pencils
#define LL long long
class Solution {
public:
long long waysToBuyPensPencils(int total, int cost1, int cost2) {
LL ans = 0;
int num = total / cost1;
for(int i = 0;i <= num;i++) {
int sum1 = i * cost1;
ans += (((total - sum1) / cost2) + 1);
}
return ans;
}
};LeetCode : 1954. Minimum Garden Perimeter to Collect Enough Apples
TODO : 效能太差，需要改進一下。
#define LL long long
class Solution {
public:
long long minimumPerimeter(long long neededApples) {
long long nowv = 0;
for(int i = 1;i <= 1000000;i++) {
if(1 == i) {
nowv += 12;
} else {
LL rr = i * 2;
LL rl = i;
LL ll = i * 2 - 1;
LL lr = i + 1;
LL t, t1, t2;
t1 = (rr + rl) * (rr - rl + 1) / 2;
t2 = (ll + lr) * (ll - lr + 1) / 2;
t = t1 + t2;
t *= 4;
nowv += t;
}
if(nowv >= neededApples) {
return (i * 2) * 4;
}
}
return -1;
}
};LeetCode : 2033. Minimum Operations to Make a Uni-Value Grid
// 矇對了...看一下其他人的解說
class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
// x 必為所有差的因數
vector<int> v;
for(int i = 0;i < grid.size();i++) {
for(int j = 0;j < grid[0].size();j++) {
v.push_back(grid[i][j]);
}
}
sort(v.begin(), v.end());
for(int i = 1;i < v.size();i++) {
if(v[i] == v[i - 1]) {
continue;
}
if((v[i] - v[i - 1]) < x) {
return -1;
}
if(0 != ((v[i] - v[i - 1]) % x)) {
return -1;
}
}
// 將所有點挪到中間的點
int index = v.size() / 2;
int ans = 0;
for(int i = 0;i < v.size();i++) {
if(v[i] == v[index]) {
continue;
}
ans += abs(v[index] - v[i]) / x;
}
return ans;
}
};LeetCode : 1276. Number of Burgers with No Waste of Ingredients
class Solution {
public:
vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
if(0 == tomatoSlices &&
0 == cheeseSlices) {
return {0, 0};
}
// x + y = cheeseSlices
// 4 * x + 2 * y = tomatoSlices
if(0 != tomatoSlices % 2) {
return {};
}
int to = tomatoSlices;
int ch = cheeseSlices;
to /= 2;
int x = 0;
int y = 0;
x = to - ch;
y = to - 2 * x;
if(x >= 0 && y >= 0) {
return {x, y};
}
return {};
}
};LeetCode : 2165. Smallest Value of the Rearranged Number
#define LL long long
class Solution {
public:
long long smallestNumber(long long num) {
string tmpst;
LL tmpv; // tmp value
if(num > 0) {
tmpv = num;
} else {
tmpv = -1 * num;
}
while(tmpv > 0) {
tmpst += to_string(tmpv % 10);
tmpv /= 10;
}
if(num > 0) {
sort(tmpst.begin(), tmpst.end());
if('0' == tmpst[0]) {
int index = 0;
for(;index < tmpst.size();index++) {
if('0' != tmpst[index]) {
break;
}
}
tmpst[0] = tmpst[index];
tmpst[index] = '0';
}
} else {
sort(tmpst.begin(), tmpst.end(), greater<char>());
}
LL ans = 0;
for(int i = 0;i < tmpst.size();i++) {
ans *= 10;
ans += tmpst[i] - '0';
}
if(num < 0) {
ans *= -1;
}
return ans;
}
};LeetCode : 2249. Count Lattice Points Inside a Circle
// TODO : 感覺還能更快
class Solution {
public:
int countLatticePoints(vector<vector<int>>& circles) {
vector<vector<bool>> grid = vector<vector<bool>>(201, vector<bool>(201, false));
int ans = 0;
for(int i = 0;i < circles.size();i++) {
int startx = circles[i][0] - circles[i][2];
int starty = circles[i][1] - circles[i][2];
int limit = circles[i][2] * circles[i][2];
int len_2 = circles[i][2] * 2;
for(int j = 0;j <= len_2;j++) {
for(int q = 0;q <= len_2;q++) {
int newx = startx + j;
int newy = starty + q;
int xv = abs(newx - circles[i][0]);
int xy = abs(newy - circles[i][1]);
xv *= xv;
xy *= xy;
if(xv + xy <= limit) {
grid[newx][newy] = true;
}
}
}
}
for(int i = 0;i < grid.size();i++) {
for(int j = 0;j < grid[0].size();j++) {
if(grid[i][j]) {
ans++;
}
}
}
return ans;
}
};LeetCode : 2244. Minimum Rounds to Complete All Tasks
// TODO : 時間，空間效能太差
// 2x + 3y = a : 只要是 a > 1 的數，都能夠有整數解
// 假如 a 是基數，只要減去 3 就會是偶數，這時候就能用 2 去湊
// 假如 a 是偶數，可以直接拿 2 去湊
// 想要取得 x + y 為最小值，可以先拿 3 去無腦湊，湊不齊就減少 3 的個數class Solution {
public:
int getMin(int v) {
int res = 0;
if(1 == v) {
return 0;
} else if(2 == v) {
return 1;
}
int tmp = v / 3;
int tmpv = tmp * 3;
while(1 == (v - tmpv) || ((v - tmpv) % 2 != 0)) {
tmp--;
tmpv = tmp * 3;
}
return tmp + (v - tmpv) / 2;
}
int minimumRounds(vector<int>& tasks) {
unordered_map<int, int> v2i;
vector<int> vs;
int nowi = 0;
for(int i = 0;i < tasks.size();i++) {
if(v2i.find(tasks[i]) == v2i.end()) {
v2i[tasks[i]] = nowi;
nowi++;
vs.push_back(0);
}
vs[v2i[tasks[i]]]++;
}
int ans = 0;
for(int i = 0;i < vs.size();i++) {
int tmp = getMin(vs[i]);
if(0 == tmp) {
return -1;
}
ans += tmp;
}
return ans;
}
};
LeetCode : 963. Minimum Area Rectangle II
// TODO : 太慢class Solution {
public:
bool isRightAngle(double long_side, double s1, double s2) {
long_side *= long_side;
s1 *= s1;
s2 *= s2;
if(abs(long_side - (s1 + s2)) < 0.00001) {
return true;
}
return false;
}
double getLen(vector<int> &p1, vector<int> &p2) {
double e1 = abs(p1[0] - p2[0]);
double e2 = abs(p1[1] - p2[1]);
double res = 0;
e1 *= e1;
e2 *= e2;
res += e1;
res += e2;
res = sqrt(res);
return res;
}
double minAreaFreeRect(vector<vector<int>>& points) {
double ans = INT_MAX;
for(int i = 0;i < points.size() - 3;i++) {
for(int j = i + 1;j < points.size() - 2;j++) {
for(int q = j + 1;q < points.size() - 1;q++) {
vector<int> &pa = points[i];
vector<int> &pb = points[j];
vector<int> &pc = points[q];
double len_a_b = getLen(pa, pb);
double len_b_c = getLen(pb, pc);
double len_a_c = getLen(pa, pc);
vector<double> lens;
lens.push_back(len_a_b);
lens.push_back(len_b_c);
lens.push_back(len_a_c);
sort(lens.begin(), lens.end());
if(!isRightAngle(lens[2], lens[1], lens[0])) {
continue;
}
for(int k = q + 1;k < points.size();k++) {
vector<int> &pd = points[k];
double len_a_d = getLen(pa, pd);
double len_b_d = getLen(pb, pd);
double len_c_d = getLen(pc, pd);
vector<double> lens2;
lens2.push_back(len_a_b);
lens2.push_back(len_b_d);
lens2.push_back(len_a_d);
sort(lens2.begin(), lens2.end());
if(!isRightAngle(lens2[2], lens2[1], lens2[0])) {
continue;
}
lens2[0] = len_a_c;
lens2[1] = len_a_d;
lens2[2] = len_c_d;
sort(lens2.begin(), lens2.end());
if(!isRightAngle(lens2[2], lens2[1], lens2[0])) {
continue;
}
lens2[0] = len_b_c;
lens2[1] = len_b_d;
lens2[2] = len_c_d;
sort(lens2.begin(), lens2.end());
if(!isRightAngle(lens2[2], lens2[1], lens2[0])) {
continue;
}
/*printf("pa : %d, %d\n", pa[0], pa[1]);
printf("pb : %d, %d\n", pb[0], pb[1]);
printf("pc : %d, %d\n", pc[0], pc[1]);
printf("pd : %d, %d\n", pd[0], pd[1]);
printf("a : %lf\n", lens[1] * lens[0]);*/
ans = min(ans, lens[1] * lens[0]);
}
}
}
}
return ans == INT_MAX ? 0 : ans;
}
};
LeetCode : 447. Number of Boomerangs
// TODO : 實在是很慢
#define LL long long
class Solution {
public:
int numberOfBoomerangs(vector<vector<int>>& points) {
// vector & unordered_map<distance, num of points>
vector<unordered_map<LL, int>> vum = vector<unordered_map<LL, int>>(points.size());
// node 2 distance
vector<vector<LL>> n2d = vector<vector<LL>>(points.size());
for(int i = 0;i < points.size();i++) {
for(int j = i + 1;j < points.size();j++) {
LL dis1 = abs(points[i][0] - points[j][0]);
LL dis2 = abs(points[i][1] - points[j][1]);
LL dis = dis1 * dis1 + dis2 * dis2;
if(0 == vum[i][dis]) {
n2d[i].push_back(dis);
}
vum[i][dis]++;
if(0 == vum[j][dis]) {
n2d[j].push_back(dis);
}
vum[j][dis]++;
}
}
int ans = 0;
for(int i = 0;i < n2d.size();i++) {
for(int j = 0;j < n2d[i].size();j++) {
LL dis = n2d[i][j];
int num = vum[i][dis];
if(num >= 2) {
ans += (num * (num - 1));
}
}
}
return ans;
}
};LeetCode : 1033. Moving Stones Until Consecutive
// TODO ： 寫法有點醜，可以再整理一下
class Solution {
public:
vector<int> numMovesStones(int a, int b, int c) {
vector<int> ans = vector<int>(2);
vector<int> tmp = {a, b, c};
sort(tmp.begin(), tmp.end());
ans[1] = tmp[2] - tmp[1] - 1 + tmp[1] - tmp[0] - 1;
int minVal = min(tmp[2] - tmp[1], tmp[1] - tmp[0]);
if(1 != minVal) {
if(2 == minVal) {
ans[0] = 1;
} else {
ans[0] = 2;
}
} else {
if(tmp[2] - tmp[1] == tmp[1] - tmp[0]) {
// 三個數字相鄰
ans[0] = 0;
} else {
ans[0] = 1;
}
}
return ans;
}
};LeetCode : 1513. Number of Substrings With Only 1s
#define LL long long
class Solution {
public:
int numSub(string s) {
LL ans = 0;
LL tmp = 0;
for(int i = 0;i < s.size();i++) {
if('1' == s[i]) {
tmp++;
} else {
if(tmp > 0) {
ans += ((1 + tmp) * tmp) / 2;
ans %= 1000000007;
}
tmp = 0;
}
}
if(tmp > 0) {
ans += ((1 + tmp) * tmp) / 2;
ans %= 1000000007;
}
return ans;
}
};LeetCode : 2396. Strictly Palindromic Number
class Solution {
public:
bool isStrictlyPalindromic(int n) {
for(int i = 2;i <= n-2;i++) {
string tmps;
int tmpn = n;
while(tmpn > 0) {
tmps += to_string(tmpn % i);
tmpn /= i;
}
int left = 0;
int right = tmps.size() - 1;
while(left <= right) {
if(tmps[left] != tmps[right]) {
return false;
}
left++;
right--;
}
}
return true;
}
};LeetCode : 360. Sort Transformed Array
// TODO : follow up
class Solution {
public:
vector<int> sortTransformedArray(vector<int>& nums, int a, int b, int c) {
vector<int> ans;
for(int i = 0;i < nums.size();i++) {
int n = nums[i];
ans.push_back(n * n * a + n * b + c);
}
sort(ans.begin(), ans.end());
return ans;
}
};LeetCode : 2413. Smallest Even Multiple
class Solution {
public:
int smallestEvenMultiple(int n) {
return n % 2 == 0 ? n : n * 2;
}
};LeetCode : 1785. Minimum Elements to Add to Form a Given Sum
#define LL long long
class Solution {
public:
int minElements(vector<int>& nums, int limit, int goal) {
LL sum = 0;
for(int i = 0;i < nums.size();i++) {
sum += nums[i];
}
LL dis = abs(sum - goal);
return dis % limit == 0 ? dis / limit : dis / limit + 1;
}
};LeetCode : 1390. Four Divisors
// TODO : 效能太差
class Solution {
public:
int sumFourDivisors(vector<int>& nums) {
int ans = 0;
for(int i = 0;i < nums.size();i++) {
int sq = sqrt(nums[i]);
int n = 0;
int tmpans = 0;
for(int j = 1;j <= sq;j++) {
if(nums[i] % j == 0) {
if(nums[i] / j == j) {
n++;
tmpans += j;
} else {
n += 2;
tmpans += j;
tmpans += nums[i] / j;
}
}
}
if(n == 4) {
ans += tmpans;
}
}
return ans;
}
};LeetCode : 2446. Determine if Two Events Have Conflict
// overlap detection
class Solution {
public:
bool haveConflict(vector<string>& event1, vector<string>& event2) {
int min1S = 0;
int min1E = 0;
int min2S = 0;
int min2E = 0;
string tmp;
tmp = event1[0].substr(0, 2);
min1S = atoi(event1[0].substr(0, 2).c_str()) * 60 +
atoi(event1[0].substr(3, 2).c_str());
min1E = atoi(event1[1].substr(0, 2).c_str()) * 60 +
atoi(event1[1].substr(3, 2).c_str());
min2S = atoi(event2[0].substr(0, 2).c_str()) * 60 +
atoi(event2[0].substr(3, 2).c_str());
min2E = atoi(event2[1].substr(0, 2).c_str()) * 60 +
atoi(event2[1].substr(3, 2).c_str());
return min1E >= min2S && min1S <= min2E;
}
};LeetCode : 2119. A Number After a Double Reversal
class Solution {
public:
bool isSameAfterReversals(int num) {
if (num == 0) {
return true;
}
return num % 10 == 0 ? false : true;
}
};LeetCode : 2481. Minimum Cuts to Divide a Circle
class Solution {
public:
int numberOfCuts(int n) {
if (n == 1) {
return 0;
}
if(n % 2 == 1) {
return n;
}
return n / 2;
}
};LeetCode : 2495. Number of Subarrays Having Even Product
#define LL long long
/*
只要陣列內有任何偶數的數字，就符合
*/
class Solution {
public:
long long evenProduct(vector<int>& nums) {
// 紀錄最近的偶數的 index
// 該 index + 1 就是該元素可組成的 subarray 數量
LL nowi = -1;
LL ans = 0;
for(int i = 0;i < nums.size();i++) {
if(nums[i] % 2 == 0) {
nowi = i;
}
ans += nowi + 1;
}
return ans;
}
};LeetCode : 899. Orderly Queue
/*
很怪的題目，只要 k == 1 就暴力解
k >= 2，表示前後兩個元素可以交換，能交換就能直接 sort，所以直接回傳 sort 之後的結果就好。
*/
class Solution {
public:
string orderlyQueue(string s, int k) {
string ans;
if(k == 1) {
ans = s;
for(int i = 0;i < s.size();i++) {
char tmp = s[0];
for(int j = 0;j < s.size() - 1;j++) {
s[j] = s[j + 1];
}
s[s.size() - 1] = tmp;
ans = min(ans, s);
}
} else {
ans = s;
sort(ans.begin(), ans.end());
}
return ans;
}
};
