Skip to content

Commit f2a67c4

Browse files
OneCodeMonkeyOneCodeMonkey
committed
update
1 parent 6798a73 commit f2a67c4

7 files changed

+245
-0
lines changed

‎codeForces/Codeforces_1886A_Sum_of_Three.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
// AC: 390 ms
2+
// Memory: 1400 KB
3+
// Greedy, construtive.
4+
// T:O(t), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1886A_Sum_of_Three {
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(), x1 = 0, x2 = 0, x3 = 0;
14+
boolean flag = true;
15+
if (n % 3 == 0) {
16+
if (n < 12) {
17+
flag = false;
18+
} else {
19+
x1 = 1;
20+
x2 = 4;
21+
x3 = n - 5;
22+
}
23+
} else if (n % 3 == 1) {
24+
if (n < 7) {
25+
flag = false;
26+
} else {
27+
x1 = 1;
28+
x2 = 2;
29+
x3 = n - 3;
30+
}
31+
} else {
32+
if (n < 8) {
33+
flag = false;
34+
} else {
35+
x1 = 1;
36+
x2 = 2;
37+
x3 = n - 3;
38+
}
39+
}
40+
41+
if (flag) {
42+
System.out.println("YES");
43+
System.out.println(x1 + " " + x2 + " " + x3);
44+
} else {
45+
System.out.println("NO");
46+
}
47+
}
48+
}
49+
}

‎codeForces/Codeforces_1901A_Line_Trip.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
// AC: 327 ms
2+
// Memory: 1100 KB
3+
// Notice: the problems says we will need to reach x, and then return to 0.
4+
// T:O(t), S:O(1)
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1901A_Line_Trip {
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(), x = sc.nextInt(), prev = 0, ret = 0;
14+
for (int j = 0; j < n; j++) {
15+
int a = sc.nextInt();
16+
if (a <= x) {
17+
ret = Math.max(ret, a - prev);
18+
if (j == n - 1) {
19+
ret = Math.max(ret, 2 * (x - a));
20+
}
21+
} else {
22+
ret = Math.max(ret, 2 * (x - prev));
23+
}
24+
25+
prev = a;
26+
}
27+
28+
System.out.println(ret);
29+
}
30+
}
31+
}

‎codeForces/Codeforces_1917A_Least_Product.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
// AC: 405 ms
2+
// Memory: 1100 KB
3+
// T:O(sum(ni)), S:O(1)
4+
// Greedy.
5+
//
6+
import java.util.Scanner;
7+
8+
public class Codeforces_1917A_Least_Product {
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(), ret = 1, firstNonZeroIndex = 0;
14+
for (int j = 0; j < n; j++) {
15+
int a = sc.nextInt();
16+
ret *= Integer.compare(a, 0);
17+
if (a != 0) {
18+
firstNonZeroIndex = j + 1;
19+
}
20+
}
21+
if (ret <= 0) {
22+
System.out.println(0);
23+
} else {
24+
System.out.println(1);
25+
System.out.println(firstNonZeroIndex + " 0");
26+
}
27+
}
28+
}
29+
}

‎codeForces/Codeforces_1927C_Choose_the_Different_Ones.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// AC: 1280 ms
2+
// Memory: 32800 KB
3+
// Calculate set with n-array and m-array which elements in [1, k],
4+
// if set1.size() >= k/2, set2.size() >= k/2 and merged set size == k, that is the answer.
5+
// T:O((sum(ni, mi))), S:O(max(k))
6+
//
7+
import java.util.HashSet;
8+
import java.util.Scanner;
9+
10+
public class Codeforces_1927C_Choose_the_Different_Ones {
11+
public static void main(String[] args) {
12+
Scanner sc = new Scanner(System.in);
13+
int t = sc.nextInt();
14+
for (int i = 0; i < t; i++) {
15+
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
16+
HashSet<Integer> record1 = new HashSet<>(), record2 = new HashSet<>();
17+
for (int j = 0; j < n; j++) {
18+
int a = sc.nextInt();
19+
if (a <= k) {
20+
record1.add(a);
21+
}
22+
}
23+
for (int j = 0; j < m; j++) {
24+
int b = sc.nextInt();
25+
if (b <= k) {
26+
record2.add(b);
27+
}
28+
}
29+
boolean ret = false;
30+
if (record1.size() >= k / 2 && record2.size() >= k / 2) {
31+
record1.addAll(record2);
32+
if (record1.size() == k) {
33+
ret = true;
34+
}
35+
}
36+
37+
System.out.println(ret ? "YES" : "NO");
38+
}
39+
}
40+
}

