亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

二分查找邊界問題

查找最接近的數

二分法避免死循環

不存在會返回比目標數字大的，因為判斷當前mid位置的數字<num時，最后一次left = mid + 1，判斷當前mide位置的數字>num時，right = mide，所以是大于目標數字。

最靠右的：

function?binarySearch(num,?nums)?{
????let?left?=?0,?right?=?nums.length?-?1;
????while(true)?{
????????if?(left?==?right)?{
????????return?left;
????????}
????????let?mid?=?left?+?Math.floor((right?-?left)?/?2);
????????if?(nums[mid]?<?num)?{
????????????left?=?mid?+?1;
????????}?else?if?(nums[mid]?==?num?&&?nums[mid?+?1]?==?num)?{
????????????left?=?mid+1;
????????}?else?{
????????????right?=?mid;
????????}
????}
}

• 1、效率；
• 2、公平

class?LRUCache?{
????private?int?capacity;
????private?int?n;
????private?DoubleLinkedList?pHead,pTail;
????private?DoubleLinkedList[]?hash;

????private?class?DoubleLinkedList{
????????int?key,?val;
????????DoubleLinkedList?prev,?next;

????????public?DoubleLinkedList(int?key,?int?val){
????????????this.key?=?key;
????????????this.val?=?val;
????????????this.prev?=?null;
????????????this.next?=?null;
????????}
????}

????public?LRUCache(int?capacity)?{
????????this.capacity?=?capacity;
????????this.n?=?0;
????????hash?=?new?DoubleLinkedList[10001];
????????pHead?=?new?DoubleLinkedList(-1,0);
????????pTail?=?new?DoubleLinkedList(-2,0);
????????pHead.next?=?pTail;
????????pTail.prev?=?pHead;
????}
????
????public?int?get(int?key)?{
????????DoubleLinkedList?node?=?hash[key];
????????if(node==null){
????????????return?-1;
????????}
????????moveFront(node);
????????return?node.val;
????}
????
????public?void?put(int?key,?int?value)?{
????????DoubleLinkedList?node?=?hash[key];
????????if(node?==?null?&&?n?<?capacity){
????????????node?=?new?DoubleLinkedList(key,value);
????????????hash[key]?=?node;
????????????addFront(node);
????????????n++;
????????????return;
????????}
????????if(node?==null?&&?n==capacity){
????????????node?=?pTail.prev;
????????????hash[node.key]?=?null;
????????????hash[key]?=?node;
????????}
????????node.key?=?key;
????????node.val?=?value;
????????moveFront(node);
????}

????private?void?moveFront(DoubleLinkedList?node){
????????node.prev.next?=?node.next;
????????node.next.prev?=?node.prev;
????????addFront(node);
????}

????private?void?addFront(DoubleLinkedList?node){
????????node.prev?=?pHead;
????????node.next?=?pHead.next;
????????pHead.next.prev?=?node;
????????pHead.next?=?node;
????}
}

/**
?*?Your?LRUCache?object?will?be?instantiated?and?called?as?such:
?*?LRUCache?obj?=?new?LRUCache(capacity);
?*?int?param_1?=?obj.get(key);
?*?obj.put(key,value);
?*/

/**
?*?Definition?for?singly-linked?list.
?*?public?class?ListNode?{
?*?????int?val;
?*?????ListNode?next;
?*?????ListNode()?{}
?*?????ListNode(int?val)?{?this.val?=?val;?}
?*?????ListNode(int?val,?ListNode?next)?{?this.val?=?val;?this.next?=?next;?}
?*?}
?*/
class?Solution?{
????public?ListNode?reverseKGroup(ListNode?head,?int?k)?{
????????int?count?=?0;
????????ListNode?current?=?head;
????????ListNode?previous?=?null;
????????ListNode?newCurrent??=?current;
????????ListNode?leftBreak?=?null,reverseTail?=?head,?reverseHead?=?null;
????????while(true){
????????????count?++;
????????????if(count?==?k){
????????????????reverseHead?=?current;
????????????????current?=?reverseTail;
????????????????previous?=?null;
????????????????while?(previous?!=?reverseHead){
????????????????????newCurrent?=?current.next;
????????????????????current.next?=?previous;
????????????????????previous?=?current;
????????????????????current?=?newCurrent;
????????????????}
????????????????if(leftBreak?==?null){
????????????????????head?=?reverseHead;
????????????????}else{
????????????????????leftBreak.next?=?reverseHead;
????????????????}
????????????????leftBreak?=?reverseTail;
????????????????reverseTail.next?=?current;
????????????????reverseTail?=?current;
????????????????count?=?0;
????????????}else{
????????????????current?=?current.next;
????????????}
????????????if(current?==?null){
????????????????break;
????????????}

????????}
????????return?head;
????}
}

1. 二分

2. 2.考點：