精选算法入门——day9

题目一

题干

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解题思路

在解决这个问题前，我们可以先看一个简单点的问题：一个整型数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 这个问题如何解决？在原来我们学过异或(^)这个操作符，他的定义是如果两个相应bit位相同，则结果为0，否则为1。（口诀是同0异1），而异或有两个非常重要的性质：

1. 0和任何数相异或都为本身。即：x^0 = x；
2. 两个相同的数相异或为0。即：x^x = 0；

也就是说在一个数组里面如果只有一个数字出现了一次，其他的数字都出现两次，那么我们将这个数组中的数字都异或，那么得到的数字就是只出现一次的数字（相同的数字异或成0，0与其他数字相异或又得到了它本身，并且异或满足交换律）。这个问题解决了，我们再回到题干中的除了两个数字之外，其他的都出现了两次的问题，我们可不可以将这个数组分为两个部分，两个不同的数字被分为不同的两个组，其余的都是相同的数字，然后再用前面的方法解决这个问题。那么核心问题就回到了，如何把不同的数字分为不同两个组，并且其余的数字都相同。我们知道：异或整个数组的结果就是这两个出现一次的数异或的结果，并且是一定不等于 0 的（因为两个数不同），那么说明这个异或结果的二进制序列中一定是有 1 的，找到这个 1（这个1表示这两个不同的数在这个bit位上一个是0，一个是1），我们就可以利用这个来分组。我们将原始数组与这个bit位上的“1”进行按位与，那么就分为了两组，分组的结果一定是，相同数据被分到了同一组，不同数据一定被分到了不同的组。（不同的数字在这个位上异或得到1，那么就证明一个是0，一个是1，那么按位与也会得到0或者1，可以分到不同的组，而相同的数，在这个位上，肯定同时为0，或者同时为1，所以按位与一定会分到同一个组上）。分成两个组后，再用上面只有一个数字出现一次的问题就可以解决了。下面是完整代码：

代码

import java.util.*;
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
    public int FindNumAppearOnce(int [] array){
        int size = array.length;
        int num = 0;
        for(int i = 0; i < size;i++){
            num = num ^ array[i];
        }
        return num;
    }

    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int size = array.length;
        int num = 0;
        for(int i = 0;i < size;i++){
            num = num ^ array[i];
        }
        int time = 0;
        while((num & 1) == 0){
            time++;
            num = num >> 1;
        }
        int []array1 = new int[size]; 
        int []array2 = new int[size]; 
        for(int i = 0;i < size;i++){
            int tmp = array[i];
            int times = time;
            while(times != 0){
                tmp = tmp>>1;
                times--;
            }
            if((tmp & 1) == 0){
                array1[i] = array[i];
            }else {
                array2[i] = array[i];
            }
        }
        num1[0] = FindNumAppearOnce(array1);
        num2[0] = FindNumAppearOnce(array2);
    }
}

题目二

题干

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

解题思路

这条题目挺有意思的，其实简单来说就是在1-100之间求出一组连续的数字等于S，正常的想法是先从两个数开始（[1,2]到[99,100]）,看看有没有等于S的区间，有就保存起来，然后再到三个数（[1,3]到[98,100]），以此类推一直到100个数（[1,100]）,但是这样做造成的时间复杂度会非常的大，我们能否换一种方法呢？假设我们要找S=9，我们画图了解一下：

初始情况下我们设置一个[1,2]的区间窗口，当我们发现此区间的和小于9时，right向右移动一个格子，即：

此时区间为[1,3]，区间的和为6，小于S（9），right向右移动一个格子，即：

此时区间为[1,4],区间和为10，大于S（9），left向右移动一个格子，即：

此时区间为[2,4]，区间和为9，等于S（9），将此区间的数值记录下来，并且left向右移动一个格子（为什么是left向右移动，而不是right向右移动，我们知道此时区间的和已经等于S了，那么如果right向右移动，那么区间的和一定是大于S的也就没有意义，所以需要将left向右移动），即：

此时区间为[3,4]，区间的和为7，小于S（9），right向右移动一个格子，即：

此时区间为[3,5]，区间和为12，大于S（9），left向右移动一个格子，即：

此时区间为[2,4]，区间和为9，等于S（9），将此区间的数值记录下来，并且left向右移动一个格子，依次类推。直到遍历到100，或者left>right为止，跳出循环。下面是完整代码：

代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param sum int整型
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) {
        // write code here
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
        int left = 1;
        int right = 2;
        int tmp = (left + right) * (right - left + 1) / 2;
        while (right <= 100 && left < right) {
            while (tmp != sum && right <= 100 && left < right) {
                if (tmp < sum) {
                    right++;
                    tmp = (left + right) * (right - left + 1) / 2;
                }
                if (tmp > sum) {
                    left++;
                    tmp = (left + right) * (right - left + 1) / 2;
                }
            }
            if (tmp == sum) {
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = left; i <= right; i++) {
                    list.add(i);
                }
                lists.add(list);
                left++;
                tmp = (left + right) * (right - left + 1) / 2;
            }
        }
        return lists;
    }
}