数组/字符串 --面试经典150题

tobegold574 Lv5
  2024-12-08 15:22:57 2024-12-08 15:22:57 Created   2024-12-15 09:04:07 2024-12-15 09:04:07 Updated    

删除有序数组中的重复元素 II(medium)

做题过程

过了一会儿才想出来用双指针，但是还是对如何组织代码没有思路，ε=(´ο｀*)))唉。

算法概述

原题

本题要求为删除出现两次以上的元素的重复项，只保留出现两次的状态，原地操作数组，返回最终长度。使用 双指针（快慢指针） 。

  • 时间复杂度为O(n)：双指针
  • 空间复杂度为O(1)：要求

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        // 直接符合要求
        if (n <= 2) {
            return n;
        }
        // 从第三个元素开始（冗余元素最先的可能位置）
        int slow = 2, fast = 2;
        // 遍历整个目标数组
        while (fast < n) {
            // 慢指针指向冗余元素
            // 快指针抵达排列中的下一个元素
            if (nums[slow - 2] != nums[fast]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        // slow会指向最后一个有效元素的索引
        return slow;
    }
}

总结

就是想不到能够写的这么优雅，我前面想的是是否有一堆判断条件要加入进来，但实际上只需要一个if (nums[slow - 2] != nums[fast])，为什么呢？因为这始终是一个 动态 的过程，也就是说每次对之前元素的重写并不会创建一个新的状态，而是在仍然在原本数组的基础上，也就是说 双指针 面对的是一个 动态 的目标数组，而它们每次的工作都是处理好 当前数字和下一个数字 ，它俩之间的差值就是 需要减少的数组长度 。

买卖股票的最佳时机 II(medium)

做题过程

这道题就是带了双指针的贪心，和上一题一样，一定要灵活的移动指针，再铺设底层贪心的思路，还是做出来了。然后发现自己写的一坨狗屎。

算法概述

原题

本题要求为给出股票价格的天数数组，拥有多次购买售出的机会，要求给出最高收益。就是 双指针+贪心 。实际上只需要 贪心 。

  • 时间复杂度为O(n)：一次遍历
  • 空间复杂度为O(1)

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxProfit(int[] prices) {
        int sum=0;
        int l=0,r=1;
        int profit=Integer.MIN_VALUE;

        while(r<prices.length){
            if(prices[l+1]<prices[l]) ++l;
            profit=Math.max(profit,prices[r]-prices[l]);
            if(r+1!=prices.length&&(prices[r]>prices[r+1])){
                l=r+1;
                ++r;
                sum+=profit;
                profit=Integer.MIN_VALUE;
            }
            ++r;
        }
        if(profit>0) sum+=profit;
        return sum;
    }
}

上面是我写的，这个是题解

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

总结

就是要搞清楚，其实完全不用考虑 在升序排列时的购买策略 ，因为 无论怎么买，收益都是一样的 。

题目的底层逻辑是一回事，但是观察规律更加重要

H指数(medium)

做题过程

叒加了依托判断，还没通过所有测试用例。

算法概述

原题

本题要求为给出论文被引次数数组，计算H指数（被引次数均大于等于该指数的论文数也大于等于该指数）。使用 排序 。

  • 时间复杂度为O(nlogn)
  • 空间复杂度为O(logn)：容器排序实现所需要的

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h=0,i=citations.length-1;
        // 从最大的论文被引数开始向前递减，同时递增当前H指数
        while(i>=0&&citations[i]>h){
            h++;
            i--;
        }
        return h;
    }
}

总结

还是组织代码的能力，一定要放弃暴力+判断的组合，沉下心来深入思考怎么得到规律。

O(1)时间插入、删除和获取随机元素

做题过程

还是完全没搞懂这类设计类的题目的解题思路从哪里出发，就只知道用哈希表。

算法概述

原题

本题要求如题所示。使用 哈希表+变长数组 作为底层数据结构。

