大衞的筆記

274 - H-Index

2024-03-02

解法

先用 cnt[i] 被 cite 過 i 次的文章總共有幾個，再用再由後向前更新。
就可以知道 >= i 的 paper 有多少，再來判斷。

程式碼

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int cnt[1020];
        for(int i = 0; i < 1020; i++) cnt[i] = 0;

        for(int i  = 0; i < citations.size(); i++){
            cnt[citations[i]]++;
        }

        for(int i = 1000; i >= 1; i--){
            cnt[i-1] += cnt[i];
            if(cnt[i] >= i) return i;
        }
        return 0;
    }
};

122 - Best Time to Buy and Sell Stock II

2024-02-18

Leetcode

解法

由於他是可以一直買賣，因此只要與前一天有賺就收集下來，全部累積下來就是答案。

程式碼

using namespace std;
int ans[30020];
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        ans[0] = 0;
        for(int i = 1; i < prices.size(); i++){
            int cnt = prices[i] - prices[i-1];
            if(cnt < 0) cnt = 0;
            ans[i] = ans[i-1] + cnt;
        }

        for(int i = 0; i < prices.size(); i++){
            cout << "i ans[i]" << i << " " << ans[i] << "\n";
        }
        return ans[prices.size()-1];
    };
};

// for(int i = 0; i < prices.size(); i++){
//     for(int j = i+1; j < prices.size(); j++){
//         int cnt = prices[j] - prices[i];
//         if(cnt < 0) cnt = 0;
//         ans[j] = max(ans[i] + cnt, ans[j-1]);
//     }
// }

055 - Jump Game

2024-02-18

Leetcode

解法

只需要不斷維護，去更新出現在能跳的最大步數就好。

程式碼

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cnt = nums[0];
        for(int i = 1; i < nums.size(); i++){
            cnt--;
            if(cnt < 0){
                return false;
            }
            cnt = max(cnt, nums[i]);
        }
        return true;
    }
};

121. Best Time to Buy and Sell Stock

2024-02-05

Leetcode

解法

貪心法，紀錄先前最小值，在跟每天的價格比對就好。

程式碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int minn = 10020;

        for(int i = 0; i < prices.size(); i++){
            minn = min(prices[i], minn);
            ans = max(ans, prices[i] - minn);
        }
        return ans;
    }
};

189. Rotate Array

2024-02-04

Leetcode

解法

由於題目限定要 $O(1)$ 完成，我們可以先將數列全部反轉，12345678 變成 87654321，再來找出從哪個點在選轉後來到第一位假設選轉後 5 變第一位則變為 56784321，之後再將未反轉的進行反轉就好，變成 56781234。

核心想法是: 由於數字肯定有序，並且一定是從特定值開始依序，在回到 1234，故可使用字串反轉。

程式碼

using namespace std;

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k );
        reverse(nums.begin()+k, nums.end());
    }
};

169. Majority Element

2024-01-31

Leetcode

解法

使用多數投票算法來解決此問題。

多數投票算法:

前提: 數列中必定有一數值過半數
做法:
- 從第一個數值開始，設 vote = 1, ans = nums[0]
- 若下個數字與 ans 相同則 vote++
- 如不同則 vote--
- 當 vote == 0 則修改 ans, vote
想法: 因為必定有一值大於 n/2，所以在這一增一減情況下，最後一定會留下 n/2 的值

程式碼

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int vote = 1;
        int ans = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] != ans){
                vote--;
                if(vote == 0){
                    vote = 1;
                    ans = nums[i];
                }
            }else{
                vote++;
            }
        }
        return ans;
    }
};

Codeforces 1513D - GCD and MST(設計解題)

2024-01-29

Codeforces

解法

由於我們要使 GCD 最大，因此必須使 n 都要是 x 的倍數，所以只需要判斷 x 可以被哪個因數整除，在判斷是否有大於 n，若有，則可以用 x / 因數 方式來解決；反之概念相同。

