三道算法

1.篮球赛，10人，每个人有一个战斗力n1-n10 分成两组（人数相等），战斗力差值最小

输入:10 9 8 7 6 5 4 3 2 1
输出:1

import java.util.*;
public class Main{
    public static Integer minValue = Integer.MAX_VALUE;
        public static void main(String[] args){
            Scanner scan=new Scanner(System.in);
            String str = scan.nextLine();
            String[] strList = str.split(" ");
            ArrayList<Integer> arrs = new ArrayList<>();
            for(int i=0;i<strList.length;i++){
                arrs.add(Integer.valueOf(strList[i]));
            }
            List<Integer> path = new ArrayList<>();
            boolean[] used = new boolean[arrs.size()];
            dfs(arrs,path,used);
            System.out.println(minValue);
        }
        //dfs全排列 每次计算前5个 和后5个的绝对值差值 取最小的
    private static void dfs(List<Integer> nums, List<Integer> path, boolean[] used) {
        if (path.size() == nums.size()) {
            minValue = Math.min(Math.abs(path.get(0)+path.get(1)+path.get(2)+path.get(3)+path.get(4)-path.get(5)-path.get(6)-path.get(7)-path.get(8)+path.get(9)),minValue);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            // 剪枝，判断重复使用的数字
            if (used[i]) continue;
            path.add(nums.get(i));
            used[i] = true;
            dfs(nums, path,  used);
            // 回溯的过程中，将当前的节点从 path 中删除
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

2.数组最长连续子序列和为固定值

输入1,2,3,4,2
输入6
输出3
import java.util.*;

public class Main{
        public static void main(String[] args){
            Scanner scan=new Scanner(System.in);
            String str = scan.nextLine();
            String[] strList = str.split(",");
            ArrayList<Integer> arrs = new ArrayList<>();
            for(int i=0;i<strList.length;i++){
                arrs.add(Integer.valueOf(strList[i]));
            }
            Integer k = scan.nextInt();
            System.out.println(maxLength(arrs,k));
        }
    public static int maxLength(List<Integer> arr, int k) {
        if(arr==null||arr.size()==0)
            return 0;
        int sum=0;
        int res=0;
        Map<Integer,Integer> map=new HashMap<Integer,Integer>();
        map.put(0,-1);
        for(int i=0;i<arr.size();i++){
            sum+=arr.get(i);
            if(map.containsKey(sum-k)){
                res=Math.max(i-map.get(sum-k),res);
            }
            if(!map.containsKey(sum))
                map.put(sum,i);
        }
        return res;
    }
}

3.停车位问题

用1分割输入的数据(split函数)，再考虑首尾为0的情况，取最大值即可

import java.util.*;

public class Main{
        public static void main(String[] args){
            Scanner scan=new Scanner(System.in);
            String str = scan.nextLine();
            str = str.replaceAll(" ","");
            str = str.replaceAll("1{2,}","1");
            System.out.println(str);
            System.out.println(maxDistance(str));
        }
    public static Integer maxDistance(String str) {
            Integer maxDis = Integer.MIN_VALUE;
        String[] strList = str.split("1");
        for (int i=0;i<strList.length;i++){
            if(strList[i].length()==0)continue;
//            System.out.println(strList[i]);
            if(strList[i].length()%2==0){
                maxDis = Math.max(strList[i].length()/2,maxDis);
            }else{
                maxDis = Math.max(strList[i].length()/2+1,maxDis);
            }
            if(str.charAt(0) == '0'){
                maxDis = Math.max(strList[0].length(),maxDis);
            }
            if(str.charAt(str.length()-1) == '0'){
                maxDis = Math.max(strList[strList.length-1].length(),maxDis);
            }
        }
        return maxDis;
    }
}