首页 > 试题广场 >

非递减序列

[编程题]非递减序列

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

对于一个长度为 n 的整数序列，你需要检查这个序列最多改变一个数后是否可以是非递减序列。

非递减序列的定义是：array[i]<=array[i+1] , for 1<=i<n;

数据范围： $1 \le n \le 10000 \$ ，数组中的值满足 $0 \le val \le 10000 \$

输入描述:

输入是一个长度为n的整数序列。

输出描述:

输出为； 是为1； 否为0

示例1

输入

3 4 6 5 5 7 8

输出

说明

将6变成4， 序列变成 [3 4 4 5 5 7 8]，符合非递减序列，因此输出1

示例2

输入

3 4 6 5 4 7 8

输出

备注:

n的取值范围为： [2, 1000]

算法知识视频讲解

Polestar_a

找逆序对儿就完事儿了呗

res = list(map(int, input().split()))
num = 0
for i in range(1,len(res)):
    if res[i]<res[i-1]:
        num+=1
print(1 if num<=1 else 0)

编辑于 2019-08-10 11:14:18 回复(4)

此益达非彼益达

public class Main {
    public static void main(String[] args) {
        System.out.println(1);
    }
}

谁能告诉我，这样也能过？？？

发表于 2019-08-06 02:11:10 回复(7)

dragonlogin

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a;
    int x;
    int len = 0;
    while (cin >> x) {
        ++len;
        a.push_back(x);
    }
    int ant = 0;
    for (int i=1; i<len - 1; ++i) {
        if (a[i] < a[i-1] || a[i] > a[i+1]) {
            a[i] = a[i-1]; // 不满足条件的， 赋值 满足条件的最小值 给它
            ++ant;
        }
        if (ant > 1) break; // 提前剪枝
    }
    if (ant > 1) {
        cout << "0" << endl;
    } else {
        cout << "1" << endl;
    }
    return 0;
}

发表于 2019-10-17 13:16:04 回复(0)

炊烟晚霞

import java.util.*;
public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        while (sc.hasNextInt()) {
            list.add(sc.nextInt());
        }
        int flag = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) < list.get(i-1)) {
                if (flag == 0) {
                    if (i == 1) {
                        list.set(i-1, list.get(i));
                    } else {
                        if (list.get(i-2) > list.get(i)) {
                            list.set(i, list.get(i-1));
                        }
                    }
                    flag = 1;
                } else {
                    System.out.println(0);
                    return;
                }
            }
        }
        System.out.println(1);
    }
}

发表于 2020-09-03 20:16:30 回复(0)

包子山

//记录一下a[i]>a[i+1]的数量，大于2直接就是非递减序列
//还有就是如果a[i]>a[i+1]时，需要把a[i]赋值给a[i+1]
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> v;
    for(int i = 0;i<n;i++)
    {
        int temp;
        cin >> temp;
        v.push_back(temp);
    }
    int counts = 0;
    for(int j = 0;j<n-1&&counts <2;j++)
    {
        if(v[j]>v[j+1])
        {
            counts++;
            v[j+1] = v[j];
        }
    }
    if(counts>=2)
        cout << 0 << endl;
    else
        cout << 1 << endl;
    return 0;
}

发表于 2019-11-01 16:43:23 回复(0)

EnvyEvil

num_list = list(map(int, input().split()))
count = 0
for i in range(len(num_list)):
    if i > 0:
        if not num_list[i - 1] <= num_list[i]:
            count += 1
print(1) if count <= 1 else print(0)

发表于 2019-09-10 08:27:06 回复(0)

Java

心刻

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);
        String str=sc.nextLine();
        sc.close();
        String[] s = str.split(" ");
        int count=0;
        for(int i=1;i<s.length;i++){
            if(Integer.parseInt(s[i-1])>Integer.parseInt(s[i])){
                count++;
                if(count>1)
                   break;
                if(i>1){
                    if(Integer.parseInt(s[i-2])<=Integer.parseInt(s[i]))
                        s[i-1]=s[i-2];
                    else
                        s[i]=s[i-1];
                }else
                    s[i-1]=s[i];
            }
        }
        if(count>1)
            System.out.println(0);
        else
            System.out.println(1);
    }
}

