[编程题]非递减序列

热度指数：1484 时间限制：1秒空间限制：32768K
算法知识视频讲解

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

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

输入描述:

输入是一个长度为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]

算法知识视频讲解

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

咽喉上的刀

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)

内蒙鸭王666

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)

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 回复(1)

Java

Phlotwe

import java.util.*;
public class Main{
public static void main(String[] args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[] s=new int[n];
int temp=0;
int flag=0;
for(int i=0;i<n;i++){
s[i]=input.nextInt();
}
for(int j=0;j<n-1;j++){
if(s[j]<=s[j+1]){
temp++;
}else if(s[j]<=s[j+2]&&flag==0){
temp++;
flag=1;
}else if(s[j+1]==s[j+2]&&flag==0){
temp++;
flag=1;
}
}
if(temp==(n-1)){
System.out.print(1);
}else{
System.out.print(0);
}
}
}

发表于 2019-08-07 22:14:28 回复(0)

菜鸡努力刷题

最简单的4 5 6 1 2 3 为什么也是非递减序列？

发表于 2019-08-06 17:00:03 回复(0)

此益达非彼益达

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

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

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

LongXiaJun

nums = list(map(int, input().strip().split()))

pre = 0
for i in range(1, len(nums)-1):
    if nums[i-1] > nums[i]:
        if pre:
            pre = 2
            break
        pre = 1
print(1 if pre < 2 else  0)

发表于 2019-08-01 00:30:50 回复(0)

来个大厂offer保命!

遍历一遍，有两次递减就输出0，否则就输出1

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

编辑于 2019-07-29 19:23:22 回复(0)

martinc

#include<iostream>
using namespace std;
int main(){
    int a,b,ctr=0;
    cin>> a;
    while(cin>>b){
        if(a>b){
            ctr++;
        }
        a = b;
    }
    cout << (ctr>1?0:1) << endl; 
    return 0;
}

发表于 2019-07-28 15:17:31 回复(0)

我叫托比欧

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner Input=new Scanner(System.in);
        String unSplStr=Input.next();
        String[] unSeqStr=unSplStr.split(" ");
            int[] unSeqInt=new int[unSeqStr.length];
            
            for(int i=0;i<unSeqStr.length;i++) {
                unSeqInt[i]=Integer.parseInt(unSeqStr[i]);
            }
            int result=1;
            for(int x=0;x<unSeqInt.length-1;x++) {
                if(unSeqInt[x]>unSeqInt[x+1]) {
                    result=0;
                    break;
                }
            }
            for(int j=0;j<unSeqInt.length;j++) {
                for(int k=0;k<=9;k++) {
                    int a=unSeqInt[j];
                    unSeqInt[j]=k;
                    for(int y=0;y<unSeqInt.length-1;y++) {
                        if(unSeqInt[y]>unSeqInt[y+1]) {
                            result=0;
                            unSeqInt[j]=a;
                            break;
                        }
                    }
                                     }
            }
       System.out.println(result);     
    }
}

发表于 2019-07-18 16:06:36 回复(0)

ミ低灬調ㄨ墨色漩涡

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

public class Main{
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        int flag = -1;
        String[] numstr = input.split("\\s+");
        int[] nums = new int[numstr.length];
        for (int i = 0; i < numstr.length; i++) {
            nums[i] = Integer.parseInt(numstr[i]);
        }
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i]>nums[i+1]){
                flag ++;
                nums[i] = nums[i]+1;
            }
        }
        if(flag<=0){
                System.out.println(1);
            }else{
                System.out.println(0);
            }
    }
}

编辑于 2019-07-13 14:45:36 回复(0)

您201810161418815

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

发表于 2019-07-03 18:32:44 回复(0)

BubblyYi

import sys
counter = 1
index_i = 1
result = 0
for line in sys.stdin:
    a = line.split()
    mlist = list(map(int, a))
    pre_item = mlist[0]
    for i in mlist[1:]:
        if i < pre_item:
            if counter>0:
                mlist[index_i]==pre_item
                result = 1
                counter = 0
            else:
                result = 0
        pre_item = i
    print(result)

只允许修改一次那么就设置一个变量counter来计算剩余修改次数

发表于 2019-06-28 00:29:18 回复(0)

yrosa

import sys

	import copy



	nums = map(int, sys.stdin.readline().strip().split())



	num_f = copy.deepcopy(nums)



	num_b = copy.deepcopy(nums)



	def solve_f():



	    flag=0



	    for i in range(len(num_f)):



	        if i+1 < len(num_f):



	            if num_f[i+1] < num_f[i]:



	                if flag:



	                    return 0



	                num_f[i+1] = num_f[i]



	                flag=1



	    return 1



	def solve_b():



	    flag = 0



	    for i in range(len(num_b)-1,-1,-1):



	        if i - 1 >= 0:



	            if num_b[i-1] > num_b[i]:



	                if flag:



	                    return 0



	                num_b[i-1] = num_b[i]



	                flag = 1



	    return 1



	print(solve_f() or solve_b())