1 鏈表反轉(zhuǎn)
Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class Solution {
//從后往前走
public ListNode reverseList(ListNode head) {
ListNode cur = head,pre=null;
while(head!=null){
head = head.next;
cur.next = pre;
pre = cur;
cur = head;
}
return pre;//最后cur和head都是NULL
}
}
2 鏈表兩兩反轉(zhuǎn)
public ListNode swapPairs(){
ListNode h = new ListNode(0);
ListNode next = h;
for (int i = 1; i < 4; i++) {
next.next = new ListNode(i);
next = next.next;
}
head = h;
ListNode dump = new ListNode(-1);//新的頭結(jié)點(diǎn)
dump.next = head浸须；//新頭結(jié)點(diǎn)指向h
ListNode f,s,p = dump;
while (head != null && head.next!=null) {
//設(shè)置交換節(jié)點(diǎn)
f = head;
s = head.next;
//交換節(jié)點(diǎn)
f.next = s.next;
s.next = f;
p.next = s;
//重置head位置和pre位置
head = f.next;
p=f;
}
print(dump);
return dump.next;
}
3 判斷鏈表是否有環(huán)
3.1 頭結(jié)點(diǎn)開(kāi)始遍歷移怯，直到位NULL（卡時(shí)間，避免死循環(huán)）
3.2 Set存儲(chǔ)走過(guò)的結(jié)點(diǎn)和橙，判斷是否有重復(fù)仔燕，復(fù)雜的O(N)
3.3 快慢指針，快走兩步魔招，慢指針走一步晰搀，O(N)
public boolean hasCycle(ListNode head) {
if(head==null || head.next == null)
return false;
ListNode s=head,f=head.next;
while(f!=null && f.next!=null){
if(s.equals(f)){
return true;
}
f = f.next.next;
s = s.next;
}
return false;
}
4 有效的括號(hào)
1 用棧存儲(chǔ)左括號(hào)([{，Map存儲(chǔ)括號(hào)對(duì){},[],()
2 遍歷字符串办斑，左括號(hào)入棧外恕，右括號(hào)的話從Map中拿到對(duì)于的左括號(hào)與棧頂值對(duì)比是否相等，相等繼續(xù)遍歷字符串乡翅，否則返回false
3 遍歷完畢字符鳞疲，最后判斷棧是否為空，空即為有效括號(hào)
class Solution {
public boolean isValid(String s) {
Map<String,String> map = new HashMap<String, String>(){
{
put(")","(");
put("]","[");
put("}","{");
}
};
Stack<String> stack = new Stack<>();
for (int i=0;i<s.length();i++){
String c = s.charAt(i)+"";
if (!map.containsKey(c)){//左括號(hào)（[{,入棧
stack.push(c);
continue;
}
//右括號(hào)）]}蠕蚜，棧頂值是否==map.get(c)
if (map.containsKey(c) && !stack.isEmpty() && stack.pop().equals(map.get(c))){
continue;
}else {
return false;
}
}
return stack.isEmpty();
}
}
5 用棧實(shí)現(xiàn)隊(duì)列
1 兩個(gè)棧實(shí)現(xiàn)尚洽，一個(gè)輸入棧一個(gè)輸出棧
2 push操作只操作輸入棧
3 pop和peek操作只操作輸出棧，并且先判斷輸出棧是否為空靶累，若為空腺毫，需要將輸入棧的元素依次轉(zhuǎn)移到輸出棧
class MyQueue {
Stack<Integer> input = new Stack<>();
Stack<Integer> ouput = new Stack<>();
/**
* Initialize your data structure here.
*/
public MyQueue() {
}
/**
* Push element x to the back of queue.
*/
public void push(int x) {
input.push(x);
}
/**
* Removes the element from in front of queue and returns that element.
*/
public int pop() {
trimToSize();
return ouput.pop();
}
/**
* Get the front element.
*/
public int peek() {
trimToSize();
return ouput.peek();
}
/**
* Returns whether the queue is empty.
*/
public boolean empty() {
return input.isEmpty() && ouput.isEmpty();
}
private void trimToSize(){
if (!ouput.isEmpty())
return;
while (!input.isEmpty()){
ouput.push(input.pop());
}
}
}
6 用隊(duì)列實(shí)現(xiàn)棧
重點(diǎn)操作Push，在push元素的時(shí)候需要將先前的元素依次出隊(duì)并且再次添加到隊(duì)列里頭挣柬，直至剛?cè)腙?duì)的元素在隊(duì)里第一位
class MyStack {
private LinkedList<Integer> queue = new LinkedList<>();
/** Initialize your data structure here. */
public MyStack() {
}
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
int size = queue.size();
while (size > 1) {
queue.add(queue.remove());
size--;
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.remove();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
7 優(yōu)先隊(duì)里
小頂堆
截屏2020-07-24 上午1.29.06.png
從圖中可以看出斐波拉契堆和嚴(yán)格的斐波拉契堆性能比較好
截屏2020-07-24 上午1.31.37.png
大頂堆
截屏2020-07-24 上午1.29.41.png
8 數(shù)據(jù)流中的第K大元素
8.1 用一個(gè)數(shù)組將前K個(gè)最大的數(shù)保存起來(lái)腐螟，每次插入判斷當(dāng)前數(shù)值是否大于第K大的數(shù)华烟，如果大于女责，將第K大元素移除樱衷，并將當(dāng)前值插入數(shù)組中,時(shí)間復(fù)雜度為NKlogK
8.2 用優(yōu)先隊(duì)里Priority隊(duì)列存前K大的元素，元素小的數(shù)值處于堆頂，當(dāng)要插入的數(shù)值大于堆頂元素時(shí)叁熔，刪除堆頂元素委乌，并將當(dāng)前值入隊(duì)到優(yōu)先隊(duì)列中，時(shí)間復(fù)雜度為N*Log(2)K
class KthLargest {
//小頂堆 pop為最小的 offer操作入隊(duì)
private PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
for (int i : nums){
add(i);
}
}
public int add(int val) {
if (priorityQueue.size()<k){//個(gè)數(shù)小于K荣回，直接放到優(yōu)先隊(duì)列（小頂堆）
priorityQueue.offer(val);
}else if (priorityQueue.peek()<val){
//個(gè)數(shù)大于K遭贸，而且val大于K個(gè)最大數(shù)值中的最小數(shù)（大于第K大數(shù)），先移除堆頂元素再插入
priorityQueue.poll();
priorityQueue.offer(val);
}
return priorityQueue.peek();
}
}
9 滑動(dòng)窗口最大值
給定一個(gè)數(shù)組 nums心软，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)壕吹。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字∩玖澹滑動(dòng)窗口每次只向右移動(dòng)一位耳贬。
1 暴力方法，有N-K+1個(gè)窗口猎唁，每次遍歷查找最大值K咒劲，復(fù)雜度為 O(Nk)
2 最大堆中 heap[0] 永遠(yuǎn)是最大的元素。在大小為 k 的堆中插入一個(gè)元素消耗 log?(k)時(shí)間诫隅，因此算法的時(shí)間復(fù)雜度為 O(Nlog?(k))
2 雙端隊(duì)里腐魂，
處理前 k 個(gè)元素，初始化雙向隊(duì)列逐纬。
遍歷整個(gè)數(shù)組蛔屹。在每一步 :
清理雙向隊(duì)列 :
- 只保留當(dāng)前滑動(dòng)窗口中有的元素的索引。
- 移除比當(dāng)前元素小的所有元素豁生，它們不可能是最大的兔毒。
將當(dāng)前元素添加到雙向隊(duì)列中。
將 deque[0] 添加到輸出中沛硅。
返回輸出數(shù)組眼刃。
class Solution {
private ArrayDeque<Integer> deque = new ArrayDeque<>();
private int[] nums;
public int[] maxSlidingWindow(int[] nums, int k) {
int length = nums.length;
if (length==0 || k ==0)
return new int[0];
if (k==1)
return nums;
this.nums = nums;
//記錄結(jié)果數(shù)組
int[] output = new int[length-k+1];
//標(biāo)記前K個(gè)值最大元素下標(biāo)
int maxIndex = 0;
for (int i=0;i<k;i++){
cleanDeque(i,k);
deque.addLast(i);
if (nums[i]>nums[maxIndex])
maxIndex = i;
}
output[0] = nums[maxIndex];
for (int i=k;i<length;i++){
cleanDeque(i,k);//先清理隊(duì)里里頭的元素绕辖，比nums[i]小的都移除
deque.addLast(i);//插入第I個(gè)元素下標(biāo)
output[i-k+1] = nums[deque.getFirst()];//記錄保存最大值
}
return output;
}
//清理隊(duì)列里的值k：插入值的下標(biāo) windowSize：窗口大小
private void cleanDeque(int index,int windowSize){
if (deque.isEmpty()) return;
if (index-deque.getFirst()==windowSize)//隊(duì)列里有K個(gè)元素摇肌，則將第一個(gè)移除
deque.removeFirst();
while (!deque.isEmpty()&&nums[index]>nums[deque.getLast()])
//如果要插入的值nums[index]大于window里頭的值，刪除移動(dòng)窗口里頭的元素仪际，因?yàn)橛衝ums[index]在围小，index前邊的元素沒(méi)有出頭之日
deque.removeLast();
}
}
10 有效的字母異位詞
1 排序，將字符排序树碱，然后再比較是否相等,時(shí)間復(fù)雜度為 O(nlog?n)
2 hash表存儲(chǔ)當(dāng)前字母?jìng)€(gè)數(shù)肯适，key為字母的值，時(shí)間復(fù)雜度O(N)
class Solution {
public boolean isAnagram(String s, String t) {
if (s==null || t==null)
return false;
if (s.length() != t.length())
return false;
int[] rst = new int[26];
for (int i = 0; i < s.length(); i++) {
rst[s.charAt(i)-'a']++;
rst[t.charAt(i)-'a']--;
}
for (int i : rst) {
if (i == 0) {
continue;
}else {
return false;
}
}
return true;
}
}
11 1. 兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target成榜，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)框舔，并返回他們的數(shù)組下標(biāo)。
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1 暴力求解發(fā)，遍歷兩次數(shù)組刘绣，時(shí)間復(fù)雜度：O(n^2)
2 哈希表存儲(chǔ)數(shù)組【值,下標(biāo)】鍵值對(duì)樱溉，遍歷數(shù)組元素，哈希表查找（target-當(dāng)前元素）是否存在纬凤，存在則返回查找對(duì)象下標(biāo)以及當(dāng)前值下標(biāo)福贞，否則將當(dāng)前值和下標(biāo)存儲(chǔ)到哈希表中
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int rst = target - nums[i];//計(jì)算hashmap的key值
if (map.containsKey(rst)) {//存在直接返回
return new int[]{map.get(rst),i};
}
map.put(nums[i],i);//存儲(chǔ)當(dāng)前值和下標(biāo)到hashmap中
}
throw new IllegalArgumentException("null tow sum solution");
}
}
12 三數(shù)之和
給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a停士，b挖帘，c ，使得 a + b + c = 0 恋技？請(qǐng)你找出所有滿足條件且不重復(fù)的三元組
1 暴力求解法拇舀，時(shí)間復(fù)雜度是 O(n3)。
2 在湊齊兩人以后猖任，他們可以找主持人登記需求的第三人你稚，而不需要在茫茫人海中去找隊(duì)友。這樣朱躺，我們就把問(wèn)題優(yōu)化成了每個(gè)人都要找其他每個(gè)人刁赖，即時(shí)間復(fù)雜度 O(n2)
3 雙指針，當(dāng)我們需要枚舉數(shù)組中的兩個(gè)元素時(shí)长搀，如果我們發(fā)現(xiàn)隨著第一個(gè)元素的遞增宇弛，第二個(gè)元素是遞減的，那么就可以使用雙指針的方法源请，將枚舉的時(shí)間復(fù)雜度從 O(N2)減少至 O(N)枪芒。為什么是 O(N)呢？這是因?yàn)樵诿杜e的過(guò)程每一步中谁尸，「左指針」會(huì)向右移動(dòng)一個(gè)位置舅踪，而「右指針」會(huì)向左移動(dòng)若干個(gè)位置，這個(gè)與數(shù)組的元素有關(guān)良蛮，但我們知道它一共會(huì)移動(dòng)的位置數(shù)為 O(N)抽碌，均攤下來(lái)，每次也向左移動(dòng)一個(gè)位置决瞳，因此時(shí)間復(fù)雜度為 O(N)货徙。
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> list = new ArrayList();
Arrays.sort(nums);
for (int first = 0; first < nums.length - 2; first++) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
int third = nums.length - 1;
int target = -nums[first];
for (int second = first + 1; second < nums.length - 1; second++) {
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
while (second < third && nums[second] + nums[third] > target) {
--third;
}
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list1 = new ArrayList<>();
list1.add(nums[first]);
list1.add(nums[second]);
list1.add(nums[third]);
list.add(list1);
}
}
}
return list;
}
}
13 驗(yàn)證二叉搜索樹(shù)
給定一個(gè)二叉樹(shù)皮胡，判斷其是否是一個(gè)有效的二叉搜索樹(shù)痴颊。
假設(shè)一個(gè)二叉搜索樹(shù)具有如下特征：
1. 節(jié)點(diǎn)的左子樹(shù)只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
2. 節(jié)點(diǎn)的右子樹(shù)只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)屡贺。
3. 所有左子樹(shù)和右子樹(shù)自身必須也是二叉搜索樹(shù)蠢棱。
- 遞歸：遞歸函數(shù) helper(root, lower, upper) 來(lái)遞歸判斷root.val的值是否在（lower锌杀，upper）中，若不在則返回false泻仙；在的話遞歸遍歷左結(jié)點(diǎn)helper(root.left, lower, root.val) 和右子樹(shù)helper(root.right, root.val, upper)
- 中序遍歷:中序遍歷二叉搜索樹(shù)一定是升序的抛丽，中序遍歷的時(shí)候?qū)崟r(shí)檢查當(dāng)前值是否大于前一個(gè)中序遍歷到的結(jié)點(diǎn)的值，如果均大于說(shuō)明是升序的饰豺。
遞歸方法
private boolean help(TreeNode node,Integer low,Integer up){
if (node==null) return true;
int val = node.val;//當(dāng)前結(jié)點(diǎn)的值
if ((up!=null && val >= up)//當(dāng)前結(jié)點(diǎn)的值大于最大值
|| (low!=null && val <= low)) //當(dāng)前結(jié)點(diǎn)值小于最小值
return false;//說(shuō)明不是一顆二叉搜索樹(shù)
if (!help(node.left, low, val))//更新左子樹(shù)值的最大值
return false;
if (!help(node.right, val, up)) {//更新右子樹(shù)值的最小值
return false;
}
return true;//左子樹(shù)和右子樹(shù)均滿足條件亿鲜，是一顆二叉搜索樹(shù)
}
中序遍歷
if (root==null)//特殊情況
return true;
double value = -Double.MAX_VALUE;//value保存當(dāng)前左子樹(shù)的最大值（前一個(gè)中序遍歷到的結(jié)點(diǎn)的值），初始化為最小值
Stack<TreeNode> stack = new Stack<>();//保存中序遍歷結(jié)點(diǎn)
while (!stack.isEmpty() || root != null) {
while (root != null) {
stack.push(root);//當(dāng)前結(jié)點(diǎn)不為空冤吨，將當(dāng)前結(jié)點(diǎn)入棧
root = root.left;//繼續(xù)將當(dāng)前結(jié)點(diǎn)的左孩子入棧,中序遍歷先遍歷左子樹(shù)
}
root = stack.pop();//*得到中序遍歷的結(jié)點(diǎn)
if (root.val<=value) return false;//*當(dāng)前結(jié)點(diǎn)值必須大于左子樹(shù)的值
value = root.val;//更新中序遍歷左子樹(shù)最大值
root = root.right;//*繼續(xù)判斷右子樹(shù)
}
return true;
簡(jiǎn)單點(diǎn)中序遍歷
List<Integer> nodeVal = new ArrayList<>();//保存中序遍歷結(jié)點(diǎn)的值
public boolean isValidBST(TreeNode root) {
input(root);
//中序遍歷升序
for (int i = 0; i < nodeVal.size()-1; i++) {
if (nodeVal.get(i) >= nodeVal.get(i + 1)) {
return false;
}
return true;
}
private void input(TreeNode node){
if (node.left != null) {//先遍歷左子樹(shù)
input(node.left);
}
nodeVal.add(node.val);//當(dāng)前結(jié)點(diǎn)
if (node.right != null) {//在遍歷右子樹(shù)
input(node.right);
}
}
14 二叉搜索樹(shù)的最近公共祖先
給定一個(gè)二叉搜索樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先
要點(diǎn)：兩個(gè)結(jié)點(diǎn)值都比根節(jié)點(diǎn)大蒿柳，則兩個(gè)結(jié)點(diǎn)都在右子樹(shù)，繼續(xù)在右子樹(shù)查找
兩個(gè)結(jié)點(diǎn)值都比跟結(jié)點(diǎn)小漩蟆，則兩個(gè)結(jié)點(diǎn)都在左子樹(shù)垒探，繼續(xù)在左子樹(shù)查找
兩個(gè)結(jié)點(diǎn)一大一小在根節(jié)點(diǎn)左右兩顆子樹(shù)中，則當(dāng)前結(jié)點(diǎn)就是最近公共祖先
- 遞歸方法
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int pVal = p.val;
int qVal = q.val;
TreeNode parent = root;
if (parent.val < pVal && parent.val < qVal) {//兩個(gè)結(jié)點(diǎn)值都在右子樹(shù)
return lowestCommonAncestor(parent.right, p, q);
}
if (parent.val > pVal && parent.val >qVal) {//兩個(gè)結(jié)點(diǎn)值都在左子樹(shù)
return lowestCommonAncestor(parent.left, p, q);
}
return parent;
}
- 迭代
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int pval = p.val;
int qval = q.val;
TreeNode parent = root;
while (parent != null) {
int parentVal = parent.val;
if (pval < parentVal && qval < parentVal) {//兩個(gè)結(jié)點(diǎn)值都在左子樹(shù)
parent = parent.left;
continue;
}
if (pval > parentVal && qval > parentVal) {//兩個(gè)結(jié)點(diǎn)值都在右子樹(shù)
parent = parent.right;
continue;
}
return parent;
}
}
15 二叉樹(shù)的最近公共祖先
給定一個(gè)二叉樹(shù), 找到該樹(shù)中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先怠李。
- 遞歸：遞歸遍歷整棵二叉樹(shù)圾叼，定義 fxf表示 xxx 節(jié)點(diǎn)的子樹(shù)中是否包含 p 節(jié)點(diǎn)或 q 節(jié)點(diǎn)，如果包含為 true捺癞，否則為 false
class Solution {
TreeNode ans = null;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root,p,q);
return ans;
}
private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
if (root==null) return false;
boolean lson = dfs(root.left, p, q);//遞歸左子樹(shù)查找p或者q的值
boolean rson = dfs(root.right, p, q);//遞歸右子樹(shù)查找p或者q的值
//如果左右子樹(shù)均包含其中一個(gè)結(jié)點(diǎn)夷蚊，則找到公共祖先
if ((lson && rson)
//若果當(dāng)前結(jié)點(diǎn)為其中一個(gè)值，并且左子樹(shù)或者右子樹(shù)包含另外一個(gè)值髓介，則說(shuō)明找到公共祖先
|| ((root.val == p.val || root.val == q.val) && (lson || rson)))
{
ans = root;
}
return root.val == p.val || root.val == q.val || lson || rson;
}
}
iShot2020-07-27上午01.54.07.png
16 Pow(x, n)
1 庫(kù)函數(shù)
2 暴力求解惕鼓，循環(huán)N次
3 X的N次冪轉(zhuǎn)成X的N/2的平方
- 遞歸寫(xiě)法
public double myPow(double x, int n) {
int N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
private double quickMul(double x, int n) {
if (n == 0) {
return 1;
}
double half = quickMul(x, n / 2);
return n % 2 == 0 ? half * half : half * half * x;
}
- 迭代
iShot2020-07-29上午12.48.49.png
iShot2020-07-29上午12.49.04.png
iShot2020-07-29上午12.49.20.png
class Solution {
public double myPow(double x, int n) {
if(x == 0.0f) return 0.0d;
long b = n;
double res = 1.0;
if(b < 0) {
x = 1 / x;
b = -b;
}
while(b > 0) {
if((b & 1) == 1) res *= x;
x *= x;
b >>= 1;
}
return res;
}
}
17 多數(shù)元素
給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素唐础。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù)大于 ? n/2 ? 的元素箱歧。
- 暴力方法，兩重循環(huán)一膨，第一層循環(huán)元素呀邢，第二層循環(huán)查找數(shù)組中元素的個(gè)數(shù)時(shí)間復(fù)雜度N的平方
- 哈希法 用Map存儲(chǔ)key表示元素?cái)?shù)值，value表示元素的個(gè)數(shù)
-排序 用Arrays.sort對(duì)數(shù)組排序豹绪，復(fù)雜度N*logN价淌，取元素中間值就是所要找的值nums[nums.length/2] - 分治 如果數(shù) a 是數(shù)組 nums 的眾數(shù)，如果我們將 nums 分成兩部分森篷，那么 a 必定是至少一部分的眾數(shù)输钩。
哈希Map
int majorityElement_2(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
//每次記錄最多元素的個(gè)數(shù)和值豺型，避免再次遍歷map數(shù)組
int maxCount = 0;//記錄當(dāng)前最多元素的個(gè)數(shù)
int majority = 0;//記錄當(dāng)前最多個(gè)數(shù)的值
for (int i = 0; i < nums.length; i++) {
int count = map.containsKey(nums[i]) ? map.get(nums[i]) + 1 : 1;
map.put(nums[i], count);
if (maxCount < count) {
maxCount = count;
majority = nums[i];
}
}
return majority;
}
排序
int majorityElement_1(int[] nums) {
//排序
Arrays.sort(nums);
return nums[nums.length / 2];//眾超過(guò)n/2個(gè)仲智，中間的那個(gè)數(shù)肯定是最多的
}
分治
class Solution {
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
private int majorityElementRec(int[] nums, int lo, int hi) {
// 只有一個(gè)元素，返回即可
if (lo == hi) {
return nums[lo];
}
// 分別查找左半部分和右半部分的最多元素
int mid = (hi-lo)/2 + lo;
int left = majorityElementRec(nums, lo, mid);
int right = majorityElementRec(nums, mid+1, hi);
// 左半部分與右半部分一樣姻氨，返回其中一個(gè)即可
if (left == right) {
return left;
}
// 查找元素最多的值
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityElementRec(nums, 0, nums.length-1);
}
}
18 買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II
給定一個(gè)數(shù)組钓辆，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）前联。
- 貪心算法功戚，有股票升值的時(shí)候就買(mǎi)入
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for (int i = 1; i < prices.length; i++) {
//第二天的股票比第一天的股票價(jià)值高，第一天買(mǎi)入似嗤，第二天賣(mài)出
if (prices[i] > prices[i - 1])
maxprofit += prices[i] - prices[i - 1];
}
return maxprofit;
}
}
19 廣度優(yōu)先遍歷
用隊(duì)列保存根節(jié)點(diǎn)元素啸臀，每次從隊(duì)列里頭拿第一個(gè)結(jié)點(diǎn)訪問(wèn)，并將該結(jié)點(diǎn)的子結(jié)點(diǎn)添加到隊(duì)里尾部烁落，如此循環(huán)直到隊(duì)列為NULL
//廣度優(yōu)先搜索乘粒，隊(duì)列實(shí)現(xiàn)
public void BFS(TreeNode root){
if (root == null) {
return;
}
ArrayDeque<TreeNode> nodeArrayDeque = new ArrayDeque<>();
nodeArrayDeque.offer(root);
while (!nodeArrayDeque.isEmpty()){
TreeNode treeNode = nodeArrayDeque.pop();
//TODO
//visitor(treeNode);
if (treeNode.left != null) {
nodeArrayDeque.offer(treeNode.left);
}
if (treeNode.right != null) {
nodeArrayDeque.offer(treeNode.right);
}
}
}
- 深度優(yōu)先搜索
遞歸方法本身就是用棧的形式維護(hù)一個(gè)方發(fā)棧，遍歷的方式的用Stack維護(hù)伤塌，訪問(wèn)了之后再將該結(jié)點(diǎn)入棧
//深度優(yōu)先搜索灯萍，隊(duì)列實(shí)現(xiàn)
public void DFS(TreeNode root) {
if (root == null) {
return;
}
//TOOD
//visit(root);
DFS(root.left);
DFS(root.right);
}
20 二叉樹(shù)的層序遍歷
給你一個(gè)二叉樹(shù)，請(qǐng)你返回其按 層序遍歷 得到的節(jié)點(diǎn)值每聪。 （即逐層地旦棉，從左到右訪問(wèn)所有節(jié)點(diǎn)）
iShot2020-07-31上午12.17.00.pngiShot2020-07-31上午12.17.11.png
- 廣度搜索BFS，每次搜索一層
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
Deque<TreeNode> deque = new LinkedList();
deque.add(root);//每次while循環(huán)存儲(chǔ)下一層結(jié)點(diǎn)的值
while (!deque.isEmpty()) {
List<Integer> levelList = new ArrayList<>();
int size = deque.size();
for (int i = 0; i < size; i++) {//每次循環(huán)遍歷一層結(jié)點(diǎn)
TreeNode cur = deque.pollFirst();
levelList.add(cur.val);
if (cur.left != null) {
deque.add(cur.left);//添加下一層結(jié)點(diǎn)的左兒子結(jié)點(diǎn)
}
if (cur.right != null) {
deque.add(cur.right);//添加下一層結(jié)點(diǎn)的右兒子結(jié)點(diǎn)
}
}
results.add(levelList);
}
return results;
}
- 深度優(yōu)先搜索DFS药薯，遞歸調(diào)用的時(shí)候傳入level值绑洛，更加level值判斷當(dāng)前元素存儲(chǔ)在哪一層（也就是list<list>的第一個(gè)元素）
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if(root==null)
return results;
_dfs(results,root,0);
return results;
}
private void _dfs(ArrayList<ArrayList<Integer>> rst, TreeNode node, int level) {
if (rst.size() - 1 < level) {
rst.add(new ArrayList<>());//添加當(dāng)前層的數(shù)據(jù)結(jié)構(gòu)
}
rst.get(level).add(node.val);//將當(dāng)前值存儲(chǔ)在對(duì)應(yīng)層的數(shù)組中
if (node.left!=null)//遍歷下一層元素
_dfs(rst,node.left,level+1);
if (node.right!=null)
_dfs(rst,node.right,level+1);
}
21 二叉樹(shù)的最大深度
給定一個(gè)二叉樹(shù)，找出其最大深度童本。
二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)诊笤。
- 遞歸：分別查找左子樹(shù)和右子樹(shù)最大的深度加一即可
public int maxDepth(TreeNode root) {
if (root==null)//葉子節(jié)點(diǎn)返回0
return 0;
int leftdepth = maxDepth(root.left);//計(jì)算左子樹(shù)的最大深度
int rightdepth = maxDepth(root.right);//計(jì)算右子樹(shù)的最大深度
return 1 + Math.max(leftdepth, rightdepth);//左右子樹(shù)最大深度+1
}
- 廣度優(yōu)先搜索 廣度優(yōu)先搜索樹(shù)，直到掃描完整棵樹(shù)
public int maxDepth(TreeNode root) {
if (root==null)
return 0;
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
int depth = 0;
while (!list.isEmpty()){
int size = list.size();
for (int i = 0; i < size; i++) {
TreeNode cur = list.poll();
if (cur.left != null) {
list.add(cur.left);
}
if (cur.right != null) {
list.add(cur.right);
}
}
depth++;
}
return depth;
}
22 二叉樹(shù)的最小深度
給定一個(gè)二叉樹(shù)巾陕，找出其最小深度讨跟。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)鄙煤。
- 廣度優(yōu)先搜索樹(shù)晾匠，遇到的第一個(gè)葉子節(jié)點(diǎn)，當(dāng)前深度即為這棵樹(shù)的最小深度
public int minDepth(TreeNode root) {
if (root==null)
return 0;
LinkedList<TreeNode> list = new LinkedList<>();
list.add(root);
int depth = 0;
while (!list.isEmpty()){
int size = list.size();
depth++;
for (int i = 0; i < size; i++) {
TreeNode cur = list.poll();
if (cur.left == null && cur.right == null) {
return depth;//廣度優(yōu)先搜索的第一個(gè)葉子節(jié)點(diǎn)就是當(dāng)前樹(shù)的最小深度
}
if (cur.left != null) {
list.add(cur.left);
}
if (cur.right != null) {
list.add(cur.right);
}
}
}
return depth;
}
- 深度優(yōu)先搜索
對(duì)于每個(gè)節(jié)點(diǎn)梯刚，按照深度優(yōu)先搜索的策略訪問(wèn)凉馆，同時(shí)在訪問(wèn)到葉子節(jié)點(diǎn)時(shí)更新最小深度。
class Solution {
public int minDepth(TreeNode root) {
LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
if (root == null) {
return 0;
}
else {
stack.add(new Pair(root, 1));
}
int min_depth = Integer.MAX_VALUE;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.pollLast();
root = current.getKey();
int current_depth = current.getValue();
if ((root.left == null) && (root.right == null)) {
min_depth = Math.min(min_depth, current_depth);
}
if (root.left != null) {
stack.add(new Pair(root.left, current_depth + 1));
}
if (root.right != null) {
stack.add(new Pair(root.right, current_depth + 1));
}
}
return min_depth;
}
- 遞歸
public int minDepth(TreeNode root) {
if (root==null)//節(jié)點(diǎn)為空返回0
return 0;
if (root.left == null && root.right == null) {
return 1;//葉子節(jié)點(diǎn)返回1
}
int minDepth = Integer.MAX_VALUE;
if (root.left != null) {
minDepth = minDepth(root.left);//計(jì)算左子樹(shù)的最小深度
}
if (root.right != null) {
minDepth = Math.min(minDepth(root.right), minDepth);//計(jì)算右子樹(shù)的最小深度并和左子樹(shù)比較得到子樹(shù)最小深度
}
return minDepth + 1;//左右子樹(shù)的最小深度+當(dāng)前節(jié)點(diǎn)深度1
}
23 括號(hào)生成
數(shù)字 n 代表生成括號(hào)的對(duì)數(shù)亡资，請(qǐng)你設(shè)計(jì)一個(gè)函數(shù)澜共，用于能夠生成所有可能的并且 有效的 括號(hào)組合。
- 暴力法锥腻，生成包含長(zhǎng)度為2*n的字符組合嗦董，每個(gè)都可能為左括號(hào)或者右括號(hào)，總共有2的n次方種組合方式瘦黑，然后再判斷每個(gè)組合是否有效
- 遞歸方法京革，長(zhǎng)度為2*n奇唤，只有當(dāng)左括號(hào)小于n的時(shí)候可以插入左括號(hào)，當(dāng)左括號(hào)大于右括號(hào)個(gè)數(shù)的時(shí)候可以插入右括號(hào)匹摇，當(dāng)左括號(hào)和右括號(hào)個(gè)數(shù)都為n時(shí)即生成一組有效組合
public List<String> generateParenthesis(int n) {
List<String> results = new ArrayList<>();//存儲(chǔ)有效組合的list
_gen(results, n,0, 0, "");
return results;
}
/**
* @param results 存儲(chǔ)有效組合的list
* @param n n個(gè)左/右括號(hào)
* @param left 左括號(hào)使用了幾個(gè)
* @param right 左括號(hào)使用了幾個(gè)
* @param s 當(dāng)前使用了左右括號(hào)的組合
*/
private void _gen(List<String> results,int n, int left, int right, String s) {
if (left == n && right == n) {
results.add(s);
return;
}
if (left < n) {//左括號(hào)個(gè)數(shù)小于n都可以填入左括號(hào)
_gen(results,n,left+1,right,s+"(");
}
if (left > right) {//只有當(dāng)右括號(hào)個(gè)數(shù)小于左括號(hào)的時(shí)候才可以填入右括號(hào)
_gen(results,n,left,right+1,s+")");
}
}
24 N皇后
n 皇后問(wèn)題研究的是如何將 n 個(gè)皇后放置在 n×n 的棋盤(pán)上咬扇，并且使皇后彼此之間不能相互攻擊。
-
剪支發(fā) 遞歸每一行row廊勃，遍歷每一個(gè)列是否滿足條件懈贺，符合條件繼續(xù)遞歸下一行（row+1),否則清理當(dāng)前放置的Q，繼續(xù)下一列的判斷
iShot2020-08-04上午12.55.13.png
List<List<Integer>> results = new ArrayList<>();//記錄結(jié)果的list
Set<Integer> cols = new HashSet<>();//記錄放置皇后Q的列坡垫，其他列就不能放置了用于剪支
Set<Integer> pie = new HashSet<>();//記錄和放置的Q處于同一對(duì)角線的元素（col+row=常亮）
Set<Integer> na = new HashSet<>();//記錄和放置的Q處于同一對(duì)角線的元素（col-row=常亮）
public List<List<String>> solveNQueens(int n) {
_queen(n,0,new ArrayList<>());
return covert(n,results);
}
/**
* @param nQueen 皇后的個(gè)數(shù)
* @param rows 遞歸遍歷到第幾行
* @param state 記錄0~rows皇后的位置
*/
private void _queen(int nQueen, int rows, List<Integer> state) {
if (rows == nQueen) {
//深拷貝一份出來(lái)記錄隅居，避免下一次遞歸修改list數(shù)組
List<Integer> list = new ArrayList<>();
list.addAll(state);
results.add(list);
return;
}
//遍歷當(dāng)前行的每一列是否滿足條件
for (int col = 0; col < nQueen; col++) {
//剪支，不能和之前的同處于同一類葛虐，同一對(duì)角線
if (cols.contains(col) || pie.contains(col+rows) || na.contains(col-rows)){
continue;
}
//滿足條件胎源，添加限制條件，列和對(duì)角線
cols.add(col);
pie.add(col + rows);
na.add(col - rows);
state.add(col);
//繼續(xù)遞歸下一行
_queen(nQueen, rows + 1, state);
//回退尋找更多可能的結(jié)果屿脐，移除當(dāng)前Q并移除對(duì)應(yīng)的限制條件
cols.remove(col);
pie.remove(col + rows);
na.remove(col - rows);
state.remove(state.size()-1);
}
}
private List<List<String>> covert(int n,List<List<Integer>> sources) {
List<List<String>> rst = new ArrayList<>();
for (int i = 0; i < sources.size();i++) {
List<String> sub = new ArrayList<>();
for (int row = 0; row < n; row++) {
sub.add(getStr(n, sources.get(i).get(row)));
}
rst.add(sub);
}
return rst;
}
private String getStr(int n, int pos) {
String rst = "";
for (int i = 0; i < n; i++) {
if (i == pos) {
rst += "Q";
}else {
rst += ".";
}
}
return rst;
}
25 解數(shù)獨(dú)
編寫(xiě)一個(gè)程序涕蚤，通過(guò)已填充的空格來(lái)解決數(shù)獨(dú)問(wèn)題。
一個(gè)數(shù)獨(dú)的解法需遵循如下規(guī)則：
數(shù)字 1-9 在每一行只能出現(xiàn)一次的诵。
數(shù)字 1-9 在每一列只能出現(xiàn)一次万栅。
數(shù)字 1-9 在每一個(gè)以粗實(shí)線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。
- 遞歸+剪支 遍歷整個(gè)9x9的找出沒(méi)有被填入的位置西疤，每次嘗試放入一個(gè)數(shù)烦粒，判斷其合法性，假如不合法繼續(xù)嘗試下一個(gè)數(shù)
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0) {
return;
}
_solve(board);
}
/**
* 遍歷整個(gè)board代赁，找出沒(méi)有確定的值并嘗試放入1-9
* @param board
* @return
*/
private boolean _solve(char[][] board) {
for (int i = 0; i < board.length; i++) {//row遍歷
for (int j = 0; j < board[0].length; j++) {//col遍歷
if (board[i][j] == '.') {//沒(méi)有被確認(rèn)的值
for (char v = '1'; v <= '9'; v++) {//嘗試放入的值
if (_isValid(board, i, j, v)) {//驗(yàn)證該位置是否可以放入v
board[i][j] = v;//驗(yàn)證通過(guò)扰她，填入該值
if (_solve(board))//遞歸判斷其他位置是否滿足條件
return true;//滿足返回true
else
board[i][j] = '.';//不滿足回退，繼續(xù)嘗試下一個(gè)值
}
}
return false;
}
}
}
return true;
}
/**
* 檢查該位置是否可以放入值
* @param board 整個(gè)9x9格式
* @param row 放入值的列
* @param col 放入值的列
* @param v 嘗試放入的值
* @return
*/
private boolean _isValid(char[][] board, int row, int col, char v) {
for (int i = 0; i < 9; i++) {
if (board[row][i]!='.'&&board[row][i]==v)return false;//檢查行是否包含該數(shù)
if (board[i][col]!='.'&&board[i][col]==v) return false;//檢查列是否包含該數(shù)
if (board[3*(row/3)+i/3][3*(col/3)+i%3]!='.'
&& board[3*(row/3)+i/3][3*(col/3)+i%3]==v)//檢查3x3的格子是否包含v
return false;
}
return true;
}
26 二分查找
有序+有上下界+索引可以找到到目標(biāo)值
int left=0,right = len(array)-1
while(left<right){
mid = (left+right)/2;
if(array[mid]==target)
break or return;
if(array[mid]<target)
left = mid+1;
else
right = mid-1;
}
- 應(yīng)用 x 的平方根
x的平方遞增函數(shù)芭碍，每次使用二分查找方法逼近目標(biāo)值
/**
* 開(kāi)平方徒役，二分查找（x的平方遞增）
* @param tartget
* @return
*/
public double sqrt(double tartget) {
if (tartget==0 || tartget ==1)
return tartget;
double left = 1.0,right = tartget,result=0;
while (right - left > 1e-10) {//精確值1e-10
double mid = left/2+right/2;
if (mid>tartget/mid)//避免mid的平方越界
right = mid;
else
left = mid;
}
Log.i("FKY_SQRT", Math.sqrt(tartget) + " " + left);
return left;
}
牛頓迭代法
圖片.png
牛頓法的思想：
在迭代過(guò)程中，以直線代替曲線窖壕，用一階泰勒展式（即在當(dāng)前點(diǎn)的切線）代替原曲線忧勿，
求直線與 xxx 軸的交點(diǎn)，重復(fù)這個(gè)過(guò)程直到收斂瞻讽。
public class Solution {
public int mySqrt(int a) {
long x = a;
while (x * x > a) {
x = (x + a / x) / 2;
}
return (int) x;
}
}
27 實(shí)現(xiàn) Trie (前綴樹(shù))
實(shí)現(xiàn)一個(gè) Trie (前綴樹(shù))鸳吸，包含 insert, search, 和 startsWith 這三個(gè)操作。
public class TrieNode {
public char val;
public boolean isWord;
public TrieNode[] children = new TrieNode[26];
public TrieNode(char c){
val = c;
}
}
class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode(' ');
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode trieNode = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (trieNode.children[c - 'a'] == null) {
trieNode.children[c - 'a'] = new TrieNode(c);
}
trieNode = trieNode.children[c-'a'];
}
trieNode.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (node.children[c-'a']==null) return false;
node = node.children[c - 'a'];
}
return node.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (node.children[c-'a']==null) return false;
node = node.children[c - 'a'];
}
return true;
}
}
28 單詞搜索 II
給定一個(gè)二維網(wǎng)格 board 和一個(gè)字典中的單詞列表 words速勇，找出所有同時(shí)在二維網(wǎng)格和字典中出現(xiàn)的單詞晌砾。
單詞必須按照字母順序，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成快集，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格贡羔。同一個(gè)單元格內(nèi)的字母在一個(gè)單詞中不允許被重復(fù)使用。
iShot2020-08-05下午11.18.26.png
- 將要所搜的word放入字典樹(shù)trie个初，遍歷二維網(wǎng)格board乖寒，將遍歷到的字符累加到一起strCur，每次累加字符的時(shí)候標(biāo)記已經(jīng)訪問(wèn)過(guò)該位置院溺，并在字典上trie上查找strCur字符楣嘁，如果不是前綴，放棄搜索珍逸，如果是逐虚，判斷當(dāng)前字符strCur是否為單詞word，是的話添加到結(jié)果集Set中谆膳，并繼續(xù)遍歷當(dāng)前結(jié)點(diǎn)上下左右結(jié)點(diǎn)值繼續(xù)遞歸
public class Solution {
Set<String> res = new HashSet<>();
public List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();//1 將搜索words放入到字典樹(shù)中
for (String word:words) {
trie.insert(word);
}
int row = board.length;
int col = board[0].length;
boolean[][] visited = new boolean[row][col];//標(biāo)記已經(jīng)被訪問(wèn)的位置結(jié)構(gòu)visited
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
find(visited,board, i, j, "",trie);//遍歷查找board中所有位置的字符
}
}
return new ArrayList<>(res);
}
/**
*
* @param visited 標(biāo)記被訪問(wèn)字符二維數(shù)組叭爱，大小和board一樣
* @param board 搜索的board
* @param x 當(dāng)前搜索的行號(hào)
* @param y 當(dāng)前搜索的列號(hào)
* @param strCur 已經(jīng)搜索到的結(jié)果
* @param trie 字典樹(shù)，存儲(chǔ)了所有需要查找的字符
*/
private void find(boolean[][] visited, char[][] board, int x, int y, String strCur,Trie trie) {
if (x<0||y<0 || x>=board.length || y>=board[0].length) return;//邊界判斷
if (visited[x][y]) return;//當(dāng)前位置是否被訪問(wèn)
strCur+=board[x][y];//沒(méi)有被訪問(wèn)開(kāi)始訪問(wèn)該位置的元素
if (!trie.startsWith(strCur))return;//字典樹(shù)中查找是否是前綴漱病，沒(méi)有前綴放棄查找
if (trie.search(strCur)) {//字典樹(shù)中查找是否存在strCur單詞买雾，找到了假如結(jié)果集中
res.add(strCur);
}
visited[x][y]=true;//標(biāo)記該位置已經(jīng)被訪問(wèn)
find(visited,board,x-1,y,strCur,trie);//遞歸當(dāng)前位置左邊的元素
find(visited,board,x+1,y,strCur,trie);//遞歸當(dāng)前位置右邊的元素
find(visited,board,x,y-1,strCur,trie);//遞歸當(dāng)前位置上邊的元素
find(visited,board,x,y+1,strCur,trie);//遞歸當(dāng)前位置下邊的元素
visited[x][y]=false;//移除標(biāo)記，繼續(xù)循環(huán)
}
}
29 位運(yùn)算
iShot2020-08-05下午11.45.18.png
1杨帽、x & 1 == 1 OR ==0 判斷奇數(shù)偶數(shù)(& 只有兩個(gè)同時(shí)為1結(jié)果才為1)
2漓穿、x=x&(x-1)清理最低位的1 如6&5=4
6---->1 1 0
5---->1 0 1
結(jié)果為1 0 0 --> 4
編寫(xiě)一個(gè)函數(shù)，輸入是一個(gè)無(wú)符號(hào)整數(shù)注盈，返回其二進(jìn)制表達(dá)式中數(shù)字位數(shù)為 ‘1’ 的個(gè)數(shù)
1 循環(huán)每次模2結(jié)果為1計(jì)數(shù)加一晃危，并將輸入數(shù)值除以2
while(target!=0){
if(target%2==1) count++;
target = target/2;
}
2 每次進(jìn)行x=x&(x-1)移除最低位的1，并count++,直到為0
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count++;
n = n & (n - 1);
}
return count;
}
給定一個(gè)整數(shù)老客，編寫(xiě)一個(gè)函數(shù)來(lái)判斷它是否是 2 的冪次方僚饭。
假如是2的冪次方，二進(jìn)制位只有一個(gè)1
public boolean isPowerOfTwo(int x) {
//數(shù)據(jù)范圍為-2147483648 ~ 2147483647[-2^31 ~ 2^31-1]
//用long存儲(chǔ)胧砰，避免只有所有都為1的情況-2147483648浪慌，再-1越界
long n = x;
return n!=0&&((n&(n-1))==0);
}
給定一個(gè)非負(fù)整數(shù) num。對(duì)于 0 ≤ i ≤ num 范圍中的每個(gè)數(shù)字 i 朴则，計(jì)算其二進(jìn)制數(shù)中的 1 的數(shù)目并將它們作為數(shù)組返回权纤。
1 遍歷每個(gè)數(shù)分別計(jì)算1的個(gè)數(shù)
2 x&(x-1) 去除x最低位的1，可以得到關(guān)系：x二進(jìn)制位1的個(gè)數(shù)等于x&(x-1)二進(jìn)制位1的個(gè)數(shù)+1乌妒，而且x&(x-1)的值小于x汹想，所有遞推即可 P(x)=P(x&(x?1))+1;
public class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for (int i = 1; i <= num; ++i)
ans[i] = ans[i & (i - 1)] + 1;
return ans;
}
}
30 N 皇后問(wèn)題的二進(jìn)制解法
public int totalNQueue(int n){
if (n<1) return -1;
_dfs(n,0,0,0,0);
return countNQueues;
}
private void _dfs(int n,int row,int cols,int pie,int na) {
if (row>=n){
countNQueues++;
return;
}
//如：第一行方了第3個(gè)位置
// cols 1--> 0 0 1 0
// pie 1--> 0 1 0 0
// na 1--> 0 0 0 1
//cols|pie|na --> 0 1 1 1
//~cols|pie|na --> 1 0 0 0 只有第一個(gè)位置可以放
int bits = (~(cols|pie|na))&((1<<n)-1);// 得到當(dāng)前所有空位
while (bits > 0) {
//如 bits 5 0000 ... 0101
// -5 1000 ... 0101
// -5反碼 1111 ... 1010（負(fù)數(shù)反碼 =除去最高位之外其他位取反
// -5補(bǔ)碼 1111 ... 1011（負(fù)數(shù)的補(bǔ)碼=反碼+1）
//計(jì)算機(jī)中負(fù)數(shù)的表示形式是以補(bǔ)碼表示
//int a a&(-a)表示取低位1
int bit = bits & -bits;//取得到最后（低位）一個(gè)1，需要放置的位置撤蚊，放置一個(gè)皇后 Q古掏，繼續(xù)遞歸遍歷
_dfs(n, row + 1, cols | bit, (pie | bit) << 1, (na | bit) >> 1);
// bits 5 --> 0000 ... 0101
// bits 5-1 --> 0000 ... 0100
//bits&(bits-1)--> 0000 ... 0100
bits = bits & bits-1;//移除最后(低位)一個(gè)1繼續(xù)遍歷其他可能情況
}
}
31 動(dòng)態(tài)規(guī)劃
理解:遞歸+記憶化------>遞推
狀態(tài)定義：op[n],dp[n],fib[n]
狀態(tài)轉(zhuǎn)移方程：op[n]=best_of(opt[n-1],opt[n-2],...)
最優(yōu)子結(jié)構(gòu)
DP VS 回溯 VS 貪心
回溯（遞歸）--》重復(fù)計(jì)算
貪心-----------》永遠(yuǎn)局部最優(yōu)
DP------------》記錄局部最優(yōu)子結(jié)構(gòu)/多種記錄值
- 斐波拉契
iShot2020-08-07上午12.27.33.png
iShot2020-08-07上午12.28.39.png
public int fblq(int n){
int[] F = new int[n+1];
F[0] = 0;
F[1] = 1;
for (int i = 2; i <= n; i++) {
F[i] = F[i-1] + F[i-2];
}
return F[n];
}
33 爬樓梯
假設(shè)你正在爬樓梯。需要 n 階你才能到達(dá)樓頂侦啸。
每次你可以爬 1 或 2 個(gè)臺(tái)階槽唾。你有多少種不同的方法可以爬到樓頂呢丧枪？
- 動(dòng)態(tài)規(guī)劃解法 定義f(k)表示爬到第k階樓梯有f(k)種不同方法，每次可以爬1或者2個(gè)臺(tái)階庞萍，所以爬到k階臺(tái)階的走法=爬到k-1階臺(tái)階的總數(shù)(再爬一步)+爬到k-2階樓梯臺(tái)階總數(shù)(再爬兩步)拧烦，即f(n)=f(n-1)+f(n-2)
class Solution {
public int climbStairs(int n) {
if(n<=1) return 1;
int rst[] = new int[n+1];
rst[0] = 1;
rst[1] = 1;
for(int i=2;i<=n;i++){
rst[i]=rst[i-1]+rst[i-2];
}
return rst[n];
}
}
34 三角形最小路徑和
給定一個(gè)三角形，找出自頂向下的最小路徑和钝计。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上恋博。
相鄰的結(jié)點(diǎn) 在這里指的是 下標(biāo) 與 上一層結(jié)點(diǎn)下標(biāo) 相同或者等于 上一層結(jié)點(diǎn)下標(biāo) + 1 的兩個(gè)結(jié)點(diǎn)。
- 遞歸方法 深度優(yōu)先搜索方法dfs(triangle,i,j)表示結(jié)點(diǎn)trangle[i][j]最小路徑和私恬，則
dfs(triangle,i,j)=min(dfs(triangle,i+1,j),dfs(triangle,i+1,j+1))+triangle[i][j]
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
return dfs(triangle, 0, 0);
}
private int dfs(List<List<Integer>> triangle, int i, int j) {
if (i == triangle.size()) {
return 0;
}
return Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
}
}
- 35 動(dòng)態(tài)規(guī)劃+空間優(yōu)化 定義DP狀態(tài)方程DP(i,j)表示從底部走到i,j結(jié)點(diǎn)最小和债沮，DP狀態(tài)轉(zhuǎn)移方程DP(i,j)=min(DP(i+1,j),DP(i+1,j+1))+triangle[i][j],由于每次只需要保存上一層DP狀態(tài)即可，所以只用以為數(shù)組保存DP結(jié)果即可
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n + 1];//存儲(chǔ)i+1行DP狀態(tài)值
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
//dp[i,j]=min(dp[i+1,j],dp[i+1][j+1])+triangle[i,j]
dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
35 乘積最大子數(shù)組
給你一個(gè)整數(shù)數(shù)組 nums 本鸣，請(qǐng)你找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組中至少包含一個(gè)數(shù)字）疫衩，并返回該子數(shù)組所對(duì)應(yīng)的乘積。
- 因?yàn)橛胸?fù)數(shù)荣德，所以需要記錄最大最小值兩個(gè)元素
DP狀態(tài)定義：dp[k][0|1] 選取表示第k個(gè)數(shù)字最大值和最小值
DP狀態(tài)轉(zhuǎn)移：
當(dāng)nums[i]大于0時(shí)->
最大值DP[i][0]=DP[i-1][0]nums[i];
最小值DP[i][1]=DP[i][1]nums[i];
當(dāng)nums[i]小于0時(shí)->
最大值DP[i][0]=DP[i-1][1]nums[i];
最小值DP[i][1]=DP[i][0]nums[i];
class Solution {
/**
* dp[k][2] 表示選擇第k個(gè)數(shù)的最大值和最小值隧土，因?yàn)橐胸?fù)數(shù)，所以需要保存兩個(gè)追
* @param nums
* @return
*/
public int maxProduct(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
//定義dp狀態(tài)命爬，dp[][0] 最大值
//定義dp狀態(tài)曹傀，dp[][1] 最小值
int[][] dp = new int[nums.length][2];
int rst = nums[0];
dp[0][0] = nums[0];
dp[0][1] = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] > 0) {
//第k個(gè)數(shù)值大于0
//最大值為num[i]*dp[i-1][0]
dp[i][0] = dp[i-1][0]*nums[i];
dp[i][0] = Math.max(dp[i][0],nums[i]);//取nums[i]本身和dp[i][0]最大值
//最小值為num[i]*dp[i-1][1]
dp[i][1] = dp[i-1][1]*nums[i];
dp[i][1] = Math.min(dp[i][1],nums[i]);
} else {
//第k個(gè)數(shù)值小于0
//最大值為num[i]*dp[i-1][1]
dp[i][0] = dp[i-1][1]*nums[i];
dp[i][0] = Math.max(dp[i][0],nums[i]);//取nums[i]本身和dp[i][0]最大值
//最小值為num[i]*dp[i-1][0]
dp[i][1] = dp[i-1][0]*nums[i];
dp[i][1] = Math.min(dp[i][1],nums[i]);
}
rst = Math.max(rst, dp[i][0]);
}
return rst;
}
}
36 最長(zhǎng)上升子序列
給定一個(gè)無(wú)序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度饲宛。
- 動(dòng)態(tài)規(guī)劃
public int lengthOfLIS(int[] nums) {
if (nums.length==0) return 0;
//狀態(tài)定義:dp[k]表示選取nums[k]時(shí)最長(zhǎng)子序列
int[] dp = new int[nums.length];
dp[0] = 1;
int lis = 1;//記錄最長(zhǎng)子序列長(zhǎng)度
for (int i = 1; i < nums.length; i++) {
int maxi = 1;//記錄包含nums[i]時(shí)最長(zhǎng)子序列長(zhǎng)度
for (int j = 0; j < i - 1; j++) {
//只有當(dāng)nums[i]>nums[j]時(shí)候才是遞增
if (nums[i] > nums[j] && dp[j]+1 > maxi) {
maxi = dp[j] + 1;
}
}
dp[i] = maxi;
if (lis < maxi) {
lis = maxi;
}
}
return lis;
}
- 另一種思路
/**
* 10 11 12 13 14 1 2 3 4 5 6
* --> 10 0 0 0 ...
* --> 10 11 0 0 ...
* ...
* -->10 11 12 13 14 0 0 0 ...
* -->1 11 12 13 14 0 0 ... 替換第一個(gè)比 1 大的數(shù)
* -->1 2 12 13 14 0 0 ... 替換第一個(gè)比 2 大的數(shù)
* -->1 2 3 13 14 0 0 ...
* -->1 2 3 4 14 0 0 ...
* -->1 2 3 4 5 0 0 0 ...
* -->1 2 3 4 5 6 ....
* @param nums
* @return
*/
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int len = 0;//記錄最長(zhǎng)子序列長(zhǎng)度
for (int k = 0; k < nums.length; k++) {
int left = 0;
int right = len;
print(dp);
while (left < right) {//二分查找找到第一個(gè)比nums[k]大的數(shù)
int mid = (left + right) / 2;
if (dp[mid] < nums[k]) {
left = mid + 1;
} else {
right = mid;
}
}
dp[left] = nums[k];//替換或者插入nums[k]到遞增隊(duì)列
if (right==len)
len++;
}
print(dp);
return len;
}
37 零錢(qián)兌換
給定不同面額的硬幣 coins 和一個(gè)總金額 amount皆愉。編寫(xiě)一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)。如果沒(méi)有任何一種硬幣組合能組成總金額艇抠，返回 -1.
原理：與爬樓梯原理一樣幕庐，爬到第k階樓梯方法dp[k]總數(shù)=爬到k-coins[0...n]中方法，取最小值值即可
/**
* 與爬樓梯一樣
* coins = [1, 2, 5], amount = 11
* 暴力法：最多可以去2個(gè)5元家淤，5個(gè)2元异剥，11個(gè)一元
* 遞歸調(diào)用（或者循環(huán)）選2個(gè)5元，0個(gè)2元絮重，1個(gè)一元冤寿，成功，
* 假如不成功則繼續(xù)選1一個(gè)五元青伤，剩余4督怜，選3個(gè)2元，成功狠角，如果不成功繼續(xù)遞歸
* @param coins
* @param amount
* @return
*/
public int coinChange(int[] coins, int amount) {
//DP狀態(tài)定義：dp[k]表示爬到k階樓梯最小值步數(shù)（在這里表示數(shù)值amount最小的組合方式）
int[] dp = new int[amount+1];
for (int i = 0; i < amount+1; i++) {
dp[i] = amount+1;//初始化号杠，方便取最小值
}
dp[0] = 0;//0元沒(méi)有方案
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j]<=i) {//保證數(shù)組不越界
//取最小值 DP狀態(tài)轉(zhuǎn)移方程
//dp[11] = min{dp[11-1],dp[11-2],dp[11-5]}+1
dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
38 編輯距離
給你兩個(gè)單詞 word1 和 word2，請(qǐng)你計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：
插入一個(gè)字符
刪除一個(gè)字符
替換一個(gè)字符
題目給定了兩個(gè)單詞姨蟋，設(shè)為 A 和 B屉凯，這樣我們就能夠六種操作方法。
注意：如果我們有單詞 A 和單詞 B：
對(duì)單詞 A 刪除一個(gè)字符和對(duì)單詞 B 插入一個(gè)字符是等價(jià)的眼溶。例如當(dāng)單詞 A 為 doge悠砚，單詞 B 為 dog 時(shí)，
我們既可以刪除單詞 A 的最后一個(gè)字符 e偷仿，得到相同的 dog哩簿，也可以在單詞 B 末尾添加一個(gè)字符 e宵蕉，
得到相同的doge酝静；
同理，對(duì)單詞 B 刪除一個(gè)字符和對(duì)單詞 A 插入一個(gè)字符也是等價(jià)的羡玛；
對(duì)單詞 A 替換一個(gè)字符和對(duì)單詞 B 替換一個(gè)字符是等價(jià)的别智。例如當(dāng)單詞 A 為 bat，單詞 B 為 cat 時(shí)稼稿，
我們修改單詞 A 的第一個(gè)字母 b -> c薄榛，和修改單詞 B 的第一個(gè)字母 c -> b 是等價(jià)的。
這樣以來(lái)让歼，本質(zhì)不同的操作實(shí)際上只有三種：
在單詞 A 中插入一個(gè)字符敞恋；
在單詞 B 中插入一個(gè)字符；
修改單詞 A 的一個(gè)字符谋右。
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
if (n * m==0) {
return n+m;
}
//DP狀態(tài)定義：DP[i][j]表示word1前i個(gè)字符和word2前j個(gè)字符匹配需要操作的最少步數(shù)
int[][] DP = new int[m + 1][n + 1];
//初始化邊緣值：表示word1前i個(gè)字符匹配word2前0個(gè)字符硬猫，刪除word1前i個(gè)字符即可
for (int i = 0; i < m + 1; i++) {
DP[i][0] = i;
}
//初始化邊緣值：表示word1前0個(gè)字符匹配word2前i個(gè)字符，插入word2前i個(gè)字符即可
for (int i = 0; i < n + 1; i++) {
DP[0][i] = i;
}
for (int i = 1; i < m + 1; i++) {
for (int j = 1; j < n + 1; j++) {
if (word1.charAt(i-1) == word2.charAt(j-1)) {//當(dāng)兩個(gè)字符相等改执，躺贏啸蜜，不要操作步數(shù)
DP[i][j] = DP[i - 1][j - 1];
} else {//不相等：可以有3中操作，對(duì)word1進(jìn)行刪除辈挂，插入衬横，替換
//DP[i][j]=DP[i-1][j]+1:表示刪除word1第i個(gè)字符刪除，
// 即word1[i]!=word2[j],刪除word[i]字符终蒂，等效于求解DP[i-1][j]+1(刪除word1第i個(gè)字符操作)
//DP[i][j]=DP[i][j-1]+1:word1刪除第1個(gè)字符等效于word2插入一個(gè)字符
//DP[i][j]=DP[i-1][j-1]+1:表示將word1第i個(gè)字符替換成word2第j個(gè)字符
DP[i][j] = Math.min(DP[i-1][j-1],Math.min(DP[i-1][j],DP[i][j-1]))+1;
}
}
}
return DP[m][n];
}
39 島嶼數(shù)量
給你一個(gè)由
'1'（陸地）和'0'（水）組成的的二維網(wǎng)格蜂林，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。
島嶼總是被水包圍拇泣，并且每座島嶼只能由水平方向或豎直方向上相鄰的陸地連接形成悉尾。
此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍挫酿。
- 暴力染色法思路：遍歷二維網(wǎng)格构眯，當(dāng)發(fā)現(xiàn)陸地‘1’的時(shí)候島嶼數(shù)+1，并遞歸上下左右結(jié)點(diǎn)早龟，將為陸地結(jié)點(diǎn)染色為水‘0’惫霸。
int numIslands = 0;
int row;
int col;
public int numIslands(char[][] grid) {
if (grid.length==0 || grid[0].length==0) {
return 0;
}
row = grid.length;
col = grid[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
numIslands++;
ranse(grid,i,j);
}
}
}
return numIslands;
}
private void ranse(char[][] grid,int i,int j){
if (i < row && j < col && j >= 0 && i >= 0 && grid[i][j]=='1') {
grid[i][j] = '0';//開(kāi)始染色
}else {
return;//數(shù)組越界或者為水'0'退出遞推
}
//遞歸遍歷上下左右結(jié)點(diǎn)
ranse(grid,i,j+1);
ranse(grid,i,j-1);
ranse(grid,i+1,j);
ranse(grid,i-1,j);
}
- 查并集
class UnionFind {
int[] roots;//查并集
int[] ranks;//查并集的層次（樹(shù)的深度）
int count;
public UnionFind(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
roots = new int[row * col];
ranks = new int[row * col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
roots[i*col+j] = i*col+j;//初始化查并集猫缭，各自為營(yíng)（自己指向自己）
ranks[i*col+j] = 0;//初始化層次為0
count++;
}
}
}
}
/**
* 遞歸查找自己的老大（老大的特點(diǎn)自己指向自己）
* @param i
* @return
*/
public int find(int i) {
if (roots[i] != i) {
return find(roots[i]);
}else {
return roots[i];
}
}
/**
* 合并結(jié)點(diǎn)p和q（p的老大是q老大的parent或者q的老大是p老大的parent）
* @param p
* @param q
*/
public void union(int p, int q) {
//查找各自的老大parent
int rootP = find(p);
int rootq = find(q);
if (rootP == rootq) {
return;
}
//根據(jù)深度來(lái)決定誰(shuí)來(lái)做老大
if (ranks[rootP] < ranks[rootq]) {
roots[rootP] = rootq;
} else if (ranks[rootP] > ranks[rootq]) {
roots[rootq] = rootP;
} else {
roots[rootP] = rootq;
ranks[rootq]++;
}
--count;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int row= grid.length;
int col = grid[0].length;
UnionFind unionFind = new UnionFind(grid);
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
grid[i][j] = '0';
//將上下左右的結(jié)點(diǎn)指向自己，作為一個(gè)島嶼
if (i - 1 >= 0 && grid[i - 1][j] == '1') {
unionFind.union(i*col+j,(i-1)*col+j);
}
if (i + 1 < row && grid[i + 1][j] == '1') {
unionFind.union(i*col+j,(i+1)*col+j);
}
if (j + 1 < col && grid[i][j + 1] == '1') {
unionFind.union(i * col + j, i* col + j+1);
}
if (j - 1 >=0 && grid[i][j - 1] == '1') {
unionFind.union(i * col + j, i* col + j-1);
}
}
}
}
return unionFind.count;
}
40 LRU&LFU算法
LRU Least Resently Used
LFU Least Frequrently Used
-LRU Cache將最近使用的放到鏈表前段壹店，由于空間有限猜丹，假如隊(duì)列已滿，將隊(duì)尾元素移除硅卢，數(shù)據(jù)結(jié)構(gòu)使用雙向鏈表實(shí)現(xiàn)
iShot2020-08-16上午12.06.43.png
iShot2020-08-16上午12.07.24.png
-
LFU Cache 將訪問(wèn)頻次最多的元素放到隊(duì)列頭部射窒，假如隊(duì)列滿了，訪問(wèn)的元素沒(méi)有空間存儲(chǔ)将塑，將隊(duì)尾元素移除脉顿，將要訪問(wèn)的元素放到隊(duì)列里(放置到哪里按照頻次優(yōu)先次序排列)
iShot2020-08-16上午12.07.51.png
41 布隆過(guò)濾器 Bloom Filter
一個(gè)很長(zhǎng)的二進(jìn)制向量和一個(gè)映射函數(shù)
布隆過(guò)濾器可以用于檢索一個(gè)元素是否存在一個(gè)集合中
優(yōu)點(diǎn)：空間效率和查詢時(shí)間遠(yuǎn)遠(yuǎn)超過(guò)一般的算法
缺點(diǎn)：有一定的誤識(shí)別率（存在的時(shí)候可能誤識(shí)別，不存在的時(shí)候是100%準(zhǔn)確）和刪除困難
iShot2020-08-16下午11.47.39.png
iShot2020-08-16下午11.51.04.png
- 附帶自定義LRU Cache
public class LRUCache {
class DLinkedNode {
int key;//hashcode
int value;//值
DLinkedNode prev;//前序結(jié)點(diǎn)
DLinkedNode next;//后續(xù)結(jié)點(diǎn)
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();//key對(duì)應(yīng)的Node結(jié)點(diǎn)映射
private int size;//當(dāng)前cache元素的個(gè)數(shù)
private int capacity;//容量
private DLinkedNode head, tail;//鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用偽頭部和偽尾部節(jié)點(diǎn)
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通過(guò)哈希表定位，再移到頭部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在押框，創(chuàng)建一個(gè)新的節(jié)點(diǎn)
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加進(jìn)哈希表
cache.put(key, newNode);
// 添加至雙向鏈表的頭部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，刪除雙向鏈表的尾部節(jié)點(diǎn)
DLinkedNode tail = removeTail();
// 刪除哈希表中對(duì)應(yīng)的項(xiàng)
cache.remove(tail.key);
--size;
}
}
else {
// 如果 key 存在蔽莱，先通過(guò)哈希表定位，再修改 value戚长，并移到頭部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
