数学类型
剑指 Offer 44. 数字序列中某一位的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int findNthDigit(int n) {
if(n==0)return 0;
long long count = 9, start = 1;
int digit = 1;
while(n>count)
{
n-=count;
digit++;
start *= 10;
count = 9 * start * digit;
}
long long num = start + (n-1)/digit;
int pos = (n-1)%digit;
string s = to_string(num);
return s[pos]-'0';
}
};
这道题目算是数学中的找规律，比较难搞的是边界问题，还有就是变量类型需要时long。其中count指的是第几位，start是每一个数量级开始的数字，digit是在该数量级数字的位数
剑指 Offer 56 - I. 数组中数字出现的次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> singleNumbers(vector<int>& nums) {
int abXOR = 0;
for(auto &i : nums)
{
abXOR ^= i;
}
int diffOne = 1;
while((diffOne & abXOR) == 0)
{
diffOne<<=1;
}
int a = 0,b = 0;
for(auto &i: nums)
{
if(diffOne & i)
{
a ^= i;
}
else b ^= i;
}
return vector<int>{a,b};
}
我觉得这算计算机类型了都。其实这道题适合看题解，不过提一嘴异或，就是如果所有的数字异或一遍，哪些一样的数字就会消失，最终的结果就是那两个不一样的数的异或，其实很好证明，异或满足交换律。那么剩下的难点就是如何把ab分到两组而且还能脱颖而出了
还有一点需要注意的是一个数左移是diffOne = diffOne<<1,我一开始只是左移了，忘记写等号了，就产生了超时，那么为什么会产生超时呢，我不说，让未来复习的我想一下
排序类型
剑指 Offer 45. 把数组排成最小的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
static bool compare(int a, int b)
{
string sa = to_string(a);
string sb = to_string(b);
return sa + sb < sb+sa;
}
public:
string minNumber(vector<int>& nums) {
sort(nums.begin(),nums.end(),compare);
string ret;
for(auto num:nums)
{
ret += to_string(num);
}
return ret;
}
};
这道题就是个排序，就比两个数作为字符串相加，看谁在前边小，谁就排在前面去，sort()真好用
动态规划类型
剑指 Offer 46. 把数字翻译成字符串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int translateNum(int num) {
string s = to_string(num);
int p = 0, q = 1, r = 1;//r是当前下标的翻译种类数量
for(int i = 1; i < s.size(); i++)
{
p = q;
q = r;
r = 0;
if(s.substr(i-1,2)>= "10" && s.substr(i-1,2)<="25")
{
r = p + q;
}else r = q;
}
return r;
}
};
简单的dp，真没啥说的，看题目就明白了，但当时就是没想到这个法子
剑指 Offer 49. 丑数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int nthUglyNumber(int n) {
int dp[1691];
int p2 = 1, p3 = 1, p5 = 1;
dp[1] = 1;
for(int i = 2; i <= n; i ++)
{
dp[i] =min(min(dp[p2]*2,dp[p3]*3),dp[p5]*5);
if(dp[i] == dp[p2]*2)p2++;
if(dp[i] == dp[p3]*3)p3++;
if(dp[i] == dp[p5]*5)p5++;
}
return dp[n];
}
};
第一次做的时候想到了丑数是由2、3、5相互组合相乘得到的，但是没往dp上想，甚至用了素数表，但超时了。使用三个指针+dp就行了，后面的丑数都是由前面的丑数乘以2、3、5得到的，还有需要注意的一点是去重，代码很清楚，不多说
数据结构
剑指 Offer 59 - II. 队列的最大值
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
class MaxQueue {
public:
deque<int> d;
queue<int> q;
MaxQueue() {
}
int max_value() {
if(d.empty()) return -1;
return d.front();
}
void push_back(int value) {
q.push(value);
while(!d.empty() && d.back() < value)
{
d.pop_back();
}
d.push_back(value);
}
int pop_front() {
if(q.empty()) return -1;
int ret = q.front();
q.pop();
if(ret == d.front())
{
d.pop_front();
}
return ret;
}
};
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue* obj = new MaxQueue();
* int param_1 = obj->max_value();
* obj->push_back(value);
* int param_3 = obj->pop_front();
*/
这道题难点在于双端队列取最大值，就是再push的时候判断，因为push时，当前值位于队列的最后一个，那么如果队列前面的值比当前值小，就说明在pop到当前值之前，调用max得到的结果都不会是前面那些比当前值小的数，所以呢，在双端队列里遇到比当前值小的删除就行。这么下来，双端队列的第一位永远也是最大的一位。
剑指 Offer 60. n个骰子的点数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<double> dicesProbability(int n) {
vector<double> dp(6,1.0/6.0);
for(int i = 2; i <= n; i ++)
{
vector<double> tmp(5 * i + 1, 0.0);
for(int m = 0; m < dp.size(); m++)
{
for(int k = 0; k < 6; k++)
{
tmp[m + k] += dp[m] / 6.0;
}
}
dp = tmp;
}
return dp;
}
};
这道题给我cpu干懵了，首先我把它当成找规律做，浪费了大票的时间。其次，得知它需要用dp做后，又开始搞二维数组，因为下标关系紊乱，又浪费了大票时间，所以看答案，使用滚动数组最简单方便了，麻了，关键的是要找对状态转移方程