发表于 2019-08-25 23:36:04 回复(0)

Java

咽喉上的刀

JAVA解答

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        String str = input.nextLine();
        String[] strlen = str.split(" ");
        int len = strlen.length;
        int[] a = new int[len];
        int i = 0;
        for (i = 0;i<len;i++){
            a[i] = Integer.parseInt(strlen[i]);
        }
        int index = 0;
        for (i = 1;i<len;i++){
            if (a[i]<a[i-1])
                index++;
        }
        if (index <= 1)
            System.out.println(1);
        else
            System.out.println(0);
    }
}

编辑于 2019-08-02 19:32:44 回复(1)

Mongolia-Duck-king

arr = input().split(' ')
list = []
for i in arr:
    i = int(i)
    list.append(i)
l = len(list)
flag = 0
for i in range(l-1):
    if list[i] <= list[i+1]:
        flag = flag + 1
    else:
        flag = flag - 1

if flag == l-1:
    print(0)
else:
    print(1)

发表于 2019-07-25 17:05:47 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    vector<int>num;
    while(cin>>n)
        num.push_back(n);
    int flag = 0;
    for (int i = 0; i < num.size()-1; i++)
        if (num[i] > num[i + 1]) 
            flag++;
    if (flag > 1)
        cout << 0 << endl;
    else 
        cout << 1 << endl;
    return 0;
}

发表于 2019-07-15 19:48:57 回复(0)

Python

卷积神经网络哦

python 3行搞定

就是记录不满足大于等于左边且小于等于右边的元素的个数，如果个数大于2，一定没法搞。如果等于2，满足其右边大于等于左边，将这个数换成其左边和右边中间的数即可。

a = [int(x) for x in input().split(" ")]
idx = [i for i in range(1, len(a)-1) if not a[i - 1] <= a[i] <= a[i + 1]]
print(1 if len(idx)==2 and a[idx[0]+1]>=a[idx[0]-1] else 0)

编辑于 2019-12-03 11:34:36 回复(0)

pein531

要想通过一次操作使数组非递减，则数组中最多只能允许出现一次递减现象，如果超过一次，肯定无法完成非递减数列的转换

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.lang.String;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            String[] strArr = line.trim().split(" ");
            int[] arr = new int[strArr.length];
            for(int i = 0; i < strArr.length; i++)
                arr[i] = Integer.parseInt(strArr[i]);
            System.out.println(solve(arr));
        }
    }
    
    private static int solve(int[] arr) {
        int flag = 1, count = 0;
        for(int i = 0; i < arr.length - 1; i++){
            if(arr[i] > arr[i + 1]){
                count ++;
                // 只允许出现一次递减现象，否则无法通过改变一次数字使得数组达到非递减的状态
                if(count > 1){
                    flag = 0;
                    break;
                }
            }
        }
        return flag;
    }
}

发表于 2020-10-27 20:34:50 回复(1)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a;
    string s;
    getline(cin, s);
    istringstream ss(s);
    int x;
    char c;
    while(ss>>x){
        a.push_back(x);
        ss>>c;
        if(c=='\n')
            break;
    }
    int flag = 0;
    for(int i=1;i<a.size();i++){
        if(a[i]<a[i-1]){
            if(flag)
                break;
            flag++;
        }
    }
    if(flag<=1)
        cout<<1<<endl;
    else
        cout<<0<<endl;
    return 0;
}

编辑于 2019-08-03 22:51:48 回复(0)

Java

今日即是救赎

用一个flag标记是否还有修改的机会

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] split = sc.nextLine().trim().split(" ");
            int[] arr = new int[split.length];
            for (int i = 0; i < split.length; i++) {
                arr[i] = Integer.parseInt(split[i]);
            }
            System.out.println(check(arr));
            
        }
    }
    public static int check(int[] nums) {
        if (nums.length == 1) return 0;
        boolean flag = nums[0] <= nums[1] ? true : false;
        //开始遍历
        for (int i = 1; i < nums.length - 1; i++) {
            //出现逆序
            if (nums[i] > nums[i + 1]) {
                //还有修改的机会
                if (flag) {
                    //方案1：将i缩小至 i+1
                    if (nums[i + 1] >= nums[i - 1]) nums[i] = nums[i + 1];
                    //方案2：将i+1扩大至i
                    else nums[i + 1] = nums[i];
                    flag = false;//用完了唯一的修改机会

                } else return 0; //没有机会，直接返回
            }
        }
        return 1;

    }
}

