跳至主要內容

【不定滑窗】2024E-字符串摘要

【不定滑窗】2024E-字符串摘要

[P3205] 【不定滑窗】2024E-字符串摘要

本题练习地址：https://www.algomooc.com/problem/P3205

视频直播讲解：2023/11/18 真题讲解

题目描述与示例

题目描述

给定一个字符串的摘要算法，请输出给定字符串的摘要值

  1. 去除字符串中非字母的符号
  2. 对于去除非字母符号后的字符串：
    1. 如果出现连续字符（不区分大小写），则输出: 该字母（小写) + 连续出现的次数
    2. 如果是非连续的字符（不区分大小写），则输出: 该字母（小写）之后字符串中出现的该字符的次数
  3. 对按照以上方式表示后的字符串进行排序：字母和紧随的数字作为一组进行排序，数字大的在前，数字相同的则按字母进行排序，字母小的在前。

输入描述

一行字符串，长度为[1,200]

输出描述

转换后的摘要字符串

示例一

输入

aabbcc

输出

a2b2c2

说明

示例二

输入

bAaAcBb

输出

a3b2b2c0

说明

第一个b非连续字母，该字母之后字符串中还出现了2次 (最后的两个Bb) ，所以输出b2；

a连续出现3次，输出a3；

c非连续，该字母之后字符串再没有出现过c，输出c0；

Bb连续2次，输出b2。

对b2a3c0b2进行排序，最终输出a3b2b2c0。

解题思路

去除非字母字符的操作非常简单，使用以下代码即可完成。

s = "".join(ch for ch in s if ch.isalpha())

每一个字符都会被摘要为字母+数字的形式。对于每一个字符ch，分为两种情况，若

  1. ch属于连续字母，那么后面的数字应该是本段连续字母的个数
  2. ch属于非连续字母，那么后面的数字应该是该ch右边的相同字母的个数

对于第一点，统计某一段连续字母的个数，可以用滑动窗口来解决这个问题。

对于第二点，储存每一个字符ch右边的相同字母的个数，很容想到用哈希表来储存元素个数，但需要从右往左遍历字符串s。

正因为上述问题的存在，所以滑动窗口的过程不再是常规的right右移再动left右移，而是先令left左移再令right左移，即构建一个从右往左进行的滑动窗口。

滑窗三问

**Q1：**对于每一个左指针left所指的元素ch，做什么操作？

**Q2：**右指针right移动到什么位置？

**Q3：**如何进行答案的更新？

滑窗三答

**A1：**将其与右指针right所指的元素s[right]进行比较

**A2：**右指针right移动到当前左指针left的位置，用于后续的继续判断

**A3：**右指针right所指字母和左指针letf所指字母不相同时，更新答案

代码

Python

# 题目：2024E-字符串摘要
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：滑动窗口
# 代码看不懂的地方，请直接在群上提问


# 用于更新答案的函数
def update(ans, dic, left, right, ch_right):
    # 当前窗口本段连续的ch的个数为right-left
    numContinue = right - left
    # 如果数量为1，说明本段窗口其实是非连续字母
    if numContinue == 1:
        # 储存该字符，以及该字符右边的相同字符的个数，储存在dic[ch_right]中
        ans.append((ch_right, dic[ch_right]))
    # 如果数量不为1，说明本段窗口是连续字母
    else:
        # 储存该字符，以及该字符连续出现的次数即numContinue
        ans.append((ch_right, numContinue))
    # 将ch_right出现的次数更新在dic中，用于后续的继续判断
    dic[ch_right] += numContinue


from collections import defaultdict

# 输入字符串
s = input()
# 去除非字母字符
s = "".join(ch for ch in s if ch.isalpha())

n = len(s)

# 初始化答案列表
ans = list()
# 初始化哈希表，用于记录一个字符ch右边，出现的相同字符的个数
dic = defaultdict(int)

