Java 인터뷰의 일반적인 배열 질문 요약(4)

1. 배열의 역순 쌍

(학습 영상 추천: java 강좌)

[주제]

두 개의 숫자가 배열에 있는 경우 첫 번째 숫자가 뒤의 숫자보다 큰 경우 두 숫자는 역순으로 쌍을 이룹니다. 배열을 입력하고 배열 P에서 역방향 쌍의 총 개수를 찾습니다. 그리고 P 모듈로 1000000007의 결과를 출력합니다. 즉, 출력 P%1000000007

질문은 입력 배열의 숫자가 동일하지 않음을 확인합니다

데이터 범위:

对于%50的数据,size<=10^4

对于%75的数据,size<=10^5

对于%100的数据,size<=2*10^5

코드:

	/**
     *在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
     * 输入一个数组，求出这个数组中的逆序对的总数 P。
     * 并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007
     *
     * 利用归并排序的思想(倒序)
     * 当得到left和right两个待归并的数组时，由于二者已经排好顺序
     * 当left中的A元素大于right中的B元素，
     * 那么right.length-b_index 个逆序对
     * */
    int count;
    public int InversePairs(int [] array) {
        return Merge(array,0,array.length-1);
    }


    public int Merge(int[] a, int start, int end) {

        if (start >= end) return count;


        int i,j,mid,index;
        int[] temp;

        mid = (start + end) / 2;

        Merge(a,start,mid);
        Merge(a,mid+1,end);

        i = start;
        j = mid + 1;
        temp = new int[end-start+1];
        index = 0;

        while (i<=mid && j<=end) {
            if (a[i] > a[j]) {
                count = (count +end - j + 1) % 1000000007;
                temp[index++] = a[i++];
            } else {
                temp[index++] = a[j++];
            }
        }

        while (i<=mid) temp[index++] = a[i++];

        while (j<=end) temp[index++] = a[j++];

        index = start;
        for (i=0;i<temp.length; i++) {
            a[index++] = temp[i];
        }

        return count;
    }

[Thinking]

병합 정렬 과정에서 뒤의 배열의 개수가 다음보다 작아야 합니다. 이전 배열의 개수는 역순 쌍을 이룰 수 있어야 하며 병합할 두 배열을 미리 병합하여 정렬해 두었기 때문에 역순 쌍의 개수를 계산할 수 있습니다. 이전보다 더 적거나 더 많은 통계는 없을 것입니다.

[A, B]의 역순 쌍 = [A]의 역순 쌍 + [B]의 역순 쌍 + A와 B를 혼합하는 역순 쌍

참고: 거기에 문제의 특별한 요구 사항입니다. 이 모듈은 결과를 모듈로 할 뿐만 아니라 프로세스 계산에서도 모듈로여야 합니다.

2. 배열에서 한 번만 나타나는 숫자

[제목]

정수 배열에서 두 개의 숫자를 제외하고 다른 모든 숫자는 두 번 나타납니다. 한 번만 나타나는 두 숫자를 찾는 프로그램을 작성해 보세요.

【코드】

    /**
     * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。
     * 请写程序找出这两个只出现一次的数字。
     *
     * 位运算中异或的性质：
     * 两个相同数字异或 = 0，一个数和 0 异或还是它本身。
     *  a ⊕ a = 0
     *  a ⊕ b ⊕ a = b.
     *  a ⊕ 0 = a
     *
     * 当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，
     * 最后剩下的就是落单的数，因为成对儿出现的都抵消了。
     *
     * 当出现两个数只出现一次时，依旧是依次异或运算，
     * 剩下的结果是两个只出现一次的数的异或结果
     * 因为这两个数不同，所以我们通过二进制的异或把二者分开，在依次异或即可分别得到
     * */
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

        int i,n,res,count,res1,res2;
        n = array.length;

        if (n == 0 || array == null) return;

        res = 0;// 记录两个不同的数的异或结果
        for (i=0; i<n; i++) {
            res = res ^ array[i];
        }

        // 找到异或结果的二进制的的从右向左的第一个1
        count = 1;
        while ((count & res) == 0) count = count << 1;

        // 通过找到的二进制结果来区分两个只出现第一次的数
        res1 = 0;
        res2 = 0;
        for (i=0; i<n; i++) {
            if ((count & array[i]) == 0) {
                res1 = res1 ^ array[i];
            } else {
                res2 = res2 ^ array[i];
            }
        }

        num1[0] = res1;
        num2[0] = res2;
    }

