Skip to content

Commit f0bd287

Browse files
OneCodeMonkeyOneCodeMonkey
committed
update
1 parent 1c5b174 commit f0bd287

7 files changed

+216
-0
lines changed

‎codeForces/Codeforces_1369B_AccurateLee.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
// AC: 296 ms
2+
// Memory: 500 KB
3+
// T:O(sum(ni)), S:O(max(ni))
4+
//
5+
import java.util.Scanner;
6+
7+
public class Codeforces_1369B_AccurateLee {
8+
public static void main(String[] args) {
9+
Scanner sc = new Scanner(System.in);
10+
int t = sc.nextInt();
11+
for (int i = 0; i < t; i++) {
12+
int n = sc.nextInt();
13+
StringBuilder ret = new StringBuilder();
14+
String s = sc.next();
15+
int pos = 0, firstZero = 0, lastOne = 0;
16+
while (pos < s.length() && s.charAt(pos) == '0') {
17+
firstZero++;
18+
pos++;
19+
}
20+
pos = s.length() - 1;
21+
while (pos >= 0 && s.charAt(pos) == '1') {
22+
lastOne++;
23+
pos--;
24+
}
25+
if (firstZero + lastOne == s.length()) {
26+
System.out.println(s);
27+
} else {
28+
ret.append("0".repeat(firstZero));
29+
ret.append('0');
30+
ret.append("1".repeat(lastOne));
31+
System.out.println(ret.toString());
32+
}
33+
}
34+
}
35+
}

‎codeForces/Codeforces_1506C_Double_ended_Strings.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
// AC: 265 ms
2+
// Memory: 700 KB
3+
// LCS: 找最长公共子串，不过我们可以使用暴力解法 过此题。
4+
// T:O(n ^ 2 ~ n ^ 3), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1506C_Double_ended_Strings {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
String a = sc.next(), b = sc.next();
14+
int maxCommon = 0, len1 = a.length(), len2 = b.length();
15+
for (int j = 0; j < len1; j++) {
16+
for (int k = 0; k < len2; k++) {
17+
int step = 0;
18+
while (j + step < len1 && k + step < len2 && a.charAt(j + step) == b.charAt(k + step)) {
19+
step++;
20+
}
21+
maxCommon = Math.max(maxCommon, step);
22+
if (len2 - k <= maxCommon) {
23+
break;
24+
}
25+
}
26+
if (len1 - j <= maxCommon) {
27+
break;
28+
}
29+
}
30+
31+
System.out.println(len1 + len2 - 2 * maxCommon);
32+
}
33+
}
34+
}

‎codeForces/Codeforces_1883C_Raspberries.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
// AC: 468 ms
2+
// Memory: 600 KB
3+
// T:O(sum(ni)), S:O(1)
4+
// math.
5+
//
6+
import java.util.HashMap;
7+
import java.util.Scanner;
8+
9+
public class Codeforces_1883C_Raspberries {
10+
public static void main(String[] args) {
11+
Scanner sc = new Scanner(System.in);
12+
int t = sc.nextInt();
13+
for (int i = 0; i < t; i++) {
14+
int n = sc.nextInt(), k = sc.nextInt(), ret = 0, countEven = 0, countOdd = 0;
15+
HashMap<Integer, Integer> record = new HashMap<>();
16+
for (int j = 0; j < n; j++) {
17+
int a = sc.nextInt();
18+
record.merge(a, 1, Integer::sum);
19+
if (a % 2 == 0) {
20+
countEven++;
21+
} else {
22+
countOdd++;
23+
}
24+
}
25+
if (!record.containsKey(k)) {
26+
if (k == 2) {
27+
ret = countEven > 0 ? 0 : 1;
28+
} else if (k == 3) {
29+
if (!record.containsKey(6) && !record.containsKey(9)) {
30+
int tmp = 2;
31+
for (int key : record.keySet()) {
32+
tmp = Math.min(tmp, 3 - key % 3);
33+
}
34+
ret = tmp;
35+
}
36+
} else if (k == 4) {
37+
if (!record.containsKey(8)) {
38+
if (countEven == 0) {
39+
int tmp = 3;
40+
for (int key : record.keySet()) {
41+
tmp = Math.min(tmp, 4 - key % 4);
42+
}
43+
tmp = Math.min(2, tmp);
44+
ret = tmp;
45+
} else if (countEven == 1) {
46+
ret = 1;
47+
}
48+
}
49+
} else if (k == 5) {
50+
if (!record.containsKey(10)) {
51+
int tmp = 4;
52+
for (int key : record.keySet()) {
53+
tmp = Math.min(tmp, 5 - key % 5);
54+
}
55+
ret = tmp;
56+
}
57+
}
58+
}
59+
60+
System.out.println(ret);
61+
}
62+
}
63+
}

