LeetCode 面試題14- II. 剪繩子 II

来源:https://www.cnblogs.com/izhoujie/archive/2020/05/02/12819456.html
-Advertisement-
Play Games

我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面試題14 II. 剪繩子 II 題目 給你一根長度為 n 的 ...


我的LeetCode:https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii

LeetCode 面試題14- II. 剪繩子 II

題目

給你一根長度為 n 的繩子,請把繩子剪成整數長度的 m 段(m、n都是整數,n>1並且m>1),每段繩子的長度記為 k[0],k[1]...k[m] 。請問 k[0]k[1]...*k[m] 可能的最大乘積是多少?例如,當繩子的長度是8時,我們把它剪成長度分別為2、3、3的三段,此時得到的最大乘積是18。

答案需要取模 1e9+7(1000000007),如計算初始結果為:1000000008,請返回 1。

示例 1:

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1

示例 2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 1000

註意:本題與主站 343 題相同:https://leetcode-cn.com/problems/integer-break/

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof
著作權歸領扣網路所有。商業轉載請聯繫官方授權,非商業轉載請註明出處。

解題思路

思路1-貪心演算法

首先分析貪心條件,以哪個值分割最大呢?
假如以x等值分割後乘積最大:

  • 可分割為:\(\frac{n}{x}\)段;
  • 最終乘積為:\(\left(x^{\frac{1}{x}}\right)^{n}\)

因為n為常數,去掉n後,最終公式為 \(y=x^{\frac{1}{x}}\)
即問題轉化為求\(x^{\frac{1}{x}}\)的最值問題,這需要求導解決,最終的結果為e,而e的取值為2.71828...;
因為只能整數分割,那麼,最佳值可能為2或者3,因為有:

  • \(2^{\frac{1}{2}}(約為1.41)<3^{\frac{1}{3}}(約為1.44)\)
  • 更直接的,當n取6時有:\(\left(2^{\frac{1}{2}}\right)^{6}<\left(3^{\frac{1}{3}}\right)^{6}\),即\(2^{3}<3^{2}\)

所以,3是最優解,分割的貪心規則為:

  • 優先分割為3的長度;
  • 最後剩餘的部分可能為0,1,2,其中若餘1,則需要把最後剩餘的4改為分割成2和2,畢竟\(3*1<2*2\)

此外:

  • 因為\(m>1\),即至少要分割一次,當\(n<4\)時,需要作特例判斷;
  • 因為n可能很大,中間數需要用long保存,最後再轉回int;

演算法複雜度:

  • 時間複雜度: $ {\color{Magenta}{\Omicron\left(n\right)}} $
  • 空間複雜度: $ {\color{Magenta}{\Omicron\left(1\right)}} $

演算法源碼示例

package leetcode;

/**
 * @author ZhouJie
 * @date 2020年4月30日 下午11:52:44 
 * @Description: 面試題14- II. 剪繩子 II
 *
 *
 */
public class LeetCode_Offer_14_2 {

}

class Solution_Offer_14_2 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月1日 上午12:13:23 
	 * @param: @param n
	 * @param: @return
	 * @return: int
	 * @Description: TODO
	 *
	 */
	public int cuttingRope_1(int n) {
		int mod = 1000000007;
		if (n < 4) {
			return n > 2 ? 2 : 1;
		} else {
			long rst = 1;
			while (n > 4) {
				rst = rst * 3 % mod;
				n -= 3;
			}
			return (int) (rst * n % mod);
		}
	}
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • php.ini中有個指令,include_path 包含路徑,指定一系列路徑列表,用於下麵函數尋找文件,如 require,include,fopen(),file(),readfile() and file_get_contents(). 格式類似於系統環境變數, ,Unix用冒號(colon)分 ...
  • 我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面試題15. 二進位中1的個數 與以下題目相同 前往:Leet ...
  • 我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 191. 位1的個數 題目 編寫一個函數,輸入是一個無符號整數 ...
  • QMovie,多線程,pyqt5,python3 網路上找遍了,根本不是我遇到的問題啊QAQ,之後就終止了這個項目,改做其他的了 但是之後貌似發現了一點問題的思路,供大家參考: 當一個視窗被打開多次時,就會觸發這種錯誤 當多個線程擠在一起的時候,比較常見 特別是當多線程和QMovie這個東西並行的時 ...
  • 基礎數據結構 棧(stack) 隊列 (queue) 雙端隊列 ( deque ) 順序表 與 記憶體 簡單瞭解一下記憶體 順序表 順序表的弊端:順序表的結構需要預先知道數據大小來申請連續的存儲空間,而在進行擴充時又需要進行數據的搬遷。 鏈表 (Linked list) 二叉樹 二叉樹 根節點 葉子節點 ...
  • 我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 343. 整數拆分 與以下題目相同 前往:LeetCode 面 ...
  • 我的LeetCode:https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]:https://github.com/izhoujie/Algorithmcii LeetCode 面試題14 I. 剪繩子 與以下題目相同 前往:LeetCod ...
  • 二叉樹 每個結點最多有兩個孩子,其餘結構和樹的結構一樣。 1. 二叉樹特點 二叉樹的特點有: 每個結點最多有兩棵子樹,所以二叉樹中不存在度大於2的結點。 左子樹和右子樹是有順序的,次序不能任意顛倒。 即使樹中某結點只有一棵子樹,也要區分它是左子樹還是右子樹。 二叉樹有五種基本形態: 空二叉樹; 只有 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...