Summary of common array questions in Java interviews (4)

1. Reverse-order pairs in an array

(Learning video recommendation: java course)

[Title]

Two numbers in the array, if the previous number is greater than the following number, then the two numbers form a reverse-order pair. Input an array and find the total number of reversed pairs in the array P. And output the result of P modulo 1000000007. That is, output P 00000007

The question ensures that the same number is not in the input array

Data range:

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

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

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

Code:

	/**
     *在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
     * 输入一个数组，求出这个数组中的逆序对的总数 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]

In the process of merge sorting, if the number of the latter array is smaller than the number of the previous array, it will definitely be able to form a reverse-order pair and the number of reverse-order pairs can be calculated, because the two arrays to be merged are advanced in advance It has been merged and sorted, so there will not be less or more statistics like before.

The reverse-order pair in [A, B] = the reverse-order pair in [A] The reverse-order pair in [B] The reverse-order pair that mixes A and B together

Note: In the title There is a special requirement, which requires modulo. This modulus is not only modulo in the result, but also modulo in the process calculation.

2. Numbers that only appear once in the array

[Title]

Except for two numbers in an integer array, all other numbers appear twice . Please write a program to find these two numbers that only appear once.

[Code]

    /**
     * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。
     * 请写程序找出这两个只出现一次的数字。
     *
     * 位运算中异或的性质：
     * 两个相同数字异或 = 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;
    }

[Thinking]

First of all: the properties of XOR in bit operations: two identical numbers XOR = 0, one number and 0 XOR Or it is itself.
When only one number appears once, we XOR all the numbers in the array in sequence, and the last remaining number is the single number, because all the numbers that appear in pairs cancel out.

Following this idea, let’s look at an array in which two numbers (we assume it is AB) appear once. We should XOR first. The remaining number must be the result of the XOR of A and B. The 1 in the binary of this result represents the different bits of A and B. We take the digit of the first 1, assuming it is the 3rd digit, and then divide the original array into two groups. The grouping criterion is whether the 3rd digit is 1. In this way, the same numbers are definitely in the same group, because all the digits of the same numbers are the same, while the different numbers are definitely not in the same group. Then XOR these two groups in sequence according to the original idea, and the remaining two results are these two numbers that only appear once.

(Recommendations for more related interview questions: java interview questions and answers)

3. Two numbers whose sum is S

[Topic]

Input an ascending sorted array and a number S, search for two numbers in the array so that their sum is exactly S. If there are multiple pairs of numbers whose sum is equal to S, output the minimum product of the two numbers. of.

Corresponding to each test case, two numbers are output, the smaller one is output first.

[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. A sequence of consecutive positive numbers whose sum is S

[Title]

Xiao Ming likes mathematics very much. One day he When doing math homework, he was asked to calculate the sum of 9~16, and he immediately wrote that the correct answer was 100. But he was not satisfied with this. He was wondering how many consecutive sequences of positive numbers the sum of which was 100 (including at least two numbers). Before long, he had another sequence of consecutive positive numbers that summed to 100: 18,19,20,21,22. Now the question is handed to you, can you quickly find all consecutive positive number sequences whose sum is S? Good Luck!

Output all consecutive positive number sequences whose sum is S. The order within the sequence is from small to large, and between the sequences, the starting number is in order from small to large

[Code]

    /**
     * 输出所有和为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;
    }

[Idea]

Double pointer method
The left and right pointers continuously circle the range of the continuous sequence

Input sum=20 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
1, define two pointers, the left pointer starts from 1, the right pointer starts from 2
Loop starts
2, sum (1 2 = 3
3, if it is judged that 3 is less than 20, the right pointer, 2 becomes 3, sum 3 3=6. Loop until right pointer = 6, and the sum is 21.
4, else if determines that 21 is greater than 20, left pointer, 1 becomes 2, and the sum subtracts the left pointer value , the sum is 21-1=20.
5, else sum is the same as the input, save the number. [Then add the right pointer to find the remaining combination]
End of loop

5. Poker Straight card

【Title】

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入门

The above is the detailed content of Summary of common array questions in Java interviews (4). For more information, please follow other related articles on the PHP Chinese website!