# 初始化右指针
right = n-1
# 不同于传统的滑窗，要考虑一个从右往左滑动的滑动窗口
for left in range(n-1, -1, -1):
    # Q1：对于每一个左指针left所指的元素ch，做什么操作？
    # A1：将其与右指针right所指的元素s[right]进行比较
    ch = s[left].lower()
    ch_right = s[right].lower()
    # 如果两者是同一个字母（不区分大小写），
    # 说明当前窗口是一段连续的相同字符，则继续循环
    # 否则，需要进行right的左移和ans的修改
    if ch != ch_right:
        # Q3：如何进行答案的更新
        # A3：右指针right所指字母和左指针letf所指字母不相同时
        update(ans, dic, left, right, ch_right)
        # Q2：右指针移动到什么位置？
        # A2：右指针right移动到当前左指针left的位置，用于后续的继续判断
        right = left

# A3：退出循环后，还需要最后再做一次答案的更新
# 因为最左边的相同连续字符串实际上并没有在上述循环中被考虑到
# 需要取left = -1，right-left才能得到符合要求的连续字母长度
update(ans, dic, -1, right, s[right].lower())


# 退出循环，需要对ans中的元组进行排序
# 先按照数字降序排序，再按照字典序排序
ans.sort(key = lambda x: (-x[1], x[0]))
# 将ans中的二元组转为字符串，合并后输出
print("".join(item[0]+str(item[1]) for item in ans))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String s = input.replaceAll("[^a-zA-Z]", "");

        int n = s.length();
        List<Map.Entry<Character, Integer>> ans = new ArrayList<>();
        Map<Character, Integer> dic = new HashMap<>();

        int right = n - 1;
        for (int left = n - 1; left >= 0; left--) {
            char ch = Character.toLowerCase(s.charAt(left));
            char chRight = Character.toLowerCase(s.charAt(right));

            if (ch != chRight) {
                update(ans, dic, left, right, chRight);
                right = left;
            }
        }
        update(ans, dic, -1, right, Character.toLowerCase(s.charAt(right)));

        ans.sort((a, b) -> {
            if (!a.getValue().equals(b.getValue())) {
                return b.getValue() - a.getValue();
            } else {
                return a.getKey() - b.getKey();
            }
        });

        StringBuilder result = new StringBuilder();
        for (Map.Entry<Character, Integer> item : ans) {
            result.append(item.getKey()).append(item.getValue());
        }

        System.out.println(result.toString());
    }

    public static void update(List<Map.Entry<Character, Integer>> ans, Map<Character, Integer> dic, int left, int right, char chRight) {
        int numContinue = right - left;
        if (numContinue == 1) {
            ans.add(new AbstractMap.SimpleEntry<>(chRight, dic.getOrDefault(chRight, 0)));
        } else {
            ans.add(new AbstractMap.SimpleEntry<>(chRight, numContinue));
        }
        dic.put(chRight, dic.getOrDefault(chRight, 0) + numContinue);
    }
}

C++

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

void update(vector<pair<char, int>>& ans, map<char, int>& dic, int left, int right, char chRight) {
    int numContinue = right - left;
    if (numContinue == 1) {
        ans.push_back(make_pair(chRight, dic[chRight]));
    } else {
        ans.push_back(make_pair(chRight, numContinue));
    }
    dic[chRight] += numContinue;
}

int main() {
    string input;
    getline(cin, input);
    string s;
    for (char ch : input) {
        if (isalpha(ch)) {
            s += tolower(ch);
        }
    }

    int n = s.length();
    vector<pair<char, int>> ans;
    map<char, int> dic;

    int right = n - 1;
    for (int left = n - 1; left >= 0; left--) {
        char ch = tolower(s[left]);
        char chRight = tolower(s[right]);

        if (ch != chRight) {
            update(ans, dic, left, right, chRight);
            right = left;
        }
    }
    update(ans, dic, -1, right, tolower(s[right]));

    sort(ans.begin(), ans.end(), [](pair<char, int>& a, pair<char, int>& b) {
        if (a.second != b.second) {
            return b.second < a.second;
        } else {
            return a.first < b.first;
        }
    });

    string result;
    for (pair<char, int>& item : ans) {
        result += item.first + to_string(item.second);
    }

    cout << result << endl;

    return 0;
}

C

#include <stdio.h>
#include <ctype.h>
#include <string.h>

// 定义一个结构体，用于存储字符和其对应的数量
typedef struct {
    char ch;
    int count;
} Pair;