程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 0x3f3f3f
using namespace std;
int t, x, n;

int process(){
    int ans = 0;
    for(int i = 1; i * i <= x; i++){
        if(x % i == 0){
            //cout << "hi " << i << "\n";
            if(i >= n) ans = max(ans, x/i);
            if(x/i >= n) ans = max(ans, i);
        }
    }
    return ans;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> x >> n;
        cout << process() << "\n";
    }

    return 0;
}

Codeforces 1513D - GCD and MST(設計解題)

2024-01-29

Codeforces

解法

使用 greedy 的方式最快判斷出 yes or no, 如果是 no 則是缺少哪個單字。

由於這題是排列組合子字串，n 個字母只能夠出現 k 個不同英文字母，因此，只需要判斷需要多少長度的字元，才可以包括 k 個不同字母，反覆 n 次測試，如成功則 yes、反之則 no。

如果是 no，則發現 no 之後的字母輸出沒有包括地英文字母就好，前面任意。

程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 0x3f3f3f
#define int long long int
using namespace std;
int t, n, k, m;
string str;
vector<int> pos[30];

void process(){
    for(int i = 0; i < 30; i++){
        pos[i].clear();
    }
    for(int i = 0; i < m; i++){
        int char_pos = (int)(str[i]-'a');
        pos[char_pos].push_back(i);
    }
    for(int i = 0; i < 30; i++){
        pos[i].push_back(m+10); //表示已經跑到字串最後一個
    }

    string ans = "";
    //high_pos: 在這次中特定字母出現的最遠位數
    //pre_high: 上次中特定字母出現最遠次數
    int high_pos = -1, high, pre_high = -1;
    char high_char;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < k; j++){
            //從上次最遠次數，尋找後面下一個更遠位數。
            high = *upper_bound(pos[j].begin(), pos[j].end(), pre_high);
            //cout << "j high high_pos " << j << " " << high_pos << "\n";
            if(high >= high_pos){
                high_char = (char) ('a' + j);
                high_pos = high;
            }
        }
        pre_high = high_pos;

        if(high_pos == m+10){ //是否已超出字串長度
            cout << "NO\n";
            for(;i < n; i++) ans += high_char;
            cout << ans << "\n";
            return;
        }
        ans += str[high_pos];

    }
    cout << "YES" << "\n";
    return;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> k >> m;
        cin >> str;
        process();
    }

    return 0;
}

088 - Merge Sorted Array

2024-01-23

Leetcode

解法

merge sort 的 “merge” step 實作。

程式碼

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index_m, index_n;
        index_m = index_n = 0;

        vector<int> ans;
        while(1){
           //檢查 nums2 是否還有值 || nums1 <= nums2
           if(index_n >= n || (index_m < m && nums1[index_m] <= nums2[index_n])){
               ans.push_back(nums1[index_m]);
               index_m++;
           } //vice versa
           else if(index_m >= m || (index_n < n && nums2[index_n] < nums1[index_m])){
               ans.push_back(nums2[index_n]);
               index_n++;
           }

           if(index_n >= n && index_m >= m) break;
        }

        nums1.clear();
        for(auto it: ans){
            nums1.push_back(it);
        }
    }

};

026 - Remove Duplicates from Sorted Array

2024-01-23

Leetcode

解法

使用雙迴圈檢查重複的資料們是否重複，有重複就更改成 int 最大值，最後再用 sort

程式碼

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int ans = nums.size();
        for(int i = 0; i < nums.size();){
            int j = i+1;
            //檢查後面有幾個相同元素，在修改
            while(j < nums.size() && nums[i] == nums[j]){
                if(nums[i] == nums[j]){
                    nums[j] = 0x3f3f3f;
                    ans--;
                }
                j++;
            }
            i = j;
        }
        int index = nums.size() - 1;
        for(int i = 0; i < nums.size(); i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(nums[i] > nums[j]) swap(nums[i], nums[j]);
            }
        }
        return ans;
    }
};