奇偶数合并

今天分享一道很有意思的算法题目

1、题目描述

奇偶数合并

将所有相邻且相同的偶数相加放入相邻偶数中间 将所有相邻且相同奇数相加，替换掉这两个相邻且相同的奇数 最后输出合并后的数组结果。

举例

数组[1,2,2,7,8,3,3,6]

数组奇偶数合并之后[1,2,4,2,7,8,6,12,6]

2、思路

由于要对偶数合并且将合并值增加到相邻且相等2个偶数之间，然后相邻且相等奇数合并，原始数组长度可能会发生改变，因此需要用额外的数据结构进行存储临时计算结果数据。这里用List进行存储，也可以用其它数据结果存储。

另外两个奇数相加等于偶数，因此要先计算偶数，再计算奇数。

第一轮计算之后，需要判断是否还需要递归进行计算，如果需要，则递归奇偶数合并即可，最后输出计算结果。

3、实战

public class Test1 {

    public static void main(String[] args) {
        int[] array = {1,2,2,7,8,3,3,6};
        calculatedNum(array);
    }

    /**
     * 奇偶数合并
     * 将所有相邻且相同的偶数相加放入相邻偶数中间
     * 将所有相邻且相同奇数相加，替换掉这两个相邻且相同的奇数
     * 最后输出合并后的数组结果
     *
     * @param array 待排序数组
     * @return int[] 结果
     */
    public static int[] calculatedNum(int[] array){
        if(array.length == 0){
            return new int[0];
        }

        List<Integer> lists = new ArrayList<>();
        for (int i = 0; i < array.length-1; i++) {
            if(array[i]==array[i+1]){
                if(array[i]%2==0){
                    lists.add(array[i]);
                    lists.add(array[i]*2);
                }else{
                    lists.add(array[i]*2);
                    i++;
                }
            }else{
                lists.add(array[i]);
            }
        }
        // 由于上面for循环结束条件是i < array.length-1，这里需要添加最后一个元素，才能遍历完全
        lists.add(array[array.length-1]);
        // 将list转成array
        int[] list2Array = Arrays.stream(lists.toArray()).mapToInt(x -> (int) x).toArray();
        if(isNeedRepeatCalculated(list2Array)){
           return  calculatedNum(list2Array);
        }
        return list2Array;
    }

    /**
     * 判断是否需要二次合并计算
     *
     * @param array 待判断的数组
     * @return boolean 结果
     */
    public static boolean isNeedRepeatCalculated(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            if(array[i] == array[i+1]){
                return true;
            }
        }
        return false;
    }
}