29道面试基础算法题，试试看会不会
欢迎关 Android茶话会 回 pdf 取阿里&字节经典面试题、Android、算法、Java等系列武功秘籍
在技术学习、个人成长的道路上，让我们一起前进！
本文主要整理了一些面试常见的算法题，涵盖 数组、字符串、哈希表、链表、二叉树
数组
704. 二分查找(easy)
描述
排序数组、无重复
要点分析
主要是在开闭区间选择上决定处理边界的不同，
1. [left,right]
闭区间 定义left，right = num.size-1,这样[left,right]两边都能取值，while循环比较时也是闭环
2. [left，right)
开区间 定义left，right = num.siz, 这样[left,right) 单边取值即可，while循环比较时开环
核心代码
//闭区间
定义left , right = nums.size-1 //由于两边都能取到 因此是闭区间
while(left<=right){
mid = (right+left) /2
if(nums[mid] == target){
return mid
} else if( nums[mid] < target){
//右边区间 [mid+1,right]
left = mid + 1
} else {
//左边区间 [left,mid-1]
right = mid - 1
}
}
//开区间
定义left , right = nums.size //由于两边都能取到 因此是闭区间
while(left<right){
mid = (right+left) /2
if(nums[mid] == target){
return mid
} else if( nums[mid] < target){
//右边区间 [mid+1,right）
left = mid +1
} else {
//左边区间 [left,mid)
right = mid
}
}
27. 移除数组元素(easy)
描述
一般会要求 O(1)空间，即不开辟新空间，返回移除元素后数组的长度
核心要点
有2种解法
- 暴力法，发现需要移除的元素，整体往前移动一位
这里就涉及到 双重for循环+元素交换，还需要改变size长度，（网图，侵删） 
效率低容易出错
- 快慢指针法
通过双指针简化for循环，这里涉及到快慢指针的定义，有时候遇到 快指针：不含有目标元素主要用来 (扫描) 慢指针：指向更新数组下标的位置 (不是目标值前进，是目标值停止)
核心代码
//双指针法
fun removeElement(nums: IntArray, `val`: Int): Int {
if (nums.isEmpty()) return -1
var slow = 0
for (fast in nums.indices) {
if (nums[fast] != `val`) {
nums[slow] = nums[fast]
slow++
}
}
//[0-slow]即为符合预期的数组元素
return slow
}
//双重for循环暴力破解
//发现相等的直接往前移动填满
fun removeElement2(nums: IntArray, `val`: Int): Int {
var size = nums.size
var index = 0
while (index < size) {
if (nums[index] == `val`) {
//暴力填充数组
for (indexInner in index until nums.size) {
nums[indexInner - 1] = nums[indexInner]
}
//此时下标i以后的数值向前移动了一位，所以i也向前移动一位
index--
//此时数组的大小-1
size--
}
index++
}
return index
}
977.有序数组的平方(easy)
描述
有序数组，平方之后也按顺序排序，不开辟新的空间
核心要点
平方之后，最大值分部在两头，这样就可以使用快慢指针来交换排序
代码
fun sortedSquares(nums: IntArray): IntArray {
var left = 0
var right = nums.size - 1
var result = IntArray(nums.size)
var index = nums.size - 1
while (left <= right) {
if (nums[left] * nums[left] > nums[right] * nums[right]) {
result[index--] = nums[left] * nums[left]
left++
} else {
result[index--] = nums[right] * nums[right]
right--
}
}
return result
}
209.(滑动窗口)长度最小的子数组(mid)
描述
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0，如: 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
要点分析
- 暴力循环 双重for循环
- 滑动窗口法
滑动窗口其实也是双指针的一种，需要重点把握的是 窗口内是什么？ 窗口起始位置如何移动？ 窗口结束位置如何移动？ 搞清楚这三个问题基本上就能拿下滑动窗口 滑动窗口有着自己的套路
回归到本题中，窗口内就是满足 sum>=s长度最小的连续子数组 窗口的起始位置如何移动：当前窗口值大于s了，窗口就要向前移动了(缩小窗口) 窗口的结束位置如何移动：窗口结束位置就是遍历数组的指针即for循环中的索引 本题的关键是如何调节起始窗口的位置
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置，从而将O(n^2)降低为O(n)
代码
//暴力法
fun minSubArrayLen0(target: Int, nums: IntArray): Int {
var sum = 0
//子序列长度
var subLength = 0
//每次比较之后的最终长度
var result = Int.MAX_VALUE
for (i in nums.indices) {
//每次sum = 0 重新累加
sum = 0
for (j in i until nums.size) {
sum += nums[j]
if (sum >= target) {
//记录此时的长度
subLength = j - i + 1
//对比之前的长度
result = if (result < subLength) return result else subLength
//符合条件跳出循环
break
}
}
}
return if(result == Int.MAX_VALUE) 0 else result
}
//滑动窗口
fun minSubArrayLen(target: Int, nums: IntArray): Int {
var sum = 0
var subLength = 0
var result = Int.MAX_VALUE
//滑动窗口起始位置
var left = 0
for(right in nums.indices){
//开始累加
sum += nums[right]
//滑动窗口
while(sum >= target){
subLength = right - left +1
result = if(result < subLength) result else subLength
//移动窗口左边界
sum-=nums[left++]
}
}
return if(result == Int.MAX_VALUE) 0 else result
}
关于滑动窗口 B站也有讲解视频 www.bilibili.com/video/BV1V4…
字符串
344. 反转字符串(easy)
核心要点
- 双指针
- 注意边界while(left<right)
通常这个方法作为一个辅助函数使用
代码
//典型的双指针
fun reverseString(s: CharArray): Unit {
if(s.isEmpty()) return
var left = 0
var right = s.size - 1
while(left < right){
//交换
var temp = s[left]
s[left] = s[right]
s[right] = temp
left++
right--
}
}
541. 反转字符串II
描述
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。 如果剩余字符少于 k 个，则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。 示例: 输入: s = "abcdefg", k = 2 输出: "bacdfeg"
要点分析
- 只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。
代码
fun reverseStr(s: String, k: Int): String {
val chars = s.toCharArray()
var index = 0
while (index < chars.size) {
var left = index
//这里是判断尾数够不够k个来取决end指针的位置
var right = Math.min(chars.size - 1, left + k - 1)
while (left < right) {
val temp = chars[left]
chars[left] = chars[right]
chars[right] = temp
//移动
left++
right--
}
index += 2 * k
}
return chars.toString()
}
剑指offer05 替换空格
描述
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例 1： 输入：s = "We are happy." 输出："We%20are%20happy."
要点分析：
- 不开辟新的空间，统计空格，扩充数组空间
- 双指针技巧
代码
class Solution {
public:
string replaceSpace(string s) {
int count = 0; // 统计空格的个数
int sOldSize = s.size();
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
count++;
}
}
// 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
s.resize(s.size() + count * 2);
int sNewSize = s.size();
// 从后先前将空格替换为"%20"
for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
if (s[j] != ' ') {
s[i] = s[j];
} else {
s[i] = '0';
s[i - 1] = '2';
s[i - 2] = '%';
i -= 2;
}
}
return s;
}
}
哈希表
需要使用键值对的情形，在处理字符串的时候可以提供一种特别的思路，
- 将字符做好映射
// 26个字母
val records = IntArray(26)
for(element in s){
records[element -'a']++
}
- 字母比较
可以通过字母数据，char-'a' 转换到字母位置，通常配合list更好处理
- 使用set 元素唯一性的特点
1. 两数之和(easy)
描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
要点分析
转换成键值对可以减少for循环
代码
fun twoSum(nums: IntArray, target: Int): IntArray {
if(nums.isEmpty()) return intArrayOf()
var tempMap = mutableMapOf<Int,Int>()
var records = mutableListOf<Int>()
for(index in nums.indices){
tempMap[nums[index]] = index
val matcher = target-nums[index]
if(tempMap.containsKey(matcher)){
records.add(tempMap[nums[index]] ?:0)
records.add(index)
return records.toIntArray()
}
}
return IntArray(0)
}
242.有效的字母异位数(easy)
描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false 说明: 你可以假设字符串只包含小写字母。
要点分析
- 利用26个字母有限数目，哈希成字母表
代码
fun isAnagram(s: String, t: String): Boolean {
if(s.length != t.length) return false
// 26个字母
val records = IntArray(26)
for(element in s){
records[element -'a']++
}
for(element in t){
records[element-'a']--
}
//如果有效字母异位词此时record数组应该都为0
for(value in records) {
//说明有不匹配的
if(value != 0){
return false
}
}
return true
}
349. 两个数组的交集(easy)
描述
给定两个数组，编写一个函数来计算他们的交集 示例: 输入: nums1=[1,2,2,1], nums2=[2,2] 输出: [2]
要点分析
- 将数组转化成 不重复 hashset
- 比较两个具有唯一值的 hashset
代码
fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
//边界判断
if(nums1.isEmpty() || nums2.isEmpty()) return IntArray(0)
val result = mutableListOf<Int>()
//将第一个转换为set过滤重复元素
val numSet = nums1.toSet()
for(num in nums2){
if(numSet.contains(num)&&!result.contains(num)){
result.add(num)
}
}
return result.toIntArray()
}
383. 赎金信
描述
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。 (题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)
要点分析
本题跟 242有效字母异位数比较像，只不过242题相当于 a,b两个字符串是否互相组成，而本题是 求字符串a能否由字符串b组成
代码
//字母匹配
fun canConstruct(ransomNote: String, magazine: String): Boolean {
if(ransomNote.isEmpty() || magazine.isEmpty()) return false
//26个字符
var records = IntArray(26)
//用magazine 添加
for(charMagazine in magazine){
records[charMagazine-'a']+=1
}
//用信封消除
for(charRansomeNote in ransomNote){
records[charRansomeNote-'a']-=1
}
//如果数组中存在负数则表示不匹配的
for(record in records){
if(record < 0) return false
}
return true
}
链表
链表涉及到指针，常用解决方法时双指针、增加虚拟头结点
由于链表的特点是操作当前节点需要找到前一个节点，由于头节点并没有前一个节点因此需要特殊操作，使用虚拟头结点就可以解决这个问题
203 移除链表元素(easy)
描述
删除链表中等于给定值 val 的所有节点 输入：head = [1,4,2,4], val = 4 输出：[1,2]
要点分析
主要是操作链表节点，防止移除元素是头结点，因此需要增加虚拟头节点
代码
// 虚拟节点
fun removeElements(head: ListNode?, `val`: Int): ListNode? {
if(head == null) return head
//前置一个虚拟节点
var virtualHead = ListNode(-1,head)
var temp:ListNode? = virtualHead
while(temp?.next != null){
if(temp.data == `val`){
//删除
temp.next = temp?.next?.next
} else {
//移动链表指针
temp = temp.next
}
}
return virtualHead.next
}
206.反转单链表(easy)
核心分析
- 虚拟头结点
- cur节点、pre节点交换
- cur，pre 前进
代码
//非递归
fun reverseList(head: ListNode?): ListNode? {
var pre:ListNode? = null
var cur = head
var temp:ListNode? = null
while(cur !=null){
//保存 cur的下一个节点,因为接下来要改变cur-next
temp = cur.next
//翻转
cur.next = pre
//移动 pre和cur
pre = cur
cur = temp
}
return pre
}
//递归版本
fun reverseList1(head: ListNode?): ListNode? {
return reverse(null, head)
}
private fun reverse(prev: ListNode?, cur: ListNode?): ListNode? {
if (cur == null) {
return prev
}
var temp: ListNode? = null
temp = cur.next // 先保存下一个节点
cur.next = prev // 反转
// 更新prev、cur位置
// prev = cur;
// cur = temp;
return reverse(cur, temp)
}
24. 两两交换链表中的元素(mid)
核心要点 跟反转单链表中核心原理一致
- 保存节点
- 反转节点
- 移动节点
image.png
fun swapPairs(head: ListNode?): ListNode? {
if (head == null) return null
// 构造虚拟节点
val virtualNode = ListNode(0, head)
//当前节点
var cur = virtualNode
while (cur.next != null && cur.next?.next != null) {
//保存节点
val temp = cur.next
val temp1 = cur.next?.next?.next
//翻转
cur.next = cur.next?.next
cur.next?.next = temp
cur.next?.next?.next = temp1
//移动2位 进行下一次循环
cur = cur.next?.next!!
}
return virtualNode.next
}
19. 删除链表倒数第N个节点(easy)
描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 进阶：使用一趟扫描实现
核心分析
- 虚拟头结点
- 双指针
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了
代码
fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
if(head == null) return null
//虚拟头节点,这样可以方便处理删除实际头结点的逻辑
var virtualNode = ListNode(0,head)
//双指针
var slowNode = virtualNode
var fastNode = virtualNode
//fast 先走n+1步
while(n > 0){
fastNode = fastNode.next
n--;
}
//找到倒数第N的节点
while(fastNode != null){
slowNode = slowNode.next
fastNode = fastNode.next
}
//此时curNode是倒数n个前节点
slowNode.next = slowNode.next?.next
return virtualNode.next
}
142.环形链表(mid)
核心要点
- 判断有没有环
经典的快慢指针问题，慢指针每次走1步，快指针每次走2步，那么有可能在环中相交
- 环的位置
先上结论
- 从头结点发出一个指针，从相遇节点也发出一个指针
- 这两个指针每次只走1步，那么这两个指针相遇的时候就是环形入口的节点
那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A
核心代码
class Solution {
fun detectCycle(head: ListNode?): ListNode? {
if(head == null) return null
var slow = head
var fast = head
var hasCircle = false
//判断是否有环
while(fast?.next != null){
//fast 每次走2步,slow每次走1步
fast = fast.next?.next
slow = slow?.next
if(fast == slow){
hasCircle = true
break
}
}
//没有环 直接退出
if(!hasCircle) return null
//有环 slow回到节点，slow fast每次走1步，相遇则是环的位置
slow = head
while(slow != fast){
slow = slow?.next
fast = fast?.next
}
return slow
}
}
二叉树
二叉树主要考察树的
- 二叉树的类型
满二叉树: 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树: 除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。
- 遍历
1.BFS(广度优先遍历) 一层层的遍历，结合队列 2.DFS(深度优先遍历) 先往深走，遇到叶子节点再往回走，递归或者结合栈
前序遍历中左右中序遍历左中右后序遍历左右中
dfs和bfs往往需要配合 栈和队列这些数据结构来，在非迭代遍历前中后序
144. (DFS)二叉树前中后遍历(easy)
145. 二叉树后序遍历
146. 二叉树中序遍历
102.(BFS)二叉树层序遍历(mid）
226. 翻转二叉树(easy)
101. 对称二叉树(easy)
104. 二叉树的最大深度(easy)
111. 二叉树的最小深度(easy)
257.二叉树的所有路径(mid)
112. 路径总和等于某个值(easy)
113. 路径总和II(mid)
二叉树更多 请关注 查看完整版
欢迎关 Android茶话会 回 pdf 取阿里&字节经典面试题、Android、算法、Java等系列武功秘籍
在技术学习、个人成长的道路上，让我们一起前进！
您的 点赞、评论，是对我的巨大鼓励！
转载自:https://juejin.cn/post/7236689719077617722