发表于 2023-02-25 02:59:25 回复(0)

C++

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v;
    int t,flag=0;
    while(cin>>t)    v.push_back(t);
    for(int i=0;i<v.size()-1;i++)
    {
        if(v[i+1]<v[i]&&!flag)
        {
            flag=1;
            if(i>0)
                v[i]=v[i-1];
            if(!i)
                v[i]=0;
            i--;
        }
        else if(v[i+1]<v[i]&&flag)
        {
            cout<<0<<endl;flag=2;
            break;
        }
    }
    if(flag!=2)    cout<<1<<endl;
}

直接遍历一遍，用一个flag标记就行。第二次出现错序退出就行了。

发表于 2022-01-19 02:39:12 回复(0)

jj11

a1=input()
a1=a1.split(' ')
a=[]
for num in a1:
    a.append(int(num))
count=0
for i in range(len(a)-1):
    if a[i]<=a[i+1]:
        count+=1
    else:
        count+=0
if count==(len(a)-1):
    print('0')
else:
    print('1')

发表于 2021-05-19 21:18:51 回复(0)

Python

spongebob7

arr=[]
for s in input().split(" "):
arr.append(int(s))
n=len(arr)
arr2=[0]*n
for i in range(0,n-1):
if arr[i]>arr[i+1]:
arr2[i]+=1
for i in range(1,n):
if arr[n-i]<arr[n-i-1]:
if arr[n-i]>=arr[n-i-2]:
arr2[n-i-1]+=1
if sum(arr2)%2==0:
print(1)
else:
print(0)

发表于 2021-03-12 14:50:15 回复(0)

哎哟喂怎么这么难起名字

#include<iostream>
#include<vector>
using namespace std;
int main() {

    vector<int> numbers;
    int number;
    int tag = 0;
    while (cin>>number) {
        numbers.push_back(number);
    }
    for (int i = 1; i <numbers.size ()-1; i++)
    {
        if (numbers[i]<numbers[i - 1] && numbers[i]>numbers[i + 1]) {
            cout << 0 << endl;
            tag = 1;
            break;
        }
    }
    if (tag==0) {
        cout << 1 << endl;
    }
    return 0;
}

发表于 2021-02-07 17:24:40 回复(0)

007havegone


/*扫描一遍，判断逆序出现次数，大于2直接0，如果0次则1。
否则出现1次，如果出现在开始位置即t=1，
则修改即可，否则判断t-2是否小于等于t位置的数即可。*/


#include<bits/stdc++.h>
using namespace std;
int main()
{
    int cnt=0;
    vector<int> vec;
    int n;
    int t;
    while(cin>> n)
    {
        vec.push_back(n);
    }
    int i;
    for(i=1;i<vec.size();++i)
    {
        if(vec[i-1]>vec[i]){
            t=i;//记录该位置
            cnt++;
        }
    }
    if(cnt>1)
        cout << 0 << endl;
    else if(cnt==0)
        cout << 1 << endl;
    else//cnt=1
    {
        if(i==1||vec[t-2]<=vec[t])
            cout << 1 << endl;
        else{
            cout << 0 << endl;
        }
            
    }
}

编辑于 2021-01-31 14:34:07 回复(0)

moscatp

3 4 8 2 3 4

那些直接找逆序对的这个测试用例是过不了的；这个测试用例中只有一个逆序对但是无法通过只改变一个数使它成为非严格增；

发表于 2020-11-16 16:35:36 回复(1)

提交观点

问题信息

职能快手数组穷举算法工程师财务 2019 排序

上传者：小小

难度：

55条回答 25收藏 7697浏览

通过挑战的用户

查看代码

牛客65043...

2022-10-26 20:10:50
牛客52981...

2022-09-13 17:14:12
陌生人mosh...

2022-09-08 08:25:47
牛客50969...

2022-09-06 03:24:37
前端学习中

2022-08-27 18:45:33

非递减序列

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题