Sign in

If we use brute force directly, get TLE.

we use 1d dp table, dp[i] means enter number from first day to i day we needed.

So how can we go to get to next room

two case:

First if nums[i] == i, that means we only need two days can…


This is my first time try to use English write article.

If has any question, please contact with me. Thanks.

This problem is hard to find the solution, how to solve it,

First, we do sort with first element, and if the first element are same, we need to decide…


這題真的是慚愧阿, 看到李哥說跟300題幾乎一模一樣, 認真看完之後還真的是

差別差在要如何知道夾在中間的數字是第幾個

舉一個例子

[1,2,3,2]依照300題的方法
會排成
[1,2,3]
但倘若我們遇到第四個2,要把3給換掉(這兩題的小差別)
會變成
[1,2,2]
而這個2的所在index + 1就是我們要結算進的值(這邊為3)

所以code可以寫成

class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
vector<int> arr, res;
for(auto o: obstacles){
if(arr.empty() ||o >= arr.back()){
arr.push_back(o);
res.push_back(arr.size());
}else{
auto it = upper_bound(arr.begin(), arr.end(), o);
*it = o;
int idx = it - arr.begin() + 1;
res.push_back(idx);
}
}
return res;

}
};

時間複雜度為O(nlogn)


周賽復盤

這題有點難, 雖然我不知道寫周賽的當下要怎麼想到

首先我們看到

]]][[[

我們可以去想, 倘若為[就+1, ]就-1, 所以可以把上面這段改成

[-1, -2, -3, -2, -1, 0]

所以可以看到最差最差為-3, 而可以發現假設要達成balance的string

必須整個數列的數字必須都是正整數或零

所以假設我們移動最左邊的],以及最右邊的[

可以看到

[ ]][[ ]
[1,0,-1, 0,1, 0]

剛剛原本最差的-3, 瞬間被加2了

所以我們可以得知, 最少要Swap的次數為最差的值除以2, 取floor, 就可以在最小限度內讓字串變得balance

時間複雜度為O(n), 但我個人覺得當下真的很難想到

真不知道周賽當下可以寫過的人怎麼想的

class Solution {
public:
int minSwaps(string s) {
int min_neg = 0;
int sum = 0;
for(auto c:s){
if(c == '['){
sum++;
}else{
sum--;
}
min_neg = min(sum, min_neg);
}
if(min_neg == 0) return 0;
return ceil(-(min_neg / 2.0));
}
};

大意了, 把他想的太複雜了

我們要注意到這必須是連續的mutating, 所以假設前面改完中間沒改後, 就要直接break了, 即便你在後面發現有可以更換的數字

所以我們先設一個flag, 倘若字串中的數字在更改後可以變更大, 我們就更換並且把flag設成true, 說明已經被改過了, 如果看到不需要改變的, 即可跳出, 因為在後面即使發現可以更改的也不再連續

時間複雜度為O(N), 空間複雜度為O(1)

class Solution {
public:
string maximumNumber(string num, vector<int>& change) {
bool flag = false;
for(int i = 0; i < num.size();i++){
int before = num[i] - '0';
int after = change[before];
if(before < after){
flag = true;
num[i] = after + '0';
}else if(before == after){
continue;
}else{
if(flag){
break;
}
continue;
}
}
return num;
}
};

自從慘敗後好久沒有在回歸了, 我想是時候再回來一步一步走了

雖然真的很不甘心,也覺得運氣很不好,但是也只能吞下去了

首先回歸後周賽第一題就苦手, 主要是要做string的大數轉換

我們先將字母換成數字, 然後根據K的次數, 每一次就是做一次convert

class Solution {
public:
int getLucky(string s, int k) {
int sum = 0, sum1 = 0;
for(auto ch: s){
int n = ch - 'a' + 1;
sum += n / 10 + n % 10;
}
k--;
while(k > 0 && sum > 9){
for(; sum;sum/=10){
sum1 += sum % 10;
}
k--;
sum = sum1;
sum1 = 0;
}
return sum;

}
};

當下再寫的時候非常卡, 感覺這種字串的轉換又變得很陌生了, 得找一下手感


這題有關於用dp O(n²)的方法我一直看不太明白

反倒是proirity_queue的方式還比較好懂

題目的意思是, 有一台車要到目的地, 途中會經過幾間加油站, 我們如何用最少的加油次數就能到加油站

我們就從0次開始看, 假設不加油, 我最遠可以到哪邊, 然後途中經過的加油站我們都把他加到proirity_queue, 等這一run結束後, 假設已經到終點了我們就退出迴圈, 還沒到的話, 我們就從途中經過的加油站, 找一間可以加最多油的幫忙加到現在的油箱, 倘若已經都找完, 表示還沒到加油站前或目的地前,已經沒油了

每次從push加油站進pq裡的時間複雜度為O(nlogn).

class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
int i = 0;
int res = 0;
priority_queue<int> pq;
int cur = startFuel;
for(res = 0; cur < target;res++){
while(i < stations.size() && stations[i][0] <= cur){
pq.push(stations[i][1]);
i++;
}
if(pq.empty()) return -1;
cur += pq.top();
pq.pop();
}
return res;
}
};

一開始想不到更快地解, 提示說可以用暴力法時間為O(n²)

class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
vector<vector<string>> res;
sort(products.begin(), products.end());
for(int i = 1; i <= searchWord.size();i++){
vector<string> cur_s;
string s = searchWord.substr(0, i);
for(auto p: products){
string compare = p.substr(0, i);
if(cur_s.size() >= 3) break;
if(s == compare){
cur_s.push_back(p);
}
}
res.push_back(cur_s);
}
return res;
}
};

