缘起

• 之前就想着刷的，但一直不曾系统过，2023年准备系统整一下，从基本到数据结构，到五大算法的难题

内容

一、基础、数组、字符串、指针

1.1、基础

1.2、数组

1.3、字符串

1.4、指针-链表

1.5、指针-树&二叉树

1.6、指针-图

二、数据结构和应用

2.1、stack栈

2.2、hash哈希

三、算法思路类

3.1、贪心

3.2、two pointers双指针

二分查找

3.3、DFS

3.4、回溯

3.5、动态规划

三、其它

1、基础题

• 7、reverse-integer
  • 输入-123，输出-321（easy）
  • 自己思路：判断第一位有没有符号，然后转成string，再反转，再拼上符号，再转整型。如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0，这个开始没考虑到。
  • code
  • 别人思路：
    • 用栈
• 13、roman-to-integer
  • 自己思路：就是把文字描述转换成代码语言
  • [code]
    • 自己写代码过程中，为了少写{}省空间，又把else给漏写，导致多执行一次，变成了顺序语句
• 9、palindrome-number
  • 自己思路：先判断是不是小于0，小于0直接false，大于0的情况下，to_string()转成字符串，二分对比，遇到不相同false
  • [code]
  • 别人思路：这个要学下人家的

2、数组

• 88、merge-sorted-array，合并两个有序数组，简单，2023-01-11
  • 自己思路：如果是之前的话，肯定是暴力了，现在用的方案是先合并，再sort
  • code
  • 别人思路：
• 35、search-insert-position，简单，2023-01-14
  • 输入: nums = [1,3,5,6], target = 5 输出: 2 输入: nums = [1,3,5,6], target = 7输出: 4【没找到7，插入到第4个位置上】
  • 自己思路：遇到有序嘛，直接二分查找，没想到，如果没找到要返回待插入位置，那就是返回low
  • [code]
    • 1）mid的时候没有放在while循环里，导致一直在cout<<3
    • 2）自己对mid的计算，还是不太熟悉，最开始直接用 (high-low)/2，这个要自己再琢磨一下
• 217、存在重复元素
• 53、最大子数组和
• 1、两数之和
• 121、买卖股票的最佳时机
• 118、杨辉三角
• 36、有效的数独
• 73、矩阵置零

数组above250

• 350、两个数组的交集II
• 566、重塑矩阵

3、字符串

• 58、length-of-last-word，简单，2023-01-14
  • 输入"a"，输出1 输入“ fly me to the moon ” 输出4
  • 自己思路
    • 取最后一位嘛，j--，只不是空' '就往前++，直接遇到空为止，跳出循环' '
  • [code]
    • 1）少写了一个else分支，导致空循环
    • 2）字符是不是空' '，不确定了，还有个就是边界处理不对，”a”这种竟然是输出0.
• 242、valid-anagram
  • 自己思路：先sort()一下，然后判断一下两个度的长度，相等后，再逐个比较。
  • [code]

字符串above250

• 387、字符串中的第一个唯一字符
• 383、赎金信

4、哈希表（map）

• 136、single-number
  • 思路：只出现一次，用hash，但用得不太熟悉，没用map，用成set，没有实现目标；想着再sort()一下，逐个比较的，这条路也没走通

  • // 2022-08-03做过一次，没做出来

  • [code]
    • 自己map的用法不熟悉啊，首先想到的竟然是set

5、栈

• 本身有点像考查stack的用法

• 20、valid-parentheses
  • （easy），判断括号，s = “()[]{}”，为true； s=”){“，为false
  • 自己思路：遇到左边的全部入栈，遇到右边的，跟栈里的top比较，配对就入栈【代码实现里面有几个问题】
    • 1、是不是要用if判断，还是switch，哪种效率高 【后面2个当时没想到，调代码才想到】
    • 2、如果括号的个数为奇数时，直接return false即可； 在stack<char> cstack时，一stack是模板要用类型，二是cstack在pop()时需要判断size()，不然会core掉
  • code
  • 别人思路：
• 150、evaluate-reverse-polish-notation
  • ，tokens = [“2”,”1”,”+”,”3”,”*”]，输出9，算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
  • 自己思路：用栈嘛，遇到符合了，前两个相加，注意一下，/和-时，顺序问题（靠近符合的元素作为除数）24（被除数）/8（除数）=3（商）
  • code
    • 1）switch语法生疏了
    • 2）用vertcor<string> tokens存的时候，自己想比较是不是+这种符合时，不知道用字符串比较tokens[i]=="+"，而是转成单字符比较tokens[i][0]=='+'
    • 3）还是把元素转成整型时，自己用的是atoi()，不知道还有stoi()，atoi()转负数时是不是会为0啊？，当然还有sstringstrem这种内容，这种IO就弄得更少了，基本都是现查。
• 232、用栈实现队列

  6、队列

7、链表

• 141、环形链表
• 21、合并两个有序链表

• 203、移除链表元素

• 206、reverse-linked-list 反转链表
  • 自己思路：想了一下用头插法（还是画图，确认了下，用头插还是尾插）2022-06-28，没做出来，当时也没啥思路
  • [code]
    • 四个问题：1）自己最开始时没有新new一个结点，直接用原来的，2）自己用new的时候，对于类的怎么用不熟了A *p = new A() 3）、最后输出多了一个，看代码想了一下，才知道是new的时候有个默认值为0，就把从head->next输入了 4）、没想到用一个临时变量去接一下，不然那个值会被冲掉 头插法，懂了思路，真正实现，还有一段路要走
  • 其它思路：
• 83、删除排序链表中的重复元素

8、树

• 144、二叉树的前序遍历
• 94、二叉树的中序遍历
• 145、二叉树的后序遍历
• 102、二叉树的层次遍历
• 104、二叉树的最大深度
• 101、对称二叉树
• 226、翻转二叉村
• 112、路径总和
• 98、验证二叉搜索树
• 235、二叉搜索树的最近公共祖先

树above250

• 780、二叉搜索树中的搜索
• 701、二叉搜索树中的插入操作
• 653、两数之和IV-输入二叉搜索树

9、

10、

履历

其它摘抄

• 2020-12-11
  • 刷完前250道（先刷高频的50道，然后再分类刷，前150道，《剑指offer》，字符串、数组可以按主题刷）
  • 看到一道题，可能有这4种情况：
    • 1）无思路，可能题目都没看懂 【多读题目，读懂意思】
    • 2）有思路，代码实现不了
    • 3）代码实现了，但没有完全AC
    • 4）存在超时
  • 考察四方面能力
    • 一、审题能力：只看题面，进行理解和判断，本题用什么知识点能解（要不要看官方题解）
    • 二、编码能力：50道起步
    • 三、调试能力：有让少借助于IDE，确实应该在，代码写好后，自己再走读（code review）几下
    • 四、用例构造能力：异常场景、边界场景