Skip to content

Commit bd9df93

Browse files
OneCodeMonkeyOneCodeMonkey
committed
update
1 parent 2b85843 commit bd9df93

7 files changed

Lines changed: 276 additions & 0 deletions

‎codeForces/Codeforces_0404A_Valera_and_X.java‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
// AC: 359 ms
2+
// Memory: 1900 KB
3+
// .
4+
// T:O(n), S:O(n)
5+
//
6+
import java.util.HashMap;
7+
import java.util.Scanner;
8+
9+
public class Codeforces_0404A_Valera_and_X {
10+
public static void main(String[] args) {
11+
Scanner sc = new Scanner(System.in);
12+
int n = sc.nextInt();
13+
String[] arr = new String[n];
14+
HashMap<Character, Integer> record = new HashMap<>();
15+
boolean flag = true;
16+
for (int i = 0; i < n; i++) {
17+
String s = sc.next();
18+
arr[i] = s;
19+
if (flag) {
20+
for (char c : s.toCharArray()) {
21+
record.merge(c, 1, Integer::sum);
22+
}
23+
if (record.size() > 2) {
24+
flag = false;
25+
}
26+
}
27+
}
28+
if (record.size() != 2) {
29+
flag = false;
30+
}
31+
if (flag) {
32+
int c1 = 0, c2 = 0;
33+
for (char c : record.keySet()) {
34+
if (c1 == 0) {
35+
c1 = record.get(c);
36+
} else {
37+
c2 = record.get(c);
38+
}
39+
}
40+
if (c1 != 2 * n - 1 && c2 != 2 * n - 1) {
41+
flag = false;
42+
} else {
43+
for (int i = 0; i < n; i++) {
44+
if (arr[i].charAt(i) != arr[0].charAt(0)) {
45+
flag = false;
46+
break;
47+
}
48+
if (arr[i].charAt(n - 1 - i) != arr[0].charAt(0)) {
49+
flag = false;
50+
break;
51+
}
52+
}
53+
}
54+
}
55+
56+
System.out.println(flag ? "YES" : "NO");
57+
}
58+
}

‎codeForces/Codeforces_1272C_Yet_Another_Broken_Keyboard.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
// AC: 296 ms
2+
// Memory: 700 KB
3+
// Combinatorics.
4+
// T:O(n + k), S:O(k)
5+
//
6+
import java.util.HashSet;
7+
import java.util.Scanner;
8+
9+
public class Codeforces_1272C_Yet_Another_Broken_Keyboard {
10+
public static void main(String[] args) {
11+
Scanner sc = new Scanner(System.in);
12+
int n = sc.nextInt(), k = sc.nextInt(), cur = 0;
13+
long ret = 0;
14+
String s = sc.next();
15+
HashSet<Character> letters = new HashSet<>();
16+
for (int i = 0; i < k; i++) {
17+
letters.add(sc.next().charAt(0));
18+
}
19+
for (int i = 0; i < n; i++) {
20+
char c = s.charAt(i);
21+
if (letters.contains(c)) {
22+
cur++;
23+
if (i == n - 1) {
24+
ret += (long) cur * (cur + 1) / 2;
25+
}
26+
} else {
27+
ret += (long) cur * (cur + 1) / 2;
28+
cur = 0;
29+
}
30+
}
31+
32+
System.out.println(ret);
33+
}
34+
}

‎codeForces/Codeforces_1351A_A_plus_B.java‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
// AC: 280 ms
2+
// Memory: 1200 KB
3+
// .
4+
// T:O(t), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1351A_A_plus_B {
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 a = sc.nextInt(), b = sc.nextInt();
14+
System.out.println(a + b);
15+
}
16+
}
17+
}

‎codeForces/Codeforces_1362A_Johnny_and_Ancient_Computer.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
// AC: 296 ms
2+
// Memory: 1100 KB
3+
// .
4+
// T:O(sum(logni)), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1362A_Johnny_and_Ancient_Computer {
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 ret = -1;
14+
long a = sc.nextLong(), b = sc.nextLong();
15+
if (a == b) {
16+
ret = 0;
17+
} else {
18+
long minVal = Math.min(a, b), maxVal = Math.max(a, b);
19+
if (maxVal % minVal == 0) {
20+
long divider = maxVal / minVal, expFor2 = 0;
21+
boolean flag = true;
22+
while (divider > 1) {
23+
if (divider % 2 != 0) {
24+
flag = false;
25+
break;
26+
}
27+
divider /= 2;
28+
expFor2++;
29+
}
30+
if (!flag) {
31+
ret = -1;
32+
} else {
33+
ret = (int) Math.ceil(expFor2 * 1.0 / 3);
34+
}
35+
}
36+
}
37+
38+
System.out.println(ret);
39+
}
40+
}
41+
}

