【 NO.1 买票需要的时间】
解题思路
签到题，使用一个 LinkedList 模拟即可。
代码展示
class Solution {
public int timeRequiredToBuy(int[] tickets, int k) {
LinkedList queue = new LinkedList<>();
for (int i : tickets) {
queue.add(i);
}
int result = 0;
while (!queue.isEmpty()) {
result++;
int t = queue.pollFirst() - 1;
if (t == 0 && k == 0) {
break;
}
if (t > 0) {
queue.addLast(t);
}
k = (k - 1 + queue.size()) % queue.size();
}
return result;
}
}
【 NO.2 反转偶数长度组的节点】
解题思路
数组更有利于反转操作，可以先将链表转换成数组，操作完后再转换成链表。
代码展示
class Solution {
public ListNode reverseEvenLengthGroups(ListNode head) {
List list = new ArrayList<>();
for (ListNode i = head; i != null; i = i.next) {
list.add(i.val);
}
for (int start = 1, len = 2; start < list.size(); ) {
int end = Math.min(list.size(), start + len);
if ((end - start) % 2 == 0) {
// reverse [start, end)
for (int l = start, r = end - 1; l < r; ) {
int t = list.get(l);
list.set(l, list.get(r));
list.set(r, t);
l++;
r--;
}
}
start += len;
len++;
}
ListNode h = new ListNode(list.get(0));
ListNode cur = h;
for (int i = 1; i < list.size(); i++) {
cur.next = new ListNode(list.get(i));
cur = cur.next;
}
return h;
}
}
【 NO.3 解码斜向换位密码】
解题思路
还原出矩阵即可，最后注意将后缀空格删去。
代码展示
class Solution {
public String decodeCiphertext(String encodedText, int rows) {
int cols = encodedText.length() / rows;
char[][] mtx = new char[rows][cols];
for (int i = 0; i < encodedText.length(); i++) {
int x = i / cols;
int y = i % cols;
mtx[x][y] = encodedText.charAt(i);
}
StringBuilder sb = new StringBuilder();
for (int startY = 0; startY < cols; startY++) {
for (int x = 0, y = startY; x < rows && y < cols; x++, y++) {
sb.append(mtx[x][y]);
}
}
while (sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ') {
sb.deleteCharAt(sb.length() - 1);
}
return sb.toString();
}
}
【 NO.4 处理含限制条件的好友请求】
解题思路
并查集，详见代码注释。
代码展示
class Solution {
public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
boolean[] result = new boolean[requests.length];
// R[i] 表示不能与 i 做朋友的人
List<Set> R = new ArrayList<>();
for (int i = 0; i < n; i++) {
R.add(new HashSet<>());
}
for (var r : restrictions) {
R.get(r[0]).add(r[1]);
R.get(r[1]).add(r[0]);
}
// uf 维护间接朋友关系
UnionFind uf = new UnionFind(n);
for (int i = 0; i < requests.length; i++) {
var r = requests[i];
int f0 = uf.find(r[0]);
int f1 = uf.find(r[1]);
if (f0 == f1) { // 说明 r[0] 和 r[1] 已经是直接或间接朋友了
result[i] = true;
continue;
}
// 由于我们总是将限制关系合并到根，所以只需判断根节点即可
result[i] = !R.get(f0).contains(f1) && !R.get(f1).contains(f0);
if (result[i]) {
uf.merge(f0, f1); // merge 后 f1 将成为 根
// 原本不能与 f0 做朋友的人也不能与 f1 做朋友了
R.get(f1).addAll(R.get(f0));
for (int j : R.get(f1)) {
R.get(j).add(f1);
}
}
}
return result;
}
}
class UnionFind {
public UnionFind(int size) {
f = new int[size];
Arrays.fill(f, -1);
}
public int find(int x) {
if (f[x] < 0)
return x;
return f[x] = find(f[x]);
}
public boolean merge(int a, int b) {
int fa = find(a);
int fb = find(b);
if (fa == fb)
return false;
f[fa] = fb;
return true;
}
public Map<Integer, List> sets() {
Map<Integer, List> res = new HashMap<>();
for (int i = 0; i < f.length; i++) {
int fi = find(i);
if (!res.containsKey(fi)) {
res.put(fi, new ArrayList<>());
}
res.get(fi).add(i);
}
return res;
}
private int[] f;
}
创作新主题