本文以前是写蓝桥杯练习记录的，后来搁了。现在打算写一写最近学算法的心得体会吧。

1.前缀和主要适⽤的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。（2022年1月23日）

class PrefixSum {
    // 前缀和数组
    private int[] prefix;
    /* 输⼊⼀个数组，构造前缀和 */
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < prefix.length; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }
    /* 查询闭区间 [i, j] 的累加和 */
    public int query(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
}

2.差分数组的主要适⽤场景是频繁对原始数组的某个区间的元素进⾏增减（2022年1月23日）

// 差分数组⼯具类
class Difference {
    // 差分数组
    private int[] diff;

    /* 输⼊⼀个初始数组，区间操作将在这个数组上进⾏ */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 根据初始数组构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i,j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /* 返回结果数组 */
    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}

第一周

第一周：1月28日-2月6日

T1：愤怒小鸟 来源：第七届蓝桥杯-决赛-Java-B组

X星球愤怒的小鸟喜欢撞火车！

一根平直的铁轨上两火车间相距1000米
两火车（不妨称A和B）以时速10米/秒相对行驶。

愤怒的小鸟从A车出发，时速50米/秒，撞向B车，
然后返回去撞A车，再返回去撞B车，如此往复....
两火车在相距1米处停车。

问：这期间愤怒的小鸟撞B车多少次？

注意：需要提交的是一个整数（表示撞B车的次数），不要填写任何其它内容。

解题思路：

代码：

public class T1 {
    public static void main(String[] args) {
        double locateA = 0, locateB = 1000;//A的初始位置为0，B的初始位置为1000
        double crashTime;//撞车时间
        int count = 0;//撞B车的次数统计
        boolean isCrashB = false;//撞的是否是B车
        //两车距离大于1时执行循环
        while (locateB - locateA > 1) {
            crashTime = (locateB - locateA) / 60;
            isCrashB = !isCrashB;//第奇数次循环撞的是B车，第偶数次循环撞的是A车
            if (isCrashB) {
                count++;
            }
            locateA += 10 * crashTime;//小鸟撞车后A的位置
            locateB -= 10 * crashTime;//小鸟撞车后B的位置
        }
        System.out.println(count);
    }
}
输出结果：9

T2：反幻方 来源：第七届蓝桥杯-决赛-Java-B组

我国古籍很早就记载着
2 9 4
7 5 3
6 1 8
这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。
下面考虑一个相反的问题。
可不可以用 1~9 的数字填入九宫格。
使得：每行每列每个对角线上的数字和都互不相等呢？
这应该能做到。
比如：
9 1 2
8 4 3
7 5 6
你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。
旋转或镜像算同一种。
比如：
9 1 2
8 4 3
7 5 6

7 8 9
5 4 1
6 3 2

2 1 9
3 4 8
6 5 7
等都算作同一种情况。
请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。

解题思路：

1.为了求出有多少种三阶反幻方，需要先求出1-9九个数字的全排列，相当于每一种情况都要判断一遍。这里就要用到深度优先搜索(DFS)的思想。

2.每一种情况，都要判断三行三列以及两对角线相加是否都不同，那么一共可以得到8个值，这8个值都不相同，才满足题意。考虑到Java中的Set集合具有元素不会重复的特性，因此可以将这8个值存入一个Set集合，如果最终集合中有8个元素，说明满足题意，小于8个元素，说明有相同的情况存在，应当舍弃。统计有多少个方阵满足每行每列每个对角线上的数字和都互不相等。

3.因为旋转或镜像算同一种情况，观察一下可以发现，一个方阵通过旋转，可以得到4种不同的形态(旋转0度、90度、180度、270度)，通过镜像，也可以得到4种形态(上下翻转、左右翻转)。因此，一个满足题意的方阵，通过旋转和镜像，会有8种不同的形态。而这8种形态，也必然会在全排列中出现，所以最终满足满足题意的方阵数目 = 每行每列每个对角线上的数字和都互不相等的数目 / 8

DFS三个重点：1.截止条件。2.候选结点。3.筛选。

public class T2 {
    private static int count = 0;

