算法问题——（查找问题2）

一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。比如，{3,1,2,4,5}，{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。3->1->2->4->5->3 方向叫作 next 方向(逆时针)，3->5->4->2->1->3 方向叫作 last 方向(顺时针)。

山峰 A 和 山峰 B 能够相互看见的条件为:

1. 如果 A 和 B 是同一座山，认为不能相互看见。

2. 如果 A 和 B 是不同的山，并且在环中相邻，认为可以相互看见。

3. 如果 A 和 B 是不同的山，并且在环中不相邻，假设两座山高度的最小值为 min。如果 A 通过 next 方向到 B 的途中没有高度比 min 大的山峰，或者 A 通过 last 方向到 B 的途中没有高度比 min 大的山峰，认为 A 和 B 可以相互看见。

问题如下：给定一个不含有负数且没有重复值的数组 arr，请问有多少对山峰能够相互看见？ 

 

题目描述

N个加油站组成一个环形，给定两个长度都是N的非负数组oil和dis(N>1)，oil[i]代表第i个加油站存的油可以跑多少千米，dis[i]代表第i个加油站到环中下一个加油站相隔多少千米。假设你有一辆油箱足够大的车，初始时车里没有油。如果车从第i个加油站出发，最终可以回到这个加油站，那么第i个加油站就算良好出发点，否则就不算。请返回长度为N的boolean型数组res，res[i]代表第i个加油站是不是良好出发点

规定只能按照顺时针走，也就是i只能走到i+1，N只能走到1

[要求]

时间复杂度为O(n)O(n)O(n)，空间复杂度为O(1)O(1)O(1)

import java.util.Scanner;

public class Main4 {
    public static void main(String[] args) {
        //输入的数据
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();

        int[] array1 = new int[m];
        int[] array2 = new int[m];

        for (int i = 0; i < m; i++) {
            array1[i] = sc.nextInt();
        }
        for (int i = 0; i < m; i++) {
            array2[i] = sc.nextInt();
        }
        //调用函数
        int[] result = test(array1, array2);

        //输出结果
        for (int val : result) {
            System.out.print(val + " ");
        }
    }


    //通过率只有30%
    private static int[] test(int[] array1, int[] array2) {
        //结果
        int[] result = new int[array1.length];

        int[] nums1 = new int[array1.length * 2];
        int[] nums2 = new int[array1.length * 2];

        for (int i = 0; i < array1.length; i++) {
            nums1[i] = array1[i];
            nums1[i + array1.length] = array1[i];
        }

        for (int i = 0; i < array2.length; i++) {
            nums2[i] = array2[i];
            nums2[i + array2.length] = array2[i];
        }

        //开始遍历
        for (int i = 0; i < nums1.length / 2; i++) {
            int flag = 0;
            int sum = 0;
            for (int j = i; j < i + nums2.length / 2; j++) {
                if (sum + nums1[j] - nums2[j] < 0) {
                    flag = 1;
                    break;
                } else {
                    sum = sum + nums1[j] - nums2[j];
                }
            }
            if (flag == 1) {
                result[i] = 0;
            } else {
                result[i] = 1;
            }
        }
        return result;
    }
}

题目描述

一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？

 

/**
 * Copyright (C), 2018-2020
 * FileName: Main11
 * Author:   xjl
 * Date:     2020/7/12 13:06
 * Description: 测试的工作
 */
package Search;

import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;

public class Main11 {

    public static void main(String[] args) {
        //输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();

        Stack stack = new Stack();
        for (int i = 0; i < m; i++) {
            stack.add(sc.nextInt());
        }
        //调用
        Collections.sort(stack, new Comparator() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

        //输出
        for (int V : stack) {
            System.out.print(V+" ");
        }
    }
}

给定一个长度为N的整形数组arr，其中有N个互不相等的自然数1-N。请实现arr的排序，但是不要把下标0∼N−10 \sim N-10∼N−1位置上的数通过直接赋值的方式替换成1∼N1 \sim N1∼N

[要求]:  时间复杂度为O(n)，空间复杂度为O(1) 

import java.util.*;

public class Main{

    public static void main(String[] args) {
        //输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();

        int[] array = new int[m];
        for (int i = 0; i < m; i++) {
            array[i] = sc.nextInt();
        }
        //函数
        Arrays.sort(array);
        //结果
        for (int V : array) {
            System.out.print(V + " ");
        }
    }
}

给定一个有序数组arr，调整arr使得这个数组的左半部分[1,n+12][1, \frac{n+1}{2}][1,2n+1​]没有重复元素且升序，而不用保证右部分是否有序

例如，arr = [1, 2, 2, 2, 3, 3, 4, 5, 6, 6, 7, 7, 8, 8, 8, 9]，调整之后arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, .....]。

[要求]   时间复杂度为O(n)，空间复杂度为O(1)。

/**
 * Copyright (C), 2018-2020
 * FileName: Main13
 * Author:   xjl
 * Date:     2020/7/12 13:37
 * Description: 数组的调整
 */
package Search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main13 {

    public static void main(String[] args) {
        //输入
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int[] array = new int[m];

        for (int i = 0; i < m; i++) {
            array[i] = sc.nextInt();
        }
        //调用
        int[] result = test1(array);
        //结果
        for (int i : result) {
            System.out.print(i + " ");
        }
    }

    private static int[] test(int[] array) {
        int[] result = new int[array.length];

        List list1 = new ArrayList();
        List list2 = new ArrayList();

        for (int i = 0; i < array.length; i++) {
            if (!list1.contains(array[i])) {
                list1.add(array[i]);
            } else {
                list2.add(array[i]);
            }
        }
        Collections.sort(list1);
        for (int V : list2) {
            list1.add(V);
        }
        int index = 0;
        for (int V : list1) {
            result[index++] = V;
        }
        return result;
    }

    private static int[] test1(int[] array) {
        for (int i = 1; i  array[i - 1]) {
                continue;
            } else {
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] > array[i] && array[j] > array[i - 1]) {
                        int temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                        break;
                    }
                }
            }
        }
        return array;
    }
}

 给定一个无序数组arr，求出需要排序的最短子数组的长度，对子数组排序后能使得整个数组有序，即为需要排序的数组。例如：arr=[1,5,3,4,2,6,7]返回4，因为只有[5,3,4,2]需要排序。

/**
 * Copyright (C), 2018-2020
 * FileName: Main4
 * Author:   xjl
 * Date:     2020/7/13 19:47
 * Description: 排序算法
 */
package Sort;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main4 {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str = reader.readLine().split(" ");
        int len = Integer.valueOf(str[0]);
        String[] arrStr = reader.readLine().split(" ");
        int[] arr = new int[arrStr.length];
        for(int i=0; i min) left = j;
        }
        return right - left + 1;
    }
}