【생각】

우선: 비트 연산에서 XOR의 속성: 두 개의 동일한 숫자는 XOR = 0이고, 숫자와 0은 XOR 또는 그 자체입니다.
하나의 숫자만 한 번 나타나면 배열의 모든 숫자를 순차적으로 XOR하고 마지막 남은 숫자는 단일 숫자입니다. 쌍으로 나타나는 모든 숫자가 상쇄되기 때문입니다.

이 아이디어에 따라 두 개의 숫자(AB라고 가정)가 한 번 나타나는 배열을 살펴보겠습니다. 먼저 XOR해야 합니다. 나머지 숫자는 A와 B의 XOR 결과여야 합니다. 이 결과의 이진수 1은 A와 B의 다른 비트를 나타냅니다. 첫 번째 1의 숫자를 세 번째 숫자로 가정하고 원래 배열을 두 그룹으로 나눕니다. 그룹화 기준은 세 번째 숫자가 1인지 여부입니다. 이런 식으로 같은 숫자는 확실히 같은 그룹에 속합니다. 왜냐하면 같은 숫자의 모든 숫자는 동일하지만 다른 숫자는 확실히 같은 그룹에 속하지 않기 때문입니다. 그런 다음 이 두 그룹을 원래 아이디어에 따라 순서대로 XOR하면 나머지 두 개의 결과는 한 번만 나타나는 이 두 숫자입니다.

(더 관련 있는 면접 질문 추천: java 면접 질문 및 답변)

3. 합이 S

[제목]

오름차순으로 정렬된 배열과 숫자 S를 입력하세요. 배열에 두 개를 찾으세요. 합이 정확히 S가 되도록 숫자를 만듭니다. 합이 S와 같은 숫자 쌍이 여러 개인 경우 두 숫자의 곱이 가장 작은 숫자 쌍을 출력합니다.

각 테스트 케이스에 따라 두 개의 숫자가 출력되고, 작은 숫자가 먼저 출력됩니다.

【Code】

    /**
     * 输入一个递增排序的数组和一个数字 S，
     * 在数组中查找两个数，使得他们的和正好是 S，
     * 如果有多对数字的和等于 S，输出两个数的乘积最小的。
     * */
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {

        int mid,i,index,n,j;
        ArrayList<Integer> list;

        n = array.length;
        if (n == 0 || array == null || sum == 0) return new ArrayList<>();

        mid = sum >> 1;

        if (array[0] > mid) return new ArrayList<>();

        // 前两个元素和为sum
        list = new ArrayList<>();
        if (array[0] == mid) {
            if (array[0] + array[1] == sum) {
                list.add(array[0]);
                list.add(array[1]);

            }
            return list;
        }

        // 获得mid在array的索引
        index = 0;
        for (i=0; i<n; i++) {
            if (array[i] >= mid) {
                index = i;
                break;
            }
        }

        i = 0;
        j = index + 1;
        while (i<=index) {
            while (array[i] + array[j] < sum) {
                j++;
            }
            if (array[i] + array[j] == sum) {
                list.add(array[i]);
                list.add(array[j]);
                break;
            } else {
                i++;
                j = index + 1;
            }
        }

        return list;
    }

4. 합계가 S

【Title】

Xiao Ming은 수학 숙제를 하다가 합계를 계산하라는 요청을 받았습니다. 9~16. 정답은 100이라고 바로 썼어요. 그러나 그는 이것에 만족하지 않고 합이 100인 양수의 연속 시퀀스(적어도 두 개의 숫자 포함)가 몇 개인지 궁금했습니다. 머지않아 그는 합이 100이 되는 또 다른 연속적인 양수 시퀀스인 18,19,20,21,22를 갖게 되었습니다. 이제 질문이 주어집니다. 합이 S인 모든 연속된 양수 시퀀스를 빠르게 찾을 수 있습니까? 행운을 빌어요!

합이 S인 연속된 양수 시퀀스를 모두 출력하세요. 시퀀스 내에서는 작은 것부터 큰 순서로, 시퀀스 사이의 시작 번호는 작은 것부터 큰 것입니다

