Yao Lirong's Blog

From Lecture: Synchronization

Monitor

idea: object state guarded by its mutex

monitor is just a class, whose all public methods “synchronize,” which means you can’t access state without holding mutex

Principal: let short methods hold the mutex in case it doesn’t affect performance

From Lecture: Concurrency

Concurrency and Parallelism

• Concurrency: multiple threads (java level, can be executed by one core or multiple core)
• parallelism: multiple cores (hardware level. can execute one thread or multiple thread)

From Lecture: Designing and documenting interfaces and implementations

An Example of Writing Interface

1. Overview: what concerns?

1
2

/** An n*n mutable 2048 puzzle. */
class Puzzle{}

From Lecture:

• representing Java values
• Generics, more lists
• Hash tables

Download my notes in OneNote here

题目来源：洛谷P1162 填涂颜色

1. 如果被包围的部分没什么特点，那么就可以看看其他部分有没有什么特点，本题中就是可以从外围开始搜索，搜到墙就停下，最后没被搜到的部分就是被墙包围的部分
2. 为了防止外围起点就是墙，或者是外围的0被墙分为好几部分导致我们无法搜索到被分割的部分，可以多开一圈数组，使得外围相互连接起来，确保不被包围的0一定可以被搜到

题目来源：洛谷P1141 01迷宫

BFS找连通块

1. 连通块肯定还是DFS找得快，因为一开始不知道什么是连通块所以写了个BFS

2. 搜索连通块不需要记录从某一个点出发最远能到达哪个点（BFS搜索最短距离），只需要记录从某一个点出发一共经过了多少个符合条件的点就行了（BFS搜索连通块），因为如果A和B联通，B和C联通，那么A和C必然联通，所以一次搜索能达到的所有点必定在同一个连通块内

题目来源：洛谷P1118 数字三角形

暴力搜索

看到题目的第一眼想的就是直接搜，发现不少TLE，我还减了不少枝…

超时，只有20分，通过几个运行结果来看，写法应该对了，只是全都TLE而已

题目来源：洛谷P1019 单词接龙

调了好几天，最后请教了醉神(@magolor)，十分钟给我调好了…

1. 这个程序一个问题就是循环根本就不会吧dict全循环一遍，那可能就是初始化出了问题： m=pointer 的位置，当时记得应该写一个副本 m 代替 pointer 被改变，但是写着写着忘了 m 具体应该在哪被初始化了，问题就出现在这
2. 回溯的状态：一定要明确回溯应当回溯到具体那个状态，是ans_temp已经被改变的状态吗？还是未改变的状态？本题中是ans_temp未改变的状态

题目来源：洛谷P1101 单词方阵

dir 这个数组是很好用的，不需要为8个方向特意写8个不同的函数，只需要写一个函数但是改变取哪一个dir[i]来判定哪一个方向符合条件就行了

题目来源：洛谷P1219 八皇后

我的解法

自己的程序出现的几个问题：

1. 对角线表达式太过复杂，各层绝对值都可以简化，应该相信大部分情况下复杂的都是错误的
2. 不需要记录这一行放没放过棋子，因为我们是按照一行一行的顺序放过来的，上一行必定有棋子，下一行必定无棋子