Skip to content

Commit 4172e5c

Browse files
author
zhuchen
committed
2021-5-21
1 parent e9f2b72 commit 4172e5c

File tree

13 files changed

+501
-0
lines changed

13 files changed

+501
-0
lines changed

‎lcp03_programmable_robot/Solution.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package lcp03_programmable_robot;
2+
3+
import java.util.HashSet;
4+
import java.util.Set;
5+
6+
public class Solution {
7+
8+
public boolean robot(String command, int[][] obstacles, int x, int y) {
9+
long curX = 0, curY = 0;
10+
Set<Long> set = new HashSet<>();
11+
set.add((curX << 32) | curY);
12+
for (int i = 0; i < command.length(); i++) {
13+
if (command.charAt(i) == 'U') {
14+
curY++;
15+
} else {
16+
curX++;
17+
}
18+
set.add((curX << 32) | curY);
19+
}
20+
long turns = Math.min(x / curX, y / curY);
21+
if (!set.contains(((x - turns * curX) << 32) | (y - turns * curY))) {
22+
return false;
23+
}
24+
for (int[] obstacle : obstacles) {
25+
if (obstacle[0] > x || obstacle[1] > y) {
26+
continue;
27+
}
28+
turns = Math.min(obstacle[0] / curX, obstacle[1] / curY);
29+
if (set.contains(((obstacle[0] - turns * curX) << 32) | (obstacle[1] - turns * curY))) {
30+
return false;
31+
}
32+
}
33+
return true;
34+
}
35+
36+
}

‎lcp12_xiao_zhang_shua_ti_ji_hua/Solution.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package lcp12_xiao_zhang_shua_ti_ji_hua;
2+
3+
public class Solution {
4+
5+
public int minTime(int[] time, int m) {
6+
int left = 0, right = 1000000000;
7+
while (left < right) {
8+
if (left + 1 == right) {
9+
if (check(time, m, left)) {
10+
return left;
11+
}
12+
return right;
13+
}
14+
int mid = left + ((right - left) >> 1);
15+
if (check(time, m, mid)) {
16+
right = mid;
17+
} else {
18+
left = mid + 1;
19+
}
20+
}
21+
return left;
22+
}
23+
24+
public static void main(String[] args) {
25+
int[] time = {999,999,999};
26+
int m = 4;
27+
System.out.println(new Solution().minTime(time, m));
28+
}
29+
30+
private boolean check(int[] time, int m, int T) {
31+
int max = Integer.MIN_VALUE, day = 0, cost = 0;
32+
for (int i = 0; i < time.length; i++) {
33+
cost += time[i];
34+
if (max != Integer.MIN_VALUE) {
35+
cost += max;
36+
}
37+
max = Math.max(max, time[i]);
38+
cost -= max;
39+
if (cost > T) {
40+
cost = 0;
41+
i--;
42+
day++;
43+
max = Integer.MIN_VALUE;
44+
}
45+
}
46+
return day < m;
47+
}
48+
49+
}

‎lcp23_er94lq/Solution.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package lcp23_er94lq;
2+
3+
public class Solution {
4+
5+
public boolean isMagic(int[] target) {
6+
int[] origin = new int[target.length];
7+
for (int i = 0; i < origin.length; i++) {
8+
origin[i] = i + 1;
9+
}
10+
int index1 = 0, index2 = 0, k = 0;
11+
while (true) {
12+
step1(origin, index1);
13+
int begin = index1;
14+
for (; index2 < target.length; index2++) {
15+
if (k != 0 && index2 - begin >= k) {
16+
break;
17+
}
18+
if (target[index1] != origin[index2]) {
19+
if (k == 0) {
20+
k = index2 - begin;
21+
}
22+
break;
23+
}
24+
index1++;
25+
}
26+
if (index1 == origin.length) {
27+
return true;
28+
}
29+
if (k == 0 || k != index2 - begin) {
30+
return false;
31+
}
32+
}
33+
}
34+
35+
// 将 nums 数组中 [index, nums.length - 1] 范围内的元素进行第一步操作
36+
private void step1(int[] nums, int index) {
37+
int[] copy = new int[nums.length - index];
38+
for (int i = 0; i < copy.length; i++) {
39+
copy[i] = nums[i + index];
40+
}
41+
int j = 0;
42+
for (int i = 1; i < copy.length; i += 2) {
43+
nums[index + j++] = copy[i];
44+
}
45+
for (int i = 0; i < copy.length; i += 2) {
46+
nums[index + j++] = copy[i];
47+
}
48+
}
49+
50+
}

