本文首要整理了一些面试常见的算法题，包括 数组、字符串、哈希表、链表、二叉树

数组

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){
returnmid
}elseif(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){
returnmid
}elseif(nums[mid]<target){
//右边区间[mid+1,right）
left=mid+1
}else{
//左面区间[left,mid)
right=mid
}
}

27. 移除数组元素(easy)

描绘

一般会要求 O(1)空间，即不拓荒新空间，回来移除元素后数组的长度

中心关键

有2种解法

  1. 暴力法，发现需求移除的元素，整体往前移动一位

这里就涉及到 双重for循环+元素交流，还需求改动size长度，（网图，侵删）

29道面试基础算法题，试试看会不会

功率低容易犯错

  1. 快慢指针法

经过双指针简化for循环，这里涉及到快慢指针的界说，有时分遇到 快指针：不含有目标元素首要用来 (扫描) 慢指针：指向更新数组下标的方位 (不是目标值行进，是目标值停止)

29道面试基础算法题，试试看会不会
中心代码

//双指针法
funremoveElement(nums:IntArray,`val`:Int):Int{
if(nums.isEmpty())return-1
varslow=0
for(fastinnums.indices){
if(nums[fast]!=`val`){
nums[slow]=nums[fast]
slow++
}
}
//[0-slow]即为符合预期的数组元素
returnslow
}
//双重for循环暴力破解
//发现持平的直接往前移动填满
funremoveElement2(nums:IntArray,`val`:Int):Int{
varsize=nums.size
varindex=0
while(index<size){
if(nums[index]==`val`){
//暴力填充数组
for(indexInnerinindexuntilnums.size){
nums[indexInner-1]=nums[indexInner]
}
//此刻下标i以后的数值向前移动了一位，所以i也向前移动一位
index--
//此刻数组的巨细-1
size--
}
index++
}
returnindex
}

977.有序数组的平方(easy)

描绘

有序数组，平方之后也按顺序排序，不拓荒新的空间

中心关键

平方之后，最大值分部在两头，这样就能够运用快慢指针来交流排序

29道面试基础算法题，试试看会不会

代码

funsortedSquares(nums:IntArray):IntArray{
varleft=0
varright=nums.size-1
varresult=IntArray(nums.size)
varindex=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--
}
}
returnresult
}

209.(滑动窗口)长度最小的子数组(mid)

描绘

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 接连 子数组，并回来其长度。假如不存在符合条件的子数组，回来 0，如: 输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

关键剖析

  1. 暴力循环 双重for循环
  2. 滑动窗口法

滑动窗口其实也是双指针的一种，需求重点把握的是 窗口内是什么？ 窗口开端方位怎么移动？ 窗口完毕方位怎么移动？ 搞清楚这三个问题基本上就能拿下滑动窗口 滑动窗口有着自己的套路

29道面试基础算法题，试试看会不会
回归到本题中，窗口内便是满足 sum>=s长度最小的接连子数组 窗口的开端方位怎么移动：当时窗口值大于s了，窗口就要向前移动了(缩小窗口) 窗口的完毕方位怎么移动：窗口完毕方位便是遍历数组的指针即for循环中的索引 本题的关键是怎么调节开端窗口的方位
29道面试基础算法题，试试看会不会
能够发现滑动窗口的精妙之处在于依据当时子序列和巨细的情况，不断调节子序列的开端方位，从而将O(n^2)降低为O(n) 代码

//暴力法
funminSubArrayLen0(target:Int,nums:IntArray):Int{
varsum=0
//子序列长度
varsubLength=0
//每次比较之后的最终长度
varresult=Int.MAX_VALUE
for(iinnums.indices){
//每次sum=0从头累加
sum=0
for(jiniuntilnums.size){
sum+=nums[j]
if(sum>=target){
//记载此刻的长度
subLength=j-i+1
//比照之前的长度
result=if(result<subLength)returnresultelsesubLength
//符合条件跳出循环
break
}
}
}
returnif(result==Int.MAX_VALUE)0elseresult
}
//滑动窗口
funminSubArrayLen(target:Int,nums:IntArray):Int{
varsum=0
varsubLength=0
varresult=Int.MAX_VALUE
//滑动窗口开端方位
varleft=0
for(rightinnums.indices){
//开端累加
sum+=nums[right]
//滑动窗口
while(sum>=target){
subLength=right-left+1
result=if(result<subLength)resultelsesubLength
//移动窗口左鸿沟
sum-=nums[left++]
}
}
returnif(result==Int.MAX_VALUE)0elseresult
}

关于滑动窗口 B站也有讲解视频 www.bilibili.com/video/BV1V4…

字符串

344. 回转字符串(easy)

中心关键

  • 双指针
  • 留意鸿沟while(left<right)

一般这个方法作为一个辅佐函数运用

29道面试基础算法题，试试看会不会

代码

