笔触狂放9

这个屌丝很懒，什么也没留下！

热门标签

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

作者：笔触狂放9 | 2024-05-29 13:35:20

踩

算法面试题

欢迎关 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
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

关于滑动窗口 B站也有讲解视频 https://www.bilibili.com/video/BV1V44y1s7zJ?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=f9b305274daffa5db46d0a6df9e6bdfa

字符串

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--
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

剑指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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

哈希表

需要使用键值对的情形，在处理字符串的时候可以提供一种特别的思路，

将字符做好映射

 // 26个字母
val records = IntArray(26)

for(element in s){
    records[element -'a']++
}
1
2
3
4
5
6

字母比较

可以通过字母数据，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)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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()
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

链表

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

由于链表的特点是操作当前节点需要找到前一个节点，由于头节点并没有前一个节点因此需要特殊操作，使用虚拟头结点就可以解决这个问题

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

核心要点
跟反转单链表中核心原理一致

保存节点
反转节点
移动节点

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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28