成双成对_网易笔试题

JulianNing

JavaScript解法：

let findsubStr = str => {
  let res = 0; // res为满足条件的字符串的最大长度
  let state = 0; // 表示字符串的当前状态，eg: state = 000001 表示当前字符a出现了奇数次，其他都出现了偶数次
  // letterMap存储的是各字符串对应的状态
  let letterMap = {
    a: 1,
    b: 2, 
    c: 4, 
    x: 8,
    y: 16,
    z: 32
  };
  // map的key是state，value是当前字符的位置
  let map = {0: -1};

  for(let i=0;i<str.length;i++) {
    let char = str[i]; // char为当前遍历到的字符
    
    // 如果当前字符是a,b,c,x,y,z中的一个，则需要对当前状态进行异或运算，即更新字符出现的次数
    if(letterMap[char] !== undefined) {
      state ^= letterMap[char];

      if(map[state] === undefined) {
        map[state] = i;
      }
    }

    let distance = i-map[state];
    res = Math.max(res, distance);
  }
  return res;
}

let str = readline();
print(findsubStr(str));

发表于 2022-07-13 16:47:20 回复(0)

雨尘ovo

//位运算+dp
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            String str=cin.nextLine();
            int[] dp=new int[str.length()];
            dp[0]=judge(str.charAt(0));
            for(int i=1;i<str.length();++i){
                int temp=judge(str.charAt(i));
                if(temp==0)
                    dp[i]=dp[i-1];
                else
                    dp[i]=dp[i-1]^temp;
            }
            int ans=0;
            for(int i=0;i<str.length();++i){
                for(int j=i;j<str.length();++j){
                    if((dp[j]^dp[j-i]^judge(str.charAt(j-i)))==0){
                        ans=i+1;
                        break;
                    }
                }
            }
            System.out.println(ans);
        }
    }

    public static int judge(char cr){
        if(cr=='a')
            return 1;
        if(cr=='b')
            return 2;
        if(cr=='c')
            return 4;
        if(cr=='x')
            return 8;
        if(cr=='y')
            return 16;
        if(cr=='z')
            return 32;
        return 0;
    }
}

发表于 2022-03-15 18:07:03 回复(0)

alaa

leetcode 1371.状态压缩＋哈希表。

import java.util.*;
public class Main{
    public static void main(String[] args) {
        // write your code here
        Scanner scanner = new Scanner(System.in);
        String next = scanner.next();
        System.out.println(findTheLongestSubstring(next));

    }

    private static int findTheLongestSubstring(String s) {
        Map<Integer, Integer> map = new HashMap<>();

        int state = 0;
        int maxlen = 0;

        // 初始化
        map.put(0, -1);

        // a b c x y z 分别在第123456个bit，来表示出现次数的奇偶性
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a') state ^= 0x000001;
            if (s.charAt(i) == 'b') state ^= 0x000010;
            if (s.charAt(i) == 'c') state ^= 0x000100;
            if (s.charAt(i) == 'x') state ^= 0x001000;
            if (s.charAt(i) == 'y') state ^= 0x010000;
            if (s.charAt(i) == 'z') state ^= 0x100000;
            if (map.containsKey(state)) {
                maxlen = Math.max(maxlen, i - map.get(state));
            } else {
                map.put(state, i);
            }
        }
        return maxlen;
    }
}

编辑于 2021-01-04 14:17:36 回复(1)

云云云一飞冲天

暴力TLE也是需要技巧的：
可以通过剪枝来减少复杂度；
可以看看更改 if 判断的顺序或者更改 if 嵌套的顺序，把 if 判断耗时少的放在外层；
只能一定程度的避免TLE，如果都不行建议换方法；

本题的话，要把更新最大值的判断条件放在检查是否符合偶数个要求的外面；

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int len = s.length();
        int maxcnt = 0;
        if (s == null || (len) < 1) {
            System.out.println(0);
            return;
        }
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (maxcnt < j - i + 1) {
                    if (check(s.substring(i, j + 1))) {
                        maxcnt = j - i + 1;
                    }
                }
            }
        }
        System.out.println(maxcnt);
    }

    private static boolean check(String substring) {
        int[] cntArray = new int[6];
        for (int i = 0; i < substring.length(); i++) {
            if (substring.charAt(i) == 'a') {
                cntArray[0]++;
            } else if (substring.charAt(i) == 'b') {
                cntArray[1]++;
            } else if (substring.charAt(i) == 'c') {
                cntArray[2]++;
            } else if (substring.charAt(i) == 'x') {
                cntArray[3]++;
            } else if (substring.charAt(i) == 'y') {
                cntArray[4]++;
            } else if (substring.charAt(i) == 'z') {
                cntArray[5]++;
            }
        }
        if (cntArray[0] % 2 == 0 && cntArray[1] % 2 == 0 && cntArray[2] % 2 == 0 && cntArray[3] % 2 == 0 && cntArray[4] % 2 == 0 && cntArray[5] % 2 == 0) {
            return true;
        } else {
            return false;
        }
    }
}

