做这种模拟
类型的算法题,有三个要诀:快、准、狠
,缺一不可:
- 快,时间控制在30分钟以内,这样才能预留充分时间给后面的题目
- 准,找准边界条件
- 狠,一旦有把握,毫不犹豫的动手写代码
此类题目很重要的几个特性:🅐对称 🅑旋转 🅒重复...,利用这些特性可以大大减少代码量
由于模拟
类型题目变化多端,要做到快准狠
实属不易,需要我们快速分析,快速找规律。以本题为例,当rowIndex=5
时,数组为1 5 10 10 5 1
,我们用1初始化这个数组,再一步步得出结果:
1 1 1 1 1 1
边界为(0, 0)
中间节点为0
1 1 1 1 1 1
边界为(0, 1)
中间节点为0
1 2 1 1 1 1
边界为(0, 2)
中间节点为1
1 3 3 1 1 1
边界为(0, 3)
中间节点为1
1 4 6 4 1 1
边界为(0, 4)
中间节点为2
1 5 10 10 5 1
边界为(0, 5)
中间节点为2
由于在边界内部是对称的,我萌可以从中间节点向一侧边界遍历,循环几遍即可得到最终的结果。
// // Created by jt on 2020/9/2. // #include <vector> using namespace std; class Solution { public: /** * * @param rowIndex int整型 * @return int整型vector */ vector<int> getRow(int rowIndex) { // write code here vector<int> res(rowIndex+1, 1); for (int i = 2; i <= rowIndex; ++i) { for (int j = i / 2; j > 0; --j) { res[j] = res[j] + res[j-1]; res[i-j] = res[j]; // 对称 } } return res; } };