‎question1845_seat_reservation_manager/SeatManager.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package question1845_seat_reservation_manager;
2+
3+
import java.util.PriorityQueue;
4+
5+
public class SeatManager {
6+
7+
private PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
8+
9+
public SeatManager(int n) {
10+
for (int i = 1; i <= n; i++) {
11+
priorityQueue.add(i);
12+
}
13+
}
14+
15+
public int reserve() {
16+
return priorityQueue.poll();
17+
}
18+
19+
public void unreserve(int seatNumber) {
20+
priorityQueue.add(seatNumber);
21+
}
22+
23+
}

‎question1846_maximum_element_after_decreasing_and_rearranging/Solution.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package question1846_maximum_element_after_decreasing_and_rearranging;
2+
3+
import java.util.Arrays;
4+
5+
public class Solution {
6+
7+
public int maximumElementAfterDecrementingAndRearranging(int[] arr) {
8+
Arrays.sort(arr);
9+
arr[0] = 1;
10+
for (int i = 1; i < arr.length; i++) {
11+
if (arr[i] - arr[i - 1] > 1) {
12+
arr[i] = arr[i - 1] + 1;
13+
}
14+
}
15+
return arr[arr.length - 1];
16+
}
17+
18+
public static void main(String[] args) {
19+
int[] arr = {100, 1, 1000};
20+
System.out.println(new Solution().maximumElementAfterDecrementingAndRearranging(arr));
21+
}
22+
23+
}

‎question1849_splitting_a_string_into_descending_consecutive_values/Solution.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package question1849_splitting_a_string_into_descending_consecutive_values;
2+
3+
public class Solution {
4+
5+
public boolean splitString(String s) {
6+
return dfs(s, 0, -1, 0);
7+
}
8+
9+
private boolean dfs(String s, int index, long pre, int len) {
10+
if (index == s.length()) {
11+
return len != 1;
12+
}
13+
if (pre == -1) {
14+
for (int i = index + 1; i <= s.length(); i++) {
15+
Long cur;
16+
try {
17+
cur = Long.parseLong(s.substring(0, i));
18+
} catch (Exception e) {
19+
continue;
20+
}
21+
if (dfs(s, i, cur, len + 1)) {
22+
return true;
23+
}
24+
}
25+
} else {
26+
for (int i = index + 1; i <= s.length(); i++) {
27+
Long cur;
28+
try {
29+
cur = Long.parseLong(s.substring(index, i));
30+
} catch (Exception e) {
31+
continue;
32+
}
33+
if (pre - 1 == cur) {
34+
if (dfs(s, i, pre - 1, len + 1)) {
35+
return true;
36+
}
37+
}
38+
}
39+
}
40+
return false;
41+
}
42+
43+
}

‎question1850_minimum_adjacent_swaps_to_reach_the_kth_smallest_number/Solution.java

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
package question1850_minimum_adjacent_swaps_to_reach_the_kth_smallest_number;
2+
3+
/**
4+
* LeetCode0031
5+
*/
6+
public class Solution {
7+
8+
public int getMinSwaps(String num, int k) {
9+
int[] nums = new int[num.length()], origin = new int[num.length()];
10+
for (int i = 0; i < num.length(); i++) {
11+
nums[i] = origin[i] = num.charAt(i) - '0';
12+
}
13+
for (int i = 0; i < k; i++) {
14+
nextPermutation(nums);
15+
}
16+
int result = 0;
17+
for (int i = 0; i < num.length(); i++) {
18+
if (origin[i] != nums[i]) {
19+
int j = i + 1;
20+
while (origin[j] != nums[i]) {
21+
j++;
22+
}
23+
while (j != i) {
24+
swap(j - 1, j, origin);
25+
result++;
26+
j--;
27+
}
28+
}
29+
}
30+
return result;
31+
}
32+
33+
34+
private static void nextPermutation(int[] nums) {
35+
int n = nums.length, i = n - 1;
36+
for (; i >= 1; i--) {
37+
if (nums[i] > nums[i - 1]) { //如果存在第i个数比第(i - 1)个数更大的情况，说明存在下一个更大的排列
38+
break;
39+
}
40+
}
41+
if (i >= 1) { //存在下一个更大的排列
42+
int j = n - 1;
43+
for (; j >= i; j--) {
44+
if (nums[j] > nums[i - 1]) { //寻找到比第(i - 1)个数更大的数，其索引是j
45+
break;
46+
}
47+
}
48+
swap(i - 1, j, nums); //交换第(i - 1)个数和第j个数
49+
reverse(nums, i); //此时[i, n - 1]仍然是一个降序排列，将其反转为一个升序排列
50+
} else { //不存在下一个更大的排列
51+
reverse(nums, 0);
52+
}
53+
}
54+
55+
private static void reverse(int[] nums, int index) {
56+
int i = index, j = nums.length - 1;
57+
while (i < j) {
58+
swap(i, j, nums);
59+
i++;
60+
j--;
61+
}
62+
}
63+
64+
private static void swap(int i, int j, int[] nums) {
65+
int tmp = nums[i];
66+
nums[i] = nums[j];
67+
nums[j] = tmp;
68+
}
69+
70+
}

