首页 > 试题广场 >

区间表达

[编程题]区间表达
  • 热度指数：5894 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
牛牛的老师给出了一个区间的定义:对于x ≤ y,[x, y]表示x到y之间(包括x和y)的所有连续整数集合。例如[3,3] = {3}, [4,7] = {4,5,6,7}.牛牛现在有一个长度为n的递增序列,牛牛想知道需要多少个区间并起来等于这个序列。
例如:
{1,2,3,4,5,6,7,8,9,10}最少只需要[1,10]这一个区间
{1,3,5,6,7}最少只需要[1,1],[3,3],[5,7]这三个区间

输入描述:
输入包括两行,第一行一个整数n(1 ≤ n ≤ 50),
第二行n个整数a[i](1 ≤ a[i] ≤ 50),表示牛牛的序列,保证序列是递增的。


输出描述:
输出一个整数,表示最少区间个数。
示例1

输入

5
1 3 5 6 7

输出

3
算法知识视频讲解
添加回答
Python
华科平凡头像 华科平凡

python 解法

n, arr = int(input()), list(map(int, input().split()))
res = 1
for i in range(1, n):
    if arr[i] - arr[i - 1] > 1:
        res += 1
print(res)

遍历数组，如果某一个数和前一个数的差大于1，那么一定要开辟新的区间。等于1不做任何处理。

发表于 2019-02-24 19:06:42 回复(0)
老骥伏枥志在千里头像 老骥伏枥志在千里 
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] array=new int[n];
        int count=1;
        for(int i=0;i<n;i++){
            array[i]=sc.nextInt();
        }
        for(int i=1;i<n;i++){
            if(array[i-1]!=array[i]-1){
                count++;
            }
        }
        System.out.println(count);
    }
}
总的来说就是判断是否连续的，即array[i]是否等于array[i+1]-1,如果不是count++
发表于 2019-03-20 17:32:20 回复(0)
C/C++
茶月猫头像 茶月猫
不需要把数据存储了，直接读进来进行相差是否为1的判断，就可以输出结果，空间复杂度为o(1) 
#include <iostream>
usingnamespacestd;
intmain(void)
{
    intlen, temp, first;
    cin >> len;
    intcount = 1;
    cin >> first;
    for(inti = 0; i < len-1; i++)
    {
        cin >> temp;
        if(temp - first != 1)
        {
            count++;
        }
        first = temp;
    }
    cout << count << endl;
    return0;
}


编辑于 2019-04-23 11:54:57 回复(0)
Alejandro1头像 Alejandro1 
#include <iostream>

using namespace std;

int main() {
    int a[50];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int counter = 1;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] + 1 != a[i + 1] ) {
            counter++;
        }
    }
    cout << counter << endl;
    return 0;
}
发表于 2019-01-24 00:34:39 回复(1)
中南的小菜鸡头像 中南的小菜鸡 
import java.util.Scanner;
/**
 * @ClassName Main
 * @Description TODO
 * @Author Wlison
 * @Date 2020/2/18 11:43
 * @Version 1.0
 **/
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int res = 1;
            int pre = sc.nextInt();
            int cur = pre;
            for (int i = 1; i < n; i++) {
                cur = sc.nextInt();
                if (cur-pre!=1){
                    res++;
                }
                pre = cur;
            }
            System.out.println(res);
        }
    }
}

发表于 2020-02-19 19:37:28 回复(0)
Java
CR7M12头像 CR7M12
前面的一个元素+1后的值跟后一个数比较，如果等于就继续，如果不等于区间数量加一 
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner cin=new Scanner (System.in);
		int n=cin.nextInt();//数组长度;
		int temp=cin.nextInt();//第一个元素(也会用于后期的比较)
		int out=1;
		for(int i=1;i<n;i++) {
			int d=cin.nextInt();
			if(temp+1 !=d) {
				out++;
				
			}
			temp=d;
			
		}
		System.out.print(out);

	}

}

发表于 2019-11-05 18:27:57 回复(0)
Java
Mono_Chrome头像 Mono_Chrome 
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int count = 1;
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if (i > 0 && arr[i] - arr[i - 1] != 1) {
                count++;
            }
        }
        System.out.println(count);
    }
}
发表于 2019-06-17 17:49:53 回复(0)
tw-luo头像 tw-luo 
//如果后一个数比前一个数大1，就将n减去1
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> v1;
    int m,s=n;
    for (int i = 0; i < n; i++){
        cin >> m;
        v1.push_back(m);
    }
    for (int i = n - 1; i >= 1; i--){
        if (v1[i] - v1[i - 1] == 1){
            s--;
        }
    }
    cout << s << endl;
    system("pause");
    return 0;
}

发表于 2019-04-22 19:44:39 回复(0)
李镇强头像 李镇强
  1. 不连续则加一
