数组调整

教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以 数组 形式返回。

也就是说奇数均放到偶数后面

简单想法使用List，来一个奇数add一个，最后再搞偶数就彳亍。

class Solution {
    public int[] trainingPlan(int[] actions) {
        List<Integer> li = new ArrayList<>();
        for(int i = 0; i < actions.length; i++){
            if(actions[i] % 2 == 1){
                li.add(actions[i]);
            }
        }
        for(int i = 0; i < actions.length; i++){
            if(actions[i] % 2 == 0){
                li.add(actions[i]);
            }
        }
        int[] ans = new int[actions.length];
        for(int i = 0; i < actions.length; i++){
            ans[i] = li.get(i);
        }
        return ans;
    }
}

双指针

class Solution {
    public int[] trainingPlan(int[] actions) {
        int i = 0, j = actions.length - 1, tmp;
        while(i < j) {
            while(i < j && (actions[i] & 1) == 1) i++;
            while(i < j && (actions[j] & 1) == 0) j--;
            tmp = actions[i];
            actions[i] = actions[j];
            actions[j] = tmp;
        }
        return actions;
    }
}

文件组合

待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 的所有文件。请返回所有符合该要求的文件传输组合列表。

注意，返回时需遵循以下规则：

每种组合按照文件编号 升序 排列；
不同组合按照第一个文件编号 升序 排列。

我采用的是双指针，直接维护指针之间这里区域的数值和。

import java.util.*;

class Solution {
    public int[][] fileCombination(int target) {
        Map<Integer, Integer> map = new TreeMap<>();
        int pre = 1, nex = 2;
        int sum = 3;
        while(nex != target){
            if(sum > target){
                sum -= pre;
                pre++;
            }else if(sum == target){
                map.put(pre, nex);
                sum -= pre;
                pre++;
            }else{
                nex++;
                sum += nex;
                
            }
        }

        int[][] ans = new int[map.size()][];
        int index = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            int[] tem = new int[entry.getValue() - entry.getKey()+1];
            for(int i = 0; i < entry.getValue() - entry.getKey() + 1; i++){
                tem[i] = i + entry.getKey();
            }
            ans[index++] = tem;
        }
        
        return ans;




    }
}

另一种是直接通过左端点和总和，搞出来右端点看是不是整数。只能说算的很好。

class Solution {
    public int[][] fileCombination(int target) {
        int i = 1;
        double j = 2.0;
        List<int[]> res = new ArrayList<>();
        while(i < j) {
            j = (-1 + Math.sqrt(1 + 4 * (2 * target + (long) i * i - i))) / 2;
            if(i < j && j == (int)j) {
                int[] ans = new int[(int)j - i + 1];
                for(int k = i; k <= (int)j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            i++;
        }
        return res.toArray(new int[0][]);
    }
}

按规则计算统计结果（DP）

为了深入了解这些生物群体的生态特征，你们进行了大量的实地观察和数据采集。数组 arrayA 记录了各个生物群体数量数据，其中 arrayA[i] 表示第 i 个生物群体的数量。请返回一个数组 arrayB，该数组为基于数组 arrayA 中的数据计算得出的结果，其中 arrayB[i] 表示将第 i 个生物群体的数量从总体中排除后的其他数量的乘积。

我直接判断0元素个数，看里面有多少个0，相对应结果。

class Solution {
    public int[] statisticalResult(int[] arrayA) {
        int ans = 1;
        int cnt = 0;
        for(int i = 0; i < arrayA.length; i++){
            if(arrayA[i] == 0) cnt++;
            if(arrayA[i] != 0)
            ans *= arrayA[i];
        }
        int[] sum = new int[arrayA.length];
        if(cnt == 0){
            for(int i = 0; i < arrayA.length; i++){
                
                    sum[i] = ans / arrayA[i];
                
            }
        }else if(cnt == 1){
            for(int i = 0; i < arrayA.length; i++){
                if(arrayA[i] == 0) sum[i] = ans;
                else sum[i] = 0;
            }
        }else{
            for(int i = 0; i < arrayA.length; i++){
                sum[i] = 0;
            }
        }
            
        return sum;
    }
}

采用DP，维护前序后续数组。找到乘积也就是左右两边乘积。

//这个鸡肋的一点是下标是从0开始的，不方便只能说。
class Solution {
    public int[] statisticalResult(int[] arrayA) {
        int n = arrayA.length;

        int[] pre = new int[n+7];
        int[] rear = new int[n+7];
        pre[0] = 1;
        //pre[1] = 1;
        for(int i = 1; i < n; i++){
            pre[i] = pre[i-1]*arrayA[i-1];
        }
        rear[n+1] = 1;
        for(int i = n; i >= 1; i--){
            rear[i] = rear[i+1] * arrayA[i-1];
        }
        int[] ans = new int[n];
        for(int i = 0; i < n; i++){
            ans[i] = pre[i] * rear[i+2];
        }
        return ans;
}
}

寻找文件副本

设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。

显然题目是想让使用set来完成。

import java.util.*;
import java.lang.*;
class Solution {
    public int findRepeatDocument(int[] documents) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < documents.length; i++){
            if(set.contains(documents[i])){
                return documents[i];
            }else{
                set.add(documents[i]);
            }
        }
        return 0;
    }
}

另一个思路是使用原地交换，有点像那个排序方法，哎忘了。

想法很好，但是实践性有待商榷。