训练题：整数中1出现的次数
题目：https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
总结规律。
//// 设数字50162，high为高位，cur为当前位，low为低位，digit为cur的数位级别// 如cur为1的位置，则high=50，low=62，digit=100（cur在百位）//// cur在个位// 个位为1的可取范围：00001 ~ 50161，high = 5016, low = 0, digit = 1, low = digit - 1// 0000 ~ 5016 = 5017 = high * digit + low + 1 = high * digit = (high + 1) * digit//// cur在十位// 十位为1的可取范围：00010 ~ 50119, high = 501, low = 9, digit = 10, low = digit - 1// 000 0 ~ 501 9 = 5020 = high * digit + low + 1 = (high + 1) * digit//// cur在百位// 百位为1的可取范围：00100 ~ 50162, high = 50, low = 62, digit = 100// 00 00 ~ 50 62 = 5063 = high * digit + low + 1//// cur在千位// 千位为1的可取范围：01000 ~ 41999, high = 5, low = 999, digit = 1000，low = digit - 1// 0 000 ~ 4 999 = 5000 = (high - 1) * digit + low + 1 = high * digit//// cur在万位// 万位为1的可取范围：10000 ~ 19999, high=0, low = 9999, digit = 10000, low = digit - 1// 0000 ~ 9999 = 10000 = high * digit + low + 1 = (high + 1) * digit//// 综上我们总结出规律，将数字拆分成 high cur low三个部分，如50162，high = 50， cur=1， low=62// 我们令此时的digit = 10，即cur的数位（个、十、百等等）// cur位为1的数字数量 = high*digit+low+1其实就是high和low拼接成新的数字，这个数字的大小。// 这是通常情况，有特殊情况：即cur位置上的数是0和1的情况。说白了就是high和low的取值有特殊情况。//// cur位置上的数=0时，count = (high-1)*digit+low+1=high*digit，此时low=digit-1。// cur位置上的数=1时，count = high*digit+low+1// 其他情况，count = high*digit+low+1=(high+1)*digit，此时low=digit-1。//
int countDigitOne(int n) {int count = 0;int high, low;char cur;long digit = 1;for(int i = n; i; i /= 10, digit *= 10){high = i / 10;cur = i % 10;if(cur == 0) count += high * digit;else if(cur == 1) {low = n % digit;count += high * digit + low + 1;}else count += (high + 1) * digit;}return count;}
训练题：数据流的中位数
题目：https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof
维护两个堆（大堆和小堆），设为maxHeap和minHeap。两个各保存一半的数字。取根的平均值就是中位数。
当插入第奇数个数字时，插入到小堆中。
- 时间复杂度：
- 插入数字：O（logn）
- 返回中位数：O（1）
- 空间复杂度：O（n） ```cpp
class MedianFinder {
public:
using MaxHeap = priority_queue
public: /* initialize your data structure here. / MedianFinder() { }
void addNum(int num) {if(maxHeap.size() == minHeap.size()){// 注意特殊情况，num本来是要插入到minHeap中，但是如果num<maxHeap.top// 表示num比左半部分的数都要小，那么要把maxHeap的根转移到minHeap中，再把num插入到maxHeap中// 这样才能保证minHeap的所有元素都不小于maxHeap。if(!maxHeap.empty() && num < maxHeap.top()) {minHeap.push(maxHeap.top());maxHeap.pop();maxHeap.push(num);}else minHeap.push(num);}else {if(num > minHeap.top()){maxHeap.push(minHeap.top());minHeap.pop();minHeap.push(num);}else maxHeap.push(num);}}double findMedian() {if(minHeap.empty()) return 0;if(maxHeap.size() == minHeap.size()) return (maxHeap.top() + minHeap.top()) / 2.0;else return minHeap.top();}
private: MaxHeap maxHeap; MinHeap minHeap; };
<a name="fb2tC"></a># 训练题：数字序列中某一位的数题目：[https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/](https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/)```cppint findNthDigit( int n ){if( n < 10 ) { return n; }char bit = 2; // 第n位所在的数是几位数long time10 = 10; // time10 = pow(10, bit-1);// 1位数：0 ~ 9 共有count=10个数// 2位数：10 ~ 99 共有count=90个数// 3位数：100 ~ 999 共有count=900个数// 4位数：1000 ~ 9999 共有count=9000个数long count = 10;// 循环过后，n是剩下的不足count个的位数。比如n是600中的6的位置。// 则n = 600 - 10*2 - 90*3 = 410// count = 900// bit = 3， time10 = 100for(;; ++bit, time10 *= 10){n -= count;count = 9 * time10 * bit;if(n < count) break;}// n/bit = 410/3 = 136，即是100开始的第136个数，也就是236。// n%bit = 410%3 = 2，即是表示在236的第2位的数，即是6。return to_string(time10 + n/bit)[n % bit] - '0';}
训练题：数字组合
题目：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/
方法一：回溯算法（递归）
排列组合问题一定要想到回溯算法。
- 时间复杂度：O（logn）
- 空间复杂度：O（logn），栈空间，log10n
int translateNum(int num){int count = 0, tmp = 0;fuck(num, count, tmp);return count;}// 从右往左遍历（低位到高位），例如 ......ab，ab是两个数字。// 组合方法一：取b一位// 组合方法二：如果ab>=10&&ab<=25，则又可以取ab两位，这又是一种组合方法。// num=0，表示当前这一个组合方法组合完毕，组合方法数count + 1void fuck(int num, int& count, int &tmp){if(num == 0){++count;return;}fuck(num / 10, count, tmp);tmp = num % 100;if(tmp <= 25 && tmp >=10 ) fuck(num / 100, count, tmp);}
方法二：动态规划
1、跳台阶（递归）
- 时间复杂度：O（logn）
- 空间复杂度：O（logn）
和跳台阶同理。
char tmp100 = -1;int translateNum( int num ){if(num < 10) return 1;tmp100 = num % 100;if(tmp100 <= 25 && tmp100 >=10 ){return translateNum(num/10) + translateNum(num/100);}elsereturn translateNum(num/10);}
2、迭代
- 时间复杂度：O（logn）
- 空间复杂度：O（1）
int translateNum( int num ){if( num < 10 ) { return 1; }// counti: dp[i-1]// counti_1: dp[i-2]int counti = 1, counti_1 = 1;for(char tmp, tmp100; num; num /= 10) {tmp100 = num % 100;if( tmp100 >= 10 && tmp100 <= 25 ){tmp = counti_1;counti_1 = counti; // dp[i-2] = dp[i-1]counti = counti + tmp; // dp[i-1] = dp[i]}else counti_1 = counti; // dp[i-2] = dp[i-1]}return counti;}
训练题：1+…+n求和
方法一：条件运算实现递归
- 时间复杂度：O（n）
- 空间复杂度：O（n） ```cpp
// n && fuck(n-1); 实现递归。 int sumNums(int n) { n && (n+= sumNums(n-1)); return n; }
<a name="pFDPD"></a>## 方法二：位移+加法=乘法```cppint sumNums(int n){return multi(n, n + 1) >> 1;}// int multi(int A, int B) {// int ans = 0;// for ( ; B; B >>= 1) {// if (B & 1) {// ans += A;// }// A <<= 1;// }// return ans;// }int multi(int a, int b){int result = 0;loop(a, b, result);return result;}bool loop(int &a, int &b, int& ans){(b & 1) && (ans += a);a <<= 1;return b && loop(a, b >>= 1, ans);}
技巧总结
位移+加法实现乘法：
int multi(int a, int b){int result = 0;for(; b; b >>= 1){if(b & 1) result += a;a <<= 1;}return result;}
位移+乘法实现幂：
int pow(int a, int b){int result = 1;for(; b; b >>= 1){if(b & 1) result *= a;a *= a;}return result;}
逻辑运算实现条件判断：
(b & 1) && (result *= a);// 等价于if( b & 1) result *= a;
递归代替循环：
// 不用条件运算符实现递归。void fuck(int n){n && fuck(n - 1); // 递归n次。}
训练题：不用加减乘除做加法
int add(int a, int b) {// carry = (unsigned int)(a & b) << 1; // carry是a + b的最后进位// unsigned int是为考虑有符号的情况，右位移不知道怎么运算。// num = a ^ b; // num是a + b不考虑最后进位的结果// sum = carry + num; // a + b的最终结果，可以循环迭代，直到carry为0for(int tmp; tmp;) {tmp = (unsigned int)(a & b) << 1;a = a ^ b;b = tmp;}return a;}
训练题：约瑟夫环
方法一：迭代
总结数学规律。
// 第一轮// 0 1 2 3 4 0 1 2 3 4// 最后剩余数字在本轮的索引idx，count为本轮的元素个数（未删除前）// idx = 3, count = 5 最后剩余数字的索引：(0 + 3) % 5// 0最后剩余数字(3)在上一轮的索引（下面一个）// 3为从0开始数，第几个数开始删除，即m的值。// 5为当前轮的元素个数（删除前）//// 综上：最后剩余数字在本轮的索引 = (lastIdx + m) % count// lastIdx:最后剩余数字在上一轮的索引//// 3 4 0 1 3 4 0 1// idx = 0, count = 4 (1 + 3) % 4//// 1 3 4 1 3 4// idx = 1, count = 3 (1 + 3) % 3//// 1 3 1 3// idx = 1, count = 2 (0 + 3) % 2//// 3// idx = 0, count = 1int lastRemaining(int n, int m) {// 最后剩余数字的索引（索引和数值相同）int targetIdx = 0; // 初始值数值0就是元素个数=1的轮的索引// len：在本轮的元素个数（未删除前），同时也表示从元素个数=2的轮，往前回推到元素个数=5的轮。for(int len = 2; len <= n; ++len){// targetIdx的初始值刚好是len=2轮的lastIdx，即(targetIdx+m)中的targetIdx的值。targetIdx = (targetIdx + m ) % len;}return targetIdx;}
方法二：递归
// n表示当前轮的元素个数（未删除前），如n=1，表示最后剩下一个数字的那一轮；n = 5，就是第一轮。// m表示从0开始的第几个数删除。// 返回最后剩下的数字在当前轮的索引int lastRemaining(int n, int m) {// n=1就是一个元素，返回值当然是0了。if(n == 1) return 0;最后剩下的数字在当前轮的索引 = (该数字在下一轮的索引 + m) % nreturn (lastRemaining(n-1, m) + m) % n;}
训练题：判断顺子
- big - small < 5，big、small为非王牌
- 无重复牌 ```cpp
bool isStraight(vector
set<int> info;int big = 0; // 最大的非0牌int small = 20; // 最小的非0牌for(char i = 0; i < 5; ++i){if(nums[i]){if(info.count(nums[i])) return false; // 有重复的非0牌肯定不是顺子big = max(big, nums[i]);small = min(small, nums[i]);info.insert(nums[i]);}}return big - small < 5; // 最大非0牌和最小牌之间不能超过4
}
<a name="LKmY0"></a># 训练题：和为s的连续整数序列题目：[http://t.cn/A67EmKAI](http://t.cn/A67EmKAI)<a name="CWEza"></a>## 方法一：数学求极值- target为目标值。- k为连续数列的个数，k为正整数，k>=2。- n为数列的起始数值。n为正整数，且n>=1。```cppvector<vector<int>> findContinuousSequence(int target) {vector<vector<int>> ret;// k为数列的长度。// 上面推导出了k的极值for(int k = (sqrt(1 + 8*target) - 1)/2, tmp; k >= 2; --k){// 目标整数序列：n n+1 ... n+k-1，其中n>=1，k>=2，target为数列和// => k*n + k(k-1)/2 = target// => k*n = target - k(k-1)/2，令tmp=target - k(k-1)/2// => k*n = tmp;// => n = tmp / k，因为n是整数，所以tmp能整数k时，则该k值为合适值tmp = target - (k*(k-1)>>1);if(tmp < k) break; // 边界条件，n = tmp / k >= 1 => tmp >=kif(!(tmp % k)){ // 判断是否能整数ret.push_back({});tmp /= k;for(int m = tmp; m < (tmp + k); ++m) ret.back().push_back(m);}}return ret;}
方法二：双指针
- left和right为某个序列的首尾索引。
- 初始，left=1，right=2。
- 当这个序列和小于目标值，就将right右移一位，使得序列值增大；反之，则将序列的left右移一位，使序列值减小。
- left必须小于right ```cpp
vector
vector<vector<int>> ret;int left = 1, right = 2, sum;for(int left = 1, right = 2, sum; left < right;) {sum = (left + right)*(right - left + 1)/2;if(sum == target){ret.emplace_back();for(int i = left; i <= right; ++i) ret.back().push_back(i);}if(sum < target) ++right;else ++left;}return ret;
}
<a name="UQvRD"></a># 训练题：打印1到n（全排列）题目：[http://t.cn/A6zxsZ55](http://t.cn/A6zxsZ55)排列组合想到回溯算法。<a name="a8yub"></a>## 方法一递归过程中记录了当前是第几位的数。```cppvector<int> printNumbers( int n ){vector<int> ret;string digitNum = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', };string tmpNum( n, '\0' );ret.reserve( pow( 10, n ) );_printNumbers( ret, digitNum, n, tmpNum, 0 );return ret;}// container：全排列应该就有10的n次方个。// digitNum：10个阿拉伯数字字符。// maxBitsvoid _printNumbers( vector<int> &container, const string &digitNum, const int &maxBits, string &tmpNum, int idx ){if( idx == maxBits ){int tmp = atoi( tmpNum.c_str() );if( tmp ) { container.push_back( tmp ); }return;}for( auto &c : digitNum ){tmpNum[idx] = c;_printNumbers( container, digitNum, maxBits, tmpNum, idx + 1 );}}
方法二
递归过程不记录第几位的数，而是在string的结尾push_back/pop_back来调整。
vector<int> printNumbers( int n ){vector<int> ret;string digitNum = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', };string tmp;bool flag = true;_printNumbers( ret, digitNum, tmp, n, flag );return ret;}void _printNumbers( vector<int> &container, const string &digitNum, string &tmp, const int &n, bool &flag ){if( tmp.size() == n ){if( flag ) { flag = false; }else { container.push_back( atoi( tmp.c_str() ) ); }return;}for( auto &c : digitNum ){tmp.push_back( c );_printNumbers( container, digitNum, tmp, n, flag );tmp.pop_back();}}
训练题：二进制中1的个数
方法一
int hammingWeight(uint32_t n){int shit = 0;for(; n; n >>= 1) {if(n & 0x1) ++shit;}return shit;}
方法二
int hammingWeight(uint32_t n) {int shit = 0;for(; n; ++shit) n &= (n-1); // 让n最右边的1变为0return shit;}
训练题：剪绳子
场景一
最先考虑剪成3，剩下的考虑剪成2。
int cuttingRope(int n) {if( n <=3 ) { return n - 1; }int a = n / 3, b = n % 3;if(b == 0) return pow(3, a); // 刚好可以剪成长度为3的绳子若干if(b == 1) return pow(3, a - 1) * 4; // 最后一段绳子长度是4，这时候要剪成2、2而不是1、3return pow(3, a) * 2; // 最后一段绳子长度是5，剪成3、2}
场景二
int cuttingRope( int n ){if( n <= 3 ) { return n - 1; }int a = n / 3 - 1;int b = n % 3;int base = 1000000007;long result = 1; // 必须声明long型long contribute = 3; // 必须声明long型// 快速求幂法while( a ){if( a & 0x1 ) { result = ( result * contribute ) % base; }contribute = ( contribute * contribute ) % base;a >>= 1;}if( b == 0 ) { return ( 3 * result ) % base; }if( b == 1 ) { return ( 4 * result ) % base; }return ( 6 * result ) % base;}
训练题：幂函数
double myPow( double x, int n ){// 为了处理负数次方，我们会考虑去相反数n = n < 0 ? -n : n; // 值溢出的情况，因为有符号整形的整数与负数可能是不对称的。}
方法一：递归
double myPow( double x, int n ){if( n == 0 || x == 1 || x == 0 ) { return 1; }return n < 0 ? ( 1 / _myPow( x, n ) ) : _myPow( x, n );}double _myPow( double x, int n ){if( n == 0 ) { return 1; }double result = _myPow( x, n / 2 );return ( ( n & 0x1 == 1 ) ? x : 1 ) * result * result;}
方法二：迭代
既然可以递归，当然就可以用迭代，时间复杂度一样，但是空间复杂度更少。难点在于对递归过程的逆解析。
double myPow(double x, int n) {if( x == 0 || x == 1 || n == 0 ) { return 1; }double ret = 1;for( int shit = n; shit; shit /= 2) // 不能用位移，因为负数的右移是系统相关。{if( shit & 0x1 ) { ret *= x; }x *= x;}return n > 0 ? ret : ( 1 / ret );}
训练题：大数加法
情形一：非负数之和
方法一：栈
从尾部往前逐位相加，结果保存在栈中。
string solve(string s, string t) {stack<char> stk;int carry = 0;for( int i = s.size() - 1, j = t.size() - 1, tmpNum = 0; i >= 0 || j >= 0; --i, --j ){if( j >= 0 && i < 0 ){tmpNum = t[j] - '0' + carry;carry = tmpNum / 10;stk.push( tmpNum % 10 );}else if( i >= 0 && j < 0 ){tmpNum = s[i] - '0' + carry;carry = tmpNum / 10;stk.push( tmpNum % 10 );}else{tmpNum = s[i] - '0' + t[j] - '0' + carry;carry = tmpNum / 10;stk.push( tmpNum % 10 );}}if( carry ) { stk.push( carry ); }if( stk.empty() ) { return "0"; }string ret;ret.reserve( stk.size() );for( ; !stk.empty(); stk.pop() ) { ret.append( 1, stk.top() + '0' ); }return ret;}
方法二：不用栈
将结果直接保存在更长的那个字符串中，省去了栈空间。
string solve(string s, string t) {int s_size = s.size();int t_size = t.size();int carry = 0;string* bigStr = &t;string* smalllStr = &t;if( s_size > t_size ) { bigStr = &s; }else { smalllStr = &s; }for( int bigIdx = std::max( s_size - 1, t_size - 1 ), smallIdx = std::min( s_size - 1, t_size - 1 ), tmpNum = 0;bigIdx >= 0 || smallIdx >= 0;--bigIdx, --smallIdx ){if( smallIdx < 0 ){tmpNum = ( *bigStr )[bigIdx] - '0' + carry;}else{tmpNum = ( *smalllStr )[smallIdx] - '0' + ( *bigStr )[bigIdx] - '0' + carry;}carry = tmpNum / 10;( *bigStr )[bigIdx] = tmpNum % 10 + '0';}if( carry ) { bigStr->insert( 0, 1, '1' ); }return *bigStr;}
训练题：整数反转
int reverse( int x ){int newNum = 0;// const int int_max = 2147483647; // 最小的数// const int int_min = -2147483648; // 最大的数for( int mod = x % 10; x; x /= 10, mod = x % 10 ){if( ( newNum > 214748364 ) || ( newNum == 214748364 && mod > 7 ) ) { return 0; }if( ( newNum < -214748364 ) || ( newNum <= -214748364 && mod < -8 ) ) { return 0; }// 这里的*10和 + mod都可能出现溢出，因此在这之前需提前判断。// 溢出情况1：*10溢出，触发条件：newNum比最数对应位置要大/小。// 溢出情况2：+mod溢出，触发条件：newNum等于最数对应位置数，且加了mod超出最数个位值。newNum = newNum * 10 + mod;}return newNum;}
训练题：回文数字
方法一
- 时间复杂度：O(n)
- 空间复杂度：O(1)
// 先遍历出所有数字到一个数组中// 然后从回文的中心位置向外扩展，依次判断是否为回文。bool isPalindrome(int x) {if( x < 0 || ( x != 0 && x % 10 == 0 ) ) { return false; }if( !( x / 10 ) ) { return true; }char num[10] = {0};char flag[2] = { 0, 1 };char maxIdx = -1;while( x ){++maxIdx;num[maxIdx] = x % 10;x /= 10;}char left = ( maxIdx >> 1 )+1;char right = ( maxIdx >> 1 ) + flag[maxIdx & 0x1] - 1;while( --left >= 0 && ++right <= maxIdx ) if( num[left] != num[right] ) { return false; }return true;}
方法二
- 时间复杂度：O(n)
- 空间复杂度：O(1) ```cpp
// rNum为翻转后的数，x为剩余的数 // 当x < rNum时，翻转过半，这个时候我们判断rNum是否等于x即可判断是否会回文。
bool isPalindrome(int x) { if(x < 0) return false; // 负数不是回文数 if(x < 10) return true; // 一位数是回文数 if(!(x % 10)) return false; // 个位为0的数不是回文数
int tmp = 0;while(tmp < x){tmp = tmp * 10 + x % 10;x /= 10;}// 情况一：翻转后的数 == 剩余的数，说明是回文，这种情况必须位数是偶数// 情况二：位数为奇数时，翻转后的数要比剩余的数多1位，而这个位就是回文的中心，应跳过它。return ( tmp == x ) || ( x == tmp / 10 );
}
```
若有收获，就点个赞吧
0 人点赞