‎question1855_maximum_distance_between_a_pair_of_values/Solution.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package question1855_maximum_distance_between_a_pair_of_values;
2+
3+
public class Solution {
4+
5+
public int maxDistance(int[] nums1, int[] nums2) {
6+
int index1 = 0, index2 = 0, result = 0;
7+
while (index1 < nums1.length) {
8+
while (index2 < nums2.length && nums2[index2] >= nums1[index1]) {
9+
index2++;
10+
}
11+
result = Math.max(result, index2 - index1 - 1);
12+
index1++;
13+
}
14+
return result;
15+
}
16+
17+
}

‎question1856_maximum_subarray_min_product/Solution.java

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package question1856_maximum_subarray_min_product;
2+
3+
import java.util.LinkedList;
4+
5+
public class Solution {
6+
7+
public int maxSumMinProduct(int[] nums) {
8+
int[] right = new int[nums.length];
9+
LinkedList<Integer> linkedList = new LinkedList<>();
10+
for (int i = 0; i < nums.length; i++) {
11+
while (!linkedList.isEmpty() && nums[linkedList.peekLast()] > nums[i]) {
12+
right[linkedList.pollLast()] = i;
13+
}
14+
linkedList.addLast(i);
15+
}
16+
while (!linkedList.isEmpty()) {
17+
right[linkedList.pollLast()] = nums.length;
18+
}
19+
int[] left = new int[nums.length];
20+
for (int i = nums.length - 1; i >= 0; i--) {
21+
while (!linkedList.isEmpty() && nums[linkedList.peekLast()] > nums[i]) {
22+
left[linkedList.pollLast()] = i;
23+
}
24+
linkedList.addLast(i);
25+
}
26+
while (!linkedList.isEmpty()) {
27+
left[linkedList.pollLast()] = -1;
28+
}
29+
long[] sums = new long[nums.length + 1]; // sums[i] = nums[0] + ... + nums[i - 1]
30+
for (int i = 1; i < sums.length; i++) {
31+
sums[i] = sums[i - 1] + nums[i - 1];
32+
}
33+
long result = 0;
34+
for (int i = 0; i < nums.length; i++) {
35+
result = Math.max(result, nums[i] * (sums[right[i]] - sums[left[i] + 1]));
36+
}
37+
return (int) (result % 1000000007);
38+
}
39+
40+
}

‎question1860_incremental_memory_leak/Solution.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package question1860_incremental_memory_leak;
2+
3+
import java.util.Arrays;
4+
5+
public class Solution {
6+
7+
public int[] memLeak(int memory1, int memory2) {
8+
int time = 1;
9+
while (true) {
10+
if (memory1 < memory2) {
11+
// 分配给 memory2
12+
if (memory2 < time) {
13+
return new int[] {time, memory1, memory2};
14+
}
15+
memory2 -= time;
16+
} else {
17+
// 分配给 memory1
18+
if (memory1 < time) {
19+
return new int[] {time, memory1, memory2};
20+
}
21+
memory1 -= time;
22+
}
23+
time++;
24+
}
25+
}
26+
27+
}

0 commit comments

Comments
 (0)