您的位置 首页 java

java面试中常见的数组题目汇总(四)

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

【思考】

在归并排序的过程中 后一个数组的数如小于前一个数组的数,则一定能够构成逆序对且逆序对的数目可计算,因为待归并的两个数组提前已经归并排序过,所以不会出现像前面那样少统计或者多统计的情况出现。

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

【思考】

首先:位运算中异或的性质:两个相同数字异或 = 0,一个数和 0 异或还是它本身。
当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。

依照这个思路,我们来看两个数(我们假设是 AB)出现一次的数组。我们首先还是先异或,剩下的数字肯定是 A、B 异或的结果,这个结果的二进制中的 1,表现的是 A 和 B 的不同的位。我们就取第一个 1 所在的位数,假设是第 3 位,接着把原数组分成两组,分组标准是第 3 位是否为 1。如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组。然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。

(更多相关面试题推荐:java面试题及答案)

3、和为 S 的两个数字

【题目】

输入一个递增排序的数组和一个数字 S,在数组中查找两个数,使得他们的和正好是 S,如果有多对数字的和等于 S,输出两个数的乘积最小的。

对应每个测试案例,输出两个数,小的先输出。

【代码】

    /**     * 输入一个递增排序的数组和一个数字 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 的连续正数序列

【题目】

小明很喜欢数学,有一天他在做数学作业时,要求计算出 9~16 的和,他马上就写出了正确答案是 100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为 100 (至少包括两个数)。没多久,他就得到另一组连续正数和为 100 的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为 S 的连续正数序列?Good Luck!

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

【思路】

双指针法
左右指针不断圈定连续序列的范围

输入sum=20(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
1,定义两个指针,左指针从1开始,右指针从2开始
循环开始
2,求和(1+2 = 3
3,如果判断3小于20,右指针++,2变为3,求和3+3=6。循环一直到右指针=6,和为21。
4,else if 判断21大于20,左指针++,1变为2,和减去左指针值,和为21-1=20。
5,else 和与输入一样,存数。 【再把右指针++,求和,求剩余组合】
循环结束

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面试中常见的数组题目汇总(四)

文章地址:https://www.zhihuclub.com/13482.shtml

关于作者: 智云科技

热门文章

网站地图