上岸算法LeetCode Weekly Contest 267解题报告

上岸算法 · 发表于 2021-11-14 17:02:13

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

【 NO.1 买票需要的时间】

解题思路
签到题，使用一个 LinkedList 模拟即可。

代码展示

class Solution {
public int timeRequiredToBuy(int[] tickets, int k) {
   LinkedList<Integer> 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<Integer> 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<Integer>> 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<Integer>> sets() {
   Map<Integer, List<Integer>> 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;
}

[吹水聊天] 上岸算法LeetCode Weekly Contest 267解题报告

登录后可回复主题

浏览过的版块

帐号		自动登录	找回密码
密码			注册账号