01. 數組篇(進行中......)

?一. 前綴和技巧

(1)前綴和

前綴和技巧適用于快速、頻繁地計算一個索引區間內的元素之和。?

class NumArray {
public:vector<int> preSum; //前綴和數組NumArray(vector<int>& nums) {//preSum[0] = 0,便于計算累加和preSum.resize(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++){preSum[i + 1] = preSum[i] + nums[i];}}int sumRange(int left, int right) {// 查詢閉區間 [left, right] 的累加和return preSum[right + 1] - preSum[left];}
};

(2)前綴和+哈希表

前綴和數組幫你快速計算子數組的元素之和,但如果讓你尋找某個符合條件的子數組,怎么辦?比方說,讓你在?nums?中尋找和為?target?的子數組,就算有前綴和數組的幫助,你也要寫個嵌套 for 循環。但我們可以借助哈希表記錄每個前綴和對應的索引,這樣就能快速計算目標和為?target?的子數組了?

class Solution {
public:int findMaxLength(vector<int>& nums) {int len = 0;vector<int> preSum(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++)preSum[i+1] = preSum[i] + (nums[i] == 0 ? -1 : 1);// 前綴和到索引的映射,方便快速查找所需的前綴和unordered_map<int, int> umap;for(int i = 0; i < preSum.size(); i++){// 如果這個前綴和還沒有對應的索引,說明這個前綴和第一次出現,記錄下來if(umap.find(preSum[i]) == umap.end()) umap[preSum[i]] = i;else len = max(len, i - umap[preSum[i]]);}return len;}
};

class Solution {
public:bool checkSubarraySum(vector<int>& nums, int k) {vector<int>preSum(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++)preSum[i + 1] = preSum[i] + nums[i];unordered_map<int, int> umap;// 尋找 i, j 使得 (preSum[i] - preSum[j]) % k == 0 且 i - j >= 2// (preSum[i] - preSum[j]) % k == 0 其實就是 preSum[i] % k == preSum[j] % kfor(int i = 0; i < preSum.size(); i++){auto it = umap.find(preSum[i] % k);if(it == umap.end()) umap[preSum[i] % k] = i;else if ((i - it->second) >=2) return true;}return false;}
};

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int ans = 0;vector<int> preSum(nums.size() + 1, 0);for(int i = 0; i < nums.size(); i++){preSum[i + 1] = preSum[i] + nums[i];}// 尋找 i, j 使得 preSum[i] - preSum[j] == k, i > j// nums = [1,2,3], k = 3, preSum = [0,1,3,6]unordered_map<int, int> umap;for(int i = 0; i < preSum.size(); i++){if(umap.find(preSum[i] - k) != umap.end()) ans += umap[preSum[i] - k]; // 該語句必須放在前面if(umap.find(preSum[i]) == umap.end()) umap[preSum[i]] = 1;else umap[preSum[i]]++;}return ans;}
};

??

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

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

相關文章

Qt圖形編輯類使用總結—正在編輯中

Qt的圖形編輯通常會涉及以下三個類:QGraphicsView類、QGraphicsScene類及QGraphicsItem類。 QGraphicsView 是構建復雜圖形用戶界面的強大工具,尤其適用于那些需要動態更新、可交互的2D圖形化應用程序,如圖表繪制、流程圖編輯器、游戲地圖顯示等等。通過結合使用 QGraphics…

Spring中的工廠模式詳解及應用示例

1. Spring中的BeanFactory BeanFactory是一個接口&#xff0c;表示它是一個工廠&#xff0c;負責生產和管理bean。在Spring中&#xff0c;BeanFactory是IOC容器的核心接口&#xff0c;定義了管理Bean的通用方法&#xff0c;如 getBean 和 containsBean。 BeanFactory與IOC容器…

Python編程:如何有效等待套接字的讀取與關閉

背景介紹 網絡編程是現代應用程序開發的重要組成部分&#xff0c;尤其是在大數據和實時通信的背景下。套接字&#xff08;Socket&#xff09;作為網絡通信的核心技術&#xff0c;是開發網絡應用程序的基礎。在Python編程中&#xff0c;如何有效地等待套接字的讀取與關閉事件是…

柔性測斜儀:監測鉆孔位移的核心利器

柔性測斜儀&#xff0c;作為一款創新的測量工具&#xff0c;憑借其卓越的設計與性能&#xff0c;在地下建筑、橋梁、隧道及水利水電工程等領域展現出非凡的應用價值。其安裝便捷、操作簡便、高精度及長壽命等特性&#xff0c;使之成為監測鉆孔垂直與水平位移的理想選擇。以下是…

算力共享,分布式大模型是什么,模型并行,流水線并行

目錄 算力共享,分布式大模型是什么 一、算力共享 二、分布式大模型 AllReduce是什么 原理概述 具體原理 簡單例子 模型并行,流水線并行是什么 模型并行 流水線并行 環形通信(如Ring AllReduce)、樹形通信(如Tree AllReduce 環形通信(Ring AllReduce) 樹形通…

【ComfyUI的API接口調用示例】

ComfyUI的API接口調用示例 本文目的 本文調用接口示例主要指導需要調用ComfyUI的開發者如何調用ComfyUI官方的API接口提交任務、查詢歷史、獲取繪畫視頻結果等。 閱讀本文的前提是你本地已經安裝了ComfyUI&#xff0c;并且對工作流繪畫和生成視頻已經有所了解。注意如圖右邊欄…

arm架構安裝chrome

在ARM架構設備上安裝谷歌軟件或應用通常涉及到幾個步驟&#xff0c;這取決于你要安裝的具體谷歌產品&#xff0c;比如谷歌瀏覽器、Google Play服務或者是其他谷歌開發的軟件。下面我會給出一些常見的指導步驟&#xff0c;以安裝谷歌瀏覽器為例&#xff1a; 在Linux ARM64上安裝…

常用的三角函數公式

sin ? 2 x cos ? 2 x 1 \sin ^2 x \cos ^2 x 1 sin2xcos2x1 tan ? x sin ? x cos ? x \tan x \dfrac{\sin x}{\cos x} tanxcosxsinx? cot ? x 1 tan ? x cos ? x sin ? x \cot x \dfrac{1}{\tan x}\dfrac{\cos x}{\sin x} cotxtanx1?sinxcosx? sec …

零基礎做項目---五子棋對戰---day02

用戶模塊 完成注冊登錄&#xff0c;以及用戶分數管理~使用數據庫來保存上述用戶信息. 使用 MyBatis來連接并操作數據庫了 主要步驟: 1.修改 Spring的配置文件,使數據庫可以被連接上. 2.創建實體類&#xff0c;用戶, User 3.創建Mapper接口~ 4.實現MyBatis 的相關xml配置…

MySQL安全值守常用語句

一、用戶權限設置 1、Mysql中用戶是如何定義的 用戶名主機域 10.0.0.5110.0.0.%%10.0.0.0/255.255.255.0Db01Localhost127.0.0.1 2、用戶創建 create user xinjing% identified by 123 3、用戶刪除 drop user username&#xff1b;username 是要刪除的用戶名:如 drop user root…

GDidees CMS v3.9.1 本地文件泄露漏洞(CVE-2023-27179)

前言 CVE-2023-27179 是一個影響 GDidees CMS v3.9.1 及更低版本的任意文件下載漏洞。這個漏洞存在于 /_admin/imgdownload.php 文件中&#xff0c;攻擊者可以通過向 filename 參數傳遞惡意輸入來下載服務器上的任意文件。 漏洞的根源在于對用戶輸入的 filename 參數處理不當…

【C++修行之道】string類練習題

目錄 387. 字符串中的第一個唯一字符 125. 驗證回文串 917. 僅僅反轉字母 415. 字符串相加&#xff08;重點&#xff09; 541. 反轉字符串 II 387. 字符串中的第一個唯一字符 字符串中的第一個唯一字符 - 力扣&#xff08;LeetCode&#xff09; 給定一個字符串 s &#…

中霖教育怎么樣?稅務專業可以考哪些證書?

在稅務專業領域&#xff0c;專業技能的認證對職業發展至關重要。以下為稅務專業相關可以考的證書&#xff1a; 1. 注冊稅務師資格證書&#xff1a;該證書是稅務專業人士的關鍵資質&#xff0c;使持證者可以從事稅務相關工作。 2. 會計職稱證書&#xff1a;會計系列證書分為初…

Linux 安裝 docker-compose

安裝 docker安裝 安裝docker-compose github安裝 版本查詢 地址: github地址 選擇自己想要安裝的版本 修改以下語句版本號 curl -L https://github.com/docker/compose/releases/download/1.27.4/docker-compose-$(uname -s)-$(uname -m) -o /usr/local/bin/docker-compo…

筆記本系統

筆記本更新升級 筆記本購入太早&#xff0c;所用內存只有4G&#xff0c;通過更好內存條升級系統性能 查看電腦支持內存大小 cmd命令輸入wmic memphysical get maxcapacity 這串數字就是電腦最大支持內存數值&#xff0c;做除法除兩次1024&#xff01;&#xff0c;得出來的…

查看oracle ojdbc所支持的JDBC驅動版本

oracle jcbc驅動的下載地址參考&#xff1a;JDBC and UCP Downloads page 其實上文中對ojdbc所支持的JDBC驅動版本已經有說明了&#xff0c;不過&#xff0c;因為oracle的驅動包很多時間&#xff0c;都是在公司內部私服里上傳維護的&#xff0c;上傳的時候&#xff0c;可能又沒…

flutter 實現AppStore左右滑動

在AppStore中如何實現左右滑動&#xff0c;因為使用PageView會居中顯示&#xff0c;不會居左顯示&#xff0c;目前沒有找到解決方案&#xff0c;我使用的方案是ListView自定義physics實現的。 代碼 SizedBox(width: 200,height: 400,child: ListView.builder(scrollDirection:…

Java中實現二維數組(矩陣)的轉置

在矩陣運算中&#xff0c;矩陣的轉置是一個基本操作&#xff0c;即將矩陣的行變成列&#xff0c;列變成行。在Java中&#xff0c;我們可以通過編寫一個方法來實現二維數組的轉置。下面&#xff0c;我將詳細介紹如何在Java中完成這一任務&#xff0c;并提供完整的代碼示例。 編…

鴻蒙語言基礎類庫:【@ohos.util.TreeSet (非線性容器TreeSet)】

非線性容器TreeSet 說明&#xff1a; 本模塊首批接口從API version 8開始支持。后續版本的新增接口&#xff0c;采用上角標單獨標記接口的起始版本。開發前請熟悉鴻蒙開發指導文檔&#xff1a;gitee.com/li-shizhen-skin/harmony-os/blob/master/README.md點擊或者復制轉到。 T…

HDFS 塊重構和RedundancyMonitor詳解

文章目錄 1. 前言2 故障塊的重構(Reconstruct)2.1 故障塊的狀態定義和各個狀態的統計信息2.2 故障文件塊的查找收集2.5.2.1 misReplica的檢測2.5.2.2 延遲隊列(postponedMisreplicatedBlocks)的構造和實現postponedMisreplicatedBlocks中Block的添加postponedMisreplicatedBloc…