whvixd | blog

leetcode 198

打家劫舍

题目链接:https://leetcode-cn.com/problems/house-robber/ 题目描述分析 1. 动态规划 dp[n] = MAX(dp[n-1], dp[n-2]+num) dp[n]是最终获取金额最多的数值；第n间房子，其最大数额是dp(n-1)或是dp[n-2]+num,num是第n间房子的金额代码实现...

Posted by Static on May 29, 2020

leetcode 394

字符串解码

题目链接:https://leetcode-cn.com/problems/decode-string/ 题目描述分析 1. 递归+循环遍历 a. 若为数字，则记录数字大小，及数字位数 b. 若为 “[“(所在位子为左指针)，若还有数字，则递归调用a c. 若为 “]“(所在位子为右指针)，执行2[ab]->abab操作代码实现 pu...

Posted by Static on May 28, 2020

leetcode 974

和可被 K 整除的子数组

题目链接:https://leetcode-cn.com/problems/subarray-sums-divisible-by-k 题目描述分析 1. 嵌套for循环遍历数组寻找能整除5的数之和，但是时间复杂度不符合题目要求 2. 同余定理同余定理:[P(j)-P(i-1)]%K==0 <=> P(j)%K==P(i-1)%...

Posted by Static on May 27, 2020

leetcode 287

寻找重复数

题目链接:https://leetcode-cn.com/problems/find-the-duplicate-number/ 题目描述分析 1. 嵌套for循环 2. 利用map查重代码实现 public enum Q287 { instance; public int findDuplicate(int[] nums) ...

Posted by Static on May 26, 2020

leetcode 146

LRU缓存机制

题目链接:https://leetcode-cn.com/problems/lru-cache/ 题目描述分析 1. 双向链表+map put(): a. 首次添加k和v，会新建节点，添加到双向链表的头结点处(头插法)，将k和节点的引用存到map中； b. 若不是首次插入，则通过map找到节点的引用，修改节点的值，再将此节点移到头结点； c. 若容量慢...

Posted by Static on May 25, 2020

leetcode 5

最长回文子串

题目链接:https://leetcode-cn.com/problems/longest-palindromic-substring/ 题目描述分析 1. 暴力时间负责度:O(n^3) 第一层:从左侧开始，寻找最长的第二层:从左边开始遍历，匹配所有回文子串，为了第一步寻找最长回文子串第三层:从右边开始遍历，为了第二步匹配代码实现 pu...

Posted by Static on May 21, 2020

leetcode 1371

每个元音包含偶数次的最长子字符串

题目链接:https://leetcode-cn.com/problems/find-the-longest-substring-containing-vowels-in-even-counts/ 题目描述分析 1. 数组记录元音下标时间负责度:O(n) a. 获取元音下标，存储到数组中 b. 数组长度0:没有元音，返回字符串长度;1:只有一个元音，...

Posted by Static on May 20, 2020

leetcode 680

验证回文字符串 Ⅱ

题目链接:https://leetcode-cn.com/problems/valid-palindrome-ii/ 题目描述分析 1. 暴力时间复杂度:O(n^2) 两个指针指向数组的左右两侧，若有字符不相等的，则截取判断是否是回文串特殊字符串：”eceec”，若按只去掉左侧字符判断是否是回文串，会有问题，所有添加了再按去掉右侧字符判断，...

Posted by Static on May 19, 2020

自实现非公平锁

CLH

参考 ReentrantLock，自实现非公平锁 1. 源码 public class QueuedSynchronizer implements Lock{ private transient Thread exclusiveOwnerThread; private volatile int state; private transient volat...

Posted by Static on May 18, 2020

CLH实现及图解代码

CLH

1. What? Craig, Landin, and Hagersten 简称 CLH，CLH锁是一个自旋锁，以自旋的方式确保无饥饿性，提供先来先服务的公平性，即公平锁。 CLH锁也是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程仅仅在本地变量上自旋，它不断轮询前驱的状态，假设发现前驱释放了锁就结束自旋。 2. Why? CLH队列锁的优点是空间复杂度低，如果有n个线程去竞争...

Posted by Static on May 14, 2020

Static