本文最后更新于2021年10月4日,已超过 7 个月没更新!
August
08-30 按权重随机选择
🧩 二分
class Solution {
int[] pre;
int total;
public Solution(int[] w) {
int n = w.length;
pre = new int[n];
pre[0] = w[0];
for (int i = 1; i < n; ++ i) {
pre[i] = pre[i - 1] + w[i];
}
total = Arrays.stream(w).sum();
}
public int pickIndex() {
int x = (int)(Math.random() * total) + 1;
return binarySearch(x);
}
private int binarySearch(int x) {
int i = 0, j = pre.length - 1;
while (i < j) {
int mid = i + (j - i) / 2;
if (pre[mid] < x) {
i = mid + 1;
} else {
j = mid;
}
}
return i;
}
}
08-29 所有奇数长度子数组的和
🧩 前缀和
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int n = arr.length;
int[] pre = new int[n + 1];
for (int i = 1; i <= n; ++ i) {
pre[i] = pre[i - 1] + arr[i - 1];
}
int ans = 0;
for (int i = 1; i <= n; i += 2) {
for (int j = i; j <= n; ++ j) {
ans += pre[j] - pre[j - i];
}
}
return ans;
}
}
⚡ 计算一个数字在多少个奇数长度的数组中出现过
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int len = arr.length;
int n;
int sum = 0;
int leftOdd, leftEven, rightOdd, rightEven;
for (int i = 0; i < len; ++i) {
leftOdd = (i + 1) / 2;
leftEven = (i + 2) / 2;
rightOdd = (len - i) / 2;
rightEven = (len - i + 1) / 2;
n = leftEven*rightEven + leftOdd*rightOdd;
sum += arr[i] * n;
}
return sum;
}
}
08-28 一维数组的动态和
🧩 求前缀和
class Solution {
public int[] runningSum(int[] nums) {
int n = nums.length;
for (int i = 1; i < n; ++ i) {
nums[i] += nums[i - 1];
}
return nums;
}
}
08-27 数据流的中位数⭐
🧩 双堆
class MedianFinder {
Queue<Integer> q1;
Queue<Integer> q2;
/** initialize your data structure here. */
public MedianFinder() {
q2 = new PriorityQueue<>(); // 小顶堆
q1 = new PriorityQueue<>((x, y) -> y - x); // 大顶堆
}
public void addNum(int num) {
if (q1.size() > q2.size()) {
q1.offer(num);
q2.offer(q1.poll());
} else {
q2.offer(num);
q1.offer(q2.poll());
}
}
public double findMedian() {
if (q1.size() == q2.size()) {
return (double)(q1.peek() + q2.peek()) / 2;
} else {
return (double)q1.peek();
}
}
}
08-24 K站中转内最便宜的航班⭐⭐
🧩 Bellman Ford
class Solution {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
final int INF = 10000 * 101 + 1;
// f[i][j] 表示从src出发经过i次中转到达j的最小代价
int[][] f = new int[k + 2][n];
for (int i = 0; i <= k + 1; ++ i) {
Arrays.fill(f[i], INF);
}
// 核心
f[0][src] = 0;
for (int t = 1; t < k + 2; ++ t) {
for (int[] flight : flights) {
int i = flight[0], j = flight[1], cost = flight[2];
f[t][j] = Math.min(f[t][j], f[t - 1][i] + cost);
}
}
// 遍历求最小值
int ans = INF;
for (int t = 0; t < k + 2; ++ t) {
ans = Math.min(ans, f[t][dst]);
}
return ans == INF ? -1 : ans;
}
}
08-23 获取生成数组中的最大值
🧩 模拟
class Solution {
public int getMaximumGenerated(int n) {
if (n == 0) return 0;
int[] nums = new int[n + 1];
nums[1] = 1;
for (int i = 2; i <= n; ++ i) {
nums[i] = nums[i / 2] + i % 2 * nums[i / 2 + 1];
}
return Arrays.stream(nums).max().getAsInt();
}
}
08-22 逃脱阻碍者⭐
🧩 曼哈顿距离
class Solution {
public boolean escapeGhosts(int[][] ghosts, int[] target) {
int[] source = {0, 0};
int distance = manhattanDistance(source, target);
for (int[] ghost : ghosts) {
int ghostDistance = manhattanDistance(ghost, target);
if (ghostDistance <= distance) return false;
}
return true;
}
// 求曼哈顿距离
// dist(A,B) 表示 A 点和 B 点的曼哈顿距离,曼哈顿距离的计算方法如下:
// dist(A,B)= ∣xA − xB∣+∣yA − yB∣
private int manhattanDistance(int[] point1, int[] point2) {
return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
}
}
08-21 压缩字符串
🧩 前后双指针
class Solution {
public int compress(char[] chars) {
int n = chars.length;
int left = 0, write = 0;
for (int read = 0; read < n; ++ read) {
if (read == n - 1 || chars[read] != chars[read + 1]) {
chars[write] = chars[read];
++ write;
int num = read - left + 1;
if (num > 1) {
int start = write;
while (num > 0) {
chars[write++] = (char)(num % 10 + '0');
num /= 10;
}
reverse(chars, start, write - 1);
}
left = read + 1;
}
}
return write;
}
// 翻转字符串
private void reverse (char[] chars, int left, int right) {
while (left < right) {
char tmp = chars[left];
chars[left] = chars[right];
chars[right] = tmp;
++ left;
-- right;
}
}
}
08-20 反转字符串 II
class Solution {
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
int n = chars.length;
int k_2 = 2 * k;
for (int i = 0; i < n; i += k_2) {
int j = i + k - 1;
if (j < n) reverse(chars, i, j);
else reverse(chars, i, n - 1);
}
return new String(chars);
}
private void reverse(char[] chars, int left, int right) {
while (left < right) {
char tmp = chars[left];
chars[left] = chars[right];
chars[right] = tmp;
++ left;
-- right;
}
}
}
08-19 反转字符串中的元音字母
🧩 双指针
class Solution {
Set<Character> vowels = new HashSet<Character>(){{
add('a');
add('A');
add('e');
add('E');
add('i');
add('I');
add('o');
add('O');
add('u');
add('U');
}};
public String reverseVowels(String s) {
char[] chars = s.toCharArray();
int n = s.length();
int i = 0, j = n - 1;
while (i < j) {
while (i < j && !vowels.contains(chars[i])) ++ i;
while (i < j && !vowels.contains(chars[j])) -- j;
char tmp = chars[i];
chars[i] = chars[j];
chars[j] = tmp;
++ i;
-- j;
}
return new String(chars);
}
}
08-17 学生出勤记录 I
class Solution {
public boolean checkRecord(String s) {
int timeA = 0, timeL = 0;
for (char c : s.toCharArray()) {
if (c == 'A') ++ timeA;
if (c == 'L') ++ timeL;
else timeL = 0;
if (timeA >= 2) return false;
if (timeL >= 3) return false;
}
return true;
}
}
08-03 最短无序连续子数组
🧩 排序+双指针 O(nlogn)
class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int[] arr = new int[n];
System.arraycopy(nums, 0, arr, 0, n);
Arrays.sort(arr);
int i = 0, j = n - 1;
while (i <= j && nums[i] == arr[i]) ++ i;
while (j >= i && nums[j] == arr[j]) -- j;
return j + 1 - i;
}
}
🧩 双指针+线性扫描 O(n)
class Solution {
int MIN = -100005, MAX = 100005;
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int i = 0, j = n - 1;
while (i < j && nums[i] <= nums[i + 1]) ++ i;
while (j > i && nums[j] >= nums[j - 1]) -- j;
if (i == j) return 0;
int min = nums[i], max = nums[j];
int l = i, r = j;
for (int u = l; u <= r; ++ u) {
if (nums[u] < min) {
while (i >= 0 && nums[u] < nums[i]) -- i;
min = i >= 0 ? nums[i] : MIN;
}
if (nums[u] > max) {
while (j < n && nums[u] > nums[j]) ++ j;
max = j < n ? nums[j] : MAX;
}
}
return j - i - 1; // (j - 1) - (i + 1) + 1
}
}
08-02 网络延迟时间⭐⭐
🧩 Dijkstra算法
class Solution {
private final int INF = Integer.MAX_VALUE / 2;
public int networkDelayTime(int[][] times, int n, int k) {
// 预处理
int[][] g = new int[n][n];
for (int i = 0; i < n; ++ i) {
Arrays.fill(g[i], INF);
}
for (int[] t : times) {
int x = t[0] - 1, y = t[1] - 1;
g[x][y] = t[2];
}
int[] dist = new int[n];
Arrays.fill(dist, INF);
// 起点
dist[k - 1] = 0;
boolean[] used = new boolean[n];
for (int i = 0; i < n; ++ i) {
int x = -1;
// 找出当前距离起始点的最短距离点
for (int y = 0; y < n; ++ y) {
if (!used[y] && (x == -1 || dist[y] < dist[x])) {
x = y;
}
}
used[x] = true;
// 使用找到的最短距离点更新其他点
for (int y = 0; y < n; ++ y) {
dist[y] = Math.min(dist[y], g[x][y] + dist[x]);
}
}
// 遍历距离dist数组找到最大值
int ans = Arrays.stream(dist).max().getAsInt();
return ans == INF ? -1 : ans;
}
}
08-01 矩阵中战斗力最弱的 K 行
🧩 二分 + 优先队列
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {
if (x[1] == y[1]) return x[0] - y[0];
return x[1] - y[1];
});
// 二分获取每行战斗力并插入小根堆
int n = mat.length, m = mat[0].length;
for (int i = 0; i < n; ++ i) {
int l = 0, r = m - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (mat[i][mid] == 0) r = mid - 1;
else l = mid;
}
if (mat[i][l] == 0) l = -1;
pq.offer(new int[]{i, l + 1});
}
// 小根堆中获取结果
int[] ans = new int[k];
for (int i = 0; i < k; ++ i) {
ans[i] = pq.poll()[0];
}
return ans;
}
}
Pages: 1 2