算法

总体思路

测开岗高频算法题

测开岗的算法题难度相对要低一些，差不多都是剑指offer上或者力扣上的热门且难度为简单、中等的题。把每个标签的前5~10道题刷一刷，面试的时候基本够用。

三个数字的最大乘积

有两个很长很很长的字符串，但是字符都是数字，实现这俩字符串的加法，输出为一个字符串。如str1=”1231213347845713824718237489123748343246217489132”, str2=”623478573127438912743892017489132748172341324132”

两数之和 标签：哈希表 （★★★）

str1能不能最多交换两次字符变成str2，并设计测试用例。

和为s的连续正数序列 标签：暴力、双指针

有效括号 标签：栈 （★★★★）

数组中重复的数字 标签：哈希表 （★★★★★）

7的倍数或者包含7打印”-“，其余的打印数字，每行不超过5个数字

从1到100000000中取出一个数(自己申明一个变量，比如num = 2333)，写代码找出取出的是哪个数。 标签：二分查找

一个数在有序数组里出现的次数。标签：二分

字符串转整数，并写测试用例。 标签：数学，有很多非数字类型需要考虑，还有数字越界的情况需要考虑，比较考察测试思维 （★★★★★）

连续子数组的最大和 标签：分治、DP （★★★★）

在字符串中找出没有重复字符的最长的连续子串，并返回子串及长度，譬如“aaabcdcbcbbb” 最长子串为abcd，长度为4

判断链表是否有环 标签：双指针

两个栈实现一个队列 （★★）

最长不含重复字符的子字符串 标签：双指针、滑动窗口 （★★★★★）

数组

• 数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

704 二分查找

要注意选取的是左闭右闭的区间还是左闭右开的区间

27 原地移除数组中的元素

双指针思路:

• 快指针用于寻找”新“数组中的元素
• 慢指针是新数组的下标值
• 快指针遍历数组，当遇见不为val的数值（即新数组中的元素）则赋值给nums[slow]，遍历完就可得到新数组

977 有序数组的平方

• 思路：因为数组中有负数，所以平方之后最大值就在数组的两端，那么定义两个指针从两边往中间遍历

209 长度最小的子数组

• 滑动窗口:

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口就要向前移动了（也就是该缩小了,此时移动左边界）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的右指针，也就是for循环里的索引。

整体思路：
右指针遍历数组，将遍历到的值添加进结果数组
每当添加一个新的值之后，判断当前数组中的值是否大于目标值，若是大于则判断当前的长度是比已记录的长度小 然后移动左指针缩写窗口，并将窗口左端的值移出结果

⭐️54螺旋矩阵

略

算法思路:

1. 空值处理： 当 matrix 为空时，直接返回空列表 [] 即可。
2. 初始化： 矩阵 左、右、上、下 四个边界 l , r , t , b ，用于打印的结果列表 res 。
3. 循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。
   1. 根据边界打印，即将元素按顺序添加至列表 res 尾部。
   2. 边界向内收缩 1 （代表已被打印）。
   3. 判断边界是否相遇（是否打印完毕），若打印完毕则跳出。
      // 对左子表进行排序
4. 返回值： 返回 res 即可。

快速排序

思路

• 是基于分治的思想的排序算法，一次排序确定一个元素（枢轴元素）的位置，将整个表划分为左右两个子表
• 使用递归的思想，算法的输入数据是：最左下标、最右下标、数组
• 一趟划分的算法中，要注意循环跳出条件是low < high ,要注意在每次移动指针之前，都要判断low < high,最终返回的是排序好的枢轴元素的下标low

数组章节总结

• 数组是存放在连续内存空间上的相同类型数据的集合。
• 数组下标都是从0开始的。
• 数组内存空间的地址是连续的；因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

链表

链表理论基础

Java中链表的定义

public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

链表操作的两种方式：

• 直接使用原来的链表来进行删除操作。

• 设置一个虚拟头结点在进行删除操作。(推荐)

206 反转链表

• 申请两个指针pre和cur
• 申请一个temp记录cur的位置
• 原地反转链表指针
• 同时向后平移两个指针

203 移除链表元素

设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

• 注意遍历终止的条件是当前指针指向的节点为空

• 每一次判断之后同时移动两个指针

• 最后返回虚拟头结点的下一个节点即为新节点的头

707 设计链表

• 首先设计链表节点
• 然后用单链表+虚拟头结点实现需求

21 合并两个有序链表

• 依次比较两个链表的节点值做就行
• 注意一个链表遍历完了之后将另一个链表的剩余部分直接拼接到新链表尾部即可