在看完李哥的解答後, 頭一次知道lower_bound可以這樣用, 只要符合這個字串的前幾個位元都對的話, 就可以鎖定lower_bound

然後接下來因為增加字母, 自然是會一直縮小範圍, 這個方法真的猛

時間複雜度為O(nlogn)

class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
vector<vector<string>>res;
string cur = "";
auto it = products.begin();
for(char c: searchWord){
cur+=c;
vector<string> suggested;
it = lower_bound(it, products.end(), cur);
for(int i = 0; i < 3 && it + i != products.end();i++){
string &s = *(it + i);
if(s.find(cur) == string::npos){
break;
}
suggested.push_back(s);
}
res.push_back(suggested);
}
return res;
}
};

第二題理論上比第一題還簡單,

只要算存在的個數就好了, 剩下的觀念跟第一題一模一樣

class Solution {
public:
bool isValid(vector<string> &board, int row, int col){
vector<vector<int>> dirs{{-1, -1}, {-1, 0}, {-1, 1}};
for(auto dir: dirs){
for(int i = row, j = col; i>= 0&& j >=0 && j < board.size();i+=dir[0], j += dir[1]){
if(board[i][j] == 'Q'){
return false;
}
}
}
return true;
}
void backtrace(vector<string> &board, int row, int &res){
if(row == board.size()){
res++;
return;
}
for(int col = 0; col < board.size(); col++){
if(!isValid(board, row, col)){
continue;
}
board[row][col] = 'Q';
backtrace(board, row + 1, res);
board[row][col] = '.';
}
}
int totalNQueens(int n) {
vector<string> board(n, string(n, '.'));
int res = 0;
backtrace(board, 0, res);
return res;
}
};

用sliding windows, 在用hash_table, 紀錄走過的index, 然後只要遇到重複的我們就滑動窗口,

class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
unordered_map<int, int> m;
int left = 0;
int res = 0;
int sum = 0;
for(int i = 0;i < nums.size();i++){
sum += nums[i];
if(m.count(nums[i]) && left <= m[nums[i]]){
for(int j = left; j < m[nums[i]] + 1;j++){
sum -=nums[j];
}
left = m[nums[i]] + 1;
}
m[nums[i]] = i;
res = max(sum, res);
}
return res;

}
};

ss

隨手筆記

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store