// 用于更新答案的函数
void update(Pair* ans, int* ansSize, int* dic, int left, int right, char chRight) {
    // 当前窗口的连续字符数量为 right - left
    int numContinue = right - left;

    // 如果数量为1，表示这个字符是非连续的
    if (numContinue == 1) {
        // 储存该字符，以及该字符右边的相同字符的个数
        ans[*ansSize].ch = chRight;
        ans[*ansSize].count = dic[chRight - 'a'];
        (*ansSize)++;
    } else {
        // 否则储存该字符及其连续出现的次数
        ans[*ansSize].ch = chRight;
        ans[*ansSize].count = numContinue;
        (*ansSize)++;
    }

    // 更新该字符的计数，用于后续判断
    dic[chRight - 'a'] += numContinue;
}

// 用于比较两个字符对的排序函数
int compare(const void* a, const void* b) {
    Pair* pairA = (Pair*)a;
    Pair* pairB = (Pair*)b;

    // 如果计数不同，按照计数降序排序
    if (pairA->count != pairB->count) {
        return pairB->count - pairA->count;
    }
    // 否则按照字母的字典顺序排序
    return pairA->ch - pairB->ch;
}

int main() {
    char input[1000], s[1000];
    // 读取输入的字符串
    fgets(input, sizeof(input), stdin);

    // 去除非字母字符，并将所有字符转换为小写
    int len = 0;
    for (int i = 0; input[i] != '\0'; i++) {
        if (isalpha(input[i])) {
            s[len++] = tolower(input[i]);
        }
    }
    s[len] = '\0';  // 结束符

    // 用于存储字符及其连续出现的次数
    Pair ans[1000];
    int ansSize = 0;
    
    // 字符字典，用于记录每个字符右边相同字符的个数
    int dic[26] = {0};

    // 初始化右指针
    int right = len - 1;

    // 从右向左遍历字符串，进行滑动窗口处理
    for (int left = len - 1; left >= 0; left--) {
        char ch = s[left];
        char chRight = s[right];

        // 如果左右指针对应的字符不同，则更新答案
        if (ch != chRight) {
            update(ans, &ansSize, dic, left, right, chRight);
            right = left;  // 更新右指针
        }
    }

    // 退出循环后，最后更新一次答案
    update(ans, &ansSize, dic, -1, right, s[right]);

    // 对答案按照计数降序，字母升序进行排序
    qsort(ans, ansSize, sizeof(Pair), compare);

    // 输出结果
    for (int i = 0; i < ansSize; i++) {
        printf("%c%d", ans[i].ch, ans[i].count);
    }
    printf("\n");

    return 0;
}

Node JavaScript

const readline = require('readline');

// 定义一个用于更新答案的函数
function update(ans, dic, left, right, chRight) {
    // 当前窗口本段连续的ch的个数为right - left
    let numContinue = right - left;
    // 如果数量为1，说明本段窗口其实是非连续字母
    if (numContinue === 1) {
        // 储存该字符，以及该字符右边的相同字符的个数，储存在dic[chRight]中
        ans.push([chRight, dic[chRight]]);
    } else {
        // 如果数量不为1，说明本段窗口是连续字母
        // 储存该字符，以及该字符连续出现的次数即numContinue
        ans.push([chRight, numContinue]);
    }
    // 将chRight出现的次数更新在dic中，用于后续的继续判断
    dic[chRight] += numContinue;
}

