力扣第 375 場周賽(Java)

文章目錄

    • 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();}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/212752.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/212752.shtml
英文地址,請注明出處:http://en.pswp.cn/news/212752.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

JavaEE 08 線程池簡介

前言 前面我們談完了定時器,單例模式,阻塞隊列等的操作并且做了模擬實現,今天我們再來說一說線程池的操作以及一些鎖策略. 注:本章幾乎均為理論篇,實踐較少. 下面就讓我們開始吧. 線程池 我們知道因為進程的頻繁創建和銷毀,帶來的開銷過大,我們無法接受,所以我們引入了更輕量級…

Linux常見壓縮指令小結

為什么需要壓縮技術 我們都知道文件是以byte作為單位的&#xff0c;如果我們的文件僅僅在低位占一個1 0000 0001這種情況我們完全可以壓縮一下&#xff0c;將高位的0全部抹掉即可。 如上所說是一種壓縮技術&#xff0c;還有一種就是將1111(此處省略96個)一共100個1&#xff0…

mysql執行帶函數命令的sql腳本報錯

一、前言 開發給了一個帶函數的sql文件讓我執行&#xff0c;但是執行導入時報以下錯誤 This function has none of DETERMINISTIC, NO SQL, or READS SQL DATA in its declaration and binary logging is enabled 二、解決 在數據庫命令行中執行以下命令&#xff08;臨時生效&…

HarmonyOS4.0從零開始的開發教程11給您的應用添加彈窗

HarmonyOS&#xff08;十&#xff09;給您的應用添加彈窗 概述 在我們日常使用應用的時候&#xff0c;可能會進行一些敏感的操作&#xff0c;比如刪除聯系人&#xff0c;這時候我們給應用添加彈窗來提示用戶是否需要執行該操作&#xff0c;如下圖所示&#xff1a; 彈窗是一種…

AI:99-基于深度學習的飛機故障檢測與維修

?? 本文選自專欄:人工智能領域200例教程專欄 從基礎到實踐,深入學習。無論你是初學者還是經驗豐富的老手,對于本專欄案例和項目實踐都有參考學習意義。 ??? 每一個案例都附帶有在本地跑過的核心代碼,詳細講解供大家學習,希望可以幫到大家。歡迎訂閱支持,正在不斷更新…

【pycharm】Pycharm中進行Git版本控制

本篇文章主要記錄一下自己在pycharm上使用git的操作&#xff0c;一個新項目如何使用git進行版本控制。 文章使用的pycharm版本PyCharm Community Edition 2017.2.4&#xff0c;遠程倉庫為https://gitee.com/ 1.配置Git&#xff08;File>Settings&#xff09; 2.去Gitee創建…

記錄一次云原生線上服務數據遷移全過程

文章目錄 背景遷移方案調研遷移過程服務監控腳本定時任務暫停本地副本服務啟動&#xff0c;在線服務下線MySQL 數據遷移Mongo 數據遷移切換新數據庫 ip 本地服務啟動數據庫連接驗證服務打包部署服務重啟前端恢復正常監控腳本定時任務啟動舊服務器器容器關閉 遷移總結 背景 校園…

正確使用React組件緩存

簡介 正常來講的話當我們點擊組件的時候&#xff0c;該組件以及該組件的子組件都會重新渲染&#xff0c;但是如何避免子組件重新渲染呢&#xff0c;我們經常用memo來解決 React.memo配合useCallback緩存組件 父組件沒有傳props const Index ()> {console.log(子組件刷新…

Java14道高頻面試題

面試題 1、JWT ①、JWT(全稱:Json Web Token)是一個開放標準(RFC 7519),它定義了一種緊湊的、自包含的方式,用于作為 JSON 對象在各方之間安全地傳輸信息。 ②、JWT 的原理是&#xff0c;服務器認證以后&#xff0c;生成一個 JSON 對象&#xff0c;發回給用戶 ③、JWT是由頭…

機器學習基本概念介紹 2023

筆記來源于&#xff1a; https://www.youtube.com/watch?vphQK8xZpgoU&t172s https://www.youtube.com/watch?vXLyPFnephpY&t645s Machine/Deep Learning 機器學習概況來說&#xff0c;讓機器具備自動找函式的能力 &#xff08;Machine Learning 約等于 Looking …