    public static void main(String[] args) {
        //Key：1-9 Value：是否被使用过
        HashMap<Integer, Boolean> map = new HashMap<>();
        for (int i = 1; i <= 9; i++) {
            map.put(i, false);
        }
        LinkedList<Integer> list = new LinkedList<>();//存储结果
        dfs(map, 1, list);//深度优先搜索
        System.out.println(count / 8);//旋转或镜像会有8种不同形态但算同一种情况
    }

    public static void dfs(HashMap<Integer, Boolean> map, int level, LinkedList<Integer> result) {
        //1.截止条件
        if (level > map.size()) {
            //截止后说明一个完整的排列已经生成，可以开始计算行、列、对角线的和
            int row1 = result.get(0) + result.get(1) + result.get(2);
            int row2 = result.get(3) + result.get(4) + result.get(5);
            int row3 = result.get(6) + result.get(7) + result.get(8);
            int col1 = result.get(0) + result.get(3) + result.get(6);
            int col2 = result.get(1) + result.get(4) + result.get(7);
            int col3 = result.get(2) + result.get(5) + result.get(8);
            int diag1 = result.get(0) + result.get(4) + result.get(8);
            int diag2 = result.get(2) + result.get(4) + result.get(6);
            /**
             * 创建一个Set集合，将这些结果存入set中，如果最终set集合中的元素数量不是8，说明有重复的元素
             */
            HashSet<Integer> set = new HashSet<>();
            Collections.addAll(set, row1, row2, row3, col1, col2, col3, diag1, diag2);
            if (set.size() == 8) {
                count++;
            }
            return;
        }
        //2.候选结点
        for (int i = 1; i <= map.size(); i++) {
            //筛选
            if (!map.get(i)) {
                result.push(i);//当前结点的值没有被使用过则可以加入结果集
                map.put(i, true);//加入结果集后要改变状态
                dfs(map, level + 1, result);
                result.pop();//通过出栈将结果集初始化
                map.put(i, false);//将各个结点的使用状态初始化
            }
        }
    }
}

T3：打靶 来源：第七届蓝桥杯-决赛-Java-B组

小明参加X星球的打靶比赛。
比赛使用电子感应计分系统。其中有一局，小明得了96分。

这局小明共打了6发子弹，没有脱靶。
但望远镜看过去，只有3个弹孔。
显然，有些子弹准确地穿过了前边的弹孔。

不同环数得分是这样设置的：
1,2,3,5,10,20,25,50

那么小明的6发子弹得分都是多少呢？有哪些可能情况呢？

下面的程序解决了这个问题。
仔细阅读分析代码，填写划线部分缺失的内容。
public class Main
{	
    static void f(int[] ta, int[] da, int k, int ho, int bu, int sc)
    {
        if(ho<0 || bu<0 || sc<0) return;
        if(k==ta.length){
            if(ho>0 || bu>0 || sc>0) return;
            for(int i=0; i<da.length; i++){
                for(int j=0; j<da[i]; j++) 
                    System.out.print(ta[i] + " ");
            }
            System.out.println();
            return;
        }
        
        for(int i=0; i<=bu; i++){
            da[k] = i;
            f(ta, da, k+1,  __________________ , bu-i, sc-ta[k]*i);   // 填空位置
        }
        
        da[k] = 0;
    }
    
    public static void main(String[] args)
    {
        int[] ta = {1,2,3,5,10,20,25,50};
        int[] da = new int[8];
        f(ta, da, 0, 3, 6, 96);
    }
}
注意：只填写划线处缺少的内容，不要填写已有的代码或符号，也不要填写任何解释说明文字等。

解题思路：

1.经过分析代码，可以得出此题各个参数的含义如下：

数组ta中存放环数分值，数组da里面存放每个分值各打了多少次，k记录DFS中当前所在层数，ho记录还剩多少个弹孔没打，bu记录还剩多少颗子弹，sc记录还剩多少分没打。

2.填空位置是让我们填写递归调用DFS方法的参数ho，ho记录还剩多少个弹孔没有打，按理说此处应该填写ho - 1。但是从for循环中的参数i可以发现，i是从0开始的，当i = 0时，da[k] = i，则此时da[k] = 0，相当于打中da[k]的次数没有增加，则没有增加弹孔。而当i > 0时，则子弹是打在了靶子上的，产生弹孔且只产生一个弹孔。

因此此题答案为：

ho - (i == 0 ? 0 : 1)