//典型的双指针
funreverseString(s:CharArray):Unit{
if(s.isEmpty())return
varleft=0
varright=s.size-1
while(left<right){
//交流
vartemp=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 就能够了，然后判别是否需求有回转的区间。

代码

funreverseStr(s:String,k:Int):String{
valchars=s.toCharArray()
varindex=0
while(index<chars.size){
varleft=index
//这里是判别尾数够不够k个来取决end指针的方位
varright=Math.min(chars.size-1,left+k-1)
while(left<right){
valtemp=chars[left]
chars[left]=chars[right]
chars[right]=temp
//移动
left++
right--
}
index+=2*k
}
returnchars.toString()
}

剑指offer05 替换空格

描绘

请完成一个函数，把字符串 s 中的每个空格替换成”%20″。 示例 1： 输入：s = “We are happy.” 输出：”We%20are%20happy.”

关键剖析：

  • 不拓荒新的空间，核算空格，扩大数组空间
  • 双指针技巧

29道面试基础算法题，试试看会不会

代码

classSolution{
public:
stringreplaceSpace(strings){
intcount=0;//核算空格的个数
intsOldSize=s.size();
for(inti=0;i<s.size();i++){
if(s[i]==''){
count++;
}
}
//扩大字符串s的巨细，也便是每个空格替换成"%20"之后的巨细
s.resize(s.size()+count*2);
intsNewSize=s.size();
//从后从前将空格替换为"%20"
for(inti=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;
}
}
returns;
}
}

哈希表

需求运用键值对的景象，在处理字符串的时分能够提供一种特别的思路，

  • 将字符做好映射
//26个字母
valrecords=IntArray(26)
for(elementins){
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循环

29道面试基础算法题，试试看会不会
代码

funtwoSum(nums:IntArray,target:Int):IntArray{
if(nums.isEmpty())returnintArrayOf()
vartempMap=mutableMapOf<Int,Int>()
varrecords=mutableListOf<Int>()
for(indexinnums.indices){
tempMap[nums[index]]=index
valmatcher=target-nums[index]
if(tempMap.containsKey(matcher)){
records.add(tempMap[nums[index]]?:0)
records.add(index)
returnrecords.toIntArray()
}
}
returnIntArray(0)
}

242.有用的字母异位数(easy)

描绘

给定两个字符串 s 和 t ，编写一个函数来判别 t 是否是 s 的字母异位词。 示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true 示例 2: 输入: s = “rat”, t = “car” 输出: false 阐明: 你能够假定字符串只包含小写字母。

关键剖析

  • 运用26个字母有限数目，哈希成字母表

29道面试基础算法题，试试看会不会

代码

funisAnagram(s:String,t:String):Boolean{
if(s.length!=t.length)returnfalse
//26个字母
valrecords=IntArray(26)
for(elementins){
records[element-'a']++
}
for(elementint){
records[element-'a']--
}
//假如有用字母异位词此刻record数组应该都为0
for(valueinrecords){
//阐明有不匹配的
if(value!=0){
returnfalse
}
}
returntrue
}

349. 两个数组的交集(easy)

描绘

给定两个数组，编写一个函数来核算他们的交集 示例: 输入: nums1=[1,2,2,1], nums2=[2,2] 输出: [2]

关键剖析

  • 将数组转化成 不重复 hashset
  • 比较两个具有仅有值的 hashset

29道面试基础算法题，试试看会不会
代码

funintersection(nums1:IntArray,nums2:IntArray):IntArray{
//鸿沟判别
if(nums1.isEmpty()||nums2.isEmpty())returnIntArray(0)
valresult=mutableListOf<Int>()
//将第一个转换为set过滤重复元素
valnumSet=nums1.toSet()
for(numinnums2){
if(numSet.contains(num)&&!result.contains(num)){
result.add(num)
}
}
returnresult.toIntArray()
}

383. 赎金信

描绘

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判别第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。假如能够构成，回来 true ；否则回来 false。 (题目阐明：为了不露出赎金信笔迹，要从杂志上查找各个需求的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中运用一次。)

关键剖析

本题跟 242有用字母异位数比较像，只不过242题相当于 a,b两个字符串是否相互组成，而本题是 求字符串a能否由字符串b组成

代码

//字母匹配
funcanConstruct(ransomNote:String,magazine:String):Boolean{
if(ransomNote.isEmpty()||magazine.isEmpty())returnfalse
//26个字符
varrecords=IntArray(26)
//用magazine添加
for(charMagazineinmagazine){
records[charMagazine-'a']+=1
}
//用信封消除
for(charRansomeNoteinransomNote){
records[charRansomeNote-'a']-=1
}
//假如数组中存在负数则表示不匹配的
for(recordinrecords){
if(record<0)returnfalse
}
returntrue

}

链表

链表涉及到指针，常用解决方法时双指针、添加虚拟头结点

由于链表的特色是操作当时节点需求找到前一个节点，由于头节点并没有前一个节点因而需求特别操作，运用虚拟头结点就能够解决这个问题

203 移除链表元素(easy)

描绘

删去链表中等于给定值 val 的一切节点 输入：head = [1,4,2,4], val = 4 输出：[1,2]

关键剖析

首要是操作链表节点，避免移除元素是头结点，因而需求添加虚拟头节点

29道面试基础算法题，试试看会不会

代码

//虚拟节点
funremoveElements(head:ListNode?,`val`:Int):ListNode?{
if(head==null)returnhead
//前置一个虚拟节点
varvirtualHead=ListNode(-1,head)
vartemp:ListNode?=virtualHead
while(temp?.next!=null){
if(temp.data==`val`){
//删去
temp.next=temp?.next?.next
}else{
//移动链表指针
temp=temp.next
}
}
returnvirtualHead.next
}

206.回转单链表(easy)

中心剖析

  1. 虚拟头结点
  2. cur节点、pre节点交流
  3. cur，pre 行进

29道面试基础算法题，试试看会不会

代码

//非递归
funreverseList(head:ListNode?):ListNode?{
varpre:ListNode?=null
varcur=head
vartemp:ListNode?=null
while(cur!=null){
//保存cur的下一个节点,由于接下来要改动cur-next
temp=cur.next
//翻转
cur.next=pre
//移动pre和cur
pre=cur
cur=temp
}
returnpre
}
//递归版别
funreverseList1(head:ListNode?):ListNode?{
returnreverse(null,head)
}
privatefunreverse(prev:ListNode?,cur:ListNode?):ListNode?{
if(cur==null){
returnprev
}
vartemp:ListNode?=null
temp=cur.next//先保存下一个节点
cur.next=prev//回转
//更新prev、cur方位
//prev=cur;
//cur=temp;
returnreverse(cur,temp)
}

24. 两两交流链表中的元素(mid)

中心关键 跟回转单链表中中心原理一致

  1. 保存节点
  2. 回转节点
  3. 移动节点

29道面试基础算法题，试试看会不会

image.png

funswapPairs(head:ListNode?):ListNode?{
if(head==null)returnnull
//结构虚拟节点
valvirtualNode=ListNode(0,head)
//当时节点
varcur=virtualNode
while(cur.next!=null&&cur.next?.next!=null){
//保存节点
valtemp=cur.next
valtemp1=cur.next?.next?.next
//翻转
cur.next=cur.next?.next
cur.next?.next=temp
cur.next?.next?.next=temp1
//移动2位进行下一次循环
cur=cur.next?.next!!
}
returnvirtualNode.next
}

19. 删去链表倒数第N个节点(easy)

描绘

给你一个链表，删去链表的倒数第 n 个结点，而且回来链表的头结点。 进阶：运用一趟扫描完成

中心剖析

  • 虚拟头结点
  • 双指针

双指针的经典应用，假如要删去倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表结尾。删掉slow所指向的节点就能够了

代码

funremoveNthFromEnd(head:ListNode?,n:Int):ListNode?{
if(head==null)returnnull
//虚拟头节点,这样能够方便处理删去实际头结点的逻辑
varvirtualNode=ListNode(0,head)
//双指针
varslowNode=virtualNode
varfastNode=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
returnvirtualNode.next
}

142.环形链表(mid)

中心关键

  1. 判别有没有环

经典的快慢指针问题，慢指针每次走1步，快指针每次走2步，那么有或许在环中相交

29道面试基础算法题，试试看会不会

  1. 环的方位

先上结论

  • 从头结点宣布一个指针，从相遇节点也宣布一个指针
  • 这两个指针每次只走1步，那么这两个指针相遇的时分便是环形进口的节点

29道面试基础算法题，试试看会不会

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A

中心代码

classSolution{
fundetectCycle(head:ListNode?):ListNode?{
if(head==null)returnnull
varslow=head
varfast=head
varhasCircle=false
//判别是否有环
while(fast?.next!=null){
//fast每次走2步,slow每次走1步
fast=fast.next?.next
slow=slow?.next
if(fast==slow){
hasCircle=true
break
}
}
//没有环直接退出
if(!hasCircle)returnnull
//有环slow回到节点，slowfast每次走1步，相遇则是环的方位
slow=head
while(slow!=fast){
slow=slow?.next
fast=fast?.next
}
returnslow

}
}

二叉树

二叉树首要考察树的

  • 二叉树的类型

满二叉树: 假如一棵二叉树只有度为0的结点和度为2的结点，而且度为0的结点在同一层上，则这棵二叉树为满二叉树。

29道面试基础算法题，试试看会不会

彻底二叉树: 除了最底层节点或许没填满外，其他每层节点数都达到最大值，而且最下面一层的节点都会集在该层最左面的若干方位。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

29道面试基础算法题，试试看会不会

  • 遍历

1.BFS(广度优先遍历) 一层层的遍历，结合行列 2.DFS(深度优先遍历) 先往深走，遇到叶子节点再往回走，递归或许结合栈

  • 前序遍历 中左右
  • 中序遍历左中右
  • 后序遍历左右中

29道面试基础算法题，试试看会不会

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)

❝

二叉树更多 请重视 查看完整版

29道面试基础算法题，试试看会不会

❞