TODO:
- 重新做一遍丑数独立思考
- 重做一遍队列的最大值
剑指 Offer 49. 丑数(中等))
动态规划问题，没有做出来。
题解
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n+1,0);
dp[0] = 1;
int ia = 0, ib = 0,ic =0;
for(int i = 1; i <n; i++){
int a = dp[ia]*2;
int b = dp[ib]*3;
int c = dp[ic]*5;
dp[i] = min(min(a,b),c);
if(dp[i] == a) ++ia;;
if(dp[i] == b) ++ib;
if(dp[i] == c) ++ic;
}
return dp[n-1];
}
};
剑指 Offer 66. 构建乘积数组(中等)
此题的考点在于不能用除法，以自己遍历两次得结果的方法来看是道简单题。题解的做法就比我少了一个数组的开辟，大体思路是一致的。
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
int n = a.size();
if(n ==0) return {};
vector<int> left(n,0);
vector<int> right(n,0);
left[0] = 1;
right[n-1] = 1;
for(int i = 1; i < n;i++){
left[i] = left[i-1]*a[i-1];
right[n-i-1] = right[n-i]*a[n-i];
}
vector<int> res(n,0);
for(int i = 0; i <n; i++){
res[i] = left[i] * right[i];
}
return res;
}
};
题解的方法:
class Solution {
public:
vector<int> constructArr(vector<int>& a) {
int n = a.size();
// 返回结果的计算
vector<int> b(n, 1);
// 从上到下，左下角的遍历
for (int i = 1; i < n; ++i)
{
b[i] *= b[i-1] * a[i-1];
}
int accu = 1; // 累计乘积的结果，用于和b[i] 来计算
// 从下到上，左上角的遍历
for (int i = n-2; i >=0 ; --i)
{
accu *= a[i+1];
b[i] *= accu;
}
return b;
}
};
剑指 Offer 59 - II. 队列的最大值(中等)
题解跟之前滑动窗口维持最小/大值做法差不多。重点是对双端队列的使用，还有注意while不要写成if。
class MaxQueue {
public:
queue<int> prim;
deque<int> maxVal;
MaxQueue() {
}
int max_value() {
return maxVal.empty()? -1:maxVal.front();
}
void push_back(int value) {
while(!maxVal.empty() && value > maxVal.back()){
maxVal.pop_back();
}
prim.push(value);
maxVal.push_back(value);
}
int pop_front() {
if(prim.empty()) return -1;
int val = prim.front();
prim.pop();
if(val == maxVal.front()){
maxVal.pop_front();
}
return val ;
}
};
/**
* 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();
*/
