Skip to content

Commit 06c8ce4

Browse files
OneCodeMonkeyOneCodeMonkey
committed
feat
1 parent d2f6422 commit 06c8ce4

7 files changed

+279
-0
lines changed

‎codeForces/Codeforces_1722D_Line.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
// AC: 328 ms
2+
// Memory: 5900 KB
3+
// Greedy.
4+
// T:O(n), S:O(n)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1722D_Line {
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+
String s = sc.next();
15+
long sum = 0, maxSum = n % 2 == 0 ? (n * (3L * n - 2) / 4) : (n / 2 + (3L * n - 1) * (n - 1) / 4);
16+
int[] arr = new int[n];
17+
StringBuilder ret = new StringBuilder();
18+
for (int j = 0; j < n; j++) {
19+
if (s.charAt(j) == 'L') {
20+
arr[j] = j;
21+
} else {
22+
arr[j] = n - 1 - j;
23+
}
24+
sum += arr[j];
25+
}
26+
int distance = 0;
27+
for (int j = 0; j < n; j++) {
28+
if (sum == maxSum) {
29+
ret.append(sum);
30+
if (j != n - 1) {
31+
ret.append(" ");
32+
}
33+
} else {
34+
// greedy. Find first char which can change to get more value.
35+
while (distance / 2 <= n / 2 - 1) {
36+
if (distance % 2 == 0) {
37+
if (s.charAt(distance / 2) == 'L') {
38+
sum += n - 1 - distance / 2;
39+
sum -= distance / 2;
40+
distance++;
41+
break;
42+
}
43+
distance++;
44+
} else {
45+
if (s.charAt(n - 1 - distance / 2) == 'R') {
46+
sum += n - 1 - distance / 2;
47+
sum -= distance / 2;
48+
distance++;
49+
break;
50+
}
51+
distance++;
52+
}
53+
}
54+
ret.append(sum);
55+
if (j != n - 1) {
56+
ret.append(" ");
57+
}
58+
}
59+
}
60+
61+
System.out.println(ret);
62+
}
63+
}
64+
}

‎codeForces/Codeforces_1744B_Even_Odd_Increments.java‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
// Time: 921 ms
2+
// Memory: 1300 KB
3+
// Record the accumulated sum.
4+
// T:O(sum(ni + qi)), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1744B_Even_Odd_Increments {
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(), q = sc.nextInt();
14+
long oddSum = 0, oddCount = 0, evenSum = 0, evenCount = 0;
15+
for (int j = 0; j < n; j++) {
16+
int a = sc.nextInt();
17+
if (a % 2 == 1) {
18+
oddSum += a;
19+
oddCount++;
20+
} else {
21+
evenSum += a;
22+
evenCount++;
23+
}
24+
}
25+
long addOdd = 0, addEven = 0;
26+
for (int j = 0; j < q; j++) {
27+
int type = sc.nextInt(), x = sc.nextInt();
28+
if (type == 0) {
29+
if (x % 2 == 0) {
30+
evenSum += evenCount * x;
31+
} else {
32+
evenSum += evenCount * x;
33+
oddCount += evenCount;
34+
evenCount = 0;
35+
}
36+
} else {
37+
if (x % 2 == 0) {
38+
oddSum += oddCount * x;
39+
} else {
40+
oddSum += oddCount * x;
41+
evenCount += oddCount;
42+
oddCount = 0;
43+
}
44+
}
45+
46+
System.out.println(oddSum + evenSum);
47+
}
48+
}
49+
}
50+
}

‎codeForces/Codeforces_1779B_MKnez_s_ConstructiveForces_Task.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// Time: 296 ms
2+
// Memory: 900 KB
3+
// Constructive.
4+
// T:O(sum(ni)), S:O(max(ni))
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1779B_MKnez_s_ConstructiveForces_Task {
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+
if (n == 3) {
16+
System.out.println("NO");
17+
} else {
18+
System.out.println("YES");
19+
int start = (n - 1) / 2 - 1, second = -(start + 1);
20+
StringBuilder ret = new StringBuilder();
21+
for (int j = 0; j < (n - 1) / 2; j++) {
22+
ret.append(start).append(" ").append(second).append(" ");
23+
}
24+
ret.append(start);
25+
System.out.println(ret);
26+
}
27+
} else {
28+
System.out.println("YES");
29+
StringBuilder ret = new StringBuilder();
30+
for (int j = 0; j < n; j++) {
31+
ret.append(j % 2 == 0 ? 1 : -1);
32+
if (j != n - 1) {
33+
ret.append(" ");
34+
}
35+
}
36+
System.out.println(ret);
37+
}
38+
}
39+
}
40+
}

