当前位置： 2024华为OD机试题库 (C卷,200分)- 最长子字符串的长度(二)（Java & JS & Python & C）

(C卷,200分)- 最长子字符串的长度(二)（Java & JS & Python & C）

2024-05-07 59

题目描述

给你一个字符串 s，字符串 s 首尾相连成一个环形，请你在环中找出 'l'、'o'、'x' 字符都恰好出现了偶数次最长子字符串的长度。

输入描述

输入是一串小写的字母组成的字符串

输出描述

输出是一个整数

备注

  • 1 ≤ s.length ≤ 5 * 10^5
  • s 只包含小写英文字母

用例

输入 alolobo
输出 6
说明 最长子字符串之一是 "alolob"，它包含 'l'，'o' 各2个，以及 0 个 'x'。
输入 looxdolx
输出 7
说明 最长的子字符串是"oxdolxl"，由于是首尾连接在一起的，所以最后一个 'x' 和开头的 'l' 是连接在一起的，此字符串包含 2 个 'l'，2个'o'，2个'x'
输入 bcbcbc
输出 6
说明 这个示例中，字符串 "bcbcbc" 本身就是最长的，因为 'l'、'o'、'x' 都出现了 0 次。

题目解析

本题其实就是

的变形体。

看本题前需要先把上面题目搞懂，否则本题解法看不懂。

本题与上面题目的区别在于，本题的主串s是环，即当遍历到s串尾部时，可以继续环动到s串头部。

如下图所示

上图中（黑色）部分是不可使用的，（绿色+黄色）的部分总是对应一个完整的字符串s。

本题如果继续按照前面leetcode那题的思路解题，则会发现使用哈希表时，不能只单单记录某个状态的最早出现位置。

而是需要记录某个状态的出现的所有位置（需要按照先后顺序依次记录）。

因为，本题随着绕环运动，黑色部分会逐渐侵蚀掉一些位置，而这些被侵蚀的位置，可能就是某个状态最早出现的位置，当该位置被侵蚀后，我们需要更新对应状态到新的最早出现位置。

如果使用队列记录某个状态出现的所有位置（按照先后顺序依次记录），那么队列头部记录的就是该状态的最早出现位置，如果该位置被侵蚀，那么我们就弹出队头，使用新的队头元素作为对应状态的最早出现位置。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const s = await readline();
  console.log(getResult(s));
})();

function getResult(s) {
  let status = 0b000;

  // map[i] 用于记录 状态i 出现的过的所有位置
  const map = new Array(8).fill(0).map(() => []);
  map[0].push(-1);

  let maxLen = 0;

  for (let i = 0; i < s.length * 2; i++) {
    // 第二轮时，i>=s.length，此时i需要对s.length求余，避免后面越界
    const c = s[i % s.length];

    switch (c) {
      case "l":
        status ^= 0b100;
        break;
      case "o":
        status ^= 0b010;
        break;
      case "x":
        status ^= 0b001;
        break;
    }

    if (i < s.length) {
      // 第一轮时，i ∈ [0, s.length()), 左闭右开
      // 记录该状态出现过的所有位置
      map[status].push(i);
    }

    while (map[status].length > 0) {
      // status状态最早出现的位置
      const earliest = map[status][0];

      // i 是当前位置，和 earliest 位置的状态相同
      if (i - earliest > s.length) {
        // 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest
        map[status].shift();
      } else {
        // 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度
        maxLen = Math.max(maxLen, i - earliest);
        break;
      }
    }
  }

  return maxLen;
}

