算法中小技巧 Bertha 。 2021-06-24 15:58 606阅读 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 }
还没有评论,来说两句吧...