最近花了点时间把剑指offer全部刷完了，对其中的部分题感觉还是有点意思，所以今天来做点笔记。
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)
旋转数组的最小值其实是一个很常见的题，HOT100里也会有涉及。但是这个题的一些样例给了一个更全能的解法：
#include <ios>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int minNumberInRotateArray(vector<int>& nums) {
int left=0,right=nums.size()-1;
while(left<right)
{
int mid=(left+right)/2;
if(nums[mid]<nums.back())right=mid;
else left=mid+1;
}
return nums[right];
}
};这是我在HOT100里的做法，我们只用判断数组末尾的数是否比当前的中间的值大即可，如果满足我们直接移动右指针否则移动左指针，且在不满足条件时当前值不可能是最小值（你都比数组末尾的值大了还能是最小值吗），所以我们的左指针移动时直接向右多移一位。
但是我们在这里这样写的话：
遇到这样的大量重复的数字组成的数组就不好使了，归根结底是因为当我们数组内有重复元素时，你当前中间值的元素和队列末尾元素相等，而你根本无法判断当前中间值是在旋转数组的左半个增长区间还是右半个增长区间，所以这个时候你必须去移动指针。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
int minNumberInRotateArray(vector<int>& nums) {
int l=0,r=nums.size()-1;
while (l<r) {
int mid=l+(r-l)/2;
if(nums[mid]<nums[r])r=mid;
else if(nums[mid]>nums[r])l=mid+1;
else r--;
}
return nums[r];
}
};于是就出现了这样的代码：直接和nums[r]进行比较，大的话说明你在左半区，小的话说明你在右半区，相等说明你遇到了之前所言的情况：相等时我们就直接移动右指针，这样如果此时中间值在右半区你的移动就是正确的，哪怕是在左半区，只要你的右指针遇到那个不重复的数字，也就是最小值，那么你就可以触发第一个情况从而得到答案。
机器人的运动范围_牛客题霸_牛客网 (nowcoder.com)
这个题说是较难，其实思路反而很清晰且简单：本质上就是一个计算数位之和小于阈值的BFS罢了。
#include <queue>
#include <vector>
class Solution {
public:
const vector<pair<int,int>> dirs={{-1,0},{1,0},{0,-1},{0,1}};
bool helper(int threshold,int i,int j){
int num=0;
while (i!=0) {
int temp=i%10;
i/=10;
num+=temp;
}
while (j!=0) {
int temp=j%10;
j/=10;
num+=temp;
}
return num<=threshold;
}
int movingCount(int threshold, int rows, int cols) {
if(rows<=0||cols<=0)return 0;
queue<pair<int,int>> q;
q.push({0,0});
vector<vector<bool>> visited(rows,vector<bool>(cols,false));
visited[0][0]=true;
int res=0;
while (!q.empty()) {
int n=q.size();
res+=n;
for(int i=0;i<n;++i){
auto [x,y]=q.front();
q.pop();
for(auto [dx,dy]:dirs){
int i=x+dx,j=y+dy;
if(i<0||i>=rows||j<0||j>=cols)continue;
if(!visited[i][j]&&helper(threshold, i, j)){
q.push({i,j});
visited[i][j]=true;
}
}
}
}
return res;
}
};这个题更多的是体现一个基本功的题，只要会写bfs和数位之和那么就不算很难。
这个题其实在HOT100中也有，用动态规划做，代码如下：
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
int cutRope(int n) {
vector<int> dp(n+1);
dp[2]=1;
for(int i=3;i<=n;++i){
for(int j=0;j<=i/2;++j){
dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));
}
}
return dp[n];
}
};也没有多复杂，就是比较三个值：当前已有的值，dp[i-j]*j代表长度为(i-j)的最大乘积乘以j以及单独分为两段的(i-j)*j这三个值取最大值即可。
但是这里我想展示的是另一个专门针对这个问题的做法：
#include <cmath>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
int cutRope(int n) {
if(n<=2)return n-1;
if(n%3==0)return pow(3, n/3);
if(n%3==1)return 4*pow(3, n/3-1);
if(n%3==2)return 2*pow(3, n/3);
return 0;
}
};针对剪绳子问题，我们完全可以按照长度为3来分段进行切割，如果余数为0则最大乘积就是3的n/3次方（n为绳子长度），余数为1则最大乘积是4乘以3的n/3-1次方，余数为2则最大乘积是2乘以3的n/3次方。
表示数值的字符串_牛客题霸_牛客网 (nowcoder.com)
这个题相对来说确实麻烦不少，因为我们要针对多个情况进行判断，这个题最大的难点就是我们的信息提取能力，或者叫如何构建完整的判断机制。
可以看到我们要处理的内容有：空格，e或者E，正负号，小数点。空格一定在数的前面和后面，如果一个空格出现在了数的内容那么返回false；e或者E首先一定只有一个，然后e前面一定得有数且后面一定得有数；正负号一定在一个数字的开头，不管这个数字是在e之前还是之后；小数点一定只有一个，且小数点前一定不能有e或者E（e或者E之后只能跟一个整数）。
#include <cctype>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return bool布尔型
*/
bool isNumeric(string str) {
int n=str.size();
bool hasnum=false,haspoint=false,hasE=false;
int i=0;
while(i<n&&str[i]==' ')++i;
if(i==n)return false;
for(;i<n;++i){
if(isdigit(str[i]))hasnum=true;
else if(str[i]=='+'||str[i]=='-'){
if(i>0&&str[i-1]!='e'&&str[i-1]!='E')return false;
}
else if(str[i]=='.'){
if(haspoint||hasE)return false;
haspoint=true;
}
else if(str[i]=='e'||str[i]=='E'){
if(!hasnum||hasE)return false;
hasnum=false;
hasE=true;
}
else if(str[i]==' '){
while (i<n&&str[i]==' ') {
++i;
}
if(i!=n)return false;
}
else return false;
}
return hasnum;
}
};
丑丑的数，这个题你看着标签又是二分又是基础数学的，但是在我看来这就是一个标准的动态规划题：
因为我们要从小到大排列只包含2，3，5作为因子的数，那么我们可以用三个指针分别代表2，3，5，然后成立一个动态规划数组，挨个取最小值更新即可。
#include <algorithm>
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param index int整型
* @return int整型
*/
int GetUglyNumber_Solution(int index) {
vector<int> dp(index+1);
dp[0]=1;
int p2=0,p3=0,p5=0;
for(int i=1;i<=index;++i){
int nex2=dp[p2]*2,nex3=dp[p3]*3,nex5=dp[p5]*5;
dp[i]=min(nex2,min(nex3,nex5));
if(dp[i]==nex2)p2++;
if(dp[i]==nex3)p3++;
if(dp[i]==nex5)p5++;
}
return dp[index-1];
}
};数组中的逆序对_牛客题霸_牛客网 (nowcoder.com)
这个题其实就是一个归并排序的应用题，归并排序的执行顺序如下：
我们要做的事就是在归并排序在合并排序的图中找到右子序列大于左子序列时进行一个最终结果的维护和更新。
代码如下：
#include <algorithm>
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型vector
* @return int整型
*/
const int MOD = 1000000007;
int helper(vector<int>& nums,int l,int r){
if(l>=r)return 0;
int mid=l+(r-l)/2;
int count=(helper(nums, l, mid)+helper(nums, mid+1, r))%MOD;
vector<int> temp(r-l+1);
int i=l,j=mid+1,idx=0;
while(i<=mid&&j<=r){
if(nums[i]<=nums[j])temp[idx++]=nums[i++];
else{
count=(count+(mid-i+1))%MOD;
temp[idx++]=nums[j++];
}
}
while(i<=mid)temp[idx++]=nums[i++];
while(j<=r)temp[idx++]=nums[j++];
copy(temp.begin(), temp.end(), nums.begin()+l);
return count;
}
int InversePairs(vector<int>& nums) {
return helper(nums, 0, nums.size()-1)%MOD;
}
};孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网 (nowcoder.com)
这个题则是一个经典问题：约瑟夫环问题。
是的，这个题是有着现成的递推公式的，那么针对这样的问题我们都可以用递归来解决。
代码如下：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @param m int整型
* @return int整型
*/
int helper(int n, int m){
if(n==1)return 0;
return (helper(n-1, m)+m)%n;
}
int LastRemaining_Solution(int n, int m) {
if(n==0||m==0)return -1;
return helper(n, m);
}
};非常的干净整洁啊，其中n是当前人数而m是要数的个数。
序列化二叉树_牛客题霸_牛客网 (nowcoder.com)
个人认为剑指offer里面最难的题目，要求我们可以根据树获得数组以及根据数组获得树。
#include <string>
#include <cstring>
using namespace std;
class Solution {
public:
char* Serialize(TreeNode* root) {
static string str;
if (!root) {
str += "#!";
} else {
str += to_string(root->val) + "!";
Serialize(root->left);
Serialize(root->right);
}
char* res = new char[str.size() + 1];
strcpy(res, str.c_str());
return res;
}
TreeNode* Deserialize(char*& str) {
if (*str == '#') {
str += 2;
return nullptr;
}
char* end = strchr(str, '!');
int val = stoi(string(str, end));
str = end + 1;
auto node = new TreeNode(val);
node->left = Deserialize(str);
node->right = Deserialize(str);
return node;
}
};