‎codeForces/Codeforces_1742D_Coprime.java‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
// AC: 2359 ms
2+
// Memory: 1600 KB
3+
// 反向思维，不记录原始 arr[n]，而只记录 a 的值去重，以 a 值 1～1000 去便利。
4+
// T:O(t * k^2), S:O(k), k =1000
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1742D_Coprime {
9+
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(), ret = -1;
15+
int[] numPos = new int[1001];
16+
for (int j = 0; j < n; j++) {
17+
int a = sc.nextInt();
18+
numPos[a] = j + 1;
19+
}
20+
for (int j = 1; j <= 1000; j++) {
21+
for (int k = j; k <= 1000; k++) {
22+
if (numPos[j] > 0 && numPos[k] > 0 && gcd(j, k) == 1) {
23+
ret = Math.max(ret, numPos[j] + numPos[k]);
24+
}
25+
}
26+
}
27+
28+
System.out.println(ret);
29+
}
30+
}
31+
32+
private static int gcd(int a, int b) {
33+
if (a > b) {
34+
return gcd(b, a);
35+
}
36+
String key = a + "#" + b;
37+
if (b % a == 0) {
38+
return a;
39+
} else {
40+
return gcd(b % a, a);
41+
}
42+
}
43+
}

‎leetcode_solved/leetcode_2501_Longest_Square_Streak_in_an_Array.java‎

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
// Runtime 58 ms Beats 28.13%
2+
// Memory 59.69 MB Beats 60.42%
3+
// Sort & hashset.
4+
// T:O(n), S:O(n)
5+
//
6+
class Solution {
7+
public int longestSquareStreak(int[] nums) {
8+
int ret = -1;
9+
List<Integer> squares = new ArrayList<>();
10+
for (int num : nums) {
11+
int sqrtN = (int) Math.sqrt(num);
12+
if (sqrtN * sqrtN == num) {
13+
squares.add(num);
14+
}
15+
}
16+
if (squares.isEmpty()) {
17+
return ret;
18+
}
19+
HashSet<Integer> original = Arrays.stream(nums).boxed().collect(Collectors.toCollection(HashSet::new)),
20+
usedSquares = new HashSet<>();
21+
squares.sort((a, b) -> b - a);
22+
int pos = 0;
23+
while (!squares.isEmpty()) {
24+
int start = -1, cur = 1;
25+
for (int i = pos; i < squares.size(); i++) {
26+
if (!usedSquares.contains(squares.get(i))) {
27+
start = squares.get(i);
28+
pos = i + 1;
29+
break;
30+
}
31+
}
32+
if (start == -1) {
33+
break;
34+
}
35+
36+
usedSquares.add(start);
37+
while (true) {
38+
int sqrtN = (int) Math.sqrt(start);
39+
if (sqrtN * sqrtN != start || !original.contains(sqrtN)) {
40+
break;
41+
}
42+
start = sqrtN;
43+
cur++;
44+
usedSquares.add(start);
45+
}
46+
if (cur > 1) {
47+
ret = Math.max(ret, cur);
48+
}
49+
}
50+
51+
return ret;
52+
}
53+
}

‎leetcode_solved/leetcode_3330_Find_the_Original_Typed_String_I.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
// Runtime 1 ms Beats 100.00%
2+
// Memory 41.92 MB Beats 100.00%
3+
// .
4+
// T:O(n), S:O(1)
5+
//
6+
class Solution {
7+
public int possibleStringCount(String word) {
8+
int ret = 1, cur = 0;
9+
char prev = ' ';
10+
for (int i = 0; i < word.length(); i++) {
11+
char c = word.charAt(i);
12+
if (i == 0) {
13+
prev = c;
14+
continue;
15+
}
16+
if (c == prev) {
17+
cur++;
18+
if (i == word.length() - 1) {
19+
ret += cur;
20+
}
21+
} else {
22+
ret += cur;
23+
cur = 0;
24+
}
25+
prev = c;
26+
}
27+
28+
return ret;
29+
}
30+
}

0 commit comments

Comments
 (0)