‎codeForces/Codeforces_1791G1_Teleporters_Easy_Version.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
// Time: 686 ms
2+
// Memory: 1200 KB
3+
// Greedy & sort.
4+
// T:O(sum(ni * logni)), S:O(max(ni))
5+
//
6+
import java.util.Arrays;
7+
import java.util.Scanner;
8+
9+
public class Codeforces_1791G1_Teleporters_Easy_Version {
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(), c = sc.nextInt(), ret = 0;
15+
int[] arr = new int[n];
16+
for (int j = 0; j < n; j++) {
17+
int a = sc.nextInt();
18+
arr[j] = a + j + 1;
19+
}
20+
Arrays.sort(arr);
21+
for (int j = 0; j < n; j++) {
22+
if (arr[j] > c) {
23+
break;
24+
}
25+
c -= arr[j];
26+
ret++;
27+
}
28+
29+
System.out.println(ret);
30+
}
31+
}
32+
}

‎leetcode_solved/leetcode_2116_Check_if_a_Parentheses_String_Can_Be_Valid.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
// Runtime 24 ms Beats 14.52%
2+
// Memory 46.74 MB Beats 5.81%
3+
// Stack: 使用两个 stack，优先使用自身的 () 配对，其次用 0 字符位置的动态位去凑对，最后看多出来的 ( 是否可用 0 字符动态位置凑对完。
4+
// T:O(n), S:O(n)
5+
//
6+
class Solution {
7+
/**
8+
* 双stack 思想，优先用自带的 ()来凑对，其次用 0 字符位置的动态位去凑对，最后看多出来的 ( 是否可用 0 字符动态位置凑对完。
9+
*
10+
* @param s
11+
* @param locked
12+
* @return
13+
*/
14+
public boolean canBeValid(String s, String locked) {
15+
int len = s.length();
16+
if (len % 2 == 1) {
17+
return false;
18+
}
19+
20+
Stack<Integer> self = new Stack<>(), dynamic = new Stack<>();
21+
for (int i = 0; i < s.length(); i++) {
22+
char c = s.charAt(i), c1 = locked.charAt(i);
23+
if (c1 == '0') {
24+
dynamic.push(i);
25+
} else if (c == '(') {
26+
self.push(i);
27+
} else if (c == ')') {
28+
if (!self.isEmpty()) {
29+
self.pop();
30+
} else if (!dynamic.isEmpty()) {
31+
dynamic.pop();
32+
} else {
33+
return false;
34+
}
35+
}
36+
}
37+
38+
while (!self.isEmpty() && !dynamic.isEmpty() && dynamic.peek() > self.peek()) {
39+
self.pop();
40+
dynamic.pop();
41+
}
42+
43+
return self.isEmpty();
44+
}
45+
}

‎leetcode_solved/leetcode_2425_Bitwise_XOR_of_All_Pairings.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
// Runtime 1 ms Beats 100.00%
2+
// Memory 61.33 MB Beats 58.62%
3+
// Trick: 因为 XOR 具有交换率，即 a^b = b^a, 假设有 arr1，arr2，如果 arr2 长度为偶数，那么 arr1 的所有元素，在最终 xor 全部叠加在一起之后，
4+
// 其 xor 结果就是 0，那么只需考虑 arr2 所有元素 xor 的结果，次数若 arr1 长度也为偶数，那么结果直接就是0.
5+
// T:O(m + n), S:O(1)
6+
//
7+
class Solution {
8+
public int xorAllNums(int[] nums1, int[] nums2) {
9+
int ret = 0;
10+
if (nums1.length % 2 == 1) {
11+
for (int i : nums2) {
12+
ret ^= i;
13+
}
14+
}
15+
if (nums2.length % 2 == 1) {
16+
for (int i : nums1) {
17+
ret ^= i;
18+
}
19+
}
20+
21+
return ret;
22+
}
23+
}

‎leetcode_solved/leetcode_3417_Zigzag_Grid_Traversal_With_Skip.java‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
// Runtime 1 ms Beats 100.00%
2+
// Memory 45.44 MB Beats 100.00%
3+
// .
4+
// T:O(m * n), S:O(m + n)
5+
//
6+
class Solution {
7+
public List<Integer> zigzagTraversal(int[][] grid) {
8+
int row = grid.length, col = grid[0].length;
9+
List<Integer> ret = new ArrayList<>();
10+
for (int i = 0; i < row; i++) {
11+
if (i % 2 == 0) {
12+
for (int j = 0; j < col; j += 2) {
13+
ret.add(grid[i][j]);
14+
}
15+
} else {
16+
int start = col % 2 == 0 ? (col - 1) : (col - 2);
17+
for (int j = start; j >= 0; j -= 2) {
18+
ret.add(grid[i][j]);
19+
}
20+
}
21+
}
22+
23+
return ret;
24+
}
25+
}

0 commit comments

Comments
 (0)