剑指offer 面试14题
2024-09-02 07:59:55
面试14题:
题目:剪绳子
题:给你一根长度为n的绳子,请把绳子剪成m段(m,n都是整数,且n>1,m>1),每段绳子的长度记为k[0],k[1],k[2],...,k[m]。请问k[0]*k[1]*...*k[m]可能的最大乘积是多少?例如,当绳子的长度为8时,我们把它剪成长度分别为2,3,3的三段,此时得到的最大乘积为18。
解题思路:基于动态规划和贪婪算法,详见剑指offer P96
解题代码:
# -*- coding:utf-8 -*-
class Solution:
def MaxProductAfterCut(self, n):
# 动态规划
if n<2:
return 0
if n==2:
return 1
if n==3:
return 2
products=[0]*(n+1)
products[0]=0
products[1]=1
products[2]=2
products[3]=3 for i in range(4,n+1):
max=0
for j in range(1,i//2+1):
product=products[j]*products[i-j]
if product>max:
max=product
products[i]=max
#print(products)
return products[n] def MaxProductAfterCut2(self, n):
# 贪婪算法
if n < 2:
return 0
if n==2:
return 1
if n==3:
return 2
timesOf3 = n//3
if n - timesOf3*3 == 1:
timesOf3 -= 1 timesOf2 = (n - timesOf3 * 3)//2
return (3**timesOf3) * (2**timesOf2) if __name__=="__main__":
print(Solution().MaxProductAfterCut(8))
print(Solution().MaxProductAfterCut(10))
#print(Solution().NumberOf1(0))
print(Solution().MaxProductAfterCut2(8))
print(Solution().MaxProductAfterCut2(10))
最新文章
- TFS API:三、TFS WorkItem添加和修改、保存
- 连接列值 mysql CONCAT函数
- 【CITE】VS2012程序打包部署
- 转-android图片降低图片大小保持图片清晰的方法
- 强大的JQuery(一)--基础篇
- Google App Engine Deployment 相关问题
- LabVIEW系列——生产现场故障邮件通知
- [BZOJ 3942] [Usaco2015 Feb] Censoring 【KMP】
- TF31003错误的解决办法
- svn的使用--解决commit冲突问题
- hadoop集群的搭建与配置(1)
- Webdriver其他定位方式
- delphi显示hello world 和退出程序
- 页面嵌套frame,Selenium定位问题
- PhantomJS 与python的结合
- 自定义类似于Jquery UI Selectable 的Vue指令v-selectable
- 关于IIS的4月26日笔记
- 微软AD相关操作的免费工具
- python3 第二十六章 - 内置函数之Number相关
- iOS.Notification.Bar.Color
热门文章
- atitit.项目设计模式---ioc&#160;attilax总结v4&#160;q11
- 【转】jQuery.extend 函数详解
- Xcode7中你一定要知道的炸裂调试神技【转载】
- 配置LANMP环境(2)-- 安装ifconfig命令与安装SecureCRT
- Linux 总结2
- php 远程调用redis
- makefile编写---:= ?= += =的区别
- C/C++程序开发中实现信息隐藏的三种类型
- 新MBP使用git命令时启用xcode的终端log
- UTI 唯一类型标识