Acwing 4204. 构造矩阵

请你构造一个 n×n 的整数矩阵。
要求，矩阵满足下列所有条件：

  1. 矩阵中的所有元素的取值范围为 [0,n−1]。
  2. 矩阵主对角线上的所有元素都为 0。主对角线是指从左上角到右下角这一斜线方向的对角线。
  3. 该矩阵是对称矩阵。对称矩阵是指以主对角线为对称轴，各元素对应相等的矩阵。
  4. 同一行上的所有元素两两不同。
  5. 同一列上的所有元素两两不同。

输入格式
一个整数 n。
输出格式
共 n 行，每行 n个空格隔开的整数，表示整个矩阵。
如果方案不唯一，输出任意合理方案均可。
数据范围
前三个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤1000，n 保证是偶数。
输入样例1：
2
输出样例1：
0 1 1 0
输入样例2：
4
输出样例2：
0 1 3 2
1 0 2 3
3 2 0 1
2 3 1 0

思路：
考虑n - 1行列如何构造，例如n = 4
构造3行3列得
1 2 3
2 3 1
3 1 2
将对角线元素添加到行尾和列为，并替换对角线元素为0，得
0 2 3 1
2 0 1 3
3 1 0 2
1 3 2 0
满足要求

  1. import java.util.*;
  2. import java.io.*;
  4. public class Main {
  5.     public static void main(String[] sss) throws IOException{
  6.         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  7.         Scanner sc = new Scanner(System.in);
  8.         int n = sc.nextInt();
  9.         int[][] res = new int[n][n];
  10.         for (int i = 0; i < n - 1; i++) {
  11.             for (int j = 0; j < n - 1; j++) {
  12.                 res[i][j] = (i + j) % (n - 1) + 1;
  13.             }
  14.         }
  15.         for (int i = 0; i < n - 1; i++) {
  16.             res[i][n - 1] = res[n - 1][i] = res[i][i];
  17.             res[i][i] = 0;
  18.         }
  21.         for (int i = 0; i < n; i++) {
  22.             for (int j = 0; j < n; j++)
  23.                 bw.write(res[i][j] + " ");
  24.             bw.write("\n");
  25.         }
  26.         bw.close();
  27.         // br.close();
  28.     }
  29. }

767. 重构字符串

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。
返回 s 的任意可能的重新排列。若不可行，返回空字符串 “” 。

示例 1:
输入: s = “aab” 输出: “aba”
示例 2:
输入: s = “aaab” 输出: “”

提示:

  • 1 <= s.length <= 500
  • s 只包含小写字母

思路：
构造，按字符出现次数从大到小排序，若存在cnt(c) > (n + 1) / 2，说明无解
否则，插空放即可

  1. class Solution {
  2.     public String reorganizeString(String s) {
  3.         int n = s.length();
  4.         int[][] cnt = new int[26][2];
  6.         for (int i = 0; i < s.length(); i++) {
  7.             cnt[s.charAt(i) - 'a'][0]++;
  8.         }
  9.         for (int i = 0; i < 26; i++)
  10.             cnt[i][1] = i;
  12.         Arrays.sort(cnt, (o1, o2) -> (o2[0] - o1[0]));
  13.         if (cnt[0][0] > (n + 1) / 2)
  14.             return "";
  15.         char[] res = new char[n];
  16.         Arrays.fill(res, '0');
  17.         int idx = 0;
  18.         for (int i = 0; i < 2; i++) {
  19.             int j = i;
  20.             while (j < n && cnt[idx][0] > 0) {
  21.                 res[j] = (char)(cnt[idx][1] + 'a');
  22.                 j += 2;
  23.                 cnt[idx][0]--;
  24.                 if (cnt[idx][0] == 0)
  25.                     idx++;
  26.             }
  27.         }
  28.         return new String(res);
  29.     }
  30. }

358. K 距离间隔重排字符串

给你一个非空的字符串 s 和一个整数 k ，你要将这个字符串 s 中的字母进行重新排列，使得重排后的字符串中相同字母的位置间隔距离 至少 为 k 。如果无法做到，请返回一个空字符串 “”。

示例 1：
输入: s = “aabbcc”, k = 3 输出: “abcabc” 解释: 相同的字母在新的字符串中间隔至少 3 个单位距离。
示例 2:
输入: s = “aaabc”, k = 3 输出: “” 解释: 没有办法找到可能的重排结果。
示例 3:
输入: s = “aaadbbcc”, k = 2 输出: “abacabcd” 解释: 相同的字母在新的字符串中间隔至少 2 个单位距离。

提示：

  • 1 <= s.length <= 3 * 105
  • s 仅由小写英文字母组成
  • 0 <= k <= s.length

思路：
相较于767，k = 2 -> k不定
优先队列 + 队列

  1. class Solution {
  2.     public String rearrangeString(String s, int k) {
  3.         if (k <= 1)
  4.             return s;
  5.         if (k > 26)
  6.             return "";
  8.         int[][] cnt = new int[26][2];
  9.         for (int i = 0; i < 26; i++)
  10.             cnt[i][1] = i;
  11.         int n = s.length();
  12.         for (int i = 0; i < n; i++) {
  13.             cnt[s.charAt(i) - 'a'][0] ++ ;
  14.         }
  16.         PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> (o2[0] == o1[0] ? o1[1] - o2[1] : o2[0] - o1[0]));
  17.         for (int i = 0; i < 26; i++)
  18.             if (cnt[i][0] != 0)
  19.                 q.offer(cnt[i]);
  21.         Queue<int[]> q2 = new LinkedList<>();
  23.         int sum = n;
  24.         StringBuilder sb = new StringBuilder();
  25.         while (!q.isEmpty()) {
  26.             int size = q.size();
  27.             if (size < Math.min(k, sum))
  28.                 return "";
  30.             int c = Math.min(k, sum);
  31.             sum -= c;
  32.             while (c-- > 0) {
  33.                 q2.offer(q.poll());
  34.             }
  35.             while (!q2.isEmpty()) {
  36.                 int[] u = q2.poll();
  37.                 sb.append((char)(u[1] + 'a'));
  38.                 u[0]--;
  39.                 if (u[0] > 0)
  40.                     q.offer(u);
  41.             }
  42.         }
  43.         return sb.toString();
  44.     }
  45. }
  1. // API
  2. class Solution {
  3.     public String rearrangeString(String s, int k) {
  4.         if(k <= 1)
  5.             return s;
  6.         Map<Character, Integer> map = new HashMap<>();
  8.         int n = s.length();
  9.         for (int i = 0; i < n; i++)
  10.             map.merge(s.charAt(i), 1, Integer::sum);
  12.         PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>((o1, o2) -> (o2.getValue() - o1.getValue()));
  13.         maxHeap.addAll(map.entrySet());
  14.         Queue<Map.Entry<Character, Integer>> q = new LinkedList<>();
  16.         StringBuilder sb = new StringBuilder();
  17.         while (!maxHeap.isEmpty()) {
  18.             var cur = maxHeap.poll();
  19.             sb.append(cur.getKey());
  20.             cur.setValue(cur.getValue() - 1);
  21.             q.offer(cur);
  22.             if (q.size() == k) {
  23.                 cur = q.poll();
  24.                 if (cur.getValue() > 0)
  25.                     maxHeap.offer(cur);
  26.             }
  27.         }
  28.         return sb.length() == n ? sb.toString() : "";
  29.     }
  30. }

324. 摆动排序 II