‎codeForces/Codeforces_1948A_Special_Characters.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// AC: 218 ms
2+
// Memory: 1000 KB
3+
// Can be proved that such special char is occurred by twice.
4+
// T:O(sum(ni)), S:O(max(ni))
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1948A_Special_Characters {
9+
public static void main(String[] args) {
10+
Scanner sc = new Scanner(System.in);
11+
int t = sc.nextInt();
12+
for (int i = 0; i < t; i++) {
13+
int n = sc.nextInt();
14+
if (n % 2 == 1) {
15+
System.out.println("NO");
16+
} else {
17+
System.out.println("YES");
18+
StringBuilder ret = new StringBuilder();
19+
ret.append("AA");
20+
ret.append("BAA".repeat(Math.max(0, n / 2 - 1)));
21+
System.out.println(ret);
22+
}
23+
}
24+
}
25+
}

‎leetcode_solved/leetcode_3206_Alternating_Groups_I.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
// Runtime 1 ms Beats 100.00%
2+
// Memory 42.83 MB Beats 100.00%
3+
// .
4+
// T:O(n), S:O(1)
5+
//
6+
class Solution {
7+
public int numberOfAlternatingGroups(int[] colors) {
8+
int len = colors.length, ret = 0;
9+
for (int i = 0; i < len; i++) {
10+
int left = i == 0 ? colors[len - 1] : colors[i - 1], right = i == len - 1 ? colors[0] : colors[i + 1];
11+
if (colors[i] != left && colors[i] != right) {
12+
ret++;
13+
}
14+
}
15+
16+
return ret;
17+
}
18+
}

‎leetcode_solved/leetcode_3210_Find_the_Encrypted_String.java‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
// Runtime 1 ms Beats 100.00%
2+
// Memory 42.42 MB Beats 100.00%
3+
// .
4+
// T:O(n), S:O(1)
5+
//
6+
class Solution {
7+
public String getEncryptedString(String s, int k) {
8+
int len = s.length();
9+
k = k % len;
10+
return s.substring(k, len) + s.substring(0, k);
11+
}
12+
}

‎leetcode_solved/leetcode_3211_Generate_Binary_Strings_Without_Adjacent_Zeros.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
// Runtime 2 ms Beats 100.00%
2+
// Memory 46.32 MB Beats 100.00%
3+
// Backtracking.
4+
// T:O(2 ^ n), S:O(2 ^ n)
5+
//
6+
class Solution {
7+
public List<String> validStrings(int n) {
8+
List<String> ret = new LinkedList<>();
9+
StringBuilder curStr = new StringBuilder();
10+
backtracking(ret, curStr, n, 1);
11+
12+
return ret;
13+
}
14+
15+
private void backtracking(List<String> ret, StringBuilder sb, int n, int prev) {
16+
if (sb.length() == n) {
17+
ret.add(sb.toString());
18+
return;
19+
}
20+
sb.append("1");
21+
backtracking(ret, sb, n, 1);
22+
sb.deleteCharAt(sb.length() - 1);
23+
if (prev == 1) {
24+
sb.append("0");
25+
backtracking(ret, sb, n, 0);
26+
sb.deleteCharAt(sb.length() - 1);
27+
}
28+
}
29+
}

0 commit comments

Comments
 (0)