每日算法-250513

每日算法 - 2024-05-13

記錄今天學習的算法題解。


2335. 裝滿杯子需要的最短總時長

題目

Problem Description

思路

貪心

這道題的關鍵在于每次操作盡可能多地減少杯子的數量。我們每次操作可以裝一杯或兩杯(不同類型)。為了最小化總時間,應該優先選擇裝兩杯不同類型的水。

解題過程

問題的最優解受到兩個因素的制約:

  1. 數量最多的那杯水:假設數量最多的水需要 max_val 杯。由于每次操作最多只能裝一杯這種類型的水,所以我們至少需要 max_val 秒才能把這種水裝完。這是一個時間的下限。
  2. 總水量:假設總水量為 total_sum = amount[0] + amount[1] + amount[2]。由于每次操作最多裝兩杯水,裝完 total_sum 杯水至少需要 ceil(total_sum / 2) 秒。這里的 ceil 表示向上取整,因為如果總數是奇數,最后一次操作只能裝一杯。在整數除法中,(total_sum + 1) / 2 可以實現向上取整的效果。這也是一個時間的下限。

最短的總時長必須同時滿足這兩個下限條件。因此,最終答案就是這兩個下限中的較大值:max(max_val, (total_sum + 1) / 2)

可以證明,總是存在一種貪心策略(例如,每次都優先選擇數量最多的兩種水來裝)可以達到這個下限。

復雜度

  • 時間復雜度: O ( 1 ) O(1) O(1)。只需要進行常數次的比較和算術運算。
  • 空間復雜度: O ( 1 ) O(1) O(1)。只需要常數級別的額外空間存儲變量。

Code

class Solution {public int fillCups(int[] amount) {// 找到數量最多的杯子數int maxVal = 0;int totalSum = 0;for (int count : amount) {maxVal = Math.max(maxVal, count);totalSum += count;}int avgOps = (totalSum + 1) / 2; return Math.max(maxVal, avgOps);}
}

1753. 移除石子的最大得分

題目

Problem Description

思路

貪心

目標是最大化操作次數(每次操作得1分)。每次操作需要從兩堆不同的非空石子堆中各取一個。為了盡可能多地進行操作,我們應該避免讓某一堆石子過早地被單獨剩下。因此,貪心策略是每次都選擇當前石子數最多的兩堆進行操作。

解題過程

為了方便分析,我們先對三堆石子的數量 a, b, c 進行排序,假設排序后為 min_val <= mid_val <= max_val

考慮貪心策略:每次都從最多的兩堆(max_valmid_val)中取石子。

分析兩種情況:

  1. max_val >= mid_val + min_val:
    在這種情況下,最大堆的石子數量大于等于另外兩堆之和。我們可以將 mid_val 堆和 min_val 堆的石子完全與 max_val 堆配對消耗完。

  2. max_val < mid_val + min_val:
    在這種情況下,最大堆的石子數不足以單獨消耗掉另外兩堆。這意味著我們可以持續地從最大的兩堆中取石子,直到所有石子幾乎被取完(最多只會剩下一個石子)。
    總石子數為 S = max_val + mid_val + min_val。每次操作減少2個石子。我們可以進行的操作次數取決于總石子數 S

    • 如果 S 是偶數,最多可以進行 S / 2 次操作,最后沒有石子剩下。
    • 如果 S 是奇數,最多可以進行 (S - 1) / 2 次操作,最后會剩下1個石子。
      這兩種情況合并起來就是 floor(S / 2) 次操作。在整數除法中,(max_val + mid_val + min_val) / 2 正好計算出 floor(S / 2)
      因此,最大得分為 (max_val + mid_val + min_val) / 2

綜合這兩種情況,即為題解。

復雜度

