日常算法笔记.md

日常算法笔记

[TOC]

链表

1. 倒数第k个节点
   • 二次便利
   • 递归反向
   • 双指针
2. 链表中的环
   • 是否存在环
     • 穷举
     • 哈希（加快穷举速度而已）
     • 快慢指针：只要相遇就是有环
   • 环的入口
     • 利用快慢指针的数学性质，从相遇点和起点同时出发两个指针，相遇时就是环的入口
   • 环的长度
     • 快慢指针再出发，相遇的时候慢指针走过的步数就是长度
3. 逆序链表
   • 迭代/递归（需要空间复杂度）
   • 头插法依次处理（不需要额外空间）
4. 剩下所有需要依次处理的题目，如：多项式相加，有序链表合并，从头到尾打印链表，都可以使用两种方法来处理：
   • 迭代（逆序的话使用栈）
   • 递归

数组

1. 数组中重复的数字：

   1.1 返回任意一个重复数字

   1.2 不允许交换数组返回任意一个重复数字（20min编码）

• 二维数组的查找：

  • 暴力每一行二分
  • 从左上角和右下角寻找
  • 行找中间，每一行进行二分，然后递归查找。否则容易退化

• 在随机数组中找任意一个一个比两边的元素都大的元素：

  • 利用二分可以达到log（n），就向大的地方二分，题目类似于找极大值点。

C++ 编程日记

• 现在写代码需要这样的步骤：
  • 思考算法
  • 写代码之前先写测试，但是不要在代码里写了，太慢了
  • 写真正的代码
• 写函数的时候先考虑清楚所有的情况，把异常情况排除
• 写while循环的时候结束条件可以先空着，最后再考虑时么时候结束

关于 C++

• sizeof只有是作为数组的时候显示数组长度，当数组指针被赋值了以后就会变成指针的长度
• 调试：查看数组的元素：parray 6 nums

错误原因：

1. 本来是要交换数组里的值，但是最后先提取了数组的值，然后做的交换，数组的值没有变化啊！！

2. std报错:不仅在main函数里需要包含下面这两句，头文件里也要

   #include <iostream>
   using namespace std;