发表于 2022-09-14 16:19:21 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Main {
    // 出现偶数次-前缀和+状态压缩
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int[] pos = new int[64]; // 64个状态
        Arrays.fill(pos, Integer.MAX_VALUE);
        int max = 0, state = 0; // 状态压缩为数字的位
        pos[0] = -1; // 前缀和base case
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'a') { // 第一位
                state ^= 1;
            } else if (c == 'b') {
                state ^= 2;
            } else if (c == 'c') {
                state ^= 4;
            } else if (c == 'x') {
                state ^= 8;
            } else if (c == 'y') {
                state ^= 16;
            } else if (c == 'z') { // 第六位
                state ^= 32;
            }
            if (pos[state] != Integer.MAX_VALUE) { // 状态再一次出现说明经过偶数次-前缀和思想
                max = Math.max(max, i - pos[state]);
            } else { // 状态第一次出现
                pos[state] = i; // 存下标
            }
        }
        System.out.println(max);
    }
}

发表于 2022-09-02 16:34:45 回复(0)

胡萝饽

比较容易想到的解法，暴力加一点点优化

let intS = readline()
// 构造函数，功能是传入字符串看是否满足条件：“a”、"b"、“c”、“x”、"y"、“z”在字符串中都恰好出现了偶数次（0也是偶数）
function func(s){
    let arr = ['a','b','c','x','y','z']
    for(let v of arr){
        if(charNum(s,v)%2 !== 0){
            return 0           
        }
    }
    return s.length
}
// 判断某字符c在字符串s出现次数的函数
function charNum(s,c){
    let arr = s.split(c)
    return arr.length-1
}
let arrNum = []
let Max = 0
for(let i=0;i<intS.length;i++){
    for(let j=i+1;j<=intS.length;j++){
        if(intS.slice(i,j).length<=Max) continue
        let count = func(intS.slice(i,j))
        Max = Math.max(Max,count)
    }
}
print(Max)

发表于 2022-08-22 15:29:08 回复(0)

被GC的垃圾

我是傻子我只能用暴力解法，一开始理解错了，以为是从0开始算到最后，结果是有可能如果算全部字符串的话长度只能为0；比如abcxyzaa从0开始算到最后长度只能为0，通过率只能有50%。也就是说有可能是从中间开始算。

import java.util.*;
public class Main {
    public static void main(String[] arg){
        Scanner sc=new Scanner(System.in);
        String word=sc.next();
        int n=word.length();
        int length=0;
        //暴力遍历从每个点开始算
        for (int i = 0; i <n; i++) {
            int[] mark=new int[26];
            for (int j = i; j <n; j++) {
                //标记每个字母的个数
                mark[word.charAt(j)-'a']++;
                //有符合题目的情况就更新length
                if(mark['a'-'a']%2==0&&mark['b'-'a']%2==0&&mark['c'-'a']%2==0&&mark['x'-'a']%2==0&&mark['y'-'a']%2==0&&mark['z'-'a']%2==0){
                    length=Math.max(length,j-i+1);
                }
            }
        }
        System.out.print(length);
    }
}

发表于 2022-08-19 20:09:03 回复(0)

牛客936519026号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        //String s = "amac";
        HashMap<Character,Integer> map = new HashMap<>();
        map.put('a',0);
        map.put('b',0);
        map.put('c',0);
        map.put('x',0);
        map.put('y',0);
        map.put('z',0);
        for(int j = s.length();j>=0;j--){
            String tmp = s.substring(0,j);
            if(fun(map,tmp)==true){
                System.out.println(tmp.length());
                return;
            }else{
                map.put('a',0);
                map.put('b',0);
                map.put('c',0);
                map.put('x',0);
                map.put('y',0);
                map.put('z',0);
            }
        }
    }
    public static boolean fun(HashMap<Character,Integer> map,String s){
        int i = 0;
        while(i<s.length()){
            char tmp = s.charAt(i);
            if(tmp!='a' && tmp!='b' && tmp!='c' && tmp!='x' && tmp!='y' && tmp!='z'){
                //res = res + String.valueOf(tmp);
            }else{
                //res = res + String.valueOf(tmp);
                map.put(tmp,map.get(tmp)+1);
            }
            i++;
        }
        if(map.get('a')%2!=0)
            return false;
        if(map.get('b')%2!=0)
            return false;
        if(map.get('c')%2!=0)
            return false;
        if(map.get('x')%2!=0)
            return false;
        if(map.get('y')%2!=0)
            return false;
        if(map.get('z')%2!=0)
            return false;
        return true;
    }
}

