Résumé des questions courantes dans les entretiens Java (4)

1. Paires d'ordre inverse dans un tableau

(vidéo d'apprentissage recommandée : cours java)

[Sujet]

Deux nombres dans le tableau, si le nombre précédent est supérieur au nombre suivant, alors les deux nombres forment une paire d'ordre inverse. Saisissez un tableau et recherchez le nombre total de paires inversées dans le tableau P. Et affichez le résultat de P modulo 1000000007. Autrement dit, la sortie P%1000000007

La question garantit que le même nombre qui n'est pas dans le tableau d'entrée

Plage de données :

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

[Pensée]

Dans le processus de tri par fusion, si le numéro de ce dernier tableau est inférieur au numéro du tableau précédent, il formera certainement une paire dans l'ordre inverse et le nombre Des paires d'ordre inverse peuvent être calculées, car les deux tableaux à fusionner sont avancés à l'avance. Ils ont été fusionnés et triés, il n'y aura donc ni moins ni plus de statistiques comme avant.

La paire d'ordre inverse dans [A, B] = la paire d'ordre inverse dans [A] + la paire d'ordre inverse dans [B] + la paire d'ordre inverse qui mélange A et B

Remarque : Il y a une exigence particulière dans la question, qui nécessite une prise modulo non seulement modulo le résultat, mais également modulo le calcul du processus.

2. Les nombres qui n'apparaissent qu'une seule fois dans le tableau

[Titre]

À l'exception de deux nombres dans un tableau d'entiers, tous les autres nombres apparaissent deux fois. Veuillez écrire un programme pour trouver ces deux nombres qui n'apparaissent qu'une seule fois.

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

[Pensée]

Premièrement : les propriétés du XOR dans les opérations sur les bits : deux nombres identiques XOR = 0, un nombre et 0 XOR Ou c'est lui-même.
Lorsqu'un seul nombre apparaît une fois, nous XOR tous les nombres du tableau dans l'ordre, et le dernier nombre restant est le nombre unique, car tous les nombres qui apparaissent par paires s'annulent.

En suivant cette idée, regardons un tableau dans lequel deux nombres (nous supposons qu'il s'agit de AB) apparaissent une fois. Nous devrions d'abord XOR. Le nombre restant doit être le résultat du XOR de A et B. Le 1 dans le binaire de ce résultat représente les différents bits de A et B. Nous prenons le chiffre du premier 1, en supposant qu'il s'agit du 3ème chiffre, puis divisons le tableau d'origine en deux groupes. Le critère de regroupement est de savoir si le 3ème chiffre est 1. De cette façon, les mêmes nombres sont définitivement dans le même groupe, car tous les chiffres des mêmes nombres sont identiques et des nombres différents ne sont certainement pas dans le même groupe. Ensuite, XOR ces deux groupes en séquence selon l'idée originale, et les deux résultats restants sont ces deux nombres qui n'apparaissent qu'une seule fois.

(Recommandations pour des questions d'entretien plus connexes : questions et réponses d'entretien Java)

Deux nombres dont la somme est S

[Sujet]

Saisissez un tableau trié par ordre croissant et un nombre S, trouvez deux nombres dans le tableau de sorte que leur somme soit exactement S. S'il existe plusieurs paires de nombres dont la somme est égale à S, affichez le produit minimum des deux numéros de.

Correspondant à chaque cas de test, affichez deux nombres, le plus petit en premier.

[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. Une séquence de nombres positifs consécutifs dont la somme est S

[Sujet]

Xiao Ming aime beaucoup les mathématiques. Un jour, alors qu'il faisait ses devoirs de mathématiques, on lui a demandé de calculer la somme de 9 à 16, et il a immédiatement écrit que la bonne réponse était 100. Mais cela ne le satisfaisait pas. Il se demandait combien de séquences consécutives de nombres positifs dont la somme était 100 (incluant au moins deux nombres). Peu de temps après, il eut une autre séquence de nombres positifs consécutifs qui totalisaient 100 : 18,19,20,21,22. Maintenant, la question vous est posée : pouvez-vous trouver rapidement toutes les séquences de nombres positives consécutives dont la somme est S ? Bonne chance !

Sortez toutes les séquences de nombres positifs consécutifs dont la somme est S. Au sein de la séquence, l'ordre est du petit au grand, et entre les séquences, le numéro de départ est dans l'ordre du petit au grand

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

[Idée]

Méthode du double pointeur
Les pointeurs gauche et droit encerclent continuellement la plage de la séquence continue

Somme d'entrée = 20 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
1, définissez deux pointeurs, le pointeur gauche commence à 1, le pointeur droit commence à 2
La boucle commence
2, somme (1+2 = 3
3, si l'on juge que 3 est inférieur à 20, le pointeur droit ++, 2 devient 3, la somme 3+3=6 Boucle jusqu'à ce que le pointeur droit = ​​6, la somme est 21, sinon si. détermine que 21 est supérieur à 20, le pointeur gauche ++, 1 devient 2, la somme est soustraite de la valeur du pointeur gauche et la somme est 21-1 = 20. La somme else est la même que l'entrée et le. la somme est ajoutée pour trouver la combinaison restante 🎜>
5 Poker Straight

[Titre]

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!