【JavaSE练习题】数组的创建和使用

奇数位于偶数之前

调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
如数组：[1,2,3,4,5,6]
调整后可能是：[1, 5, 3, 4, 2, 6]

public static void func4(int[] array) {
    int i = 0;
    int j = array.length-1;
    while (i < j) {
        //循环外面给了i < j  ,思考这里为什么还需要判断？
        while (i < j && array[i] % 2 != 0) {
            i++;
        }
        //i 下标一定是偶数
        while (i < j && array[j] % 2 == 0) {
            j--;
        }
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

冒泡排序

给定一个整型数组, 实现冒泡排序(升序排序)

进一步进行了优化，当数据在排序过程当中有序了，会在某一趟排序后，发现数据没有交换。
所以，每一趟排序完，都去检查是否发生了交换，没有交换证明数据已近有序，不需要再进行剩余趟数的排序了。

public static void bubbleSort(int[] array) {
    boolean flg = false;
    //1、确定一个趟数
    for (int i = 0; i < array.length-1; i++) {
        for (int j = 0; j < array.length-1-i; j++) {
            if(array[j] > array[j+1]) {
                int tmp = array[j];
                array[j] = array[j+1];
                array[j+1] = tmp;
                flg = true;
            }
        }
        if(flg == false) {
            //没有交换
            break;
        }
    }
}

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

本题最重要的一句话：假设每种输入只会对应一个答案
也就意味着不会有多个答案，暴力求解就是挨个匹配查找即可，代码如下：

public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];
    // 双指针i和j，i从前向后遍历，j从后向i遍历，若arr[i]+arr[j]=target,即为题解
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = nums.length - 1; j > i; j--) {
            if (nums[i] + nums[j] == target) {
                result[0] = i;
                result[1] = j;
            }
        }
    }
    return result;
}

如果想提升效率，需要用到后期学习的哈希表来解答，目前大家属于初学阶段，暂且以上述解法为准。

只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
本题主要考察运算符：异或。

异或的特点是：
1、n ^ n = 0；即两个相同的数字异或是0
2、0 ^ n = n；即0和任何数字进行异或，结果就是那个任何数字。

public int singleNumber(int[] nums) {
    // 用异或运算的性质可以巧妙的解决这个问题，因为数组中只有一个数字出现一次
    // 则其他出现两次的数字用异或运算后都是0，最终整个数组异或运算的结果即为所求。
    int ret = 0;
    for (int i : nums) {
        ret ^= i;
    }
    return ret;
}

多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：[3,2,3]
输出：3
示例 2：
输入：[2,2,1,1,1,2,2]
输出：2

数组中出现次数超过一半的数字，一定是排好序之后，中间位置的数字。

/**
 * 排序法
 * 将数组排序后，数组n/2的元素一定是众数
 */
public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length/2];
}

存在连续三个奇数的数组

给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。
示例 1：
输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。
示例 2：
输入：arr = [1,2,34,3,4,5,7,23,12]
输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。

本题比较简单，数字是连续出现的，所以我们只需要定义一个计数器，如果连续出现的次数超过3，则返回true。

public boolean threeConsecutiveOdds(int[] arr) {
    // 引入标志位记录连续出现奇数的个数
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        if (isConsecutiveOdd(arr[i])) {
            // 出现奇数，count ++;
            count ++;
            if (count == 3) {
                // 出现连着三个奇数，返回true
                return true;
            }
        }else {
            // 碰到偶数，count重置
            count = 0;
        }
    }
    return false;
}

private boolean isConsecutiveOdd(int num) {
    return num % 2 != 0;
}