JAVA

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
class RandomizedSet {
    List<Integer> nums;
    Map<Integer, Integer> indices;
    Random random;

    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        indices = new HashMap<Integer, Integer>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (indices.containsKey(val)) {
            return false;
        }
        int index = nums.size();
        nums.add(val);
        // 重要的是用当前元素个数（索引）作为哈希表的值，便于后续删除
        indices.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        if (!indices.containsKey(val)) {
            return false;
        }
        // 获取删除元素索引
        int index = indices.get(val);
        // 获取当前最后一个元素
        int last = nums.get(nums.size() - 1);
        // 将当前最后一个元素替换删除元素
        nums.set(index, last);
        // 哈希表中同步更改
        indices.put(last, index);
        // 删除最后一个元素（此时是重复的）
        nums.remove(nums.size() - 1);
        // 哈希表中删除对应元素
        indices.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

总结

这种类设计就是要结合不同数据结构的优势，取长补短，所以要对各个数据结构的优势和具体的应用场景有更深一步的了解才行。

加油站(medium)

做题过程

感觉用数学解决，但是规律没找对。而且题目也读错了，还以为顺序不限，其实是循环一周😐。

算法概述

原题

本题要求为给出各个加油站可加的油和前往加油站所消耗的油量，给出能够循环一周的起点。

  • 时间复杂度为O(n)
  • 空间复杂度为O(1)

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        // minSum记录的是最少的总剩余油量
        int minSum = Integer.MAX_VALUE;
        int sum = 0;
        // 记录最小总剩余油量的索引
        int minIndex = 0;
        // 只从0开始进行一次遍历
        for (int i = 0; i < n; i++) {
            sum += gas[i] - cost[i];
            if (sum < minSum) {
                minSum = sum;
                minIndex = i;
            }
        }
        // 当sum小于0，说明不可能进行一次来回，%n循环遍历
        return sum < 0 ? -1 : ((minIndex + 1) % n);
        
    }
}

总结

官方题解是通过贪心的思路确定了 剪枝 ，下一次遍历不用从上一次遍历起点的下一个站点开始，而是从最后一个能达到的站点的后一个站点开始，因为不能遍历完的原因就是缺少了加油量大于耗油量的站点，但这样最坏的时间复杂度仍是$O(n^2)$。

这里的解法的思想是这样的：总剩余油量在下一次加油之前往往都要大于等于0，那么 从最坏情况考虑 ，根本 不用考虑次序 ，总剩余油量都会到一个最大负值，然后就会从负值开始往上到0，也就意味着最大负值站点之后的站点得到的都是正值，因为 起点是不耗油的 ，所以选择最大负值对应的下一个站点作为起点，那么就不会再进入负值了。

分发糖果(hard)

做题过程

题目一开始就没读懂，虽然看似很简单，但其实内在的关系还是有点复杂的，没做出来。

算法概述

原题

本题要求为给出孩子们的评分，相邻一对孩子中分数高的那个会比分数低的多一个糖果，至少每个孩子都有糖果，求最少需要多少个糖果，看似条件简单，但实际求解不依靠常用数据结构，而是对题目的理解和思维的敏捷度。

  • 时间复杂度为O(n)
  • 空间复杂度为O(1)：参考的是常数级求法，因为更加贴近滑动窗口的思路

JAVA

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
class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        // 只进行从左向右遍历一次
        for (int i = 1; i < n; i++) {
            // 在递增序列中
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                // 更新当前元素为pre
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                // 直接+1
                ret += pre;
                // 记录递增序列长度
                inc = pre;
            } else {    // 递减序列
                // 记录递减序列长度
                dec++;
                // 当递减序列数长度累积到和递增序列一样大
                if (dec == inc) {
                    // 则把递增序列的最后一个元素纳入递减序列，即最后一个元素的值会比在递增序列时大
                    dec++;
                }
                // 相当于从后往前加
                ret += dec;
                // pre重新设置，等待下一个递增序列
                pre = 1;
            }
        }
        return ret;
    }
}

总结

这道题的思想是把问题分化成 递增序列 和 递减序列 ，和滑动窗口的一些题目思想相类似，但难点在于 转化 和 迁移 。

罗马数字转整数(easy)

做题过程

就是判断前后元素谁大谁小就好了。

算法概述

原题

本题要求为将罗马数字转换为一般数字（罗马数字的特别之处是如果左边的数大就进行加法，反之减法）。 模拟 。

  • 时间复杂度为O(n)
  • 空间复杂度为O(1)

JAVA

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
class Solution {
    Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};

    public int romanToInt(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues.get(s.charAt(i));
            // 当右值大于左值且不越界
            if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
}

