8000 n · hitzzc/go-leetcode@0ba6c17 · GitHub
[go: up one dir, main page]
Skip to content
< 8000 header class="Box-sc-g0xbh4-0 prc-PageLayout-Header-mQXK1" style="--spacing:var(--spacing-none)">

Commit 0ba6c17

Browse files
hitzzchitzzc
committed
n
1 parent 3a54877 commit 0ba6c17

File tree

8 files changed

+127
-0
lines changed

8 files changed

+127
-0
lines changed

‎README.md

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -266,6 +266,13 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
266266
#### [386. Lexicographical Numbers](https://github.com/hitzzc/go-leetcode/tree/master/lexicographical_numbers)
267267
#### [387. First Unique Character in a String](https://github.com/hitzzc/go-leetcode/tree/master/first_unique_character_in_a_string)
268268
#### [388. Longest Absolute File Path](https://github.com/hitzzc/go-leetcode/tree/master/longest_absolute_file_path)
269+
#### [389. Find the Difference](https://github.com/hitzzc/go-leetcode/tree/master/find_the_difference)
270+
#### [390. Elimination Game](https://github.com/hitzzc/go-leetcode/tree/master/elimination_game)
271+
#### [391. Is Subsequence](https://github.com/hitzzc/go-leetcode/tree/master/is_subsequence)
272+
#### [394. Decode String](https://github.com/hitzzc/go-leetcode/tree/master/decode_string)
273+
#### [395. Longest Substring with At Least K Repeating Characters](https://github.com/hitzzc/go-leetcode/tree/master/longest_substring_with_at_least_k_repeating_characters)
274+
#### [396. Rotate Function](https://github.com/hitzzc/go-leetcode/tree/master/rotate_function)
275+
#### [400. Nth Digit](https://github.com/hitzzc/go-leetcode/tree/master/nth_digit)
269276

270277

271278

‎decode_string/decode_string.cpp

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
class Solution {
2+
public:
3+
string decodeString(string s) {
4+
int i = 0;
5+
return decode(s, i);
6+
}
7+
8+
string decode(string& s, int& idx) {
9+
string ret;
10+
while (idx < s.size() && s[idx] != ']') {
11+
if (s[idx] < '0' || s[idx] > '9') {
12+
ret += s[idx++];
13+
} else {
14+
int num = 0;
15+
while (s[idx] != '[') {
16+
num = 10*num + s[idx++] - '0';
17+
}
18+
++idx;
19+
string tmp = decode(s, idx);
20+
while (num-- > 0) {
21+
ret += tmp;
22+
}
23+
++idx;
24+
}
25+
}
26+
return ret;
27+
}
28+
};

‎elimination_game/elimination_game.cpp

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
class Solution {
2+
public:
3+
int lastRemaining(int n) {
4+
return n == 1 ? 1 : 2*(n/2 + 1 - lastRemaining(n/2));
5+
}
6+
};

‎find_the_difference/find_the_difference.cpp

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
class Solution {
2+
public:
3+
char findTheDifference(string s, string t) {
4+
vector<int> vec(26, 0);
5+
for (auto& c: s) {
6+
++vec[c-'a'];
7+
}
8+
char ret;
9+
for (auto& c: t) {
10+
if (vec[c-'a'] == 0) {
11+
ret = c;
12+
break;
13+
}
14+
--vec[c-'a'];
15+
}
16+
return ret;
17+
}
18+
};

‎is_subsequence/is_subsequence.cpp

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class Solution {
2+
public:
3+
bool isSubsequence(string s, string t) {
4+
if (s.size() == 0) return true;
5+
int ps = 0, pt = 0;
6+
for (; pt < t.size() && ps < t.size(); ++pt) {
7+
if (s[ps] == t[pt]) ++ps;
8+
}
9+
return ps == s.size();
10+
}
11+
};

‎longest_substring_with_at_least_k_repeating_characters/longest_substring_with_at_least_k_repeating_characters.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution {
2+
public:
3+
int longestSubstring(string s, int k) {
4+
int ret = 0;
5+
int i = 0;
6+
while (i+k < s.size()) {
7+
int mask = 0, i_max = i;
8+
vector<int> cnt(26, 0);
9+
for (int j = i; j < s.size(); ++j) {
10+
int idx = s[j] - 'a';
11+
++cnt[idx];
12+
if (cnt[idx] < k) mask |= (1 << idx);
13+
else mask &= ~(1 << idx);
14+
if (mask == 0) {
15+
ret = max(ret, j-i+1);
16+
i_max = j;
17+
}
18+
}
19+
i = i_max + 1;
20+
}
21+
return ret;
22+
}
23+
};

‎nth_digit/nth_digit.cpp

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
class Solution {
2+
public:
3+
int findNthDigit(int n) {
4+
long len = 1;
5+
long count = 9;
6+
long start = 1;
7+
while (n > len*count) {
8+
n -= len*count;
9+
start += count;
10+
++len;
11+
count *= 10;
12+
}
13+
return to_string(start + (n-1)/len)[(n-1)%len] - '0';
14+
}
15+
};

‎rotate_function/rotate_function.cpp

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class Solution {
2+
public:
3+
int maxRotateFunction(vector<int>& A) {
4+
if (A.size() == 0) return 0;
5+
int sum = 0;
6+
int pre = 0;
7+
for (int i = 0; i < A.size(); ++i) {
8+
sum += A[i];
9+
pre += i * A[i];
10+
}
11+
int ret = pre;
12+
int len = A.size();
13+
for (int i = 0; i < len-1; ++i) {
14+
pre = pre - sum + len*A[i];
15+
ret = max(ret, pre);
16+
}
17+
return ret;
18+
}
19+
};

0 commit comments

Comments
 (0)
0