刷leetcodehot100返航版--雙指針5/16

for (int i = 0, j = 0; i < n; i ++ )
{
? ? while (j < i && check(i, j)) j ++ ;

? ? // 具體問題的邏輯
}
常見問題分類:
? ? (1) 對于一個序列,用兩個指針維護一段區間
? ? (2) 對于兩個序列,維護某種次序,比如歸并排序中合并兩個有序序列的操作

核心思想:把for i{for j}O(n^2)優化為O(n)

樸素做法——>O(n)

1.最長連續不重復子序列【看解析】

799. 最長連續不重復子序列 - AcWing題庫

e.g.12245

最長連續不重復子序列:245

一般思路:確定起止點,雙層for遍歷,比如i是終止點,j是子序列起始點;for 0~n-1 看有沒有重,計max的子序列長度

優化:在這個過程中,其實隨著i增大,j是不會往左走的,因為重復的子序列不會向左增加

也就是j其實在i遍歷過程是單調遞增的【當然也可以不增,起碼不減】,就省了j的遍歷

有一點點像:

128. 最長連續序列 - 力扣(LeetCode)

主體思路是遍歷子序列最后一個元素,判斷j是不是要往右移

其中,判斷重復與否用到的是unordered_map

#include<iostream>
#include<algorithm>//algorithm
#include<unordered_map>
using namespace std;int main(){//請找出最長的不包含重復的數的連續區間int n;cin>>n;vector<int>nums(n);for(int i = 0;i<n;i++){cin>>nums[i];}unordered_map<int,int> s;//初始化int maxNum = 0;int j = 0;//j是子序列的開頭int i;for(i = 0;i<n;i++){//i是結尾s[nums[i]]++;while(i>j){// if(s[i] != s[j]){//判斷不重復不合理if(s[nums[i]]>1){//每次其實新加的是第i個元素s[nums[j]]--;//刪除的是j對應元素j ++;}else{//沒寫break;}//沒保存max}maxNum = max(i-j+1,maxNum);}cout<<maxNum<<endl;
}

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

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

相關文章

手撕四種常用設計模式(工廠,策略,代理,單例)

工廠模式 一、工廠模式的總體好處 解耦&#xff1a;客戶端與具體實現類解耦&#xff0c;符合“開閉原則”。統一創建&#xff1a;對象創建交由工廠處理&#xff0c;便于集中控制。增強可維護性&#xff1a;新增對象種類時不需要大改動調用代碼。便于擴展&#xff1a;易于管理…

阿里通義萬相 Wan2.1-VACE:開啟視頻創作新境界

2025 年 5 月 14 日&#xff0c;阿里巴巴為視頻創作領域帶來了重磅驚喜 —— 開源通義萬相 Wan2.1-VACE。這一模型堪稱視頻生成與編輯領域的集大成者&#xff0c;憑借其全面且強大的功能&#xff0c;為廣大創作者、開發者以及企業用戶開辟了全新的視頻創作天地。它打破了以往視…

自定義類、元組、字典和結構體對比——AutoCAD C# 開發中建立不同對象之間的聯系

以下是對它們的詳細分析和對比&#xff1a; 1. 自定義類&#xff08;Class&#xff09; 優勢 封裝性強&#xff1a;可以定義字段、屬性、方法和事件&#xff0c;實現復雜的行為和邏輯。繼承與多態&#xff1a;支持繼承體系&#xff0c;可通過接口或抽象類實現多態。引用類型…

MVC架構模式

mvc架構是一種常見的開發模式,以下是三個核心部分 Model&#xff08;模型&#xff09;&#xff1a;負責應用程序的數據和業務邏輯。它與數據庫交互&#xff0c;處理數據的存儲、檢索和更新&#xff0c;是應用程序的核心業務所在。View&#xff08;視圖&#xff09;&#xff1a…

Python實例題:Python百行制作登陸系統

目錄 Python實例題 題目 python-login-systemPython 百行登錄系統腳本 代碼解釋 用戶數據庫&#xff1a; 注冊功能&#xff1a; 登錄功能&#xff1a; 主程序&#xff1a; 運行思路 注意事項 Python實例題 題目 Python百行制作登陸系統 python-login-systemPython…

uniapp使用全局組件,

在 Uniapp 中&#xff0c;如果你的組件是應用層組件&#xff08;例如全局懸浮按鈕、全局通知欄等&#xff09;&#xff0c;并且希望它自動出現在所有頁面而無需在每個頁面模板中手動添加組件標簽&#xff0c;可以通過以下兩種方案實現&#xff1a; 方案一&#xff1a;通過 app.…

(8)python開發經驗

文章目錄 1 下載python2 pip安裝依賴無法訪問3 系統支持4 下載python文檔5 設置虛擬環境6 編譯安裝python 更多精彩內容&#x1f449;內容導航 &#x1f448;&#x1f449;Qt開發 &#x1f448;&#x1f449;python開發 &#x1f448; 1 下載python 下載地址盡量不要下載最新版…

【原創】基于視覺大模型gemma-3-4b實現短視頻自動識別內容并生成解說文案

&#x1f4e6; 一、整體功能定位 這是一個用于從原始視頻自動生成短視頻解說內容的自動化工具&#xff0c;包含&#xff1a; 視頻抽幀&#xff08;可基于畫面變化提取關鍵幀&#xff09; 多模態圖像識別&#xff08;每幀圖片理解&#xff09; 文案生成&#xff08;大模型生成…

每日算法刷題計劃Day5 5.13:leetcode數組3道題,用時1h

11. 26. 刪除有序數組中的重復項(簡單&#xff0c;雙指針) 26. 刪除有序數組中的重復項 - 力扣&#xff08;LeetCode&#xff09; 思想: 1.我的思想: 雙指針遍歷集合儲存已有元素 2.官方思想&#xff1a; 題目條件有序數組刪除重復元素&#xff0c;所以重復元素都是連續存在…

Transformer 架構在目標檢測中的應用:YOLO 系列模型解析

目錄 Transformer 架構在目標檢測中的應用&#xff1a;YOLO 系列模型解析 一、YOLO 模型概述 二、YOLO 模型的核心架構 &#xff08;一&#xff09;主干網絡 &#xff08;二&#xff09;頸部結構 &#xff08;三&#xff09;頭部結構 三、YOLO 模型的工作原理 &#xf…

一個完整的項目示例:taro開發微信小程序

前一周完成了一個項目&#xff0c;體測成績轉換的工具&#xff0c;沒做記錄&#xff0c;。這次計劃開發一個地圖應用小程序&#xff0c;記錄一下。方便給使用的人。 一、申請微信小程序&#xff0c;填寫相應的信息&#xff0c;取得開發者ID。這個要給騰訊地圖使用的。 二、申…

動態規劃-LCR 166.珠寶的最大價值-力扣(LeetCode)

一、題目解析 frame二維矩陣中每個值代表珠寶的價值&#xff0c;現在從左上角開始拿珠寶&#xff0c;只能向右或向下拿珠寶&#xff0c;到達右下角時停止拿珠寶&#xff0c;要求拿的珠寶價值最大。 二、算法解析 1.狀態表示 我們想要知道的是到達[i,j]為位置時的最大價值&am…

安裝nerdctl和buildkitd腳本命令

#!/bin/bash set -euo pipefail # 檢查是否以root權限運行 if [ "$(id -u)" -ne 0 ]; then echo "錯誤&#xff1a;請使用root權限或sudo運行本腳本" >&2 exit 1 fi # 檢測openEuler系統&#xff08;兼容大小寫&#xff09; detect_distrib…

實現視頻分片上傳 OSS

訪問 OSS 有兩種方式&#xff0c;本文用到的是使用臨時訪問憑證上傳到 OSS&#xff0c;不同語言版本的代碼參考&#xff1a; 使用STS臨時訪問憑證訪問OSS_對象存儲(OSS)-阿里云幫助中心 1.安裝并使用 首先我們要安裝 OSS&#xff1a; npm install ali-oss --save 接著我們…

動態規劃(3)學習方法論:構建思維模型

引言 動態規劃是算法領域中一個強大而優雅的解題方法,但對于許多學習者來說,它也是最難以掌握的算法范式之一。與貪心算法或分治法等直觀的算法相比,動態規劃往往需要更抽象的思維和更系統的學習方法。在前兩篇文章中,我們介紹了動態規劃的基礎概念、原理以及問題建模與狀…

elementplus el-tree 二次封裝支持配置刪除后展示展開或折疊編輯復選框懶加載功能

本文介紹了基于 ElementPlus 的 el-tree 組件進行二次封裝的 TreeView 組件&#xff0c;使用 Vue3 和 JavaScript 實現。TreeView 組件通過 props 接收樹形數據、配置項等&#xff0c;支持懶加載、節點展開/收起、節點點擊、刪除、編輯等操作。組件內部通過 ref 管理樹實例&…

2025年滲透測試面試題總結-安恒[實習]安全工程師(題目+回答)

網絡安全領域各種資源&#xff0c;學習文檔&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各種好玩的項目及好用的工具&#xff0c;歡迎關注。 目錄 安恒[實習]安全工程師 一面 1. 自我介紹 2. 前兩段實習做了些什么 3. 中等難度的算法題 4. Java的C…

網絡編程中的直接內存與零拷貝

本篇文章會介紹 JDK 與 Linux 網絡編程中的直接內存與零拷貝的相關知識&#xff0c;最后還會介紹一下 Linux 系統與 JDK 對網絡通信的實現。 1、直接內存 所有的網絡通信和應用程序中&#xff08;任何語言&#xff09;&#xff0c;每個 TCP Socket 的內核中都有一個發送緩沖區…

TransmittableThreadLocal使用場景

&#x1f680; 為什么要用 TransmittableThreadLocal&#xff1f;一文讀懂線程上下文傳遞問題 在 Java Web 開發中&#xff0c;我們經常用 ThreadLocal 來保存每個請求的用戶信息&#xff0c;例如 userId。但當我們使用線程池或異步方法&#xff08;如 Async&#xff09;時&am…

Milvus(24):全文搜索、文本匹配

1 全文搜索 全文搜索是一種在文本數據集中檢索包含特定術語或短語的文檔&#xff0c;然后根據相關性對結果進行排序的功能。該功能克服了語義搜索的局限性&#xff08;語義搜索可能會忽略精確的術語&#xff09;&#xff0c;確保您獲得最準確且與上下文最相關的結果。此外&…