通过率50%，是时间复杂度太高吗？

发表于 2022-04-16 18:12:11 回复(1)

landf31

//通过率60%，不知道哪里出了问题，大佬们帮忙看看
import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        int res=0; 
        String str;
        for(int i=0;i<s.length();i++){
            for(int j=i+1;j<=s.length();j++){
               str=s.substring(i,j);
            if(isRight(str)){
                res=Math.max(str.length(),res);
            }
        }
    }
        System.out.println(res);
 }
    public static Boolean isRight(String s){
        int a=0,b=0,c=0,x=0,y=0;
        for(int i=0;i<s.length();i++){
            switch(s.charAt(i)){
                case 'a':a++; 
                     break;
                case 'b':b++;
                    break;
                case 'c':c++;
                    break;
                case 'x':x++;
                    break;
                case 'y':y++;
                    break;
                default: 
                      break;
            }
        }
        if(a%2==0&&b%2==0&&c%2==0&&x%2==0&&y%2==0){
            return true;
        }else return false;
    }
}

发表于 2022-04-16 17:19:55 回复(0)

C/C++

0offer-选手

只能通过一半，哪位大佬帮忙看一下出错在哪了？😭

#include
using namespace std;    
int main(){
    string str;
    cin>>str;
    map H;
    bool *flag = new bool[str.length()];
    memset(flag, 0, sizeof(flag));
    for(long long i=0; i<str.length(); i++){
        if(str[i]=='a'||str[i]=='b'||str[i]=='c'||str[i]=='x'||str[i]=='y'||str[i]=='z'){
           H[str[i]]++; 
        }
        if(H['a']%2==0&&H['b']%2==0&&H['c']%2==0&&H['x']%2==0&&H['y']%2==0&&H['z']%2==0){
            //flag[i]等于1表示从下标0到i的子串满足条件
            flag[i] = 1;
        }
    }
    long long res = 0;
    for(long long i=str.length()-1; i>=0; i--){
        if(flag[i]==1){
            res = i+1;
            break;
        }
    }
    cout<<res<<endl;
}

发表于 2022-04-15 16:30:19 回复(0)

风中一匹狼v

暴力O(n³)也全部通过了。。

发表于 2022-03-26 13:14:12 回复(0)

Javascript_V8

皮克斯儿

以下是js的，思路不对，输入let at = "ooooooaobobobo"的时候结果不对，也跑过了70%，我再好好好想想这个思路
while(line=readline()){
let at=line
let zimu =
["a", "b", "c", "x", "y", "z"]
let a1 = at.split("")
function jie(a, b) {
let a1 = a.split("")
let shu = 0
a1.forEach(item => {
// console.log(item);
if(item == b) {
shu++
}
})
// console.log(shu);
// 如果出现了单数次
// console.log(shu, b);
if(shu % 2 == 1) {
let d1 = a.indexOf(b)
let d9 = a.lastIndexOf(b)
if(d1 >= a.length - 1 - d9) {
let cun = a.slice(0, d9)
at = cun
// console.log(at);
return cun
} else{
let cun = a.slice(d1 + 1)
at = cun
// console.log(at);
return cun
}
// console.log(d1,d9);
} else{
return a
}

}
// jie("amabchhchhahh","a")
// console.log(jie(a1,"a"));
while(1) {
let o =
[]
let oo
// o存入这时的at

at.split("").forEach(item => {
o.push(item)
})
for(let i = 0; i < zimu.length; i++) {

// console.log(at,zimu[i]);
oo = jie(at, zimu
[i]) //oo是操作完了之后的a1字符串
// console.log(oo);

}
if(oo.length == o.length) {
// kk = 1
// console.log(oo,oo.length," kk=1");
break
}
}
console.log(at.length);
}

发表于 2022-01-17 19:47:56 回复(0)

