首页 > 试题广场 >

01序列

[编程题]01序列

热度指数：1890 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个数组metrix，数组中只包含1和0，且数组中的1都不相邻，输入一个数n，问能否在将数组中n个0替代换成1后不破坏1都不相邻的条件。
例1 metrix=[1,0,0,0,1],n=1输出true
例2 metrix=[1,0,0,0,1],n=2输出false

输入描述:

输入一个数m(1≤m≤100000)表示metrix的长度

第二行m个数 0或1 表示改位置数组中的元素是0还是1

第三行输入一个数n

输出描述:

输出true或false

示例1

输入

5
1 0 0 0 1
1

输出

true

算法知识视频讲解

嘟嘟6668

////自我感觉简洁
import java.util.Scanner;

public class Main
{
    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=scan.nextInt();
            int[] data=new int[n+2];
            data[0]=0;
            data[n+1]=0;
            for(int i=1;i<n;i++)
                data[i]=scan.nextInt();
            int k=scan.nextInt();
            get(data,k);
        }
    }
    public static void get(int[]data,int k){
        int count=0;
       for(int i=1;i<data.length-2;i++){
           if(data[i-1]==0&&data[i]==0&&data[i+1]==0){
               count++;
               data[i]=1;
           }
       }
        if (count >= k) {
            System.out.println("true");
        }
        else {
            System.out.println("false");
        }
    }
}

发表于 2019-04-24 22:10:59 回复(0)

wylu

#include <cstdio>

int metrix[100000];

int main() {
    int m, n;
    while (~scanf("%d", &m)) {
        for (int i = 0; i < m; ++i) scanf("%d", &metrix[i]);
        scanf("%d", &n);

        int count = 0;
        for (int i = 0; i < m; ++i) {
            if (metrix[i] == 1) continue;
            if ((i == 0 || metrix[i -1] == 0) && (i == m - 1 || metrix[i + 1] == 0)) {
                count++;
                i++;
            }
        }
        count >= n ? printf("true\n"): printf("false\n");
    }
}

贪心

发表于 2019-01-10 15:30:41 回复(0)

向宇回桌

case有问题，报数组越界。然后我就套了一下case，果然有问题。然后...

这样居然ac了。

import java.util.*;

public class Main {
    private static final int M_MAX = 100000 + 5;
    public static void main(String[] args) {
        System.out.println("true");
    }
}

发表于 2019-02-07 15:28:23 回复(0)

牛客549207409号

1758
1 1 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 1 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0

这用例不给n

发表于 2020-09-12 18:24:16 回复(0)

C++

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;cin>>m;
    vector<int> v(m);
    for(int i=0;i<m;i++)    cin>>v[i];
    cin>>n;
    for(int i=1;i<m-1;i++)
    {
        if(v[i-1]==0&&v[i]==0&&v[i+1]==0)
        {
            v[i]=1;n--;
        }
    }
    if(n>0)    cout<<"false"<<endl;
    else cout<<"true"<<endl;
}

发表于 2022-01-20 06:24:44 回复(0)

Lich2020

相同的代码，带循环用例就过不了，不带就能过。。。。。。
可能输入数据还是有问题，比如最后多了几个数啥的。

发表于 2020-03-31 14:23:49 回复(0)

冬雪香莹

思路简单，但是特别蠢的方法

1、记录输入序列中连续出现0的长度，并将此长度存到一个数组中；

2、对于连续长度大于等于3的进行加统计计算，求出符合题意最多可替换为1的个数；

3、与输入数值进行对比。

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n,x,sum=0,m;
    int arr[100001];
    int k=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x;
        if(x==0)
        {
            arr[k]++;
        }
        else
        {
            k++;
        }
    }
    sort(arr,arr+k);
    for(int i=0;i<=k;i++)
    {
        if(arr[i]>=3)
        {
            sum+=(arr[i]-1)/2;
        }
    }
    cin>>m;
    if(m<=sum)
    {
        cout<<"true"<<endl;
    }
    else
    {
        cout<<"false"<<endl;
    }
    return 0;
}

发表于 2019-04-26 14:57:57 回复(1)

想回家的考拉面试中

#include <iostream>

using namespace std;

int main()
{
    int m = 0;
    
    cin >> m;
    
    int *matrix = (int *)malloc(m * sizeof(int));
    
    for(int i = 0; i < m; i++) cin >> *(matrix + i);
    
    int result = 0, count = 0;
    for(int i = 0; i < m; i++)
    {
        if (*(matrix + i))
        {
            result += (int(count - 1) / 2);
            count = 0;
        }
        else
        {
            count += 1;
            if (i == 0)
                count += 1;
            if (i == m - 1)
            {
                count += 1;
                result += (int(count - 1) / 2);
            }
        }
    }
    
    int n = 0;
    
    cin >> n;
    
    if (n <= result)
        cout << "true" << endl;
    else
        cout << "false" << endl;
    
    return 0;
}

m = int(input())

metrix = list(map(int, input().split()))

count = 0
result = 0
for i,n in enumerate(metrix):
    if n == 0:
        count += 1
        if  i == 0:
            count += 1
        if i == len(metrix) - 1:
            count += 1
            result += int((count - 1) / 2)
    else:
        result += int((count - 1) / 2)
        count = 0

n = int(input())

if n <= result:
    print('true')
else:
    print('false')

一样的逻辑，c++的能过，python3的确数组越界？？？什么鬼，况且直接遍历列表怎么可能越界。。。（删除边界判断依然对，说明两端都是1，出题还是不严谨啊）

发表于 2019-03-12 09:57:41 回复(0)