‎leetcode_solved/leetcode_3127_Make_a_Square_with_the_Same_Color.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
// Runtime 0 ms Beats 100.00% of users with Java
2+
// Memory 41.81 MB Beats 50.00% of users with Java
3+
// Brute-force.
4+
// T:O(m * n * k^2), S:O(1)
5+
//
6+
class Solution {
7+
public boolean canMakeSquare(char[][] grid) {
8+
final char black = 'B', white = 'W';
9+
int row = grid.length, col = grid[0].length;
10+
for (int i = 0; i < row - 1; i++) {
11+
for (int j = 0; j < col - 1; j++) {
12+
int countB = 0, countW = 0;
13+
for (int r = i; r <= i + 1; r++) {
14+
for (int t = j; t <= j + 1; t++) {
15+
if (grid[r][t] == black) {
16+
countB++;
17+
} else {
18+
countW++;
19+
}
20+
if (countB == 3 || countW == 3) {
21+
return true;
22+
}
23+
}
24+
}
25+
}
26+
}
27+
28+
return false;
29+
}
30+
}

‎leetcode_solved/leetcode_3128_Right_Triangles.java‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
// Runtime 32 ms Beats 66.67% of users with Java
2+
// Memory 145.21 MB Beats 66.67% of users with Java
3+
// Prefix sum.
4+
// T:O(m * n), S:O(m * n)
5+
//
6+
class Solution {
7+
public long numberOfRightTriangles(int[][] grid) {
8+
int row = grid.length, col = grid[0].length;
9+
long ret = 0;
10+
int[][] rowSum = new int[row][col], colSum = new int[row][col], rowSumRev = new int[row][col],
11+
colSumRev = new int[row][col];
12+
for (int i = 0; i < row; i++) {
13+
int curSum = 0;
14+
for (int j = 0; j < col; j++) {
15+
curSum += grid[i][j];
16+
rowSum[i][j] = curSum;
17+
}
18+
curSum = 0;
19+
for (int j = col - 1; j >= 0; j--) {
20+
curSum += grid[i][j];
21+
rowSumRev[i][j] = curSum;
22+
}
23+
}
24+
for (int i = 0; i < col; i++) {
25+
int curSum = 0;
26+
for (int j = 0; j < row; j++) {
27+
curSum += grid[j][i];
28+
colSum[j][i] = curSum;
29+
}
30+
curSum = 0;
31+
for (int j = row - 1; j >= 0; j--) {
32+
curSum += grid[j][i];
33+
colSumRev[j][i] = curSum;
34+
}
35+
}
36+
for (int i = 0; i < row; i++) {
37+
for (int j = 0; j < col; j++) {
38+
if (grid[i][j] == 1) {
39+
int rowSumVal = rowSum[i][j], rowSumRevVal = rowSumRev[i][j], colSumVal = colSum[i][j],
40+
colSumRevVal = colSumRev[i][j];
41+
ret += (long) (rowSumVal - 1 + rowSumRevVal - 1) * (colSumVal - 1 + colSumRevVal - 1);
42+
}
43+
}
44+
}
45+
46+
return ret;
47+
}
48+
}

‎leetcode_solved/leetcode_3131_Find_the_Integer_Added_to_Array_I.java‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
// Runtime 0 ms Beats 100.00% of users with Java
2+
// Memory 42.76 MB Beats 100.00% of users with Java
3+
// .
4+
// T:O(n), S:O(1)
5+
//
6+
class Solution {
7+
public int addedInteger(int[] nums1, int[] nums2) {
8+
int max1 = -1, max2 = -1;
9+
for (int num : nums1) {
10+
max1 = Math.max(max1, num);
11+
}
12+
for (int num : nums2) {
13+
max2 = Math.max(max2, num);
14+
}
15+
16+
return max2 - max1;
17+
}
18+
}

0 commit comments

Comments
 (0)