* 判断一个数组中的数值是否连续相邻
* 满足以下条件：
* 1.0是例外可以反复出现 0可以通配任何字符
* 2.相同的数值不会重复出现
* 3.该数组可以是乱序的
* 当数组不含有0时满足最大值-最小值=n(数组长度)-1
* 当数组数组含有0时.满足最大值-最小值
* 所以，当最大值最大值-最小值>n(数组长度)-1时，一定不是连续相邻数组
package datastruct.usearray;
public class JudgeAdjacent {
private static boolean judege(int a[]) {
int min=Integer.MAX_VALUE;
int max=Integer.MIN_VALUE;
for (int i = 0; i < a.length; i++) {
if (a[i]!=0) {
if (min>a[i]) {
min=a[i];
}
if (maxa.length-1) {
return false;
}else {
return true;
}
}
public static void main(String[] args) {
int a[]={8,5,0,10,6,7,0,0};
if (judege(a)) {
System.out.println("该数组是相邻的！");
}else {
System.out.println("该数组不是相邻的！");
}
}
}
以上这篇java 判断一个数组中的数值是否连续相邻的方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持脚本之家。

一个整数数组，元素取值可能是0~65535中的任意一个数，相同数值不会重复出现；0是例外，可以反复出现。设计一个算法，判断这个数组中的元素是否连续相邻。需要注意以下4点：
(1)数值允许是乱序的，如 8 7 5 0 6。
(2)0可以通配任意数值，如8 7 5 0 6中的0可以通配成9或者4.
(3)0可以多次出现。
(4)全0算连续，只有一个非0算连续。
思路分析：
如果没有0的存在，要组成连续的数列，最大值和最小值的差距必须是n-1；存在0的情况下，只要最大值可最小值的差距小于n-1就可以了，缺失的数值可以用0通配。所以找出数列中非0的最大值和非0的最小值，时间复杂度为O(n)。如果非0最大-非0最小+1
程序示例代码如下：
#include "stdafx.h"
#include
bool IsContinuous(int* a, int n)
{
if (a == NULL || n <= 0)
return false;
int min = a[0], max = a[0];
for (int i = 1; i < n; i++)
{
if (a[i] != 0)
{
if (min>a[i])
min = a[i];
if (max < a[i])
max = a[i];
}
}
if (max - min>n - 1)
return false;
else
return true;
}
int main()
{
int array[] = { 8, 7, 5, 0, 6 };
int len = sizeof(array) / sizeof(array[0]);
if (IsContinuous(array, len))
printf("数组连续相邻\n");
else
printf("数组不连续相邻\n");
getchar();
return 0;
}
效果如图：

Ivo Merchier..
7
除了不能完全回答问题之外，这里讨论的其他算法的另一个缺点是它们必须对整个列表进行排序。这导致〜N log(N)的复杂性。
然而，也可以实现同样的结果〜n的。这种方法将数据帧分为两个子集，一个子集小于期望值。在较小的数据帧中，较低的邻居比最大值大，对于较高的邻居，反之亦然。
这给出了以下代码片段：
def find_neighbours(value):
exactmatch=df[df.num==value]
if !exactmatch.empty:
return exactmatch.index[0]
else:
lowerneighbour_ind = df[df.num
upperneighbour_ind = df[df.num>value].idxmin()
return lowerneighbour_ind, upperneighbour_ind
这种方法类似于在熊猫中使用分区，这在处理大型数据集时变得非常有用，而复杂性成为一个问题。
两种策略的比较表明，对于较大的N，分区策略的确更快。对于较小的N，排序策略将以更低的级别实现，因此效率更高。它也是单行代码，可能会提高代码的可读性。
复制此图的代码如下所示：
from matplotlib import pyplot as plt
import pandas
import numpy
import timeit
value=3
sizes=numpy.logspace(2, 5, num=50, dtype=int)
sort_results, partition_results=[],[]
for size in sizes:
df=pandas.DataFrame({"num":100*numpy.random.random(size)})
sort_results.append(timeit.Timer("df.iloc[(df['num']-value).abs().argsort()[:2]].index",
globals={'find_neighbours':find_neighbours, 'df':df,'value':value}).autorange())
partition_results.append(timeit.Timer('find_neighbours(df,value)',
globals={'find_neighbours':find_neighbours, 'df':df,'value':value}).autorange())
sort_time=[time/amount for amount,time in sort_results]
partition_time=[time/amount for amount,time in partition_results]
plt.plot(sizes, sort_time)
plt.plot(sizes, partition_time)
plt.legend(['Sorting','Partitioning'])
plt.title('Comparison of strategies')
plt.xlabel('Size of Dataframe')
plt.ylabel('Time in s')
plt.savefig('speed_comparison.png')

数字三角形最长路径问题就是在如图所示的三角形中，由上至下，寻找一条路径使得经过所有路径之后，所得数值最大。

输入样例：

第一行是三角形的行数n

以下n行都是三角形各行数据
3
1
2 3
5 3 6

输出：
10

递推方法
# include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100
int n,D[MAX][MAX];
int maxPath(int i,int j)
{
    if(i == n)
        return D[i][j];
    else
    {
        return max(maxPath(i+1,j),maxPath(i+1,j+1)) + D[i][j];
    }
    
}

int main()
{
    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);
    cin >>n;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= i;j++)
            cin >> D[i][j];
    cout << maxPath(1,1);
}

这种方法可行，但是算法复杂度过大，在样例超过一定规模会TLE

原因是重复计算！！！


记忆递推式动态规划
将每次计算出的结点最大路径值记录在数组中，避免重复运算
# include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100
int n,D[MAX][MAX],maxData[MAX][MAX];
int maxPath(int i,int j)
{
    if(maxData[i][j] != -1)
        return maxData[i][j];
    else if(i == n)
    {
        maxData[i][j] = D[i][j];
        return maxData[i][j];
    }

        
    else
    {
        maxData[i][j] = max(maxPath(i+1,j),maxPath(i+1,j+1)) + D[i][j];
        return maxData[i][j];
    }
    
}

int main()
{
    freopen("1.txt","r",stdin);
    freopen("2.txt","w",stdout);
    cin >>n;
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= i;j++)
            {
                cin >> D[i][j];
                maxData[i][j] = -1;
            }
    cout << maxPath(1,1);
}