01游戏

[编程题]01游戏

热度指数：1138 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对01字符串进行一些操作，01字符串上的0和0相邻时会变成1，而1和1相邻时会在字符串上消失，而0和1相邻时什么都不会发生，问这个字符串最后会变成什么样。

示例1

输入

"00110001"

输出

"01"

说明

00110001→1110001→10001→1101→01

备注:

，字符串上的合并消失应优先与左边进行，例如000，中间的0优先与左边的0合并变为10，消失同理

算法知识视频讲解

JavaScript

niukeno1

/**
 * 
 * @param str string字符串 初始字符串
 * @return string字符串
 */
function solve( str ) {
    // write code here
    let s=[];
    s.push(str[0]);
    let a=str[0];
    for(let i=1;i<str.length;i++){
        if(s.length==0){
            s.push(str[i]);
            a=str[i];
        }else if(a==1&&str[i]==1){
            s.pop();
            while(s[s.length-1]==1&&s[s.length-2]==1){
                s.pop();
                s.pop();
            }
            if(s.length!=0) a=s[s.length-1];
            
        }else if(a==0&&str[i]==0){
            s.pop();
            s.push(1);
            while(s[s.length-1]==1&&s[s.length-2]==1){
                s.pop();
                s.pop();
            }
            if(s.length!=0) a=s[s.length-1];
            
        }else{
            s.push(str[i]);
            a=str[i];
        }
    }
    return s.toString().split(/,/g).join("");
}

一个栈，两个指针，要注意在11和00后对之前的项进行再次11的循环处理。

编辑于 2020-09-04 16:05:06 回复(3)

Python 3

ZhongHaoWang

class Solution:
    def solve(self , str ):
        # write code here
        stack = []
        for c in str:
            if not stack:
                stack.append(c)
            else:
                if c == '0':
                    if stack[-1] == '0':
                        stack.pop(-1)
                        tag = 0
                        while stack and stack[-1] == '1':
                            tag = 1
                            stack.pop(-1)
                        if not tag:
                            stack.append('1')
                    else:
                        stack.append(c)
                else:
                    if stack[-1] == '1':
                        stack.pop(-1)
                    else:
                        stack.append(c)
        return ''.join(stack)

发表于 2021-08-27 12:54:30 回复(0)

絮雨在心

import java.util.*;


public class Solution {
    public String solve (String str) {
        // write code here
        Stack<Character> stack=new Stack<>();
        stack.push(str.charAt(0));
        char a=str.charAt(0);
        for(int i=1;i<str.length();i++){
            char ch=str.charAt(i);
            if(stack.size()==0){
                stack.push(ch);
                a=ch;
            }else if(a=='1' && ch=='1'){
                stack.pop();
                while(stack.size()>1 && stack.get(stack.size()-1)=='1' && stack.get(stack.size()-2)=='1'){
                    stack.pop();
                    stack.pop();
                }
                if(stack.size()!=0){
                    a=stack.peek();
                }
            }else if(a=='0' && ch=='0'){
                stack.pop();
                stack.push('1');
                while(stack.size()>1 &&stack.get(stack.size()-1)=='1' && stack.get(stack.size()-2)=='1'){
                    stack.pop();
                    stack.pop();
                }
                if(stack.size()!=0){
                    a=stack.peek();
                }
            }else{
                stack.push(ch);
                a=ch;
            }
        }
        String ss="";
        while(!stack.isEmpty()){
            ss=stack.pop()+ss;
        }
        return ss;
    }
}

发表于 2021-08-27 10:59:16 回复(0)

随便来个offer吧，球球了

public static String solve(final String str) {
        // write code here
        final StringBuilder sb = new StringBuilder();
        for (final char c : str.toCharArray()) {
            sb.append(c);
            while (sb.length() > 1) {
                final int n = sb.length();
                if( sb.charAt(n-1) == '0' && sb.charAt(n-2) == '0'){
                    sb.deleteCharAt(sb.length() - 1);
                    sb.deleteCharAt(sb.length() - 1);
                    sb.append('1');
                }else if( sb.charAt(n - 2) == '1' && sb.charAt(n - 1) == '1' ){
                    sb.deleteCharAt(sb.length() - 1);
                    sb.deleteCharAt(sb.length() - 1);
                }else{
                    break;
                }
            }
        }
        return sb.toString();
    }

贴一下我的代码吧，就维护一个StringBuilder，然后就模拟就可以了

发表于 2020-09-04 16:01:55 回复(0)

404_boy

StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append(str.charAt(0));

        // 遍历源字符串 拿出每一个字符和StringBuffer中的字符进行比较
        for(int i= 1;i < str.length();i++){
            if (stringBuffer.length()==0){
                stringBuffer.append(str.charAt(i));
                continue;
            }


            if (stringBuffer.charAt(stringBuffer.length() - 1) == str.charAt(i)){
                if (str.charAt(i)== '0'){
                    stringBuffer.setCharAt(stringBuffer.length() -1,'1');

                    if (stringBuffer.length()>=2 && stringBuffer.charAt(stringBuffer.length()-2) == '1'){
                        stringBuffer.delete(stringBuffer.length()-2,stringBuffer.length());
                    }

                }else{
                    stringBuffer.deleteCharAt(stringBuffer.length() - 1);
                }
            }else{
                stringBuffer.append(str.charAt(i));
            }
        }

        System.out.println(stringBuffer.toString());

先创建一个StringBuffer 往里先放一个字符，遍历源字符串，进行比较，如果是 00 就将StringBuffer中的字符置为1 如果是 1 1 就删除其中字符，由于这样无法照顾前面的字符，就需要一个判断（写错好久才反应过来）通过比较前一个字符和当前置为1的字符如果相同，使用delete（beginIndex,endIndex）来删除，筛选后就是 01 情况，直接加入String Buffer就好，大体思路就是这样吧（一个Java新手，不喜勿喷，嘤嘤嘤）

发表于 2020-08-26 16:46:54 回复(0)