哈希表理论基础和总结

哈希表是根据关键码的值而直接进行访问的数据结构

• 需要 判断一个元素是否出现过 或者一个元素出现的频次场景应该第一时间想到哈希法。

• 数组就是一张简单的hash表

• 使用哈希表的时候注意数据结构的选择

  • 数组 : 适用于元素不是太大的情况,将数据转换成哈希数组的效率较高，建议优先使用。
  • set :转变成set需要进行hash运算，效率较低。
  • map :要存放两个元素（数值和频率）（key和value）

• 解题思路

  • 先想到用哈希表 python中一律使用字典!
  • 考虑用什么存储结构

49 字母异位词分组

• 将字符串列表中的每一个字符串排序 排序之后如果一样 证明就是字母异位词

242 有效的字母异位词

• 申请一个长为26位的数组用来记录字符串中字母出现的次数，然后将字符串s的频次依次存入数组 数组下标对应26个字母， 数组的值对应频次；然后遍历字符串t减去对应频次；最后遍历数组，只要有位置上值不为0，就说明当前字母的出现频次不一样多
• 字母运算时会自动取 ASCII 码。
• 在Java中，s.charAt(i) 是一个常用的字符串（String）方法，用于获取字符串 s 中索引位置为 i 的字符

数组交集

• 思路是记录两个数组中相同元素出现的次数，只要都>1就证明是有交集 ; 因为记录频次所以想到用hash 因为不清楚数值的范围且哈希值比较少比较分散 所以不选择数组，而是使用set ， 在java中对应的数据结构就是hashset

• Java 基础回顾

在Java中，List是一个接口，它代表了一个有序的集合，允许重复的元素。List接口继承自Collection接口，它是集合框架中的一部分，用于存储一组元素，并且可以对这些元素进行访问、添加、删除和修改等操作。

Java中常用的List实现类包括：

ArrayList：基于数组实现的动态数组，支持随机访问，但在插入和删除操作时可能会涉及元素的移动。大小可以动态增长。
LinkedList：基于链表实现的双向链表，插入和删除操作性能较好，但随机访问效率较低。
Vector：与ArrayList类似，但是它是线程安全的，因此在多线程环境下使用较为安全，但性能相对较低。
List接口定义了一系列方法，包括但不限于：

int size()：返回列表中的元素数量。
boolean isEmpty()：检查列表是否为空。
boolean contains(Object o)：检查列表是否包含指定的元素。
boolean add(E e)：将指定的元素添加到列表的末尾。
void add(int index, E element)：将指定的元素插入到列表的指定位置。
E remove(int index)：移除列表中指定位置的元素。
void clear()：清空列表中的所有元素。
E get(int index)：返回列表中指定位置的元素。
E set(int index, E element)：将列表中指定位置的元素替换为指定的元素。

• 使用数组来做哈希的题目，是因为题目都限制了数值的大小;而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。此时就要使用另一种结构体了，set。

1 两数之和

• 思路：一边遍历，一边将其存入哈希表，在遍历时判断我们要找的元素之前是否出现过。

• 我们既要知道元素的值，还要知道元素的下标所以此时用set 和 数组都不合适 要使用map ，Java中对应的数据结构是hashmap

• 注意：map是要存放 遍历过 的元素, 我们是要判断元素是否出现过，所以元素得作为key ，而value用来存放元素在数组中对应的下标，因为最后要返回的是元素的下标

• 在遍历数组的时候，只需要去map查询目标元素是否已出现过，有的话就找到了，没有则将当前遍历的元素放入map中

202 快乐数

• 无限循环，即求和的过程中,如果求出的和反复出现了，那么就说明这个数永远不可能是快乐数了 所以无限循环的终止条件是n = 1 或着n重复出现过了 ,因为这里出现了判断一个数是否出现过的情况，所以用hash法
• 求和的过程中需要取出数值各个位上的数，这个算法经常用到，要记熟:用n % 10取出最小位上的数，然后n / 10舍去这一位

四数相加

• 思路：前两个数组遍历相加，把所有的和存到一个数组A里，同时要记录出现的次数；后两个数组遍历相加，把所有的和存在一个数组B里,同时要记录出现的次数；遍历A看看想要的数在B中是否存在
• 因为既要知道数，还要统计次数，所以使用map（键值对）作为hash表的存储结构，此时key是值，value是出现的次数
• 注意：两两分组的复杂度是n^2, 一三分组是n^3。
• 每次配对成功后，count计数应该是加value里的值

