当前位置：首页 > article >正文

每日算法一练：剑指offer——字符串篇（2）

article 2024/11/7 4:31:17

1.招式拆解I

某套连招动作记作序列 arr，其中 arr[i] 为第 i 个招式的名字。请返回 arr 中最多可以出连续不重复的多少个招式。

示例 1:

输入: arr = "dbascDdad"
输出: 6
解释: 因为连续且最长的招式序列是 "dbascD" 或 "bascDd"，所以其长度为 6。

示例 2:

输入: arr = "KKK"
输出: 1
解释: 因为无重复字符的最长子串是"K"所以其长度为 1。

示例 3:

输入: arr = "pwwkew"
输出: 3
解释: 因为连续且最长的招式序列是 "wke"，所以其长度为 3。     
请注意区分 子串 与 子序列 的概念：你的答案必须是 连续招式 的长度，也就是 子串。而 "pwke" 是一个非连续的 子序列，不是 子串。

提示：

0 <= arr.length <= 40000
arr 由英文字母、数字、符号和空格组成。

1.1滑动窗口+哈希表

代码实现思路

滑动窗口的概念：我们使用两个指针 i 和 j 来表示当前无重复字符的子串范围。i 是左边界，j 是右边界。
更新左指针：我们通过 i 保证 [i+1, j] 范围内没有重复字符。对于每个字符 arr[j]：
- 如果 arr[j] 出现过，那么我们将 i 移动到 arr[j] 上次出现的位置的后面，确保子串无重复。
更新哈希表：dic 记录每个字符上一次出现的位置，以便快速查找重复字符的位置。
更新结果：每次更新 res 为当前无重复子串的最大长度。

复杂度分析

时间复杂度：O(N)，其中 N 为字符串长度。因为每个字符最多访问两次（一次放入 dic，一次取出更新左指针 i）。
空间复杂度：O(1)，由于字符 ASCII 码范围有限（如 ASCII 字符集 128 位以内），哈希表 dic 最多使用固定大小的空间。

代码示例

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int dismantlingAction(String arr) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0, len = arr.length();
        
        for (int j = 0; j < len; j++) {
            char currentChar = arr.charAt(j);
            
            // 更新左指针 i
            if (dic.containsKey(currentChar)) {
                i = Math.max(i, dic.get(currentChar));
            }
            
            // 更新哈希表记录当前字符的最新索引
            dic.put(currentChar, j);
            
            // 计算当前无重复子串的长度，并更新最大长度
            res = Math.max(res, j - i);
        }
        
        return res;
    }
}

1.2动态规划+哈希表

状态定义与转移方程

状态定义：
- 定义 dp[j] 表示以字符 arr[j] 为结尾的最长不重复子字符串的长度。
- 我们可以压缩 dp 列表，将每次的 dp[j] 存入变量 tmp，并且使用变量 res 来记录目前的最大值。
转移方程：
- 假设在位置 j 上，字符 arr[j] 左侧距离最近的相同字符为 arr[i]（即 arr[i] == arr[j]）。
- 我们可以分情况讨论：
  - 如果字符 arr[j] 左边无重复字符（即 i < 0），则 dp[j] = dp[j - 1] + 1。
  - 如果前一状态的长度小于 j - i（即 dp[j - 1] < j - i），表示 arr[i] 不在子串范围 [i+1, j-1] 中。因此 dp[j] = dp[j - 1] + 1。
  - 如果前一状态的长度大于等于 j - i（即 dp[j - 1] >= j - i），说明 arr[i] 在当前子串中，因此此时的无重复子串以 arr[j] 结尾，长度为 j - i。
- 状态压缩：
  我们并不需要完整地存储 dp 列表。只需一个变量 tmp 存储 dp[j] 即可。每次遍历到新的字符时更新 tmp，并同时更新 res 记录最大的 dp[j] 值。

哈希表的使用

在每次遍历到字符 arr[j] 时，使用哈希表 dic 存储每个字符最后一次出现的索引位置。

通过 dic.getOrDefault(arr[j], -1) 可以获取 arr[j] 最近的重复位置索引 i。
如果 arr[j] 在当前子串范围内已经出现，则通过更新 tmp 来跳过这些字符，从而维持无重复子串的状态。

