2023-01-06：给定一个只由小写字母组成的字符串str，长度为N，给定一个只由0、1组成的数组arr，长度为N，arr[i

福大大架构师每日一题

发布于 2023-02-01 03:56:50

63000

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2023-01-06：给定一个只由小写字母组成的字符串str，长度为N，

给定一个只由0、1组成的数组arr，长度为N，

arr[i]等于 0 表示str中i位置的字符不许修改，

arr[i] 等于 1表示str中i位置的字符允许修改，

给定一个正数m，表示在任意允许修改的位置，

可以把该位置的字符变成a~z中的任何一个，

可以修改m次。

返回在最多修改m次的情况下，全是一种字符的最长子串是多长。

1 <= N, M <= 10^5，

所有字符都是小写。

来自字节。

答案2023-01-06：

尝试全变成a一直到全变成z，遍历26次。每次滑动窗口。

时间复杂度：O(N)。

空间复杂度：O(1)。

代码用rust和solidity编写。

代码用rust编写。代码如下：

use rand::Rng;
use std::{iter::repeat, vec};
fn main() {
    let str = "bbbcdbcade";
    let mut arr = vec![1, 1, 0, 1, 0, 1, 0, 0, 1, 0];
    let m = 4;
    let ans = max_len2(&str, &mut arr, m);
    println!("ans = {}", ans);
    let nn: i32 = 100;
    let rr: i32 = 5;
    let test_time: i32 = 5000;
    println!("测试开始");
    for i in 0..test_time {
        let n = rand::thread_rng().gen_range(0, nn) + 1;
        let m = rand::thread_rng().gen_range(0, n) + 1;
        let str = random_string(n, rr);
        let mut arr = random_array(n);
        let ans1 = max_len1(&str, &mut arr, m);
        let ans2 = max_len2(&str, &mut arr, m);
        if ans1 != ans2 {
            println!("出错了!{}", i);
            println!("str = {}", str);
            println!("arr = {:?}", arr);
            println!("m = {}", m);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

// 暴力方法
// 为了测试
fn max_len1(str1: &str, arr: &mut Vec<i32>, m: i32) -> i32 {
    let s = str1.as_bytes();
    let n = s.len() as i32;
    let mut ans = 0;
    for c in 'a' as u8..='z' as u8 {
        for i in 0..n {
            let mut j = n - 1;
            while j >= i {
                if ok(s, i, j, c, arr, m) {
                    ans = get_max(ans, j - i + 1);
                    break;
                }
                j -= 1;
            }
        }
    }
    return ans;
}

// 为了测试
fn ok(s: &[u8], l: i32, r: i32, c: u8, arr: &mut Vec<i32>, mut m: i32) -> bool {
    for i in l..=r {
        if s[i as usize] == c {
            continue;
        }
        if arr[i as usize] == 0 || m == 0 {
            return false;
        }
        m -= 1;
    }
    return true;
}

// 正式方法
fn max_len2(str1: &str, arr: &mut Vec<i32>, m: i32) -> i32 {
    let s = str1.as_bytes();
    let n = s.len() as i32;
    let mut ans = 0;
    for aim in 'a' as u8..='z' as u8 {
        // 右边界
        // [l..r)
        let mut r = 0;
        // 用了几次修改了
        // change == m 用完的时候
        let mut change = 0;
        for l in 0..n {
            // l......r ->
            while r < n {
                if s[r as usize] == aim {
                    r += 1;
                    continue;
                }
                // s[r] != aim
                if arr[r as usize] == 0 || change == m {
                    break;
                }
                // s[r] != aim && arr[r] == 1 && change < m
                change += 1;
                r += 1;
            }
            // l....r-1 r
            // X l+1
            ans = get_max(ans, r - l);
            if s[l as usize] != aim && arr[l as usize] == 1 {
                change -= 1;
            }
            // r r
            // l l
            // X
            r = get_max(r, l + 1);
        }
    }
    return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

// 为了测试
fn random_string(n: i32, r: i32) -> String {
    let mut arr = String::new();
    for _i in 0..n {
        arr.push((rand::thread_rng().gen_range(0, r) as u8 + 'a' as u8) as char);
    }
    return arr;
}

// 为了测试
fn random_array(n: i32) -> Vec<i32> {
    let mut arr: Vec<i32> = vec![];
    for _i in 0..n {
        arr.push(rand::thread_rng().gen_range(0, 2));
    }
    return arr;
}

代码用solidity编写。代码如下：

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

contract Hello{
    function main() public pure returns (int32){
    bytes memory s = "bbbcdbcade";
    int32[] memory arr = new int32[](10);
    arr[0] = 1;
    arr[1] = 1;
    arr[2] = 0;
    arr[3] = 1;
    arr[4] = 0;
    arr[5] = 1;
    arr[6] = 0;
    arr[7] = 0;
    arr[8] = 1;
    arr[9] = 0;
    int32 m = 4;
    return maxLen2(s,arr,m);
    }

  // 正式方法
  function maxLen2(bytes memory s, int32[] memory arr, int32 m) public pure returns (int32){
    int32 n = int32(int(s.length));
    int32 ans = 0;
    for (bytes1 aim = 'a'; aim <='z'; aim = bytes1(uint8(aim)+1)) {
      // 右边界
      // [l..r)
      int32 r = 0;
      // 用了几次修改了
      // change == m 用完的时候
      int32 change = 0;
      for (int32 l = 0; l < n; l++) {
        // l......r ->
        while (r < n) {
          if (s[uint32(r)] == aim) {
            r++;
            continue;
          }
          // s[r] != aim
          if (arr[uint32(r)] == 0 || change == m) {
            break;
          }
          // s[r] != aim && arr[r] == 1 && change < m
          change++;
          r++;
        }
        // l....r-1 r
        // X l+1
        ans = getMax(ans, r - l);
        if (s[uint32(l)] != aim && arr[uint32(l)] == 1) {
          change--;
        }
        // r r
        // l l
        // X
        r = getMax(r, l + 1);
      }
    }
    return ans;
  }

    function getMax(int32 a,int32 b) public pure returns (int32){
        if(a>b){
            return a;
        }else{
            return b;
        }
    }

}