cppStart

Start

Install complier


sudo apt install g++;

Create a cpp file


#include <iostream>

int main(){
    using namespace std;
    cout << "Hello Wolrd\n";
    return 0;
}

Compile and debug

press F5 to compile and debug. (config files are in /.vscode/ )

Complie single source file and multi single files

Edit .vscode/tasks.json

 {
     ...

     "args": [

         "-Wall",
         "-g",
         // "${file}",      // 单个源文件编译
         "${fileDirname}/*.cpp", // 当前路径下所有源文件编译
         "-o",
         // "${fileDirname}/${fileBasenameNoExtension}.out",  // 单个源文件编译输出: 文件名.out
         "${fileDirname}/main.out" // 多个源文件编译输出: main.out
     ],

     ...
 }

初级算法
- 数组
  - 买股票的最佳时机-2

代码随想录

数组

二分法、双指针法、滑动窗口、模拟行为 https://mp.weixin.qq.com/s/LIfQFRJBH5ENTZpvixHEmg

35 搜索插入位置二分搜索注意数组区间
27 移除元素/数组去重双指针
- 一个快指针不停取非重复数，非重复数swap到慢指针，
- 慢指针最终位置即新不重复数组
209 长度最小的子数组双指针滑窗法
59 螺旋矩阵II 模拟顺时针画矩阵、循环不变式、注意数组区间

链表

203 移除链表元素使用虚拟头节点（在单链表中移除头结和移除其他节点的操作方式是不一样）
707 设计链表使用虚拟头节点 size struct
206 反转链表（相邻）双指针/重新创建/递归
141 环形链表快慢双指针
142 环形链表2 找环形链表入口双指针、解方程、归纳

哈希表/散列表** hash table（数组集合set 映射map）

底层实现：哈希表O(1)/红黑树O(logn)

  虽然map是万能的，但也要知道什么时候用数组，什么时候用set
  数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
  set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为要返回x 和 y的下表。所以set 也不能用。
  https://mp.weixin.qq.com/s/g8N6WmoQmsCUw3_BaWxHZA
  https://mp.weixin.qq.com/s/1s91yXtarL-PkX07BfnwLg

242 有效的字母异位词排序比较/数组哈希表/哈希表
349 两个数组的交集 unordered_set
202 快乐数不停计算，结果存到unordered_set，有即是快乐数
1 两数之和 unordered_map 存储每一次的数target-curr查是否存在与map中。O(n)
454 四数相加II 分组 + 哈希表 o(n^2)
383. 赎金信 (只有小写字母)数组/哈希表 O(n)
15 三数之和排序+双指针 o(n^2) / ~~哈希表法~~
18 四数之和排序+双指针 o(n^3) / ~~哈希表法~~

字符串

char-code计算 s - 'a'

344 反转字符串（首尾）双指针
541 反转字符串2 每隔2k个反转一次，注意区间/（首尾双指针
剑指offer05 替换空格双指针/从后往前填充 s.resiz(s.size()+count*2)
- 先把s resize到对应的长度（每有一个空格长度加2）
- 再从后开始填充字符串（从前往后需要O(n^2)因为从前往后需把每个字符串往后挪动）
151 翻转字符串里的单词
- 移除多余空格移除首尾空格+移除字间空格+双指针移+resize
- 反转字符串首尾双指针反转字符串
- 反转单词遍历+每个单词块中首尾双指针反转字符串
剑指Offer58-II. 左旋转字符串

      例如 ：示例1中 输入：字符串abcdefg，n=2
      反转区间为前n的子串 ：bacdefg
      反转区间为n到末尾的子串：bagfedc
      反转整个字符串：cdefgab

- 反转0到n个字符串
- 反转n到末尾的字符串
- 反转整个字符串即是答案

KMP算法：解决字符串匹配的问题 https://leetcode-cn.com/problems/implement-strstr/solution/bang-ni-ba-kmpsuan-fa-xue-ge-tong-tou-ming-ming-ba/
- 最长相等前后缀
- 前缀表、后缀表：
- 前缀：包含首字母不包含尾字母的所有字符串
- 后缀：包含尾字母不包含首字母的所有字符串
- 一个字符没有前缀也没有后缀
- PMT中的值是字符串的前缀集合与后缀集合的交集最长元素的长度
28 实现strStr kmp算法解决/已学习
458 重复的字符串

双指针法

栈与队列

232 用栈实现队列
- 两个栈负负得正
225 用队列实现栈
- 一个队列操作、另一个队列用于备份，pop到剩一个即是后出，再从备份队列拷贝回来
20 有效的括号
- map存储左右括号匹配，三种情况：左括号多了、右括号多了右括号不一致
1047 删除字符串中的所有相邻重复项
- 栈，空栈或当前字符不等于栈顶字符即入栈，否则出栈，最出栈内字符的逆序（先进后出，所以需要reverse一下）
150 逆波兰表达式求值 - 已学习
239 滑动窗口最大值 - 实现单调队列 - 已学习
347 前 K 个高频元素 - 已学习
- 建堆堆排序

