[编程题]非递减序列

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

对于一个长度为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]

算法知识视频讲解

不爱吃饭，只爱学习

#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)

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)

包子山

//记录一下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)

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

此益达非彼益达

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

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

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

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)

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)

小云云是真的很想学习

s = [int(i) for i in input().split()]
flag = 0
for i in range(len(s)-1):
    if s[i] > s[i+1]:
        flag +=1
if flag > 1:
    print(0)
else:
    print(1)

遍历集合，并比较集合的当前数和下一个数的大小，若前一个数大于后一个数，则标志位+1。最后标志位大于1的说明集合不满足题目要求。

发表于 2019-11-04 14:23:25 回复(0)

dgi

可以提前退出，得到答案

l=list(map(int,input().split(" ")))
#print(l)
length_l = len(l)
sig = 0
for i in range(length_l - 1):
    
    if l[i] > l[i+1]:
        sig += 1 
        if sig > 1:
            print(0)
if sig <= 1:
    print(1)

发表于 2019-10-15 22:46:21 回复(0)

Java

Endings

import java.util.ArrayList;
import java.util.Scanner;
public class Demo03 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = sc.nextLine();
        String[] strs = line.split(" ");
        ArrayList<Integer> list = new ArrayList<>();
        for (String str : strs) {
            String s = String.valueOf(str);
            list.add(Integer.parseInt(s));
        }
        int conut=0;
        for (int i = 0; i < list.size(); i++) {
            if (i<list.size()-1){
                if ( list.get(i) > list.get(i+1) ){
                    conut++;
                }
            }
        }
        if(conut == 1 || conut == 0){
            System.out.println(1);
        }else {
            System.out.println(0);
        }

    }
}

发表于 2019-10-14 19:25:15 回复(0)

小萨摩111

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        list.add(-1);
        while (in.hasNext()) {
            list.add(in.nextInt());
        }
        int cnt = 0;
        for (int i = 1; i < list.size() && cnt <= 1; i++) {
            if (list.get(i) < list.get(i - 1)) {
                ++cnt;
            }
        }
        System.out.println(cnt == 1 ? 1 : 0);
    }
}

发表于 2019-10-01 11:59:30 回复(0)

Zero_Nine

import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] array = str.split(" ");
        if(array.length > 1000 || array.length < 2){
            throw new Exception("数组过长");
        }
        
        int count = 0;
        for(int i=0;i<array.length;i++){
            int target = Integer.parseInt(array[i]);
            int next = Integer.parseInt(array[(i+1<array.length)?i+1:i]);
            if(target <= next){
                continue;
            }
            if(count > 1){
                break;
            }
            ++count;
        }
        System.out.println((count > 1)?0:1);
    }
}

发表于 2019-09-28 00:49:14 回复(0)

Python

小小cx猿

nums = list(map(int, input().split()))
n = len(nums)
flag = True
count = 1
for i in range(n):
if(i + 1 < n):
if(nums[i] > nums[i+1]):
if(count == 0):
flag = False
break
else:
if(i-1 >= 0):
if(nums[i-1] <= nums[i+1]):
count -= 1
else:
nums[i+1] = nums[i]
count -= 1
else:
nums[i+1] = nums[i]
count -= 1
if(flag):
print(1)
else:
print(0)

发表于 2019-09-20 19:38:47 回复(0)

许愿Offer快点来呀

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<numeric>
#include<limits>
#include<cmath>
using namespace std;

int solve(vector<int>& v) {
    int ans = 0;
    for(int  i = 0; i < v.size()-1; i++){
        if(v[i] > v[i+1]){
            ans++;
        }
    }
    return ans <= 1 ? 1 : 0;
}

int main(){
    // freopen("./t1.txt", "r", stdin);
    vector<int> digits;
    int n;
    while(cin >> n){
        digits.push_back(n);
    }
    int ans = solve(digits);
    cout << ans;
    return 0;
}

发表于 2019-09-16 01:41:16 回复(0)

ARong.

凸点大于1时就不能满足了：

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String param = input.nextLine();
        char[] chars = param.toCharArray();
        int n = chars.length;
        int count = 0;
        count = (chars[0] < chars[1]) ? 1 : 0;
        count = (chars[n - 1] > chars[n - 2]) ? count + 1 : count;
        for (int i = 1; i < chars.length - 1; i++) {
              count = (chars[i] > chars[i - 1] && chars[i] < chars[i + 1]) ? count + 1 : count;
        }
        System.out.println((count <= 1) ? 1 : 0);
    }
}

发表于 2019-09-10 20:21:17 回复(0)

给个offer好吗

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String[] strarr = s.split(" ");
        int[] num = new int[strarr.length];
        for (int i = 0; i < num.length; i++) {
            num[i] = Integer.parseInt(strarr[i]);
        }
        //System.out.println(Arrays.toString(num));
        for (int i = 0; i < num.length - 1; i++) {
            if (num[i] <= num[i + 1]) {
            } else {
                num[i] = num[i - 1];
                break;
            }
        }
        //System.out.println(Arrays.toString(num));
        int count = 0;
        for (int i = 0; i < num.length - 1; i++) {
            if (num[i] <= num[i + 1]) {
                count++;
            }
        }
        if(count==num.length-1){
            System.out.println(1);
        }else{
            System.out.println(0);
        }
    }
}

发表于 2019-09-09 10:41:52 回复(0)