[코드]

    /**
     * 输出所有和为S的连续正数序列。
     * 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
     *
     * 思路：回溯
     * 算子，paths，path
     * */
    TreeSet<Integer> path;
    ArrayList<ArrayList<Integer>> paths;
    ArrayList<Integer> list;

    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        if (sum < 3) return new ArrayList<>();

        int n,i,j,mid,count;

        paths = new ArrayList<>();

        if (sum == 3) {
            list = new ArrayList<>();
            list.add(1);
            list.add(2);
            paths.add(list);
            return paths;
        }

        // n代表sum这个数最多由几个数字构成
        n = (int)Math.sqrt(sum) + 1;


        for (i=n; i>=2; i--) {
            count = 0;
            mid = sum / i;
            count += mid;
            path = new TreeSet<>();
            path.add(mid);
            j = 1;
            while (count < sum) {
                count += mid+j;
                path.add(mid+j);
                count += mid-j;
                path.add(mid-j);
                j++;
            }
            if (count == sum) {
                list = new ArrayList<>();
                list.addAll(path);
                paths.add(list);
            } else {
                int last = path.last();
                int first = path.first();
                if (count-last == sum) {
                    path.remove(last);
                    list = new ArrayList<>();
                    list.addAll(path);
                    paths.add(list);
                }
                if (count-first == sum) {
                    path.remove(first);
                    list = new ArrayList<>();
                    list.addAll(path);
                    paths.add(list);

                }
            }
        }

        return paths;
    }

[아이디어]

더블 포인터 방식
왼쪽 포인터와 오른쪽 포인터가 연속적으로 연속 시퀀스의 범위에 동그라미를 쳐보세요

입력 합계=20(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
1, 두 개의 포인터 정의, 왼쪽 포인터는 1부터 시작하고 오른쪽 포인터는 2
부터 시작합니다
루프는
2, sum (1+2 = 3
3, 3이 20보다 작다고 판단되면 오른쪽 포인터 ++, 2가 됩니다) 3, 합은 3+3=6이 됩니다. 오른쪽 포인터 = 6이 될 때까지 루프가 계속되고 합은 21이 됩니다.
4, 그렇지 않으면 21이 20보다 크다고 판단되면 왼쪽 포인터는 ++, 1이 됩니다. 2, 왼쪽 포인터 값에서 합계를 빼면 합계는 21-1=20입니다.
5, 그렇지 않으면 입력과 동일합니다. 그런 다음 오른쪽 포인터 ++를 사용하여 합계를 찾습니다. 남은 조합 찾기]

End of loop

5. 포커 스트레이트

[제목]🎜

LL 今天心情特别好，因为他去买了一副扑克牌，发现里面居然有 2 个大王，2 个小王 (一副牌原本是 54 张 _)… 他随机从中抽出了 5 张牌，想测测自己的手气，看看能不能抽到顺子，如果抽到的话，他决定去买体育彩票，嘿嘿！！“红心 A, 黑桃 3, 小王，大王，方片 5”,“Oh My God!” 不是顺子…LL 不高兴了，他想了想，决定大 \ 小 王可以看成任何数字，并且 A 看作 1,J 为 11,Q 为 12,K 为 13。上面的 5 张牌就可以变成 “1,2,3,4,5”(大小王分别看作 2 和 4),“So Lucky!”。LL 决定去买体育彩票啦。 现在，要求你使用这幅牌模拟上面的过程，然后告诉我们 LL 的运气如何， 如果牌能组成顺子就输出 true，否则就输出 false。为了方便起见，你可以认为大小王是 0。

【代码】

    /**
     * 判断顺子，大小王为0
     *
     * 计算0的个数
     * 计算非0的差
     * */
    public boolean isContinuous(int [] numbers) {

        if (numbers.length == 0 || numbers == null) return false;

        Arrays.sort(numbers);

        int n,i,count,minus;

        n = numbers.length;
        count = 0;
        minus = 0;
        for (i=0; i<n-1; i++) {
            if (numbers[i] == 0) {
                count++;
            } else {

                minus += numbers[i+1] - numbers[i];
            }
        }
        // 除了最后一个其他都是0
        if (count == n-1) return true;
        // 存在相同的值
        if (minus != (numbers[n-1] - numbers[count])) return false;
        if (minus == 0) return false;

        return (minus - (n-count-1)) > count ? false : true;
    }

【思考】

可以考虑使用treeset这个结构，本身带有排序功能，并且不会存储相同元素，可以方便判断。

相关推荐：java入门

위 내용은 Java 인터뷰의 일반적인 배열 질문 요약(4)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!