二叉树

二叉树解题的大忌就是自己稀里糊涂的过了，但是也不知道自己是怎么遍历的。

中序遍历，（通过一个全局值存储上一节点值）判断节点值是否有序递增，（注意return值是左右都为true才是返回true）

回溯算法

1. 关于回溯
- 什么是回溯法
- 回溯法的效率 虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。 因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
- 回溯法解决的问题
  - 组合问题：N个数里面按一定规则找出k个数的集合
  - 切割问题：一个字符串按一定规则有几种切割方式
  - 子集问题：一个N个数的集合里有多少符合条件的子集
  - 排列问题：N个数按一定规则全排列，有几种排列方式
  - 棋盘问题：N皇后，解数独等等
- 如何理解回溯法
  - 回溯法解决的问题都可以抽象为树形结构（N叉树），是的，我指的是所有回溯法的问题都可以抽象为树形结构！
  - 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

        void backtracking(参数) {
          if (终止条件) {
              存放结果;
              return;
          }

          for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
              处理节点;
              backtracking(路径，选择列表); // 递归
              回溯，撤销处理结果
          }
      }

贪心算法

动态规划

动态规划思想：找出递推公式（规律）, 自底向上积累出结果
动规五部曲
- 1 确定dp数组以及下标的含义
- 2 确定递推公式
- 3 确定dp数组如何初始化
- 4 确定遍历顺序（以及idx,循环次数）
- 5 举例推导dp数组（手动推导几个正确的结果比如0-3的结果）
[509] 斐波那契数动态规划解法
[70] 爬楼梯
[746] 使用最小花费爬楼梯
小结
[62] 不同路径
[63] 不同路径 II
[343] 整数拆分
[96] 不同的二叉搜索树
背包问题系列
- 01背包

其他练习

数组

两数之和哈希表 o(n)
三数之和排序+双指针 o(n^2)
四数之和排序+双指针 o(n^3)
js数组扁平化简单递归/迭代
384 打乱数组
- 伪随机数生成器，数组中每个数字与当前idx到末尾的一个idx进行swap
- 排列的相同机会
- knuth-shuffle算法
- 标准库有shuffle实现(c++、js都有)
- seed不能设置为时间，不然无法通过用例..
旋转数组
80. 删除有序数组中的重复项 II
- 双指针、cnt、区间

树

129 求根到叶子节点数字之和 DFS 带参prev递归，非用和尾调用版本
589 N叉树的前序遍历
- 递归法 children遍历之前push 根节点优先，兄弟节点顺序按遍历顺序
- 迭代法即N叉树的层序
590 N叉树的后序遍历
- children遍历之后push 根节点最后，兄弟节点顺序按遍历顺序
429 N叉树的层序遍历
- 队列 push节点记录层级
找扁平N叉树的所有路径
1490 克隆N叉树
- N叉树的先序遍历/ 尾递归和非尾递归
102 二叉树的层序遍历:
- 队列实现、且push节点时需要记录层级
107 二叉树的层序遍历2
- 队列实现、且push节点时需要记录层级
- 自底向上顺序，需要把结果数组reverse
剑指 Offer 33. 二叉搜索树的后序遍历序列

二分查找

- [ ] 69 x的平方根 
  - 1 二分查找/需要注意ans更新的时机
  - 2 牛顿迭代法
  - 3 袖珍计算器算法 https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/
- [ ] 153.寻找旋转排序数组中的最小值

Name		Name	Last commit message	Last commit date
Latest commit History 283 Commits
.vscode		.vscode
PAT		PAT
SimpleCppServer		SimpleCppServer
algorithm/sort/nlogn		algorithm/sort/nlogn
benchmark/nbody		benchmark/nbody
designpattern/创建型模式		designpattern/创建型模式
leetcode-extension/leetcode-extension		leetcode-extension/leetcode-extension
leetcode-learn		leetcode-learn
leetcode		leetcode
notes		notes
practice		practice
tryCmake		tryCmake
tryQt/helloworld		tryQt/helloworld
.gitignore		.gitignore
README.md		README.md
package.json		package.json
yarn.lock		yarn.lock
小结.md		小结.md

leoooy/cppStart

Folders and files

Latest commit

History

Repository files navigation

cppStart

Start

Complie single source file and multi single files

数组

链表

哈希表/散列表** hash table（数组 集合set 映射map）

字符串

双指针法

栈与队列

二叉树

回溯算法

贪心算法

动态规划

其他练习

数组

树

二分查找

About

Resources

Stars

Watchers

Forks

Languages

哈希表/散列表** hash table（数组集合set 映射map）