C++ 二分查找、线性枚举、模拟-拓冰建站

二分查找，伪代码见下

function findMinGreenIndex(array, len, target)

l = -1, r = len

while l + 1 < r

mid = (l + r) / 2

if isGreen(array, mid, target)

r = mid

else

l = mid

return r

function isGreen(array, mid, target)

return array[mid] >= target

线性枚举特点：暴力算法、简单有效、用于开拓思路

求最大值的代码：

function getMax(n,a)

max = -inf;

for i -> (0, n-1)

if a[i] >max

max = a[i]

return max

线性枚举，对应力扣，有序数组中的单一元素，代码见下

class Solution {
public:int singleNonDuplicate(vector<int>& nums) {for(int i=1; i<nums.size()-1; ++i){if(nums[i] != nums[i-1] && nums[i] != nums[i+1]){return nums[i];}}if(nums.size() == 1){return nums[0];}if(nums[0] != nums[1]){return nums[0];}return nums.back();}
};

模拟（概念）：模拟算法其实是根据题目做，题目要求什么，就去做什么，有以下关键点：

第一点：数据结构，对于模拟题而言，最关键的其实是数据结构，看到一个问题，选择合适的数据结构，然后根据问题实现对应的功能。模拟题常见的数据结构是：数组、字符串、矩阵、二叉树、链表等等

第二点：算法技巧，模拟时一般会用到一些算法技巧，或者说混合算法，比如排序，递归，迭代等等

模拟题一：对应力扣，交换数字，代码见下

class Solution {
public:vector<int> swapNumbers(vector<int>& numbers) {a[0] = a[0] ^ a[1];a[1] = a[0] ^ a[1];a[0] = a[0] ^ a[1]; return a;}
};

模拟题二：对应力扣，位1的个数，代码见下

class Solution {
public:int hammingWeight(uint32_t n) {int sum = 0;while(n){sum += n & 1;n = (n >> 1);}return sum;}
};

递推：递推就是一个循环和迭代的过程。

递推例子：

1 斐波那契数列 F(0) = 0 F(1) = 1

F(n) = F(n-1) + F(n-2) ，其中n > 1，给定n（0<=n<=30），请计算F(n)

伪代码见下：

int fib(int n){

int i;

int F(31) = {0, 1};

for(i=2; i<=n; ++i){

F[i] = F[i-1] + F[i-2];

}

return F[n];

}

2 泰波那契序列

T(0) = 0; T(1) = 1; T(2) = 1

且在 n > 2的情况下，T(n) = T(n-1) + T(n-2) + T(n-3)

3 二维递推问题：如果一维解决不了问题的话，需要升维度处理。

代码练习 1 ，对应力扣斐波那契数列，代码见下：

class Solution {
public:int fib(int n) {int f[31];f[0] = 0;f[1] = 1;for(int i=2; i<=n; ++i){f[i] = f[i-1] + f[i-2];}return f[n];}
};

代码练习2 ，对应力扣，杨辉三角 ||

class Solution {
public:vector<int> getRow(int rowIndex) {int f[2][34];int now = 1;int pre = 0;f[pre][0] = 1;for(int i=1; i<=rowIndex; ++i){for(int j=0; j<=i; ++j){if(j == 0 || j == i){f[now][j] = 1;}else{f[now][j] = f[pre][j]+f[pre][j-1];}}pre = 1 - pre;now = 1 - now;}vector<int> res;for(int j=0; j<=rowIndex; ++j){res.push_back(f[pre][j]);}return res;}
};