Java算法源码

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    System.out.println(getResult(s));
  }

  public static int getResult(String s) {
    int status = 0b000;

    // map.get(i) 用于记录 状态i 出现的过的所有位置
    ArrayList<LinkedList<Integer>> map = new ArrayList<>();
    for (int i = 0; i < 8; i++) {
      map.add(new LinkedList<>());
    }

    map.get(0).add(-1);

    int maxLen = 0;

    for (int i = 0; i < s.length() * 2; i++) {
      // 第二轮时，i>=s.length()，此时i需要对s.length()求余，避免后面越界
      char c = s.charAt(i % s.length());

      switch (c) {
        case 'l':
          status ^= 0b100;
          break;
        case 'o':
          status ^= 0b010;
          break;
        case 'x':
          status ^= 0b001;
          break;
      }

      if (i < s.length()) {
        // 第一轮时，i ∈ [0, s.length()), 左闭右开
        // 记录该状态出现过的所有位置
        map.get(status).add(i);
      }

      while (map.get(status).size() > 0) {
        // status状态最早出现的位置
        int earliest = map.get(status).getFirst();

        // i 是当前位置，和 earliest 位置的状态相同
        if (i - earliest > s.length()) {
          // 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest
          map.get(status).removeFirst();
        } else {
          // 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度
          maxLen = Math.max(maxLen, i - earliest);
          break;
        }
      }
    }

    return maxLen;
  }
}

 

Python算法源码

# 输入获取
s = input()


# 算法入口
def getResult():
    status = 0b000

    # dic[i] 用于记录 状态i 出现的过的所有位置
    dic = [[] for _ in range(8)]
    dic[0].append(-1)

    maxLen = 0

    for i in range(2 * len(s)):
        # 第二轮时，i>=s.length，此时i需要对s.length求余，避免后面越界
        c = s[i % len(s)]

        if c == 'l':
            status ^= 0b100
        elif c == 'o':
            status ^= 0b010
        elif c == 'x':
            status ^= 0b001

        if i < len(s):
            # 第一轮时，i ∈ [0, s.length()), 左闭右开
            # 记录该状态出现过的所有位置
            dic[status].append(i)

        while len(dic[status]) > 0:
            # status状态最早出现的位置
            earliest = dic[status][0]

            # i 是当前位置，和 earliest 位置的状态相同
            if i - earliest > len(s):
                # 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest
                dic[status].pop(0)
            else:
                # 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度
                maxLen = max(maxLen, i - earliest)
                break

    return maxLen


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MAX_SIZE 500000

char s[MAX_SIZE];

typedef struct ListNode {
    int ele;
    struct ListNode *next;
} ListNode;

typedef struct LinkedList {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));
    link->size = 0;
    link->head = NULL;
    link->tail = NULL;
    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));
    node->ele = ele;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}

int removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
    }

    link->size--;

    int res = removed->ele;

    free(removed);

    return res;
}

int getResult() {
    int status = 0b000;

    // map[i] 用于记录 状态i 出现的过的所有位置
    LinkedList *map[8];
    for (int i = 0; i < 8; i++) {
        map[i] = new_LinkedList();
    }

    addLast_LinkedList(map[0], -1);

    int maxLen = 0;

    int n = (int) strlen(s);

    for (int i = 0; i < n * 2; i++) {
        // 第二轮时，i>=s.length()，此时i需要对s.length()求余，避免后面越界
        char c = s[i % n];

        if (c == 'l') {
            status ^= 0b100;
        } else if (c == 'o') {
            status ^= 0b010;
        } else if (c == 'x') {
            status ^= 0b001;
        }

        if (i < n) {
            // 第一轮时，i ∈ [0, s.length()), 左闭右开
            // 记录该状态出现过的所有位置
            addLast_LinkedList(map[status], i);
        }

        while (map[status]->size > 0) {
            // status状态最早出现的位置
            int earliest = map[status]->head->ele;

            // i 是当前位置，和 earliest 位置的状态相同
            if (i - earliest > n) {
                // 如果 [earliest, i] 范围子串长度超过s串长度，则说明earliest左越界，应该尝试更大一点的earliest
                removeFirst_LinkedList(map[status]);
            } else {
                // 如果 [earliest, i] 范围子串长度未超过s串长度，则该范围子串就是一个符合要求的子串，记录此时子串长度
                maxLen = (int) fmax(maxLen, i - earliest);
                break;
            }
        }
    }

    return maxLen;
}

int main() {
    gets(s);

    printf("%dn", getResult());

    return 0;
}

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

取消

首页 发现 VIP 我的

站点公告

没有账号？注册  忘记密码？