给你一根长度为 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
输入: 10
2 <= n <= 58
来源：力扣（LeetCode）https://leetcode-cn.com/problems/jian-sheng-zi-lcof
自己的思路：
这道题说实话看到了之后抱着试一试的心态写了一下，5切分成2和3，4切分成2和2，用动态规划的思想考虑了一下，就是后面到5+2,5+3的时候就切分成 2,3,2和2,3,3就分别都是最大的乘积，由此就能切出3就切出3，用4和5进行一个截止，但是到6的时候也要做一个特殊情况的判断(好像很是暴力，是一个递归)。
写出下面的代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution {public : int cuttingRope (int n) if (n <= 2 ) return 1 ; switch (n){ case 3 : return 2 ; case 4 : return 4 ; case 5 : return 6 ; case 6 : return 9 ; } return 3 * cuttingRope(n - 3 ); } };
后面看了题解里的推论，看是看懂了，想是真没想到：
题解的方法得出来的结论应该是这样的：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : int cuttingRope (int n) if (n==2 ){ return 1 ; }else if (n == 3 ){ return 2 ; } int t = n / 3 ; int r = n % 3 ; if (r == 0 ){ return pow (3 ,t); }else if (r == 1 ){ return pow (3 ,t-1 )*4 ; }else if (r == 2 ){ return pow (3 ,t)*2 ; } return -1 ; } };
难度中等53
给你一根长度为 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。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
1 2 3 输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
1 2 3 输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
与上一道题差不多，但是不同的是n的范围，和答案要对1e9+7取模，所以在计算的时候不能使用pow直接计算，因为这样会导致溢出，运算的时候换成for循环，在乘积大于1e9+7时进行取模运算。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : int cuttingRope (int n) long res = 1 ; if (n <= 3 ) { return n - 1 ; } int ord = n/3 ; int r = n%3 ; int mul; switch (r){ case 0 : mul = 1 ; break ; case 1 : mul = 4 , --ord; break ; case 2 : mul = 2 ; break ; } for (int i = 0 ; i < ord; ++i) { res *= 3 ; if (res > 1000000007 ) { res = res % 1000000007 ; } } return res * mul % 1000000007 ; } };
难度简单72
请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
1 2 3 输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
1 2 3 输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
1 2 3 输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
这题没啥可说的感觉，就循环右移，并且与上1，如果结果是1就证明该位是1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution {public : int hammingWeight (uint32_t n) int res = 0 ; while (n != 0 ) { if (n & 1 == 1 ) { ++res; } n = n >> 1 ; } return res; } };
看了题解之后只知道还有n&(n-1)这个操作，真是太6了，每次可以消去最右边的1。
难度中等96
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
示例 1:
1 2 输入: 2.00000, 10 输出: 1024.00000
示例 2:
1 2 输入: 2.10000, 3 输出: 9.26100
示例 3:
1 2 3 输入: 2.00000, -2 输出: 0.25000 解释: 2-2 = 1/22 = 1/4 = 0.25
说明:
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
这道题，只想到了暴力方法。。，就是判断一下正负之后en递归,en递归没有通过测试（递归深度太深了，在指数是2147483647 的时候）。
所以看了题解，复杂度是log(n)， n是阶数，用了二进制编码+二分的思想。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : double myPow (double x, int n) if (n == 0 ) return 1 ; if (x == 0 ) return 0 ; long ord = n; double res = 1 ; if (ord < 0 ) { x = 1 /x; ord = -ord; } while (ord) { if (ord & 1 ) { res *= x; } x *= x; ord >>= 1 ; } return res; } };
难度简单65
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
1 2 输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]
说明：
这个。。也没啥说的，基础吧。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution {public : vector <int > printNumbers(int n) { int max = pow (10 , n); vector <int > res(max-1 , 0 ); for (int i = 1 ; i < max; ++i) { res[i - 1 ] = i; } return res; } };
真正考的是n位0到9的全排列，这时要按照字符串去操作，有全排列的思想还有大数加法加1时的思想。
全排列时的方法(dfs)：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : void printNumbers (int n) dfs(0 , 0 , n, "" ); return ; } void printNumber (string s, int n) { int idx = 0 ; while (s[idx] == '0' ) ++idx; if (idx < n) cout << s.substr(idx) << endl ; } void dfs (int start, int depth, int n, string num) { if (depth == n) { printNumber(num, n); } else { for (int i = start; i < 10 ; ++i) { dfs(start, depth + 1 , n, num + char ('0' + i)); } } } };
大数加法加1时的操作：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution {public : void printNumbers (int n) string s (n, '0' ) while (!increment(s, n)) { printNum(s, n); } return ; } void printNum (string s, int n) { int idx = 0 ; while (s[idx] == '0' ) ++idx; if (idx < n) cout << s.substr(idx) << endl ; } bool increment (string & s, int n) { bool isOverFlow = false ; int take = 0 ; for (int i = n - 1 ; i >= 0 ; --i) { int temp = s[i] - '0' ; if (temp + take + 1 >= 10 ) { if (i == 0 ) { isOverFlow = true ; break ; } else { s[i] = '0' + (temp + take + 1 - 10 ); } } else { s[i] += (1 + take); take = 0 ; break ; } } return isOverFlow; } };
难度简单72
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意： 此题对比原题有改动
示例 1:
1 2 3 输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
1 2 3 输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
说明：
题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
特殊处理一下头结点就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : ListNode* deleteNode (ListNode* head, int val) { if (head == nullptr ) return head; if (head->val == val) { head = head->next; return head; } ListNode *pre = head, *cur = pre->next; while (cur) { if (cur->val == val) { pre->next = cur->next; } pre = cur; cur = cur->next; } return head; } };
