首页 > 试题广场 >

非递减序列

[编程题]非递减序列

热度指数：6619 时间限制：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]

算法知识视频讲解

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)

Java

何止hz

第一次出现逆序对有两种策略：

策略1：把number[i]增大至与number[i-1]相等；

策略2：把number[i-1]减小至与number[i]相等。

显然策略2更能让后续序列满足非递减条件，优先考虑策略2，但是实施策略2还需要满足number[i]大于或等于number[i-2],否则number[i-1]减小至与number[i]相等，number[i-2]就大于number[i-2]了。

程序实现如下：

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 13:59
 * @Description: 非递减序列
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int nums[] = new int[s.length];
        for (int i = 0; i < s.length; i++)
            nums[i] = Integer.valueOf(s[i]);
        int chance = 1;
        for (int i = 1; i < s.length; i++){
            if (nums[i] < nums[i-1]){
                if (chance ==0){
                    System.out.println(0);
                    return;
                }else {
                    chance--;
                    if (i - 2 < 0 || nums[i] >= nums[i-2])//此时把i-1变小
                        continue;
                    else
                        nums[i] = nums[i-1];
                }
            }
        }
        System.out.println(1);
    }
}

发表于 2020-05-10 14:23:28 回复(0)

Java

肥咩咪

后面的数减去前面的数要大于等于0，统计不满足要求的次数，如果违规次数大于1，就输出0，否则输出1

import java.util.*;
public class Main
{
  public static void main(String [] args)
  {
      Scanner sc=new Scanner(System.in);
      while(sc.hasNextLine())
      {
          String str=sc.nextLine();
          String [] arr=str.split(" ");
          int [] arr2=new int[arr.length];
          for(int i=0;i<arr.length;i++)
          {
              arr2[i]=Integer.parseInt(arr[i]);
          }
          int count=0;//不满足要求的次数
          for(int i=0;i<arr2.length-1;i++)
          {
              int a=arr2[i+1]-arr2[i];
              if(a<0)
              {
                  count++;
              }
          }
          if(count>1)
          {
              System.out.println(0);
          }
          else
          {
              System.out.println(1);
          }
      }
  }
}

发表于 2020-03-29 23:12:22 回复(0)

Java

LHC0512

Java解法

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    /**
     * 运行时间：33ms
     *
     * 占用内存：10432k
     * */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(" ");
        ArrayList<Integer> list = new ArrayList<>();
        for (String s1 : s) {
            list.add(Integer.parseInt(s1));
        }
        int count=0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i)<list.get(i-1))
                count++;
        }
        System.out.println(count>=2?0:1);
    }
}

发表于 2020-02-29 23:13:03 回复(0)

Java

你的offer对我打了烊

import java.io.*;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] str = bf.readLine().split(" ");
        int[] arr = new int[str.length];
        int count = 0;
        for(int i = 0;i < str.length;i++){
            arr[i] = Integer.parseInt(str[i]);
        }
        for(int j = 0;j < arr.length - 1;j++){
            if(arr[j] > arr[j + 1]){
                arr[j] = arr[j - 1];
                j--;
                count += 1;
            }
            if(count == 2){
                System.out.println(0);
                break;
            }
        }
        if(count <= 1){
            System.out.println(1);
        }
    }
}

发表于 2020-02-28 16:26:22 回复(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)

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

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)

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)

提交观点

问题信息

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

上传者：小小

难度：

9条回答 25收藏 7764浏览

通过挑战的用户

查看代码

牛客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

非递减序列

输入描述:

输出描述:

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题