记录：2022-9-30 打家劫舍 二叉搜索树中第K小的元素 公平锁 磁盘调度
学习时间：2022-9-30
学习内容
1、LeetCode
198. 打家劫舍
思路
dp[i] = dp[i-1]之前的最大值 + num[i]
优化思路：把最大值用一个变量来存
代码
class Solution {
public int rob(int[] nums) {
int[] dp = new int[nums.length];
if(nums.length == 1){
return nums[0];
}
if(nums.length == 2){
return Math.max(nums[0],nums[1]);
}
int max = nums[0];
dp[0] = nums[0];
dp[1] = nums[1];
int ans = Math.max(dp[0],dp[1]);
for(int i = 2;i<nums.length;i++){
dp[i] = nums[i] + max;
max = Math.max(max,dp[i-1]);
ans = Math.max(dp[i],ans);
}
return ans;
}
}
更优解
优化DP数组为一个变量
public int rob(int[] nums) {
int prev = 0;
int curr = 0;
// 每次循环，计算“偷到当前房子为止的最大金额”
for (int i : nums) {
// 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
// dp[k] = max{ dp[k-1], dp[k-2] + i }
int temp = Math.max(curr, prev + i);
prev = curr;
curr = temp;
// 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
}
return curr;
}
作者：nettee
链接：https://leetcode.cn/problems/house-robber/solution/dong-tai-gui-hua-jie-ti-si-bu-zou-xiang-jie-cjavap/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
230. 二叉搜索树中第K小的元素
思路
要注意他是二叉搜索树，如果要找的话，可以从最小开始，然后用一个栈来不停的push和pop，具体为让节点所有左孩子进栈，每次出栈时让该元素的右节点进栈，然后将右节点的所有左孩子也进栈，循环此过程
代码
class Solution {
Stack<TreeNode> path = new Stack<TreeNode>();
int ans;
int index = 0;
public int kthSmallest(TreeNode root, int k) {
TreeNode temp = root;
while(temp!=null){
path.push(temp);//所有左节点进栈
ans = temp.val;
temp = temp.left;
}
while(!path.isEmpty()){
TreeNode node = path.pop();
index++;
if(k == index){
ans = node.val;
break;
}
if(node.right!=null){
//将right所有左子树进栈
TreeNode right = node.right;
while(right != null){
path.push(right);//所有左节点进栈
right = right.left;
}
}
}
return ans;
}
}
更优解
记录子树的结点数
class Solution {
public int kthSmallest(TreeNode root, int k) {
MyBst bst = new MyBst(root);
return bst.kthSmallest(k);
}
}
class MyBst {
TreeNode root;
Map<TreeNode, Integer> nodeNum;
public MyBst(TreeNode root) {
this.root = root;
this.nodeNum = new HashMap<TreeNode, Integer>();
countNodeNum(root);
}
// 返回二叉搜索树中第k小的元素
public int kthSmallest(int k) {
TreeNode node = root;
while (node != null) {
int left = getNodeNum(node.left);
if (left < k - 1) {
node = node.right;
k -= left + 1;
} else if (left == k - 1) {
break;
} else {
node = node.left;
}
}
return node.val;
}
// 统计以node为根结点的子树的结点数
private int countNodeNum(TreeNode node) {
if (node == null) {
return 0;
}
nodeNum.put(node, 1 + countNodeNum(node.left) + countNodeNum(node.right));
return nodeNum.get(node);
}
// 获取以node为根结点的子树的结点数
private int getNodeNum(TreeNode node) {
return nodeNum.getOrDefault(node, 0);
}
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solution/er-cha-sou-suo-shu-zhong-di-kxiao-de-yua-8o07/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
效率比我的还低。。当令解算了
2、Java锁机制（3） 公平锁
ReentrantLock
公平锁和非公平锁的实现是ReentrantLock
当调用公平锁时，调用此方法
static final class FairSync extends Sync {
final void lock() {
acquire(1);
}
}
public final void acquire(int arg) {
if (!tryAcquire(arg) &&
acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
selfInterrupt();
}
这里需要分析tryAcquire和acquireQueued方法
protected final boolean tryAcquire(int acquires) {//1
final Thread current = Thread.currentThread();
int c = getState();//c==0 则说明有可能可以执行，因为公平锁还需要排队
if (c == 0) {//如果此时
if (!hasQueuedPredecessors() &&//如果前面还有元素，则无法加锁，返回false
compareAndSetState(0, acquires)) {//这个考虑的是并发原子性问题，如果被其他线程先抢占，则等待
setExclusiveOwnerThread(current);
return true;
}
}
else if (current == getExclusiveOwnerThread()) {//可重入锁 一个线程可以多次加锁
int nextc = c + acquires;
if (nextc < 0)
throw new Error("Maximum lock count exceeded");
setState(nextc);
return true;
}
return false;
}
对于上述的hasQueuedPredecessors方法，实际上是使用了AQS队列，
队列是一个双向链表，一个node上有thread，还有一个waitStatus，这个属性会被他的下一个节点赋值成-1，代表这个node后面还有元素，需要唤醒
public final boolean hasQueuedPredecessors() {
Node t = tail; // Read fields in reverse initialization order
Node h = head;
Node s;
return h != t &&//还有元素
((s = h.next) == null //并发问题，如果有第三个节点进来，发现s==null，说明第二个节点正在操作，第三个节点返回true，表示前面还有排队的元素
|| s.thread != Thread.currentThread());//如果不是当前的线程，则说明还没执行到他，前面就还存在元素
}
//这个代码会将node加入到队列中挂起，上面的两个方法作用为：先尝试获取锁，如果获取不到锁，则尝试将node加入到队列中。完成这个操作后中断当前线程
final boolean acquireQueued(final Node node, int arg) {
boolean failed = true;
try {
boolean interrupted = false;
for (;;) {
final Node p = node.predecessor();//循环获取node的上一个元素
if (p == head && tryAcquire(arg)) {//如果上一个元素是head，说明p是第一个应该出队的元素，然后去加锁，如果加锁成功，执行以下方法
setHead(node);
p.next = null; // help GC
failed = false;
return interrupted;
}
if (shouldParkAfterFailedAcquire(p, node) &&//加锁失败的代码，如果这里还失败，将会继续请求，外层是一个循环
parkAndCheckInterrupt())
interrupted = true;
}
} finally {
if (failed)
cancelAcquire(node);
}
}
3、磁盘调度
磁盘调度问题是一个多线程问题，有多个线程需要请求数据，有一个线程来负责寻道
FCFS调度
先来先服务，从队列中pop出元素并移动磁盘
SSTF 最短寻道距离
每次找离目前最近的距离
这可能会引发饥饿
SCAN算法（电梯算法）
先从一个方向开始，每次找离的最近的，然后再反向移动
LOOK算法
在SCAN基础上，当移动到最后，会回到开始的位置，形成一个环形队列