牛腩牛肉面

真的做不出来。。我是不是不适合搞技术

发表于 2021-09-16 17:16:53 回复(0)

孩子就要一个offer球球了

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
 
public class Main {
    public static void main(String[] args) {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        char[] str= new char[0];
        try {
            str = br.readLine().toCharArray();
        } catch (IOException e) {
            e.printStackTrace();
        }
        int n=str.length;
        int ans=0;
        boolean judgement=true;
        HashMap<Character,Integer> map=new HashMap<Character, Integer>();
 
 
        for(int i=0;i<n;i++)
        {
            map.put('a',0);
            map.put('b',0);
            map.put('c',0);
            map.put('x',0);
            map.put('y',0);
            map.put('z',0);
            for(int j=i;j<n;j++) {
 
 
                judgement = true;
                if (map.containsKey(str[j])) {
                    int num = map.get(str[j]) + 1;
                    map.put(str[j], num);
                    for (Object key : map.keySet()) {
                        if (map.get(key) % 2 != 0) {
                            judgement = false;
                            break;
                        }
                    }
                    if (judgement == true)
                        if(j-i+1>ans)
                        {
                            ans=j-i+1;
                        }
                } else {
                    for (Object key : map.keySet()) {
                        if (map.get(key) % 2 != 0) {
                            judgement = false;
                            break;
                        }
                    }
                    if (judgement == true)
                        if(j-i+1>ans)
                        {
                            ans=j-i+1;
                        }
                }
            }
        }
 
        System.out.println(ans);
 
    }
 
}

发表于 2021-05-07 17:44:02 回复(0)

前端菜鸡一枚

while(s=readline()){
var s;
print(maxSubStrLength(s));
}
function maxSubStrLength(s) {
// write code here
let charList = ['a', "b", 'c', 'x', 'y', 'z'];
let ss = s.split('');
let left = 0,
right = ss.length - 1;
while (left < right) {
if (charList.indexOf(ss[left]) == -1) {
left++;
} else if (charList.indexOf(ss[right]) == -1) {
right--;
} else if (charList.indexOf(ss[left]) != -1 && charList.indexOf(ss[right]) != -1) {
let sss = ss.slice(left, right + 1);

let flag = true;
for (let i = 0; i < charList.length; i++) {
if (get(sss, charList[i]) == false) {
flag = false;
left++;

break;
}
}

if (flag) {
return (right - left) + 1;
}
}
}
if (left == right) {
return s.length;
}

function get(arr, item) {
let count = 0;
arr.forEach((elem) => {
if (item == elem) {
count++;
}
});
if (count % 2 == 0) {
return true;
} else {
return false;
}
}
}

js 30%，已经尽力了

发表于 2021-04-10 18:57:09 回复(0)

SleepyMan

import java.util.Arrays;
import java.util.Map;
import java.util.Scanner;

public class oddtimes {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int[] pos = new int[1 << 6];//存储64种状态第一次出现的位置
        Arrays.fill(pos,-1);
        pos[0] = 0;
        int now = 0;
        int maxlen = 0;
        for (int i = 0; i < s.length(); i++) {
            switch (s.charAt(i)) {
                case 'a': {
                    now ^= 1;
                }
                break;
                case 'b': {
                    now ^= 2;

                }
                break;
                case 'c': {
                    now ^= 4;

                }
                case 'x': {
                    now ^= 8;

                }
                break;
                case 'y': {
                    now ^= 16;

                }
                break;
                case 'z': {
                    now ^= 32;
                }
                break;
                default:
                    break;
            }
            if (pos[now] >= 0) {
                maxlen = Math.max(maxlen, i - pos[now] + 1);
            } else {
                pos[now] = i + 1;
            }
        }
        System.out.println(maxlen);
    }
}

发表于 2021-03-25 18:40:48 回复(0)

Jackson大话秋招

python 3 30 % 通过。本地没问题

用例:
alkjkhhbjfgdab
对应输出应该为: 14
你的输出为: 13

但是，手查也是长度为13个，可能是case 有问题吧

import sys
def findSame(s):
    if s == None:
        return 0
    length = len(s)
    target = 0
    for i in range(length):
        j = i + 1
        while j < length:
            if s[i] == s[j]:
                number = j - i + 1
                if number > target:
                    target = number
            j += 1
    return target

if __name__ == '__main__':
    s = list(input())
    print(findSame(s))

发表于 2021-03-08 06:41:41 回复(1)

成双成对

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题