三数相加

• 先排序
• 去重逻辑（有了再考虑去重，而不是还没有用就去考虑去重）
• 双指针解 i left right

四数之和

• 思路类似三数之和 i j left right
• 注意剪枝操作和去重操作

字符串

替换空格

实现一个函数，将一个字符串中的所有空格替换为”%20”

这里关于字符串操作要注意:

• String 是不可变的，所以没有类似append、delete、replace等增删改的方法,需要操作的话必须先转化为StringBuffer类型

public class solution {

  //法1
  public static String replaceSpace( StringBuffer str){
    return str.toString().replace(" ","%20");//转换成字符串String类型，然后调用方法replace
  }

  // 法2 遍历字符串
  public static String replaceSpace2(StringBuffer str) {

    int length = str.length();
    StringBuffer result = new StringBuffer();
    // 遍历字符串
    for (int i = 0; i < length; i++) {
      char b = str.charAt(i);//取出当前index下的字符
      if (String.valueOf(b).equals(" ")) { //此处 String.valueOf方法用于将其他类型转化为字符串类型String
        result.append("%20"); //如果为空格 则在result后方插入%20
      } else {
        result.append(b); //如果不是则直接append
      }
    }
    return result.toString(); //由于result是StringBuffer类型 ， 所以要转化为String类型返回

  }
}

1768合并字符串

• 不可便字符序列String以及常用api

（1）boolean isEmpty()：字符串是否为空

（2）int length()：返回字符串的长度

（3）String concat(xx)：拼接

（4）boolean equals(Object obj)：比较字符串是否相等，区分大小写

（5）boolean equalsIgnoreCase(Object obj)：比较字符串是否相等，不区分大小写

（6）int compareTo(String other)：比较字符串大小，区分大小写，按照Unicode编码值比较大小

（7）int compareToIgnoreCase(String other)：比较字符串大小，不区分大小写

（8）String toLowerCase()：将字符串中大写字母转为小写

（9）String toUpperCase()：将字符串中小写字母转为大写

（10）String trim()：去掉字符串前后空白符

（11）public String intern()：结果在常量池中共享

• 可变字符序列StringBuilder和StringBuffer 前者线程不安全，后者线程安全 两者常用api一致

（1）StringBuffer append(xx)：提供了很多的append()方法，用于进行字符串追加的方式拼接

（2）StringBuffer delete(int start, int end)：删除[start,end)之间字符

（3）StringBuffer deleteCharAt(int index)：删除[index]位置字符

（4）StringBuffer replace(int start, int end, String str)：替换[start,end)范围的字符序列为str

（5）void setCharAt(int index, char c)：替换[index]位置字符

（6）char charAt(int index)：查找指定index位置上的字符

（7）StringBuffer insert(int index, xx)：在[index]位置插入xx

（8）int length()：返回存储的字符数据的长度

（9）StringBuffer reverse()：反转

解题思路

直接模拟过程就行

1071字符串的最大公因子

344 反转字符串

• 双指针秒了

541 反转字符串2

难点就在如何去除多余的空格：这其实就是删除元素的算法，需要使用快慢指针的方法: 快指针寻找符合要求的字母（要收集的字母）、慢指针就是来表示要更新在哪里

题目要求：

• 输入: “the sky is blue”
• 输出: “blue is sky the”
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解题思路：

• 将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。

所以解题思路如下：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

KMP算法

• 用以解决字符串匹配的问题 我直接放弃

双指针法

27 移除元素

• 暴力法：两层for循环

• 双指针法:

  • 快指针：遍历旧数组
  • 慢指针：指向新数组下标

19 移除链表倒数第N个元素

• 双指针法,让fast先移动n个，然后同时移动fast和slow直到fast指向链表尾部，然后删除slow指向的节点即可

459 重复的子字符串

• 暴力法：一个for循环获取字串的终止位置，然后另一个for循环判断字串是否能重复构成字符串；不需要遍历到结尾，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。

链表相交

• 两链表相交的起始节点，代表指针相同，而不是值相同

• 如下图 只要定义两个指针 同时移动，如若有交点 一定会左a+c+b步之后相遇

  

二叉树

回溯算法

⭐️贪心算法

⭐️动态规划

其他

9. 回文数

• 反转后看是否和原来的数字相等

将整数反转的代码

public int reverseNum(int x ){
  int temp = x;
  int rev = 0;
  while (temp != 0){
    int p = temp % 10;
    temp = temp / 10;
    rev = rev * 10 + p;
  }
  return rev;
}