  • 時間復雜度: O ( 1 ) O(1) O(1)。對三個數排序(或找到最大、最小、中間值)以及后續計算都是常數時間。
  • 空間復雜度: O ( 1 ) O(1) O(1)。只需要常數級別的額外空間。

Code

class Solution {public int maximumScore(int a, int b, int c) {int max = Math.max(a, Math.max(b, c));int min = Math.min(a, Math.min(b, c));int mid = (a + b + c) - (max + min);if (max >= mid + min) {return mid + min;} else {return (max + mid + min) / 2;}}
}

2592. 最大化數組的偉大值(復習)

題目

Problem Description

這是第二次寫這道題了,典型的田忌賽馬問題,寫的還不錯,就不多說了,詳細題解可以參考之前的筆記:每日算法-250428

Code

class Solution {public int maximizeGreatness(int[] nums) {int ret = 0;Arrays.sort(nums);int left = 0, right = nums.length - 1, i = right;while (left <= right) {if (nums[i] >= nums[right]) {left++;} else {ret++;right--;}i--;}return ret;}
}

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

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

相關文章

城市生命線綜合管控系統解決方案-守護城市生命線安全

一、政策背景 國務院辦公廳《城市安全風險綜合監測預警平臺建設指南》?要求&#xff1a;將燃氣、供水、排水、橋梁、熱力、綜合管廊等納入城市生命線監測體系&#xff0c;建立"能監測、會預警、快處置"的智慧化防控機制。住建部?《"十四五"全國城市基礎…

分布式AI推理的成功之道

隨著AI模型逐漸成為企業運營的核心支柱&#xff0c;實時推理已成為推動這一轉型的關鍵引擎。市場對即時、可決策的AI洞察需求激增&#xff0c;而AI代理——正迅速成為推理技術的前沿——即將迎來爆發式普及。德勤預測&#xff0c;到2027年&#xff0c;超半數采用生成式AI的企業…

auto.js面試題及答案

以下是常見的 Auto.js 面試題及參考答案&#xff0c;涵蓋基礎知識、腳本編寫、運行機制、權限、安全等方面&#xff0c;適合開發崗位的技術面試準備&#xff1a; 一、基礎類問題 什么是 Auto.js&#xff1f;它的主要用途是什么&#xff1f; 答案&#xff1a; Auto.js 是一個…

C語言中的指定初始化器

什么是指定初始化器? C99標準引入了一種更靈活、直觀的初始化語法——指定初始化器(designated initializer), 可以在初始化列表中直接引用結構體或聯合體成員名稱的語法。通過這種方式,我們可以跳過某些不需要初始化的成員,并且可以以任意順序對特定成員進行初始化。這…

高德地圖在Vue3中的使用方法

1.地圖初始化 容器創建&#xff1a;通過 <div> 標簽定義地圖掛載點。 <div id"container" style"height: 300px; width: 100%; margin-top: 10px;"></div> 密鑰配置&#xff1a;綁定高德地圖安全密鑰&#xff0c;確保 API 合法調用。 參…

RabbitMQ發布訂閱模式深度解析與實踐指南

目錄 RabbitMQ發布訂閱模式深度解析與實踐指南1. 發布訂閱模式核心原理1.1 消息分發模型1.2 核心組件對比 2. 交換機類型詳解2.1 交換機類型矩陣2.2 消息生命周期 3. 案例分析與實現案例1&#xff1a;基礎廣播消息系統案例2&#xff1a;分級日志處理系統案例3&#xff1a;分布式…

中小型培訓機構都用什么教務管理系統?

在教育培訓行業快速發展的今天&#xff0c;中小型培訓機構面臨著學員管理復雜、課程體系多樣化、教學效果難以量化等挑戰。一個高效的教務管理系統已成為機構運營的核心支撐。本文將深入分析當前市場上適用于中小型培訓機構的教務管理系統&#xff0c;重點介紹愛耕云這一專業解…

C++虛函數食用筆記

虛函數定義與作用&#xff1a; virtual關鍵字聲明虛函數&#xff0c;虛函數可被派生類override(保證返回類型與參數列表&#xff0c;名字均相同&#xff09;&#xff0c;從而通過基類指針調用時&#xff0c;實現多態的功能 virtual關鍵字: 將函數聲明為虛函數 override關鍵…

運算放大器相關的電路

1運算放大器介紹 解釋&#xff1a;運算放大器本質就是一個放大倍數很大的元件&#xff0c;就如上圖公式所示 Vp和Vn相差很小但是放大后輸出還是會很大。 運算放大器不止上面的三個引腳&#xff0c;他需要獨立供電&#xff1b; 如圖比較器&#xff1a; 解釋&#xff1a;Vp&…

華為OD機試真題——通信系統策略調度(用戶調度問題)(2025B卷:100分)Java/python/JavaScript/C/C++/GO最佳實現

2025 B卷 100分 題型 本專欄內全部題目均提供Java、python、JavaScript、C、C++、GO六種語言的最佳實現方式; 并且每種語言均涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、3個測試用例以及綜合分析; 本文收錄于專欄:《2025華為OD真題目錄+全流程解析+備考攻略+經驗分…

Ubuntu 系統默認已安裝 python,此處只需添加一個超鏈接即可

步驟 1&#xff1a;確認 Python 3 的安裝路徑 查看當前 Python 3 的路徑&#xff1a; which python3 輸出類似&#xff1a; /usr/bin/python3 步驟 2&#xff1a;創建符號鏈接 使用 ln -s 創建符號鏈接&#xff0c;將 python 指向 python3&#xff1a; sudo ln -s /usr/b…

深度學習-分布式訓練機制

1、分布式訓練時&#xff0c;包括train.py的全部的代碼都會在每個gpu上運行嗎&#xff1f; 在分布式訓練&#xff08;如使用 PyTorch 的 DistributedDataParallel&#xff0c;DDP&#xff09;時&#xff0c;每個 GPU 上運行的進程會執行 train.py 的全部代碼&#xff0c;但通過…

yarn的介紹

### Yarn 的基本概念 Yarn 是 Hadoop 生態系統中的一個重要組成部分&#xff0c;它是一種分布式資源管理框架&#xff0c;旨在為大規模數據處理提供高效的資源管理和調度能力。以下是關于 Yarn 的一些核心概念&#xff1a; #### 1. **Yarn 的定義** Yarn 是一個資源調度平臺&a…

Spring-messaging-MessageHandler接口實現類ServiceActivatingHandler

ServiceActivatingHandler實現了MessageHandler接口&#xff0c;所以它是一個MessageHandler&#xff0c;在spring-integration中&#xff0c;它也叫做服務激活器&#xff08;Service Activitor&#xff09;&#xff0c;因為這個類是依賴spring容器BeanFactory的&#xff0c;所…

快速入門深度學習系列(2)----損失函數、邏輯回歸、向量化

針對深度學習入門新手目標不明確 知識體系雜亂的問題 擬開啟快速入門深度學習系列文章的創作 旨在幫助大家快速的入門深度學習 寫在前面&#xff1a; 本系列按照吳恩達系列課程順序發布(說明一下為什么不直接看原筆記 因為內容太多 沒有大量時間去閱讀 所有作者需要一次梳理…

KingBase問題篇

安裝環境 操作系統&#xff1a;CentOS7 CPU&#xff1a;X86_64架構 數據庫&#xff1a;KingbaseES_V008R006C009B0014_Lin64_install.iso 項目中遇到的問題 Q1. 執行sql中有字符串常量&#xff0c;且用雙引號包裹&#xff0c;執行報錯 A1. 默認KingBase不認雙引號&#xff0…

瀕危仙草的重生敘事:九仙尊米斛花節如何以雅集重構中醫藥文化IP

五月的霍山深處,層巒疊翠之間,中華仙草霍山米斛迎來一年一度的花期。九仙尊以“斛韻雅集,春野茶會”為主題,舉辦為期半月的米斛花文化節,融合中醫藥文化、東方美學與自然體驗,打造一場跨越古今的沉浸式文化盛宴。活動涵蓋古琴雅集、書法創作、茶道冥想、詩歌吟誦、民族歌舞等多…

LeetCode100.1 兩數之和

今天晚上看了許多關于未來計算機就業的視頻&#xff0c;有種正被販賣焦慮的感覺&#xff0c;翻來覆去下決定先做一遍leetcode100給自己降降溫&#xff0c;打算每周做四題&#xff0c;盡量嘗試不同的方法與不同的語言。 一開始想到的是暴力解法&#xff0c;兩層循環。數據量為1e…

python制造一個報錯

以下是用Python制造常見錯誤的示例及解析&#xff0c;涵蓋不同錯誤類型&#xff0c;便于理解調試原理&#xff1a; 一、語法錯誤 (SyntaxError) # 錯誤1&#xff1a;缺少冒號 if Trueprint("這行不會執行")# 錯誤2&#xff1a;縮進錯誤 def func(): print("未對…

idea整合maven環境配置

idea整合maven 提示&#xff1a;幫幫志會陸續更新非常多的IT技術知識&#xff0c;希望分享的內容對您有用。本章分享的是springboot的使用。前后每一小節的內容是存在的有&#xff1a;學習and理解的關聯性。【幫幫志系列文章】&#xff1a;每個知識點&#xff0c;都是寫出代碼…