【剑指Offer】数学(1)

【剑指Offer】数学(1)

剑指 Offer 14- I. 剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[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 <= n <= 58

class Solution {
public:int foo(int n, int m){if(n == 1){return 0;}int x = foo(n - 1, m);return (m + x) % n;}int lastRemaining(int n, int m) {return foo(n, m);}
};

算法思路

这一题就是吧n拆成尽可能多的3(4不用拆)，比如5最优的情况是拆成3和2，6拆成3和3、7拆成4和3…下面进行一些小证明

由算术几何不等式
∑ i = 1 n a i n ≥ ∏ i = 1 n a i n {sum_{i=1}^na_iover n} ge {sqrt[n]{prod_{i=1}^n ai}} n∑i=1n​ai​​≥ni=1∏n​ai ​
得当且仅当ai全部相等时，累乘得到最大值。

设x为ai的值，f为结果
f ( x ) = x n x f(x) = x^{frac nx} f(x)=xxn​
转换一下
l n f = n x l n x lnf = frac nxlnx lnf=xn​lnx
两边求导
f ′ f = − n l n x x 2 + n x 2 frac {f'}{f} = -frac {nlnx}{x^2}+frac n{x^2} ff′​=−x2nlnx​+x2n​

整理
f ′ = n x n x x 2 ( 1 − l n x ) f'=frac {nx^{frac nx}}{x^2}(1-lnx) f′=x2nxxn​​(1−lnx)
因此可以得到当x=e(自然对数时)f取得最大值，并由单调性得到x为整数时3应该是最优解。

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

• 1 <= target <= 10^5

class Solution {
public:vector<vector<int>> ans;void ansPush(queue<int> q){vector<int> ve;pty() == false){ve.push_back(q.front());q.pop();}ans.push_back(ve);}vector<vector<int>> findContinuousSequence(int target) {queue<int> q;ans.clear();int sum = 0, cur = 0;for(int i = 1; i <= target / 2 + 1; ++ i){if(sum > target){while(sum > target){sum -= q.front();q.pop();}}if(sum == target){ansPush(q);sum -= q.front();q.pop();}q.push(i);sum += i;}if(sum > target){while(sum > target){sum -= q.front();q.pop();}}if(sum == target){ansPush(q);sum -= q.front();q.pop();}return ans;}
};

算法思路

这一题应该算比较经典的滑动窗口，两个指针指向窗口两边，如果此时窗口内元素大小和小于target，右指针右移，如果大于target，左指针左移，直至遍历完整个数组。

剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：

输入: n = 5, m = 3
输出: 3

示例 2：

输入: n = 10, m = 17
输出: 2

限制：

• 1 <= n <= 10^5
• 1 <= m <= 10^6

class Solution {
public:int foo(int n, int m){if(n == 1){return 0;}int x = foo(n - 1, m);return (m + x) % n;}int lastRemaining(int n, int m) {return foo(n, m);}
};

算法思路

这一题用的是回溯算法，回溯的值为目标值在当前数组的位数，很容易知道随着数组不断变短，最后数组只剩下一个元素，这个就是目标值，且位置为0。简单模拟一下取递归的过程

n = 5, k = 3					取出的值  位置   target(3)的位置(原始数组)	
第一轮：0 1 2 3 4				==> 2 	   2			3					
第二轮：0 1 3 4 0 1 3 4			==> 0      0			2					
第三轮：1 3 4 1 3 4				==> 4      2			1					
第四轮：1 3 1 3					==> 1      0			1					
第五轮：3						==> 	   0			0					

限制要求的就是f(n,m)和f(n - 1,m)的关系，n为当前数组长度，m为题目的m

又因为m>n时其实是在对数组遍历，因此m可以转换为m%n，我们称f(n-1,m)层所剩的数组为上层数组，因为保留着所以上层数组中的元素是不会被拿走的，因此则说明上层数组前面有m%n个元素，即target的位置来到了(m+x)%n，因此可以推到递归数组。

这题是个约瑟夫环问题，真的挺不简单的…

【剑指Offer】系列：
【剑指Offer】栈
【剑指Offer】链表
【剑指Offer】字符串
【剑指Offer】查找算法
【剑指Offer】查找算法(1)
【剑指Offer】搜索与回溯算法
【剑指Offer】搜索与回溯算法(1)
【剑指Offer】动态规划
【剑指Offer】动态规划(1)
【剑指Offer】动态规划(2)
【剑指Offer】双指针
【剑指Offer】双指针(1)
【剑指Offer】双指针(2)
【剑指Offer】搜索与回溯算法(2)
【剑指Offer】搜素与回溯算法(3)
【剑指Offer】排序
【剑指Offer】排序(1)
【剑指Offer】搜索与回溯算法(4)
【剑指Offer】搜索与回溯算法(5)
【剑指Offer】分治算法
【剑指Offer】位运算
【剑指Offer】位运算(1)
【剑指Offer】数学