274 - H-Index

解法

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

解法

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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]);
// }
// }

189. Rotate Array

解法

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

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
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

解法

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

多數投票算法:

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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(設計解題)

解法

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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(設計解題)

解法

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

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

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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

解法

merge sort 的 “merge” step 實作。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

解法

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

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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;
}
};
  • © 2020-2024 John Doe
  • Powered by Hexo Theme Ayer
  • PV: UV: