每日算法-250502

每日算法 - 2025.05.02

記錄一下今天刷的幾道 LeetCode 算法題。


3191. 使二進制數組全部等于 1 的最少操作次數 I

題目

Problem 3191 Description

思路

貪心

解題過程

遍歷數組 nums。當我們遇到 nums[i] 時:

  1. 如果 nums[i] 是 1,我們不需要進行操作,因為目標是全 1,并且之前的元素 [0, i-1] 已經被處理為 1(基于貪心策略)。
  2. 如果 nums[i] 是 0,我們 必須 在此時進行翻轉操作。因為這是唯一一次可以影響 nums[i] 的操作(操作窗口是 [i, i+1, i+2])。任何后續的操作都無法再將 nums[i] 從 0 變為 1。因此,我們翻轉 nums[i], nums[i+1], nums[i+2],并增加操作計數。

我們只遍歷到 n-3,因為操作需要三個連續的元素。當循環結束后,我們需要檢查最后兩個元素 nums[n-2]nums[n-1]。由于我們無法再對它們執行翻轉操作(沒有足夠的后續元素形成長度為 3 的窗口),它們必須已經是 1。如果其中任何一個是 0,則無法完成目標,返回 -1。否則,返回累計的操作次數。

復雜度

  • 時間復雜度: O(N),其中 N 是數組的長度,我們只需要遍歷數組一次。
  • 空間復雜度: O(1),我們只使用了常數級別的額外空間。

Code

class Solution {public int minOperations(int[] nums) {int n = nums.length;int ret = 0;for (int i = 0; i <= n - 3; i++) {if (nums[i] == 0) {nums[i] = 1;nums[i + 1] = 1 - nums[i + 1];nums[i + 2] = 1 - nums[i + 2];ret++;}}if (nums[n - 2] == 0 || nums[n - 1] == 0) {return -1;}return ret;}
}

1827. 最少操作使數組遞增

題目

Problem 1827 Description

思路

貪心

解題過程

我們要使數組嚴格遞增,并且操作次數最少。我們可以從左到右遍歷數組,比較相鄰的兩個元素 nums[i]nums[i+1]

  1. 如果 nums[i] < nums[i+1],數組在 ii+1 之間已經是嚴格遞增的,我們不需要做任何操作。
  2. 如果 nums[i] >= nums[i+1],為了滿足嚴格遞增的要求,nums[i+1] 必須至少增加到 nums[i] + 1。為了使操作次數最少,我們選擇將其恰好增加到 nums[i] + 1。增加的操作次數是 (nums[i] + 1) - nums[i+1]。同時,我們需要更新 nums[i+1] 的值為 nums[i] + 1,以便后續的比較基于更新后的值。

累加所有操作次數即可。

復雜度

  • 時間復雜度: O(N),其中 N 是數組的長度,我們只需要遍歷數組一次。
  • 空間復雜度: O(1),我們是在原地修改數組(或者可以只用一個變量記錄前一個元素的值),只使用了常數級別的額外空間。

Code

class Solution {public int minOperations(int[] nums) {int n = nums.length;int ret = 0;for (int i = 0; i < n - 1; i++) {if (nums[i] >= nums[i + 1]) {ret += nums[i] + 1 - nums[i + 1];nums[i + 1] = nums[i] + 1;}}return ret;}
}

2027. 轉換字符串的最少操作次數

題目

Problem 2027 Description

思路

貪心

解題過程

我們需要將字符串中的所有 ‘X’ 轉換成 ‘O’,每次操作可以連續轉換 3 個字符。目標是使用最少的操作次數。

我們可以從左到右遍歷字符串 s

  1. 如果當前字符 s[i] 是 ‘O’,它已經滿足條件,我們不需要操作,直接看下一個字符 s[i+1]
  2. 如果當前字符 s[i] 是 ‘X’,我們必須執行一次操作來轉換它。根據貪心策略,這次操作應該盡可能地覆蓋更多的 ‘X’。由于操作固定影響 s[i], s[i+1], s[i+2] 這三個字符,我們執行一次操作,將這三個字符(無論它們原來是 ‘X’ 還是 ‘O’)都視為已處理(邏輯上變成 ‘O’),然后將索引 i 直接增加 3(即跳過 i+1i+2),因為這三個位置都已經被這次操作覆蓋了。操作次數加 1。

遍歷結束后,累計的操作次數就是最少次數。

復雜度

  • 時間復雜度: O(N),其中 N 是字符串的長度。雖然我們可能會跳過字符 (i += 2),但每個字符最多被訪問一次。
  • 空間復雜度: O(N)(如果使用 toCharArray())或 O(1)(如果直接操作字符串索引)。Java 中字符串是不可變的,toCharArray() 會創建字符數組副本,空間復雜度為 O(N)。如果語言支持原地修改或僅通過索引訪問,則可以是 O(1)

Code

class Solution {public int minimumMoves(String ss) {char[] s = ss.toCharArray();int n = s.length;int ret = 0;for (int i = 0; i < n; /* i 在循環內部更新 */) {// 如果當前字符是 'X'if (s[i] == 'X') {// 需要一次操作ret++;// 這次操作覆蓋了 i, i+1, i+2,所以下次從 i+3 開始檢查i += 3; } else {// 如果當前字符是 'O',直接檢查下一個字符i++;}}return ret;}
}

注意:原代碼中 i += 2; 配合 for 循環的 i++ 實際上是 i += 3 的效果,這里修改為在 if 塊內直接 i += 3else 塊內 i++,更清晰地表達了邏輯。


3397. 執行操作后不同元素的最大數量 (復習)

題目

Problem 3397 Description

這是第二次做這道題了,已經算是掌握了。核心思想是貪心地調整每個數的值,以最大化不同元素的數量。

詳細題解見之前的博客:每日算法-250427,里面還有點小優化。

Code

class Solution {public int maxDistinctElements(int[] nums, int k) {Arrays.sort(nums);int ret = 1;nums[nums.length - 1] += k;for (int i = nums.length - 2; i >= 0; i--) {nums[i] = Math.max(Math.min(nums[i] + k, nums[i + 1] - 1), nums[i] - k);if (nums[i] < nums[i + 1]) {ret++;}}return ret;}
}

2476. 二叉搜索樹最近節點查詢 (復習)

題目

Problem 2476 Description

這道題也是復習,核心思路已經掌握。主要步驟是:

  1. 通過 中序遍歷 將二叉搜索樹(BST)轉換為一個 有序數組
  2. 對于每個查詢值 k,在有序數組中使用 二分查找 來找到 min_i (小于等于 k 的最大值) 和 max_i (大于等于 k 的最小值)。

二分查找細節:
通常使用二分查找找到第一個大于等于 k 的元素的索引 idx

  • max_i 就是 nums[idx](如果 idx 沒越界)。如果 idx 越界,說明 k 比所有元素都大,max_i 為 -1。
  • min_i
    • 如果 nums[idx] == k,則 min_i = k
    • 如果 nums[idx] > k,則 min_iidx 前一個元素 nums[idx-1](如果 idx > 0)。如果 idx == 0,說明 k 比所有元素都小,min_i 為 -1。
    • 如果 idx 越界(即 k 比所有元素都大),min_i 是數組最后一個元素 nums[n-1]

詳細題解見之前的博客:每日算法-250413

Code

class Solution {public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {List<Integer> arr = new ArrayList<>();rootToList(root, arr);int len = arr.size();int[] nums = new int[len];ListToArray(nums, arr);int n = queries.size();int min = 0, max = 0;List<List<Integer>> ret = new ArrayList<>(n);for (int i = 0; i < n; i++) {List<Integer> tmp = new ArrayList<>();int k = queries.get(i);int index = search(nums, k);if (index >= len) {max = -1;min = nums[len - 1];} else {min = index == 0 ? -1 : nums[index - 1];if (nums[index] == k) {min = nums[index];}max = nums[index];}tmp.add(min);tmp.add(max);ret.add(tmp);}return ret;}private void rootToList(TreeNode root, List<Integer> arr) {if (root == null) {return;}rootToList(root.left, arr);arr.add(root.val);rootToList(root.right, arr);}private void ListToArray(int[] nums, List<Integer> arr) {for (int i = 0; i < nums.length; i++) {nums[i] = arr.get(i);}}private int search(int[] nums, int k) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < k) {left = mid + 1;} else {right = mid - 1;}}return left;}
}

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

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

相關文章

移動端開發中設備、分辨率、瀏覽器兼容性問題

以下是針對移動端開發中設備、分辨率、瀏覽器兼容性問題的 系統化解決方案&#xff0c;按開發流程和技術維度拆解&#xff0c;形成可落地的執行步驟&#xff1a; 一、基礎環境適配&#xff1a;從「起點」杜絕兼容性隱患 1. Viewport 元標簽標準化 <meta name"viewpor…

2025最新AI繪畫系統源碼 - 畫圖大模型/GPT-4全支持/AI換臉/自定義智能體

在AI繪畫技術日新月異的2025年&#xff0c;比象AI繪畫系統源碼以其突破性的技術創新重新定義了數字藝術創作的邊界。作為第四代AI繪畫引擎&#xff0c;我們不僅集成了最先進的GPT-4o多模態畫圖模型&#xff0c;實現了從基礎文生圖到專業級藝術創作的全面進化。本系統源碼經過多…

構造函數詳解

構造函數的作用 構造函數的主要任務是初始化對象&#xff0c;而不是創建對象&#xff08;對象的內存空間在構造函數被調用前已經分配好&#xff09;。 構造函數特性 命名規則&#xff1a;函數名必須與類名完全相同。 返回值&#xff1a;構造函數沒有返回值類型&#xff08;連…

jaffree 封裝ffmpeg 轉換視頻格式,獲取大小,時間,封面

下載 參考網址 【收藏級教程】FFmpeg音視頻處理寶典&#xff1a;從入門到精通的50個實用技巧_ffmpeg教程-CSDN博客 配置環境變量 驗證 重啟idea開發工具 springboot maven集成 <dependency><groupId>com.github.kokorin.jaffree</groupId><artifactId&…

2505C++,wmi客戶端示例

原文 #define _WIN32_DCOM #include <iostream> using namespace std; #include <comdef.h> #include <Wbemidl.h> #pragma comment(lib, "wbemuuid.lib") int main(int argc, char **argv) {HRESULT hres;//初化COM.hres CoInitializeEx(0, CO…

[面試]SoC驗證工程師面試常見問題(三)

SoC驗證工程師面試常見問題(三) 在 SoC 驗證工程師的面試中,面試官可能會要求候選人現場編寫 SystemVerilog、UVM (Universal Verification Methodology) 或 SystemC 代碼,以評估其編程能力、語言掌握程度以及解決實際驗證問題的能力。這種隨機抽題寫代碼的環節通常…

HTML5+JavaScript實現連連看游戲之二

HTML5JavaScript實現連連看游戲之二 以前一篇&#xff0c;見 https://blog.csdn.net/cnds123/article/details/144220548 連連看游戲連接規則&#xff1a; 只能連接相同圖案&#xff08;或圖標、字符&#xff09;的方塊。 連線路徑必須是由直線段組成的&#xff0c;最多可以有…

《深入淺出Git:從版本控制原理到高效協作實戰》?

Git的原理和使用 1、Git初識與安裝2、Git基本操作2.1、創建Git本地倉庫2.2、配置Git2.3、認識工作區、暫存區、版本庫2.4、修改文件2.5、版本回退2.6、撤銷修改2.7、刪除文件 3、Git分支管理3.1、理解分支3.2、創建、切換、合并分支3.3、刪除分支3.4、合并沖突3.5、合并模式3.6…

數據分析_問題/優化

1 報表開發 1.1 數據問題 (1) 數據易錯 問題描述 ①數據整合困難:數據來源多樣、格式差異大,整合時處理不當易丟錯數據. ②計算邏輯復雜:開發人員對復雜計算邏輯的理解產生偏差,會導致計算結果不準. 解決方案 ①建立數據標準,統一修正字段命名、數據類型、日期格式等 ②加強…

“深入剖析ThreadLocal原理:從多線程數據隔離到內存泄漏防范“

1.在沒有ThreadLocal遇到的問題&#xff1a; 在多線程編程領域&#xff0c;多個線程同時訪問同一個變量時&#xff0c;數據一致性成為關鍵挑戰。為防止修改數據時出現覆蓋問題&#xff0c;傳統解決方案是采用加鎖機制&#xff0c;讓線程排隊依次訪問共享變量。然而&#xff0c…

讀懂 Vue3 路由:從入門到實戰

在構建現代化單頁應用&#xff08;SPA&#xff09;時&#xff0c;Vue3 憑借其簡潔高效的特性成為眾多開發者的首選。 而 Vue3 路由&#xff08;Vue Router&#xff09;則是 Vue3 生態中不可或缺的一部分&#xff0c;它就像是單頁應用的 “導航地圖”&#xff0c;幫助用戶在不同…

Mac M1安裝 Docker Desktop 后啟動沒反應

Mac M1安裝 Docker Desktop 后啟動沒反應 如果在 Mac M1 上安裝 Docker&#xff0c;那最好的選擇是安裝 Docker Desktop但是今天重新安裝 Docker Desktop 后&#xff0c;發現點擊圖標啟動怎么也沒反應&#xff0c;經過排查后發現換個版本安裝就好了&#xff0c;可能是最新的版…

快速上手c語言

快速上手c語言 快速上手c語言關于學c語言的一些信息雜談第一個C語言程序通過命令行運行c程序Dev-c5.11Visual Studio系列產品 數據類型變量、常量定義變量的方法變量的命名變量的分類變量的使用變量的作用域和生命周期常量 操作符簡單介紹語句選擇語句循環語句 數組數組定義數組…

Nginx核心功能及正則表達

目錄 一&#xff1a;正向代理 1&#xff1a;編譯安裝nginx &#xff08;1&#xff09;安裝支持軟件 &#xff08;2&#xff09;創建運行用戶、組和日志目錄 &#xff08;3&#xff09;編譯安裝nginx &#xff08;4&#xff09;添加nginx系統服務 2&#xff1a;配置正向代…

npm命令介紹(Node Package Manager)(Node包管理器)

文章目錄 npm命令全解析簡介基礎命令安裝npm&#xff08;npm -v檢插版本&#xff09;初始化項目&#xff08;npm init&#xff09;安裝依賴包&#xff08;npm install xxx、npm i xxx&#xff09;卸載依賴包&#xff08;npm uninstall xxx 或 npm uni xxx、npm remove xxx&…

【Linux】Linux基礎概念

一些比較重要的使用Linux的前情提要。 部分經驗來源于網絡&#xff0c;若有侵權請聯系我刪除&#xff0c;主要是做筆記的時候忘記寫來源了&#xff0c;做完筆記很久才寫博客。 專欄目錄&#xff1a;記錄自己的嵌入式學習之路-CSDN博客 目錄 1 Shell命令參數 2 系統變量…

阿里開源Qwen3:大語言模型的新突破

一、模型概覽&#xff1a;豐富的模型家族 Qwen3 系列包含了 2 款混合專家&#xff08;MoE&#xff09;模型與 6 款密集&#xff08;Dense&#xff09;模型&#xff0c;參數量覆蓋范圍極廣&#xff0c;從 0.6B 一直延伸至 235B 。其中&#xff0c;旗艦模型 Qwen3 - 235B - A22B…

數字智慧方案5856丨智慧環保綜合解決方案(50頁PPT)(文末有下載方式)

資料解讀&#xff1a;智慧環保綜合解決方案 詳細資料請看本解讀文章的最后內容。 隨著城市化進程的加速和環境問題的日益嚴峻&#xff0c;智慧環保成為提升城市環境管理水平的重要手段。本文將對智慧環保綜合解決方案進行詳細解讀&#xff0c;探討其在實際應用中的需求、解決…

基于ssm的網盤管理系統(全套)

一、系統架構 前端&#xff1a;vue | element-ui 后端&#xff1a;spring | springmvc | mybatis 環境&#xff1a;jdk1.8 | mysql | maven | tomcat | nodejs 二、代碼及數據庫 三、功能介紹 01. 注冊 02. 登錄 03. 管理員-首頁 04. 管理員-個人中心 …

PostgreSQL 的 VACUUM 與 VACUUM FULL 詳解

PostgreSQL 的 VACUUM 與 VACUUM FULL 詳解 一、基本概念對比 特性VACUUMVACUUM FULL定義常規維護操作&#xff0c;清理死元組激進重組操作&#xff0c;完全重寫表數據鎖級別不阻塞讀寫(共享鎖)排他鎖(阻塞所有操作)空間回收只標記空間為可用&#xff0c;不返還OS空間返還操作…