本文以前是写蓝桥杯练习记录的，后来搁了。现在打算写一写最近学算法的心得体会吧。
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;
}
}
3.二分查找的三种情况
区间问题，如果区间是左闭右闭，则while条件要写left<=right，且left = mid + 1，right = mid - 1。左闭右开，则while条件写left<right，且left = mid + 1，right = mid。
基本情况下，相等时，直接返回即可。如果是寻找左边界，则要收紧右侧区间，每次相等时，修改right的值，继续查找。如果是寻找右边界，则要收紧左侧区间，每次相等时，修改left的值。
注意越界问题。
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 直接返回
return mid;
}
}
return -1;
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，收缩右侧区间继续向左找
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回，收缩左侧边界继续向右找
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
4.什么问题可以运用二分搜索算法技巧？
首先，你要从题题中抽象出一个自变量 x，一个关于 x 的函数 f(x)，以及一个目标值 target。
同时，x, f(x), target 还要满足以下条件：
1、f(x) 必须是在 x 上的单调函数（单调增单调减都可以）。
2、题目是让你计算满足约束条件 f(x) == target 时的 x 的值。
二分搜索框架如下：
// 函数 f 是关于自变量 x 的单调函数
int f(int x) {
// ...
}
// 主函数，在 f(x) == target 的约束下求 x 的最值
int solution(int[] nums, int target) {
if (nums.length == 0) return -1;
// 问自己：自变量 x 的最小值是多少？
int left = ...;
// 问自己：自变量 x 的最大值是多少？
int right = ...+1;
while (left < right) {
int mid = left + (right - left) / 2;
if (f(mid) == target) {
// 问自己：题⽬是求左边界还是右边界？
// ...
} else if (f(mid) < target) {
// 问自己：怎么让 f(x) 大⼀点？
// ...
} else if (f(mid) > target) {
// 问自己：怎么让 f(x) 小⼀点？
// ...
}
}
return left;
}
具体来说，想要用二分搜索算法解决问题，分为以下三步：
1、确定 x, f(x), target 分别是什么，并写出函数 f 的代码。
2、找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量，注意x的取值范围非常重要，不能无脑的把left定义为从0开始。
3、根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。
以Leetcode-875题为例：爱吃香蕉的珂珂
要找到珂珂在H小时内吃完所有香蕉的最小速度K，在这里就可以分析出如下信息：
自变量x：吃香蕉的速度k根/小时（求谁，谁就是自变量）
f(x)：吃完所有香蕉需要多少小时
target：题目要求的吃完所有香蕉用时h小时（题目要求的时间就是target，通常会传递到参数中）
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的⼀系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的⼀系列更新
...
}
}
}
7.善用PriorityQueue，这个队列是有序的，但需要自定义比较器。
8.快慢指针的常见算法
(1)判断链表是否有环
boolean hasCycle(ListNode head) {
while (head != null)
head = head.next;
return false;
}
(2)已知链表中含有环，返回这个环的起始位置
当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
slow = head;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
(3)寻找链表的中点
让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
ListNode middleNode(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// slow 就在中间位置
return slow;
}
(4)寻找链表的倒数第n个元素
让快指针先走n步，然后快慢指针开始同速前进。这样当快指针走到链表末尾null时，慢指针所在的位置就是倒数第n个链表节点（n不会超过链表长度）。
ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast, slow;
fast = slow = head;
// 快指针先前进 n 步
while (n-- > 0) {
fast = fast.next;
}
if (fast == null) {
// 如果此时快指针走到头了，
// 说明倒数第 n 个节点就是第一个节点
return head.next;
}
// 让慢指针和快指针同步向前
while (fast != null && fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// slow.next 就是倒数第 n 个节点，删除它
slow.next = slow.next.next;
return head;
}
(5)移除元素和数组去重
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
9.左右指针的常用算法
左右指针在数组中实际是指两个索引值，一般初始化为
left = 0, right = nums.length - 1。
(1)二分查找
(2)只要数组有序，就应该想到双指针技巧。
(3)反转数组
(4)滑动窗口算法
10.链表操作的递归思维
(1)递归反转整个链表
ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
(2)反转链表从head开始的前n个节点
ListNode successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点，返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点，需要反转前 n - 1 个节点
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;
}
11.单调栈解决Next Greater Element问题
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int[] result = new int[nums1.length];
HashMap<Integer,Integer> resultMap = new HashMap<>();
Stack<Integer> stack = new Stack<>();
for(int i = nums2.length - 1;i >= 0;i--){
while(!stack.empty() && stack.peek() <= nums2[i]){
//栈顶元素<前面的元素，则不满足，弹飞
stack.pop();
}
//如果此时栈为空说明当前比较的元素后面没有比它大的，为了节约时间就不把-1给put进去
//不为空说明栈顶就是下一个比它大的，因为后进先出
if(!stack.empty()){
resultMap.put(nums2[i],stack.peek());
}
//nums2倒着进栈，这行代码放最后是为了先把最后一个元素的下一个更大值设置为-1
stack.push(nums2[i]);
}
for(int i = 0;i < nums1.length;i++){
result[i] = resultMap.getOrDefault(nums1[i],-1);
}
return result;
}
12.二叉树的层级遍历
标准的二叉树层级遍历框架，从上到下，从左到右打印每一层二叉树节点的值，可以看到，队列 q 中不会存在 null 指针。
void traverse(TreeNode root) {
if (root == null) return;
// 初始化队列，将 root 加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
/* 层级遍历代码位置 */
System.out.println(cur.val);
/*****************/
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
第一周
第一周：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)
2 Comments
嗯，好复杂
踩踩