Skip to content

Latest commit

 

History

History
126 lines (87 loc) · 4.97 KB

05.05.02-Exercises.md

File metadata and controls

126 lines (87 loc) · 4.97 KB

05.05.02 练习题目(第 13 天)

1.1 题目大意

描述:给定两个整数数组 $nums1$$nums2$,两个数组长度都为 $n$

要求:将 $nums2$ 中的元素重新排列,使得两个数组的异或值之和最小。并返回重新排列之后的异或值之和。

说明

  • 两个数组的异或值之和:$(nums1[0] \oplus nums2[0]) + (nums1[1] \oplus nums2[1]) + ... + (nums1[n - 1] \oplus nums2[n - 1])$(下标从 $0$ 开始)。
  • 举个例子,$[1, 2, 3]$ 和 $[3,2,1]$ 的异或值之和 等于 $(1 \oplus 3) + (2 \oplus 2) + (3 \oplus 1) + (3 \oplus 1) = 2 + 0 + 2 = 4$
  • $n == nums1.length$
  • $n == nums2.length$
  • $1 \le n \le 14$
  • $0 \le nums1[i], nums2[i] \le 10^7$

示例

  • 示例 1:
输入nums1 = [1,2], nums2 = [2,3]
输出2
解释 nums2 重新排列得到 [3,2] 。
异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2
  • 示例 2:
输入nums1 = [1,0,3], nums2 = [5,3,4]
输出8
解释 nums2 重新排列得到 [5,4,3] 。
异或值之和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8

2.1 题目大意

描述:有一份由 $n$ 个问题组成的调查问卷,每个问题的答案只有 $0$$1$。将这份调查问卷分发给 $m$ 名学生和 $m$ 名老师,学生和老师的编号都是 $0 \sim m - 1$。现在给定一个二维整数数组 $students$ 表示 $m$ 名学生给出的答案,其中 $studuents[i][j]$ 表示第 $i$ 名学生第 $j$ 个问题给出的答案。再给定一个二维整数数组 $mentors$ 表示 $m$ 名老师给出的答案,其中 $mentors[i][j]$ 表示第 $i$ 名导师第 $j$ 个问题给出的答案。

每个学生要和一名导师互相配对。配对的学生和导师之间的兼容性评分等于学生和导师答案相同的次数。

  • 例如,学生答案为 $[1, 0, 1]$,而导师答案为 $[0, 0, 1]$,那么他们的兼容性评分为 $2$,因为只有第 $2$ 个和第 $3$ 个答案相同。

要求:找出最优的学生与导师的配对方案,以最大程度上提高所有学生和导师的兼容性评分和。然后返回可以得到的最大兼容性评分和。

说明

  • $m == students.length == mentors.length$
  • $n == students[i].length == mentors[j].length$
  • $1 \le m, n \le 8$
  • $students[i][k]$$0$$1$
  • $mentors[j][k]$$0$$1$

示例

  • 示例 1:
输入students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
输出8
解释按下述方式分配学生和导师- 学生 0 分配给导师 2兼容性评分为 3- 学生 1 分配给导师 0兼容性评分为 2- 学生 2 分配给导师 1兼容性评分为 3最大兼容性评分和为 3 + 2 + 3 = 8
  • 示例 2:
输入students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
输出0
解释任意学生与导师配对的兼容性评分都是 0

3.1 题目大意

描述:给定一个整数 $n$

要求:返回可以构造的「优美的排列」的数量。

说明

  • 优美的排列:假设有 $1 \sim n$$n$ 个整数。如果用这些整数构造一个数组 $perm$(下标从 $1$ 开始),使得数组第 $i$ 位元素 $perm[i]$ 满足下面两个条件之一,则该数组就是一个「优美的排列」:

    • $perm[i]$ 能够被 $i$ 整除;
    • $i$ 能够被 $perm[i]$ 整除。
  • $1 \le n \le 15$

示例

  • 示例 1:
输入n = 2
输出2
解释 1 个优美的排列是 [1,2]:
    - perm[1] = 1 能被 i = 1 整除
    - perm[2] = 2 能被 i = 2 整除
 2 个优美的排列是 [2,1]:
    - perm[1] = 2 能被 i = 1 整除
    - i = 2 能被 perm[2] = 1 整除
  • 示例 2:
输入n = 1
输出1

习题解析

  1. 1879. 两个数组最小的异或值之和」习题解析:网页链接Github 链接
  2. 1947. 最大兼容性评分和」习题解析:网页链接Github 链接
  3. 0526. 优美的排列」习题解析:网页链接Github 链接