// 创建接口以读取用户输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 读取输入
rl.question('', (input) => {
    // 去除非字母字符
    let s = input.replace(/[^a-zA-Z]/g, '');

    let n = s.length;

    // 初始化答案列表
    let ans = [];
    // 初始化字典，用于记录一个字符ch右边，出现的相同字符的个数
    let dic = {};

    // 初始化字典的默认值为0
    for (let i = 0; i < 26; i++) {
        dic[String.fromCharCode(97 + i)] = 0;  // 初始化字典中的所有字母为0
    }

    // 初始化右指针
    let right = n - 1;

    // 从右向左滑动窗口
    for (let left = n - 1; left >= 0; left--) {
        let ch = s[left].toLowerCase();
        let chRight = s[right].toLowerCase();

        // 如果两者是同一个字母（不区分大小写），则继续循环
        if (ch !== chRight) {
            // 否则，更新答案并移动右指针
            update(ans, dic, left, right, chRight);
            right = left;
        }
    }

    // 最后一次更新答案，处理剩余的部分
    update(ans, dic, -1, right, s[right].toLowerCase());

    // 对ans中的元组进行排序
    // 先按照数字降序排序，再按照字母升序排序
    ans.sort((a, b) => {
        if (a[1] !== b[1]) {
            return b[1] - a[1];  // 按出现次数降序
        }
        return a[0].localeCompare(b[0]);  // 按字典序升序
    });

    // 将ans中的二元组转为字符串并输出结果
    const result = ans.map(item => `${item[0]}${item[1]}`).join('');
    console.log(result);

    rl.close();
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strings"
        "unicode"
)

// 用于更新答案的函数
func update(ans *[][2]interface{}, dic map[rune]int, left int, right int, chRight rune) {
        // 当前窗口本段连续的字符的个数为right-left
        numContinue := right - left
        // 如果数量为1，说明本段窗口其实是非连续字母
        if numContinue == 1 {
                // 储存该字符，以及该字符右边的相同字符的个数，储存在dic[chRight]中
                *ans = append(*ans, [2]interface{}{chRight, dic[chRight]})
        } else {
                // 如果数量不为1，说明本段窗口是连续字母
                // 储存该字符，以及该字符连续出现的次数即numContinue
                *ans = append(*ans, [2]interface{}{chRight, numContinue})
        }
        // 将chRight出现的次数更新在dic中，用于后续的继续判断
        dic[chRight] += numContinue
}

func main() {
        // 读取输入字符串
        scanner := bufio.NewScanner(os.Stdin)
        scanner.Scan()
        s := scanner.Text()

        // 去除非字母字符，并将字母转换为小写
        var filteredString strings.Builder
        for _, ch := range s {
                if unicode.IsLetter(ch) {
                        filteredString.WriteRune(unicode.ToLower(ch)) // 将字母转换为小写
                }
        }
        s = filteredString.String()
        n := len(s)

        // 初始化答案列表
        var ans [][2]interface{}
        // 初始化哈希表，用于记录一个字符ch右边，出现的相同字符的个数
        dic := make(map[rune]int)

        // 初始化右指针
        right := n - 1

        // 不同于传统的滑动窗口，要考虑一个从右往左滑动的窗口
        for left := n - 1; left >= 0; left-- {
                // Q1: 对于每一个左指针left所指的元素ch，做什么操作？
                // A1: 将其与右指针right所指的元素s[right]进行比较
                ch := rune(s[left])
                chRight := rune(s[right])

                // 如果两者是同一个字母（不区分大小写），
                // 说明当前窗口是一段连续的相同字符，则继续循环
                // 否则，需要进行right的左移和ans的修改
                if ch != chRight {
                        // Q3: 如何进行答案的更新？
                        // A3: 右指针right所指字母和左指针left所指字母不相同时
                        update(&ans, dic, left, right, chRight)
                        // Q2: 右指针移动到什么位置？
                        // A2: 右指针right移动到当前左指针left的位置，用于后续的继续判断
                        right = left
                }
        }

        // Q3: 退出循环后，还需要最后再做一次答案的更新
        // 因为最左边的相同连续字符串实际上并没有在上述循环中被考虑到
        // 需要取left = -1，right-left才能得到符合要求的连续字母长度
        update(&ans, dic, -1, right, rune(s[right]))

        // 退出循环，需要对ans中的元组进行排序
        // 先按照数字降序排序，再按照字典序排序
        sort.Slice(ans, func(i, j int) bool {
                if ans[i][1].(int) != ans[j][1].(int) {
                        return ans[i][1].(int) > ans[j][1].(int) // 按出现次数降序排序
                }
                return ans[i][0].(rune) < ans[j][0].(rune) // 按字典序升序排序
        })

        // 将ans中的二元组转为字符串，并输出结果
        var result strings.Builder
        for _, item := range ans {
                result.WriteRune(item[0].(rune))
                result.WriteString(fmt.Sprintf("%d", item[1]))
        }

        // 打印最终结果
        fmt.Println(result.String())
}

时空复杂度

时间复杂度：O(``N``)。仅需逆序遍历一次字符串s

空间复杂度：O(``N``)。哈希表所占空间。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法