一道快手的算法面试题,没想到对数学要求还蛮高的!

栏目: IT技术 · 发布时间: 4年前

内容简介:今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题14.I 剪绳子。根据统计,近期出现在快手的算法面试环节,属于中等难度,需要一定的数学功底。题目链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

本文约1500字,阅读大概需要8分钟

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题14.I 剪绳子。根据统计,近期出现在快手的算法面试环节,属于中等难度,需要一定的数学功底。

题目链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

题目描述

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例1

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例2

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

题目解析

一、数学推导法

设绳子长度为,总共拆分为段,每一段的长度均为,请问 每一段的长度为多少时,乘积最大呢?

设绳子的长度为,且切分为段,则得到的乘积为(这里我们假设每一段的长度均为,则这道题目就转化为一个求函数  关于的一个最大值问题,稍微翻一下大学课本里的高等数学书中求导相关的内容,接着看;

对函数两边同时取对数:

上式两边对求导,注意,得:

一道快手的算法面试题,没想到对数学要求还蛮高的!

于是

令,则,则;

即,当每一段绳子的长度取时,乘积取得最大值,但是每一段绳子的长度只能取整数,到底是取 2 好 还是取 3 好呢?

当时,等分的话,可以是,也可以是  ,乘积则分别对应和,显然  ,所以当然是取 3 好了。

也就是说对于长度为的绳子,我们尽可能以每一段为 3 进行分割,得到的乘积最大。

当绳子的长度时,也就两种情况(因为题目中绳子的长度要求是:

  1. ,只能拆为,乘积为 1 ;

  2. ,只能拆为,乘积为 2 ;

一道快手的算法面试题,没想到对数学要求还蛮高的!

当绳子的长度时,我们就可以直接用对 3 进行求余运算,设商数为,余数为,即,其中余数又分为三种情况进行处理:

  1. 余数,此时直接返回即为最大的乘积,比如是,最大乘积为;时,最大乘积为;整除的情况都是如此。

  2. 余数,此时直接返回是不对的,为什么呢?因为

    所以当时,而是返回. 比如,最大乘积为;当,最大乘积为;

  3. 余数, 此时直接返回即可。比如,最大乘积为;当,最大乘积为。

一道快手的算法面试题,没想到对数学要求还蛮高的!

实现代码

class Solution {
    public int cuttingRope(int n) {
        if(n <= 3){
            return n-1;
        }
        int a = n / 3;
        int b = n % 3;
        if(0 == b){
            return (int)Math.pow(3,a);
        }else if(1 == b){
            return (int)Math.pow(3,a-1) * 4;
        }else{
            return (int)Math.pow(3,a) * 2;
        }
    }
}

复杂度分析

  • 时间复杂度:,实现中仅涉及取整、求余和求幂运算。

  • 空间复杂度:保存商数的变量 a 和保存余数的变量 b 仅使用常量空间。

二、动态规划

当时,就分为两种情况:

  1. 时,绳子只能剪为两个长度 1 的绳子,最大乘积为 1;

  2. 时,绳子只能剪为长度为 2 和 1 的两段,最大乘积为 2;直接返回。

当 n > 3 时,就可以按照动态规划的逻辑进行处理了:

  1. 初始值为:

为什么这么设置呢?

因为对于的绳子而言,我们完全可以拆分得到长度为 3、2 和 1 的绳子,拆分得到长度为 3 的绳子不必再拆分,算入乘积的话最大就是 3本身,2 和 1 同理。在举个栗子,比如,我们可以拆分为、和,而 3 、2 和 1 都是最终直接作为计算乘积时的因子出现的,所以.

  1. 递推公式为:

对于长度为的绳子而言,要取得最大乘积,就需要知道它的前 3 个状态和,而相应的最大乘积分别为:、和,的最大乘积则取三者中的最大值。

动态规划的递推公式为:

一道快手的算法面试题,没想到对数学要求还蛮高的!

动画演示

一道快手的算法面试题,没想到对数学要求还蛮高的!

实现代码

class Solution {
    public int cuttingRope(int n) {
         if(n <= 3){
             return n-1;
         }
         int dp[] = {1,2,3};
         for(int i = 3; i < n; i++) {
          int tmp = Math.max(3 * dp[0],Math.max(2 * dp[1], 1 * dp[2]));
          dp[0] = dp[1];
          dp[1] = dp[2];
          dp[2] = tmp;
         }
         return dp[2];
    }
}

复杂度分析

  • 时间复杂度

  • 空间复杂度,使用的是长度为 3 的定长数组。

三、贪心方法

按照贪心策略来剪绳子,当时,我们尽可能多地剪长度为 3 的绳子;当剩下的绳子长度为 4 时,把绳子剪成长度为 2 的两段绳子,因。

一道快手的算法面试题,没想到对数学要求还蛮高的!

实现代码

class Solution {
    public int cuttingRope(int n) {
      if (n <= 3) {
       return n-1;
      }

      int NumOf3 = n / 3;
      if (n - NumOf3 * 3 == 1) {
       NumOf3--;
      }
      
      int NumOf2 = (n - NumOf3 * 3) / 2;
      
      return (int)Math.pow(3, NumOf3) * (int)Math.pow(2, NumOf2);
    }
}

复杂度分析

  • 时间复杂度:

  • 空间复杂度:

知识点

贪心思想、动态规划、数学推导

Read More

《隐秘的角落》开播之后就没下过热搜?

20年前的几行代码竟如此牛逼?惊了

一文凑齐四种变量转换方法!

End

奶糖猫   

优秀的人都在看   

一道快手的算法面试题,没想到对数学要求还蛮高的!

在看点一下


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

精通Spring

精通Spring

罗时飞 / 第1版 (2005年4月1日) / 2005-4 / 39.0

本书深入剖析了当前流行的轻量级开发框架Spring技术。本书总共分成3部分。第一部分,重点阐述Spring的架构。这部分内容循序渐进带领开发者进入Spring中。主要在于阐述Spring IoC和Spring AOP。第二部分,重点阐述Spring的使用。这部分内容从简化Java/J2EE的角度出发,从J2EE平台各个技术层面分析、并给出大量的研究实例,对Spring提供的API进行阐述。主要在于......一起来看看 《精通Spring》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

随机密码生成器
随机密码生成器

多种字符组合密码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码