算法中小技巧

Bertha 。 2021-06-24 15:58 740阅读 0赞

## **思路** ##

1、递归可以从头到尾访问，也可以从尾到头访问  
2、前序的第一个访问节点是根节点，然后是左子树和右子树；中序先访问的是左子树，然后根节点和右子树  
3、一定要考虑特殊情况，null， 空值，长度为0啊  
4、分治算法将算法拆分，这也就意味着需要有合并的策略。  
5、递归，迭代一般能够将问题转换成同样的问题，但会减小问题难度。  
6、动态算法将子问题的最优解存储下来，以供父问题使用，也就存在一个从子问题到父问题的转换逻辑。  
7、贪心：局部最优能够保证后续的最优。

## **递归-存储** ##

如果递归计算过程中需要重复计算某个参数的值，则应该将其存储起来。

int fib(int n){
    	if(n<=1) return n;
    	return fib(n-1)+fib(n-1);
    }

int memo[MAXN+1];
    int fib(int n){
    	if(n<=1) return n;
    	if(memo[n]!=0) return memo[n];  //查询
    	return memo[n] = fib(n-1)+fib(n-1); //存储
    }

## **深度，广度搜索-剪枝** ##

穷竭搜索可能会将所有的可能解都检查一遍，但有时早已明确知道从当前状态无论如何转移也不会存在解，这种情况下应该跳过继续往下搜索。

## **memset赋值初始化** ##

memset是按字节为单位进行填充，一般可以直接赋值0、-1（每一位二进制都为1）。对于无穷大，一般采用0x3f3f3f3f

## **加速c++的cin和cout** ##

std::ios::sync\_with\_stdio(false); //cin，cout效率低是因为要把输入、输出的东西存入缓冲区，再输入、输出，导致效率降低。该语句可以来取消iostream的输入、输出缓存，使效率与scanf与printf相差无几。C++为了兼容C，保证程序在使用了std::printf和std::cout的时候不发生混乱，将输出流绑到了一起。  
cin.tie(NULL); //默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，会增加IO负担。可以通过tie(0)（0表示NULL）来解除cin与cout的绑定，进一步加快执行效率。

#include <iostream>
    int main() 
    {
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        // IO
    }