普通版 剑指 Offer 浅刷浅刷(13)


case 1: cur=0
2 3 0 4
千位和百位可以选00 01 02…22 十位可以取到1( 形如[00|01…|22]1[0-9] 都是 当千位和百位取23,如果十位取1 那就是形如 231[0-9] > 2304,所以当千位和百位取23,十位只能能取0,个位取0-4即 2300 2301 2302 2303 2304
但是2301不应该算进来,这个1是 单独 出现在个位的(而11,121,111这种可以被算多次)
即 23*10
case 2: cur=1
2 3 1 4
千位和百位可以选00 01 02…22 十位可以取到1 个位可以选0-9 共有 23 * 10 中排列
当千位和百位取23,十位取1,个位可以去0-4 即 2310-2314共5个
即 23 *10 + 4 +1
case 3: cur>1 即2-9
2 3 2 4
千位和百位可以选00 01 02…22 十位可以取到1(形如 [00|01…|22]1[0-9] 都是 当千位和百位取23,十位取1,个位可以去0-9 即 2310-2319共10个 (其中2311,被计算了两次,分别是从个位和十位分析得到的1次)
即 23 *10 + 10
只能说困难题还是不是我能指染的 。
剑指 Offer 44. 数字序列中某一位的数字
class Solution {public:int findNthDigit(int n) {long int start = 1; //每digit位数的起始数字int digit = 1; //位数long int count = 9; //数位数量//找到该数的位数while (n > count) {n -= count;digit++;start *= 10;count = 9 * start * digit;}//找到具体数字long int num = start + (n - 1) / digit;//找到具体位return to_string(num)[(n - 1) % digit] - '0';}};
剑指 Offer 45. 把数组排成最小的数
class Solution {public:string minNumber(vector& nums) {vector> stringVector;for (auto num : nums) {stringVector.push_back(to_string(num));}//compareString位用于规定排序的方法,可不填,默认升序 。sort(stringVector.begin(), stringVector.end(), compareString);string myString;for (auto temp : stringVector) {myString += temp;}return myString;}private:static bool compareString(const string &a, const string &b) {return a + b < b + a;}};
这道题就是一个排序题,其实你想明白当a+b>b+a时进行交换,这道题就游刃而解了 。但是这里的a+b和b+a并不是简单的相加,而是字符串进行相加,即拼接 。
剑指 Offer 46. 把数字翻译成字符串
class Solution {public:int translateNum(int num) {if (num == 0) {return 1;}//将数字转换成数组vector myNum;while (num) {myNum.push_back(num % 10);num /= 10;}reverse(myNum.begin(), myNum.end());vector transNumber;int i = 0;for (i = 0; i < myNum.size(); i++) {if (i == 0) { //一个数字它肯定就只有一种翻译方法transNumber.push_back(1);} else if (i == 1) {if (myNum[i - 1] * 10 + myNum[i] < 26) {transNumber.push_back(2);} else {transNumber.push_back(1);}} else {if (myNum[i - 1] * 10 + myNum[i] < 26 && myNum[i - 1] * 10 + myNum[i] > 9) {transNumber.push_back(transNumber[i - 1] + transNumber[i - 2]);} else {transNumber.push_back(transNumber[i - 1]);}}}return transNumber[i - 1];}};
思路就是找规律,这个其实和之前的青蛙跳台阶差不多,不过每次都加一个判断条件,看其是否可以组合(即该位和上一位组合是不是大于10小于26,因为存在0这个数,所以要考虑其特殊的结合情况),如果可以组合,那么该位的dp[i]就是dp[i] = dp[i - 1] + dp[i - 2];,不可以结合的话就是dp[i] = dp[i - 1];因为之前已经考虑过各自翻译的情况了,所以现在就算新加一个数也没有啥影响,它的dp数不会增加 。
剑指 Offer 47. 礼物的最大价值
class Solution {public:int maxValue(vector>& grid) {int i = 0, j = 0;int section = grid.size(), row = grid[0].size();for (int i = 0; i < section; i++) {for (int j = 0; j < row; j++) {if (i == 0 && j > 0) {grid[i][j] += grid[i][j - 1];} else if (i > 0 && j == 0) {grid[i][j] += grid[i - 1][j];} else if (i > 0 && j > 0) {grid[i][j] += max(grid[i - 1][j], grid[i][j - 1]);}}} return grid[section - 1][row - 1];}};