Llen ,L = int(input()),list(map(int,input().split()))
count = 1
obj = L[0]
if Llen == 1:
    print(1)
else:
    for i in range(1,Llen):
        if L[i] != obj + 1:
            count +=1
        obj = L[i]
    print(count)

发表于 2019-04-12 19:24:09 回复(0)
Python
我要扛offer回家头像 我要扛offer回家 
n=int(input())
seq=list(map(int,input().split()))
res=1
i=0
while i<n-1:
    if seq[i]+1!=seq[i+1]:
        i+=1
        res+=1
    else:
        i+=1
print(res)

编辑于 2019-03-29 17:01:18 回复(0)
我是如此相信头像 我是如此相信 
    private static int solve(int[] a, int n) {
        int count = 1;
        for (int i = 0; i < n - 1; i++) {
            if (a[i + 1] - a[i] == 1) {
                continue;
            }
            count++;
        }
        return count;
    }

发表于 2019-03-23 14:13:52 回复(0)
Python
十月_13头像 十月_13 




n = int(input())
a = list(map(int, input().split()))
count = 0 for i in range(n-1):  if a[i+1] - a[i] != 1:
        count += 1 print(count+1)

发表于 2019-03-19 20:33:21 回复(0)
木然猫猫头像 木然猫猫 
n = int(input())
a = list(map(int, input().split()))
res = 0
i = 0
while i < n:
    if i+1 < n and a[i+1] - a[i] == 1:
        i += 1
    else:
        res += 1
        i += 1
print(res)

发表于 2019-03-18 18:44:19 回复(0)
C/C++
小陈也只是想要一个实习罢了头像 小陈也只是想要一个实习罢了
如果后一个数和前一个数的差距大于1，则必须开辟新的区间，最后到最后一个数的时候，计数还应该加一表示最后的分为一组。感觉我写的的还算简单！😎 
#include<iostream>
using namespace std;
int main(){
    int n,count=0;
    cin>>n;
    int* a=new int[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++){
        if(a[i]-a[i-1]!=1)
            count++;
        if(i==n-1)
            count++;
    }
    cout<<count<<endl;
}

发表于 2019-03-05 17:27:04 回复(1)
C/C++
刘炳辰头像 刘炳辰 
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[55];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int count = 1;
    for(int i = 1; i < n; i++){
        if(a[i] - a[i - 1] <= 1){
            continue;
        }
        else{
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

编辑于 2019-03-02 16:20:05 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>

using namespace std;

int main()
{     int n,x;     while(cin>>n){         int cnt=1,a[n];         for(int i=0;i<n;i++){             cin>>a[i];             if(i>0 && a[i]>a[i-1]+1)                 cnt++;         }         cout<<cnt<<endl;     }     return 0;
}

发表于 2019-02-15 02:07:49 回复(0)
向宇回桌头像 向宇回桌 
import java.util.*;
public class Main {
    private static final int N_MAX = 50 + 5;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[N_MAX];
        for (int i=1; i<=n; i++) {
            arr[i] = sc.nextInt();
        }
        int count = 0;
        for (int i=2; i<=n+1; i++) {
            if (arr[i] - arr[i-1] != 1) {
                count++;
            }
        }
        System.out.println(count);
    }
}
发表于 2019-01-20 23:40:20 回复(0)
Java
成程晨头像 成程晨 
import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            int n = in.nextInt();
            int[] a = new int[n];
            for(int i = 0;i < n;i++){
                a[i] = in.nextInt();
            }
            System.out.println(helper(a));
        }
    }
    public static int helper(int[] a){
        int sum = 1;
        for(int i = 1;i < a.length;i++){
            if(a[i] - a[i - 1] != 1) sum++;
        }
        return sum;
    }
}

发表于 2019-01-16 17:06:44 回复(0)
为啥要起名字头像 为啥要起名字 
n=int(raw_input().strip())
nums=list(map(int,raw_input().strip().split()))
count=1
for i in range(1,len(nums)):
    if nums[i]-nums[i-1]>1:
        count+=1
print(count)

只要查看前后值相差大于1的个数有多少个就可以了

发表于 2018-06-26 10:00:39 回复(0)
元气の悟空头像 元气の悟空 
#include<stdio.h>
int main(){
    int n,res=1,i,a[100];
    for(scanf("%d",&n),i=0;i<n;i++){
        scanf("%d",a+i);
        if(i&&a[i]-a[i-1]-1) res++;
    }
    printf("%d",res);
}

发表于 2017-11-28 23:24:22 回复(0)
提交观点

问题信息

贪心 数组 模拟 穷举 前端工程师 爱奇艺 2018
来自：爱奇艺2018秋季校招...
上传者：小小
难度：
74条回答 6600浏览

热门推荐

通过挑战的用户

查看代码

相关试题

区间表达

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号