总结

模拟没有什么好的总结的。

整数转罗马数字(medium)

做题过程

做出来了，但靠的是硬编码和数位。

算法概述

原题

本题要求为将一般数字转为罗马数字。应该用 基于贪心的模拟 。

  • 时间复杂度为O(n)
  • 空间复杂度为O(1)

C++

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
const pair<int, string> valueSymbols[] = {
    {1000, "M"},
    {900,  "CM"},
    {500,  "D"},
    {400,  "CD"},
    {100,  "C"},
    {90,   "XC"},
    {50,   "L"},
    {40,   "XL"},
    {10,   "X"},
    {9,    "IX"},
    {5,    "V"},
    {4,    "IV"},
    {1,    "I"},
};

class Solution {
public:
    string intToRoman(int num) {
        string roman;
        for (const auto &[value, symbol] : valueSymbols) {
            // 从大往小的减
            while (num >= value) {
                num -= value;
                roman += symbol;
            }
            if (num == 0) {
                break;
            }
        }
        return roman;
    }
};

总结

其实写起来没比我的好，我的硬编码还少一点，主要是这个 贪心 的思路，放在其他情况也可用，不想我的思路基于数位，更有局限性。

最后一个单词的长度(easy)

做题过程

反向遍历，分类讨论，做出来了。

算法概述

原题

本题要求为给出一个用一些空格分隔单词的字符串，返回单词数量。 反向遍历 。

  • 时间复杂度为O(n)：最坏
  • 空间复杂度为O(1)

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLastWord(String s) {
        int index = s.length() - 1;
        // 找到最后一个单词
        while (s.charAt(index) == ' ') {
            index--;
        }
        int wordLength = 0;
        // 遍历最后一个单词
        while (index >= 0 && s.charAt(index) != ' ') {
            wordLength++;
            index--;
        }
        return wordLength;
    }
}

总结

最后还是采取了官方题解，因为我自己写的时候用的if较多，这样耦合性较高，我认为还是减少if，转而使用不同的while进行分离，更加合适。需要锻炼自己分离代码的能力。

最长公共前缀(easy)

做题过程

就是模拟。

算法概述

原题

本体要求为找出给出字符串中单词的最长前缀。 模拟 。

  • 时间复杂度为O(nm)：每个都遍历
  • 空间复杂度为O(1)

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return ""; // 特殊情况处理

        int i = 0; // 用于记录前缀的长度
        while (true) {
            // 判断是否越界
            if (i >= strs[0].length()) break;

            char t = strs[0].charAt(i); // 获取第一个字符串的第 i 个字符
            for (String s : strs) {
                // 如果当前字符串的长度小于等于 i 或字符不匹配，则结束
                if (i >= s.length() || s.charAt(i) != t) {
                    return strs[0].substring(0, i); // 返回公共前缀
                }
            }
            i++; // 前缀长度增加
        }
        return strs[0].substring(0, i); // 返回最长公共前缀
    }
}

总结

用的是GPT最后改的版本，写的更简洁一点，总之这样做思路很简单，也很基础。也可以通过 排序后 比较第一个和最后一个字符串的前缀来减少开销。

反转字符串中的单词(medium)

做题过程

要么就是栈，要么就是API，我直接看的答案。

算法概述

原题

本题要求为反转单词顺序，不改变单词本身。用API。

JAVA

1
2
3
4
5
6
7
8
9
10
class Solution {
    public String reverseWords(String s) {
        // 移除开头和结尾的空白字符
        s=s.trim();
        // \\s代表空白字符，+代表一个以上的个数
        List<String> wordList=Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ",wordList);
    }
}

总结

还是要会正则，和一些便于处理字符串的基本方法。

Z字形变换

做题过程

想了想顶多用滚动数组来优化，以及数学规律，又没做。

算法概述

原题

