文章目錄
- T1 統計已測試設備
- 代碼解釋
- T2 雙模冪運算
- 代碼解釋
- T3 統計最大元素出現至少 K 次的子數組
- 代碼解釋
- T4 統計好分割方案的數目
- 代碼解釋
鏈接:第 375 場周賽 - 力扣(LeetCode)
T1 統計已測試設備
給你一個長度為 n
、下標從 0 開始的整數數組 batteryPercentages
,表示 n
個設備的電池百分比。
你的任務是按照順序測試每個設備 i
,執行以下測試操作:
- 如果
batteryPercentages[i]
大于0
:- 增加 已測試設備的計數。
- 將下標在
[i + 1, n - 1]
的所有設備的電池百分比減少1
,確保它們的電池百分比 不會低于0
,即batteryPercentages[j] = max(0, batteryPercentages[j] - 1)
。 - 移動到下一個設備。
- 否則,移動到下一個設備而不執行任何測試。
返回一個整數,表示按順序執行測試操作后 已測試設備 的數量。
示例 1:
輸入:batteryPercentages = [1,1,2,1,3]
輸出:3
解釋:按順序從設備 0 開始執行測試操作:
在設備 0 上,batteryPercentages[0] > 0 ,現在有 1 個已測試設備,batteryPercentages 變為 [1,0,1,0,2] 。
在設備 1 上,batteryPercentages[1] == 0 ,移動到下一個設備而不進行測試。
在設備 2 上,batteryPercentages[2] > 0 ,現在有 2 個已測試設備,batteryPercentages 變為 [1,0,1,0,1] 。
在設備 3 上,batteryPercentages[3] == 0 ,移動到下一個設備而不進行測試。
在設備 4 上,batteryPercentages[4] > 0 ,現在有 3 個已測試設備,batteryPercentages 保持不變。
因此,答案是 3 。
示例 2:
輸入:batteryPercentages = [0,1,2]
輸出:2
解釋:按順序從設備 0 開始執行測試操作:
在設備 0 上,batteryPercentages[0] == 0 ,移動到下一個設備而不進行測試。
在設備 1 上,batteryPercentages[1] > 0 ,現在有 1 個已測試設備,batteryPercentages 變為 [0,1,1] 。
在設備 2 上,batteryPercentages[2] > 0 ,現在有 2 個已測試設備,batteryPercentages 保持不變。 因此,答案是 2 。
提示:
1 <= n == batteryPercentages.length <= 100
0 <= batteryPercentages[i] <= 100
代碼解釋
暴力 O(n^2)
class Solution {public int countTestedDevices(int[] batteryPercentages) {int ans = 0;int n = batteryPercentages.length;for (int i = 0; i < n; i++) {if (batteryPercentages[i] > 0) {for (int j = i + 1; j < n; j++) {batteryPercentages[j] = Math.max(0, batteryPercentages[j]-1);}ans++;}}return ans;}
}
T2 雙模冪運算
給你一個下標從 0 開始的二維數組 v a r i a b l e s variables variables ,其中 v a r i a b l e s [ i ] = [ a i , b i , c i , m i ] variables[i] = [a_i, b_i, c_i, m_i] variables[i]=[ai?,bi?,ci?,mi?],以及一個整數 target 。
如果滿足以下公式,則下標 i 是 好下標:
- 0 < = i < v a r i a b l e s . l e n g t h 0 <= i < variables.length 0<=i<variables.length
- ( ( a i b i m o d 10 ) c i ) m o d m i = = t a r g e t ((a_i^{b_i} mod~ 10)^{c_i}) ~mod~ m_i == target ((aibi??mod?10)ci?)?mod?mi?==target
返回一個由 好下標 組成的數組,順序不限 。
提示:
1 <= variables.length <= 100
variables[i] == [ai, bi, ci, mi]
1 <= ai, bi, ci, mi <= 103
0 <= target <= 103
代碼解釋
暴力 O(n(b+c))
,用 BigInteger
防止超范圍
import java.math.BigInteger;
class Solution {public List<Integer> getGoodIndices(int[][] variables, int target) {List<Integer> ans = new ArrayList<>();int n = variables.length;for (int j = 0; j < n; j++) {int[] v = variables[j];int a = v[0], b = v[1], c = v[2], m = v[3];long sum = 1;for (int i = 0; i < b; i++) {sum *= a;sum %= 10;}BigInteger s = new BigInteger(String.valueOf(sum));long t = sum;for (int i = 1; i < c; i++) {s = s.multiply(BigInteger.valueOf(t));}if (s.mod(BigInteger.valueOf(m)).intValue() == target) {ans.add(j);}}return ans;}
}
T3 統計最大元素出現至少 K 次的子數組
給你一個整數數組 nums
和一個 正整數 k
。
請你統計有多少滿足 「 nums
中的 最大 元素」至少出現 k
次的子數組,并返回滿足這一條件的子數組的數目。
子數組是數組中的一個連續元素序列。
示例 1:
輸入:nums = [1,3,2,3,3], k = 2
輸出:6
解釋:包含元素 3 至少 2 次的子數組為:[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。
示例 2:
輸入:nums = [1,4,2,1], k = 3
輸出:0
解釋:沒有子數組包含元素 4 至少 3 次。
提示:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
1 <= k <= 10^5
代碼解釋
滑動窗口,窗口內最大值剛好為 K 次時包含此窗口數組的子數組數為左長度乘右長度,用隊列記錄每個最大值的位置,多找到一個最大值,左長度向右側移動一個位置,防止左側算重復了。時間復雜度 O(n)
。
做的時候腦抽了,以為是子數組里的最大元素出現至少 K 次,沒寫出來,快結束了才發現最大值固定了。
class Solution {public long countSubarrays(int[] nums, int k) {int n = nums.length;int max = Arrays.stream(nums).max().getAsInt();Queue<Integer> queue = new LinkedList<>();int cnt = 0, l = 0, r = 0;for (int i = 0; i < n; i++) {if (nums[i] == max) {cnt++;queue.add(i);r = i;}if (cnt == k) {break;}}if (cnt < k) return 0;int pre = queue.poll();long ans = (long) (pre + 1) * (n - r);while (++r < n) {if (nums[r] == max) {queue.add(r);int t = queue.poll();ans += (long) (t - pre) * (n - r);pre = t;}}return ans;}
}
T4 統計好分割方案的數目
給你一個下標從 0 開始、由 正整數 組成的數組 nums
。
將數組分割成一個或多個 連續 子數組,如果不存在包含了相同數字的兩個子數組,則認為是一種 好分割方案 。
返回 nums
的 好分割方案 的 數目。
由于答案可能很大,請返回答案對 109 + 7
取余 的結果。
示例 1:
輸入:nums = [1,2,3,4]
輸出:8
解釋:有 8 種 好分割方案 :([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]) 和 ([1,2,3,4]) 。
示例 2:
輸入:nums = [1,1,1,1]
輸出:1
解釋:唯一的 好分割方案 是:([1,1,1,1]) 。
示例 3:
輸入:nums = [1,2,1,3]
輸出:2
解釋:有 2 種 好分割方案 :([1,2,1], [3]) 和 ([1,2,1,3]) 。
提示:
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
代碼解釋
這次最后一題也比較簡單,用一個哈希表記數的出現次數,一個哈希集合記出現的數,所有集合中的數都有了就劃分為一個組,劃分出來的所有組可以隨意組合,根據組合公式可以知道 n n n 組就有 2 n 2^n 2n 個方案數,最后用 BigInteger
防止超范圍。
import java.math.BigInteger;
class Solution {public int numberOfGoodPartitions(int[] nums) {Map<Integer, Integer> map = new HashMap<>();for (int n : nums) {map.putIfAbsent(n, 0);map.put(n, map.get(n) + 1);}int n = nums.length, cnt = 0;Set<Integer> set = new HashSet<>();for (int num : nums) {set.add(num);map.put(num, map.get(num) - 1);if (map.get(num) == 0) {set.remove(num);}if (set.isEmpty()) {cnt++;}}BigInteger ans = new BigInteger("1");BigInteger t = new BigInteger("2");BigInteger mod = new BigInteger("1000000007");for (int i = 1; i < cnt; i++) {ans = ans.multiply(t);}return ans.mod(mod).intValue();}
}