Zusammenfassung häufiger Array-Fragen in Java-Interviews (4)

1. Paare in umgekehrter Reihenfolge in einem Array

(Lernvideo-Empfehlung: Java-Kurs)

[Thema]

Zwei Zahlen in einem Array, wenn die erste Zahl größer als die zweite Zahl ist Die beiden Zahlen bilden in umgekehrter Reihenfolge ein Zahlenpaar. Geben Sie ein Array ein und ermitteln Sie die Gesamtzahl der umgekehrten Paare im Array P. Und geben Sie das Ergebnis von P modulo 1000000007 aus. Das heißt, Ausgabe P%1000000007

Die Frage stellt sicher, dass das Eingabearray nicht die gleiche Nummer hat

Datenbereich:

对于%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;
    }

[Denken]

Wenn im Prozess der Zusammenführungssortierung Die Nummer des letzteren Arrays ist kleiner als Die Zahlen im vorherigen Array müssen in der Lage sein, Paare in umgekehrter Reihenfolge zu bilden, und die Anzahl der Paare in umgekehrter Reihenfolge kann berechnet werden Da die beiden zusammenzuführenden Arrays im Voraus zusammengeführt und sortiert wurden. Es wird nicht mehr oder weniger Statistiken geben als bisher.

Das Paar in umgekehrter Reihenfolge in [A, B] = das Paar in umgekehrter Reihenfolge in [A] + das Paar in umgekehrter Reihenfolge in [B] + das Paar in umgekehrter Reihenfolge, das A und B miteinander vermischt

Hinweis: Dort Eine besondere Anforderung in der Frage ist, dass Sie Modulo benötigen. Dieses Modulo moduliert nicht nur das Ergebnis, sondern muss auch in der Prozessberechnung modulo sein.

2. Zahlen, die nur einmal im Array erscheinen

[Titel]

Mit Ausnahme von zwei Zahlen in einem ganzzahligen Array erscheinen alle anderen Zahlen zweimal. Bitte schreiben Sie ein Programm, um diese beiden Zahlen zu finden, die nur einmal vorkommen.

【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;
    }

【Denken】

Zuallererst: die Eigenschaften von XOR bei Bitoperationen: Zwei identische Zahlen sind XOR = 0, eine Zahl und 0 sind XOR oder sich selbst.
Wenn nur eine Zahl einmal vorkommt, XORen wir alle Zahlen im Array der Reihe nach und die letzte verbleibende Zahl ist die einzelne Zahl, da sich alle Zahlen, die paarweise erscheinen, aufheben.

Dieser Idee folgend schauen wir uns ein Array an, in dem zwei Zahlen (nehmen wir an, es sei AB) einmal vorkommen. Wir sollten zuerst XOR verwenden. Die verbleibende Zahl muss das Ergebnis der XOR-Verknüpfung von A und B sein. Die 1 in der Binärdatei dieses Ergebnisses repräsentiert die verschiedenen Bits von A und B. Wir nehmen die Ziffer der ersten 1, vorausgesetzt, es ist die 3. Ziffer, und teilen dann das ursprüngliche Array in zwei Gruppen auf. Das Gruppierungskriterium ist, ob die 3. Ziffer 1 ist. Auf diese Weise gehören die gleichen Zahlen definitiv zur gleichen Gruppe, da alle Ziffern der gleichen Zahlen gleich sind, während die unterschiedlichen Zahlen definitiv nicht zur gleichen Gruppe gehören. Dann XOR diese beiden Gruppen der Reihe nach gemäß der ursprünglichen Idee, und die verbleibenden beiden Ergebnisse sind diese beiden Zahlen, die nur einmal vorkommen.

(Empfehlungen für weitere verwandte Interviewfragen: Java-Interviewfragen und -antworten)

3. Zwei Zahlen, deren Summe S ist Zahlen so, dass ihre Summe genau S ist. Wenn es mehrere Zahlenpaare gibt, deren Summe gleich S ist, wird dasjenige mit dem kleinsten Produkt der beiden Zahlen ausgegeben.

Entsprechend jedem Testfall werden zwei Zahlen ausgegeben, wobei die kleinere zuerst ausgegeben wird.

【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. Eine Folge aufeinanderfolgender positiver Zahlen, deren Summe S ist von 9~16. Er schrieb mir sofort, dass die richtige Antwort 100 sei. Damit war er jedoch nicht zufrieden. Er fragte sich, wie viele aufeinanderfolgende Folgen positiver Zahlen die Summe 100 ergaben (einschließlich mindestens zweier Zahlen). Bald hatte er eine weitere Folge aufeinanderfolgender positiver Zahlen, die in der Summe 100 ergaben: 18,19,20,21,22. Nun stellt sich Ihnen die Frage: Können Sie schnell alle aufeinanderfolgenden positiven Zahlenfolgen finden, deren Summe S ist? Viel Glück!

Gib alle aufeinanderfolgenden positiven Zahlenfolgen aus, deren Summe S ist. Innerhalb der Sequenz ist die Reihenfolge von klein nach groß, und zwischen den Sequenzen ist die Startnummer in der Reihenfolge von klein nach groß

[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;
    }

[Idee]

Doppelzeigermethode

Der linke und rechte Zeiger kontinuierlich Kreisen Sie den Bereich der kontinuierlichen Sequenz ein

Eingabesumme=20 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

1, definieren Sie zwei Zeiger, Der linke Zeiger beginnt bei 1, der rechte Zeiger beginnt bei 2

Die Schleife beginnt mit

2, Summe (1+2 = 3

3, wenn festgestellt wird, dass 3 kleiner als 20 ist, wird der rechte Zeiger zu ++, 2 3 und die Summe 3+3=6. Die Schleife wird fortgesetzt, bis der rechte Zeiger = 6 ist und die Summe 21 beträgt.

4, andernfalls wird der linke Zeiger zu ++, 1, wenn festgestellt wird, dass 21 größer als 20 ist 2, und die Summe wird vom linken Zeigerwert subtrahiert, und die Summe ist
5, sonst ist sie die gleiche wie die Eingabe, dann ++ den rechten Zeiger, summieren und finden verbleibende Kombination]

Ende der Schleife

5. Poker gerade

[Titel]

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

Das obige ist der detaillierte Inhalt vonZusammenfassung häufiger Array-Fragen in Java-Interviews (4). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!