智能優化算法應用:基于飛蛾撲火算法3D無線傳感器網絡(WSN)覆蓋優化 - 附代碼

智能優化算法應用&#xff1a;基于飛蛾撲火算法3D無線傳感器網絡(WSN)覆蓋優化 - 附代碼 文章目錄 智能優化算法應用&#xff1a;基于飛蛾撲火算法3D無線傳感器網絡(WSN)覆蓋優化 - 附代碼1.無線傳感網絡節點模型2.覆蓋數學模型及分析3.飛蛾撲火算法4.實驗參數設定5.算法結果6.…

訂單系統的設計與海量數據處理實戰

概述 訂單系統可以說是整個電商系統中最重要的一個子系統&#xff0c;因此訂單數據可以算作電商企業最重要的數據資產。訂單系統從代碼上來說可分為兩部分&#xff1a;訂單程序和歷史訂單處理程序。數據存儲進行分庫分表。 訂單系統業務分析 對于一個合格的訂單系統&#xf…

如何使用bash寫腳本

本章主要介紹如何使用bash寫腳本。 了解通配符了解變量了解返回值和數值運算數值的對比判斷語句循環語句 grep的用法是“grep 關鍵字 file”&#xff0c;意思是從file中過濾出含有關鍵字的行。 例如&#xff0c;grep root /var/log/messages&#xff0c;意思是從/var/log/me…

基于Html+騰訊云播SDK開發的m3u8播放器

周末業余時間在家無事&#xff0c;學習了一下騰訊的云播放sdk&#xff0c;并制作了一個小demo&#xff08;m3u8播放器&#xff09;&#xff0c;該在線工具是基于騰訊的云播sdk開發的&#xff0c;云播sdk非常牛&#xff0c;可以支持多種播放格式。 預覽地址 m3u8player.org 源碼…

JVM進程緩存

引言 緩存在日常開發中啟動至關重要的作用&#xff0c;由于是存儲在內存中&#xff0c;數據的讀取速度是非常快的&#xff0c;能大量減少對數據庫的訪問&#xff0c;減少數據庫的壓力。我們把緩存分為兩類&#xff1a; 分布式緩存&#xff0c;例如Redis&#xff1a; 優點&…

Mybatis之簡介、使用操作(安裝、XML、SqlSession、映射的SQL語句、命名空間、作用域和生命周期)

學習的最大理由是想擺脫平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;遲一天就多一天平庸的困擾。各位小伙伴&#xff0c;如果您&#xff1a; 想系統/深入學習某技術知識點… 一個人摸索學習很難堅持&#xff0c;想組團高效學習… 想寫博客但無從下手&#xff0c;急需…

Java項目-瑞吉外賣Day4

實現文件的上傳下載&#xff1a; 前端代碼&#xff1a; 對文件的操作就是對流的操作。 上傳文件的后端代碼&#xff0c;需要注意MultipartFile的名字必須與前端相對&#xff1a; 為文件存儲位置進行動態設置&#xff0c;配置application.xml 在CommonController中設置屬性讀…

Nodejs后端+express框架

前言 基于vue3Node后臺管理項目&#xff0c;補充nodejs和express相關知識。 文章目錄 一&#xff0c;express 1.官網 Express - 基于 Node.js 平臺的 web 應用開發框架 - Express中文文檔 | Express中文網 2.安裝 npm install express --save 二、MongoDB 特點 非關…

uniapp 藍牙小程序

在 uni-app 中開發藍牙相關的小程序涉及到使用 uni-app 提供的藍牙 API。uni-app 為多端開發提供了統一的 API&#xff0c;這意味著你編寫的代碼可以在不同的平臺上運行&#xff0c;包括微信小程序。 以下是實現藍牙功能的基本步驟和代碼示例&#xff1a; 1. 開啟藍牙適配器 …

java之SpringBoot開發實用篇

MENU SpringBoot開發實用篇KF-1.熱部署KF-1-1.手動啟動熱部署KF-1-2.自動啟動熱部署KF-1-3.參與熱部署監控的文件范圍配置KF-1-4.關閉熱部署 KF-2.配置高級KF-2-1.ConfigurationPropertiesKF-2-2.寬松綁定/松散綁定KF-2-3.常用計量單位綁定KF-2-4.校驗KF-2-5.數據類型轉換 KF-3…