文章目錄
- T1 找到兩個數組中的公共元素
- 代碼解釋
- T2 消除相鄰近似相等字符
- 代碼解釋
- T3 最多 K 個重復元素的最長子數組
- 代碼解釋
- T4 關閉分部的可行集合數目
- 代碼解釋
鏈接:第 119 場雙周賽 - 力扣(LeetCode)
T1 找到兩個數組中的公共元素
給你兩個下標從 0 開始的整數數組 nums1
和 nums2
,它們分別含有 n
和 m
個元素。
請你計算以下兩個數值:
統計 0 <= i < n
中的下標 i
,滿足 nums1[i]
在 nums2
中 至少 出現了一次。
統計 0 <= i < m
中的下標 i
,滿足 nums2[i]
在 nums1
中 至少 出現了一次。
請你返回一個長度為 2
的整數數組 answer
,按順序 分別為以上兩個數值。
示例 :
輸入:nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
輸出:[3,4]
解釋:分別計算兩個數值:
- nums1 中下標為 1 ,2 和 3 的元素在 nums2 中至少出現了一次,所以第一個值為 3 。
- nums2 中下標為 0 ,1 ,3 和 4 的元素在 nums1 中至少出現了一次,所以第二個值為 4 。
提示:
n == nums1.length
m == nums2.length
1 <= n, m <= 100
1 <= nums1[i], nums2[i] <= 100
代碼解釋
暴力 O(n^2)
class Solution {public int[] findIntersectionValues(int[] nums1, int[] nums2) {int[] ans = new int[]{0, 0};for (int k : nums1) {for (int i : nums2) {if (k == i) {ans[0]++;break;}}}for (int k : nums2) {for (int i : nums1) {if (k == i) {ans[1]++;break;}}}return ans;}
}
T2 消除相鄰近似相等字符
給你一個下標從 0 開始的字符串 word
。
一次操作中,你可以選擇 word
中任意一個下標 i
,將 word[i]
修改成任意一個小寫英文字母。
請你返回消除 word
中所有相鄰 近似相等 字符的 最少 操作次數。
兩個字符 a
和 b
如果滿足 a == b
或者 a
和 b
在字母表中是相鄰的,那么我們稱它們是 近似相等 字符。
示例 1:
輸入:word = “aaaaa”
輸出:2
解釋:我們將 word 變為 “acaca” ,該字符串沒有相鄰近似相等字符。 消除 word 中所有相鄰近似相等字符最少需要 2 次操作。
示例 2:
輸入:word = “abddez”
輸出:2
解釋:我們將 word 變為 “ybdoez” ,該字符串沒有相鄰近似相等字符。 消除 word 中所有相鄰近似相等字符最少需要 2 次操作。
示例 3:
輸入:word = “zyxyxyz”
輸出:3
解釋:我們將 word 變為 “zaxaxaz” ,該字符串沒有相鄰近似相等字符。 消除 word 中所有相鄰近似相等字符最少需要 3 次操作
提示:
1 <= word.length <= 100
word
只包含小寫英文字母。
代碼解釋
一次遍歷,相鄰近似相等字符換一次右邊的就是操作次數最少的
class Solution {public int removeAlmostEqualCharacters(String word) {int ans = 0;for (int i = 1; i < word.length(); i++) {if (Math.abs(word.charAt(i) - word.charAt(i-1)) < 2) {ans++;i++;}}return ans;}
}
T3 最多 K 個重復元素的最長子數組
給你一個整數數組 nums
和一個整數 k
。
一個元素 x
在數組中的 頻率 指的是它在數組中的出現次數。
如果一個數組中所有元素的頻率都 小于等于 k
,那么我們稱這個數組是 好 數組。
請你返回 nums
中 最長好 子數組的長度。
子數組 指的是一個數組中一段連續非空的元素序列。
示例 1:
輸入:nums = [1,2,3,1,2,3,1,2], k = 2
輸出:6
解釋:最長好子數組是 [1,2,3,1,2,3] ,值 1,2 和 3 在子數組中的頻率都沒有超過 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子數組。最長好子數組的長度為 6 。
示例 2:
輸入:nums = [1,2,1,2,1,2,1,2], k = 1
輸出:2
解釋:最長好子數組是 [1,2] ,值 1 和 2 在子數組中的頻率都沒有超過 k = 1 。[2,1] 也是好子數組。 最長好子數組的長度為 2 。
示例 3:
輸入:nums = [5,5,5,5,5,5,5], k = 4
輸出:4
解釋:最長好子數組是 [5,5,5,5] ,值 5 在子數組中的頻率沒有超過 k = 4 。 最長好子數組的長度為 4 。
提示:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length
代碼解釋
滑動窗口,哈希表記次數大于 K
時左邊界右移,時間復雜度 O(n)
class Solution {public int maxSubarrayLength(int[] nums, int k) {int ans = 0, l = 0, r = 0, n = nums.length;Map<Integer, Integer> map = new HashMap<>();while (r < n) {map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);while (map.get(nums[r]) > k) {map.put(nums[l], map.get(nums[l]) - 1);l++;}ans = Math.max(ans, ++r - l);}return ans;}
}
T4 關閉分部的可行集合數目
一個公司在全國有 n
個分部,它們之間有的有道路連接。一開始,所有分部通過這些道路兩兩之間互相可以到達。
公司意識到在分部之間旅行花費了太多時間,所以它們決定關閉一些分部(也可能不關閉任何分部),同時保證剩下的分部之間兩兩互相可以到達且最遠距離不超過 maxDistance
。
兩個分部之間的 距離 是通過道路長度之和的 最小值 。
給你整數 n
,maxDistance
和下標從 0 開始的二維整數數組 roads
,其中 roads[i] = [ui, vi, wi]
表示一條從 ui
到 vi
長度為 wi
的 無向 道路。
請你返回關閉分部的可行方案數目,滿足每個方案里剩余分部之間的最遠距離不超過 maxDistance
。
注意,關閉一個分部后,與之相連的所有道路不可通行。
注意,兩個分部之間可能會有多條道路。
提示:
1 <= n <= 10
1 <= maxDistance <= 105
0 <= roads.length <= 1000
roads[i].length == 3
0 <= ui, vi <= n - 1
ui != vi
1 <= wi <= 1000
- 一開始所有分部之間通過道路互相可以到達。
代碼解釋
這次最后一題比較簡單,就是 位運算 可以將每個節點選就是 1 不選就是 0,使用 弗洛伊德算法(Floyd) 求最短路,時間復雜度最壞為 O ( 2 n n 3 ) O(2^nn^3) O(2nn3)
class Solution {public int numberOfSets(int n, int maxDistance, int[][] roads) {int ans = 0;int[][] g = new int[n][n];for (int s = (1 << n) - 1; s >= 0; s--) {for (int i = 0; i < n; i++) {Arrays.fill(g[i], Integer.MAX_VALUE / 2);g[i][i] = 0;}for (int[] r : roads) {int u = r[0], v = r[1], w = r[2];if ((s >> u & 1) != 0 && (s >> v & 1) != 0) {g[u][v] = Math.min(g[u][v], w);g[v][u] = Math.min(g[v][u], w);}}for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);}}}int max = 0;for (int u = 0; u < n; u++) {for (int v = 0; v < n; v++) {if ((s >> u & 1) != 0 && (s >> v & 1) != 0) {max = Math.max(max, g[u][v]);}}}if (max <= maxDistance) ans++;}return ans;}
}