TODO：
- 都不大会做重新做一遍吧
- 手动写堆排序
剑指 Offer 14- II. 剪绳子 II(中等)
两个要点: ①快速幂 ②找到最优解的模式
class Solution {
public:
int cuttingRope(int n) {
if(n == 2) return 1;
else if(n==3) return 2;
if(n==4) return 4;
int t1 = n/3;
int t2 = n%3;
int b = t1 -1;
long res = 1;
long k =3;
while(b){
if(b%2 == 1){
res = (res*k)%1000000007;
}
b = b/2;
k = k %1000000007;
k = (k*k)%1000000007;
}
if(t2 == 0) return (res*3)%1000000007;
else if(t2 == 1) return (res*4)%1000000007;
else return (res*3*2)%1000000007;
}
};
class Solution {
public:
int cuttingRope(int n) {
if(n == 2) return 1;
if(n == 3) return 2;
long result = 1;
while(n > 4){
n -=3;
result*=3;
result%=1000000007;
}
return (int)(n*result%1000000007);
}
};
剑指 Offer 43. 1～n 整数中 1 出现的次数(困难)
想了一会发现是1出现的次数，也就是11表示1有出现2次...直接看题解好了。很有趣的一道题！！！
这个代码很简洁
class Solution {
public:
int countDigitOne(int n) {
if(n == 0) return 0;
int high = n/10;
int cur = n%10;
int low = 0;
long digit = 1;
int res = 0;
while(high || cur){
if(cur == 0){
res += high*digit;
}else if(cur == 1){
res += (high*digit + low +1);
}else{
res += (high+1)*digit;
}
low += cur*digit;
cur = high%10;
high = high/10;
digit = digit*10;
}
return res;
}
};
剑指 Offer 44. 数字序列中某一位的数字(中等)
不会做看的题解。
class Solution {
public:
int findNthDigit(int n) {
int digit =1;
long start =1, count = 9;
while( n > count){
n -= count;
start*=10;
digit+=1;
count = 9*start*digit;
}
int num = start + (n-1)/digit;
string snume = to_string(num);
return snume[(n-1)%digit]-'0';
}
};