复杂度分析

时间复杂度：O(N)，其中 N 为字符串长度。每个字符在哈希表中的操作是 O(1)。
空间复杂度：O(1)，由于字符的 ASCII 码范围固定，哈希表 dic 使用的空间是有限的常数级别。

代码示例

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int dismantlingAction(String arr) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0, len = arr.length();
        
        for (int j = 0; j < len; j++) {
            int i = dic.getOrDefault(arr.charAt(j), -1); // 获取上次出现的位置索引 i
            dic.put(arr.charAt(j), j); // 更新字符出现的位置
            
            // 根据转移方程更新 tmp
            tmp = tmp < j - i ? tmp + 1 : j - i;
            
            // 更新最大长度
            res = Math.max(res, tmp);
        }
        
        return res;
    }
}

2.招式拆解II

某套连招动作记作仅由小写字母组成的序列 arr，其中 arr[i] 第 i 个招式的名字。请返回第一个只出现一次的招式名称，如不存在请返回空格。

示例 1：

输入：arr = "abbccdeff"
输出：'a'

示例 2：

输入：arr = "ccdd"
输出：' '

限制：

0 <= arr.length <= 50000

`2.1哈希表`

解题思路

哈希表统计字符频率：
- 遍历字符串 arr，用哈希表记录每个字符的出现次数。
- 如果字符第一次出现，存储 true 表示该字符目前只出现一次；如果字符再次出现，将其值设为 false，表示出现次数超过一次。
查找第一个不重复字符：
- 再次遍历字符串 arr，根据哈希表找到第一个值为 true 的字符并返回它。
- 如果遍历完仍未找到，返回空格 ' ' 表示不存在只出现一次的字符。

复杂度分析

时间复杂度：O(N)，其中 N 是字符串 arr 的长度。遍历字符串两次，每次是 O(N)，哈希表查找和插入的平均时间复杂度是 O(1)。
空间复杂度：O(1)，因为字符集限制为小写字母，最多只有 26 个不同字符，哈希表所需的额外空间是固定的 O(1)。

代码示例

import java.util.HashMap;

class Solution {
    public char dismantlingAction(String arr) {
        HashMap<Character, Boolean> hmap = new HashMap<>();
        char[] sc = arr.toCharArray();
        
        // 统计每个字符的出现情况
        for (char c : sc) {
            hmap.put(c, !hmap.containsKey(c));
        }
        
        // 查找第一个只出现一次的字符
        for (char c : sc) {
            if (hmap.get(c)) return c;
        }
        
        // 如果没有找到返回空格
        return ' ';
    }
}

2.2有序哈希表

解题思路

使用有序哈希表（在 Java 中使用 LinkedHashMap）的实现可以优化查找首个只出现一次的字符，因为 LinkedHashMap 会按插入顺序保存键值对。这样一来，在统计字符频率后，可以直接遍历有序的哈希表来查找第一个只出现一次的字符，避免再次遍历整个字符串，从而提高效率。

复杂度分析

时间复杂度：O(N)，其中 N 是字符串 arr 的长度。遍历字符串一次构建有序哈希表，遍历哈希表一次找出第一个只出现一次的字符。
空间复杂度：O(1)，由于只包含小写字母，哈希表最多包含 26 个字符，因此额外空间复杂度为 O(1)。

代码示例

import java.util.LinkedHashMap;
import java.util.Map;

class Solution {
    public char dismantlingAction(String arr) {
        Map<Character, Boolean> hmap = new LinkedHashMap<>();
        char[] sc = arr.toCharArray();
        
        // 统计每个字符的出现情况，并记录顺序
        for (char c : sc) {
            hmap.put(c, !hmap.containsKey(c)); // 记录字符是否只出现一次
        }
        
        // 查找第一个只出现一次的字符
        for (Map.Entry<Character, Boolean> entry : hmap.entrySet()) {
            if (entry.getValue()) return entry.getKey();
        }
        
        // 如果没有找到返回空格
        return ' ';
    }
}

查看全文

http://www.kler.cn/a/382492.html