第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

206. 反轉(zhuǎn)鏈表

class Solution {

????public:

????????ListNode* reverseList(ListNode* head) {

????????????ListNode* prev = nullptr;

????????????ListNode* current = head;

????????????while(current != nullptr){

????????????????ListNode* tempNext = current->next;

????????????????current->next = prev;

????????????????prev = current;

????????????????current = tempNext;

????????????}

????????????return prev;

????????}

};

92. 反轉(zhuǎn)鏈表 II

class Solution {

????public ListNode reverseBetween(ListNode head, int left, int right) {

????????int count = 1;

????????ListNode current = head;

????????ListNode previous = null;

????????ListNode tempNext = null;

????????ListNode leftBreak = null;

????????ListNode reverseTail = null;

????????while(count <= right){

????????????tempNext = current.next;

????????????if(left == count){

????????????????leftBreak = previous;

????????????????reverseTail = current;

????????????} else if(left < count){

????????????????current.next = previous;

????????????}

????????????previous = current;

????????????current = tempNext;

????????????count++;

????????}

????????reverseTail.next = current;

????????if(leftBreak != null){

????????????leftBreak.next = previous;

?????????} else {

????????????return previous;

????????}

????????return head;

????}

}

二分查找邊界問題

查找最接近的數(shù)

二分法避免死循環(huán)

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

最靠右的：

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.考點：