本题要求为按照给定的V字形高度（行数）处理输入字符串，然后逐行读取字符，变为新的字符串。

  • 时间复杂度为O(n)
  • 空间复杂度为O(1)：输出答案不算

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
class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.length(), r = numRows;
        if (r == 1 || r >= n) {
            return s;
        }
        string ans;
        // 一个V字形的长度
        int t = r * 2 - 2;
        // 以一个V字形为单位，平行处理多个
        for (int i = 0; i < r; ++i) {
            // 跳至每个V字形中 
            for (int j = 0; j + i < n; j += t) {
                // 一个一个V地处理 
                ans += s[j + i]; 
                // 双向处理（从V的两个头向下）
                if (0 < i && i < r - 1 && j + t - i < n) {
                    ans += s[j + t - i];
                }
            }
        }
        return ans;
    }
};

总结

偏数学的还是用C++更方便，因为随机索引更加方便，然后还要学习这种类似多线程的代码结构。

找出字符串中第一个匹配项的下标(easy)

做题过程

M*N秒了，但其实用STL更快，有方法可用。然后优化为加法级别就需要用KMP算法。

算法概述

原题

本题要求为找出两个字符串的第一个匹配项，返回第一个相同元素索引。 KMP

  • 时间复杂度为O(n+m)：O(n)来自前缀函数（匹配字符串），O(m)来自使用前缀函数(longest prefix suffix)进行匹配
  • 空间复杂度为O(m)

C++

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
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        // 前缀函数
        vector<int> pi(m);
        // 计算模式字符串前缀函数（增量算法）
        for (int i = 1, j = 0; i < m; i++) {
            // 
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                // 用以跳过已经匹配的部分
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};

总结

就是用 动态前缀长度 定位j向后退到的地方，这样就可以节约从头遍历的时间。KMP算法是基础中的基础，需要熟练掌握。

文本左右对齐(hard)

做题过程

一看就是贪心+模拟，就没写了。

算法概述

原题

本体要求为对给定字符串数组按照规定的行长度划分格式。 贪心 。

  • 时间复杂度为O(n)：所有字符串长度总和
  • 空间复杂度为O(1)：答案不算

JAVA

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
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> ans = new ArrayList<String>();
        int right = 0, n = words.length;
        while (true) {
            int left = right; // 当前行的第一个单词在 words 的位置
            int sumLen = 0; // 统计这一行单词长度之和
            // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
                sumLen += words[right++].length();
            }

            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if (right == n) {
                StringBuffer sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                ans.add(sb.toString());
                return ans;
            }

            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;

            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
            if (numWords == 1) {
                StringBuffer sb = new StringBuffer(words[left]);
                sb.append(blank(numSpaces));
                ans.add(sb.toString());
                continue;
            }

            // 当前行不只一个单词
            int avgSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuffer sb = new StringBuffer();
            sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接额外加一个空格的单词
            sb.append(blank(avgSpaces));
            sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其余单词
            ans.add(sb.toString());
        }
    }

    // blank 返回长度为 n 的由空格组成的字符串
    public String blank(int n) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; ++i) {
            sb.append(' ');
        }
        return sb.toString();
    }

    // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
    public StringBuffer join(String[] words, int left, int right, String sep) {
        StringBuffer sb = new StringBuffer(words[left]);
        for (int i = left + 1; i < right; ++i) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }
}

总结

是老题了，不涉及复杂算法和逻辑，就麻烦在代码结构的管理上。

  • Title: 数组/字符串 --面试经典150题
  • Author: tobegold574
  • Created at : 2024-12-08 15:22:57
  • Updated at : 2024-12-15 09:04:07
  • Link: https://tobegold574.me/2024/12/08/数组-字符串-面试经典150题/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
数组/字符串 --面试经典150题
  1. 删除有序数组中的重复元素 II(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  2. 买卖股票的最佳时机 II(medium)
    1. 做题过程
    2. 算法概述
    3. Java
    4. 总结
  3. H指数(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  4. O(1)时间插入、删除和获取随机元素
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  5. 加油站(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  6. 分发糖果(hard)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  7. 罗马数字转整数(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  8. 整数转罗马数字(medium)
    1. 做题过程
    2. 算法概述
    3. C++
    4. 总结
  9. 最后一个单词的长度(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  10. 最长公共前缀(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  11. 反转字符串中的单词(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  12. Z字形变换
    1. 做题过程
    2. 算法概述
    4. 总结
  13. 找出字符串中第一个匹配项的下标(easy)
    1. 做题过程
    2. 算法概述
    3. C++
    4. 总结
  14. 文本左右对齐(hard)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结