LEETCODE学习记录(链表+数学+字符串+图)

# 7.链表(Linked List)
## 7.1 环形链表
### `141. Linked List Cycle`
 给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
```
 示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2:
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
         return funcDulPointer(head);
    }
    //方法一：缓存cache法
    bool funcCache(ListNode *head)
    {
         set<ListNode*> cache;
         while(head)
         {
             if(cache.find(head)!=cache.end()) return true;
             else{
                 cache.insert(head);
             }
             head = head->next;
         }
         return false;
    }
    //方法二：将所有访问过的node的val都设置为一个新的值，以此来判断是否有环。
    //具体实现略过，因为该方法不推荐！！！

//方法三：快慢指针法,有环的话，快指针理论上一定能追上慢指针
    bool funcDulPointer(ListNode* head)
    {
         if(head==NULL || head->next == NULL) return false;
        
        ListNode* fast = head->next->next;
        ListNode* slow = head->next;
        
        //  //这种修改后的写法也比较简洁
        //  while(fast)
        //  {   //判断
        //      if(fast == slow) return true;
        //      //移动快指针
        //      fast = fast->next != NULL?fast->next->next:NULL;             
        //      //移动慢指针
        //      slow = slow->next;
        //  }
        // return false;
        
        //下面写法比较简洁

while(fast!=slow)
        {
            if(fast== NULL || fast->next == NULL || fast->next->next == NULL) return false;
            fast = fast->next->next;
            slow = slow->next;
        }
         return true;
    }
};
```
### `142. Linked List Cycle II`
- 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

- 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

- 说明：不允许修改给定的链表。
```
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        return func3(head);
    }
    //缓存法，效率不高
    ListNode *func(ListNode *head)
    {  
        set<ListNode*> cache;
        while(head)
        {
            if(cache.count(head)) return head;
            cache.insert(head);
            head = head->next;
        }
        return NULL;
    }

//双指针法，高效解法！
    ListNode* func2(ListNode* head)
    {
        /*快慢双指针，先看是否能相遇，如不能，返回NULL。
        如果能够相遇，则可以推导出：如果此时，一个指针指向head，另一个不变。速度均改为1，继续移动，将会在入环点再次相遇。*/
        if(head == NULL || head->next == NULL) return NULL;
        //快慢指针，一定要保证fast指针走的路程是slow的2倍
        ListNode* fast = head->next->next;
        ListNode* slow = head->next;
        //先判断是否有环
        while(fast!=slow)
        {
            if(fast == NULL || fast->next == NULL) return NULL;
            fast = fast->next->next;
            slow = slow->next;
        }
        //到此说明有环
        slow = head;
        while(fast!=slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
    //与上面的思想一样，只是换了下写法，双指针
    ListNode* func3(ListNode* head)
    {
        if(head == NULL || head->next == NULL) return NULL;
        //快慢指针，一定要保证fast指针走的路程是slow的2倍
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast)
        {
            fast = fast->next ? fast->next->next:NULL;
            slow = slow->next;
            if(fast == slow)
            {
               //到此说明有环
                slow = head;
                while(fast!=slow)
                {
                    fast = fast->next;
                    slow = slow->next;
                }
                return fast;        
            }
        }
        return NULL;
    }
};
```
## 7.2 相交链表
`160. Intersection of Two Linked Lists`
- 编写一个程序，找到两个单链表相交的起始节点。
- 注意:
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
```
测试样例 略
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
         return func(headA,headB); 
    }
    ListNode* func(ListNode *headA,ListNode* headB)
    {
        if(headA == NULL || headB == NULL) return NULL;
        ListNode* pA = headA;
        ListNode* pB = headB;

//常规写法,好理解
        //while(pA!=NULL || pB!=NULL)
        //{
        //    if(pA == pB) return pA;
        //    pA = pA==NULL? headB:pA->next;
        //    pB = pB==NULL? headA:pB->next;
        //}
        //return NULL;

//写法二:简洁一点
        // while(1)
        // {
        //     if(pA == pB) return pA;
        //     pA = pA==NULL? headB:pA->next;
        //     pB = pB==NULL? headA:pB->next;
        // }
        
        //写法三:最简洁
        while(pA != pB)
        {
            pA = pA==NULL? headB:pA->next;
            pB = pB==NULL? headA:pB->next;
        }
        return pA;
    }
};
```
## 7.3 删除排序链表中的重复元素
###`83. Remove Duplicates from Sorted List`
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。这两道题可以结合着`删除排序数组中的重复项 I & II`一起比较学习.
```
输入: 1->1->2->3->3
输出: 1->2->3
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
         return iteration(head);
    }
    //法一：迭代
    ListNode* iteration(ListNode* head)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode* curr = head,*p;

//其中一种写法  
        // while(curr && curr->next)
        // {
        //     p = curr;
        //     while(p && p->next && p->val == p->next->val) p = p->next;
        //     curr->next = p->next;
        //     curr = curr->next;
        // }

//另一种更简洁的写法
        p = head;
        while(p->next)
        {
            if(p->val == p->next->val) p->next = p->next->next;
            else p = p->next;
        }

return head;
    }
    //法二：递归
    ListNode* recursion(ListNode* head)
    {
        if(head == NULL || head->next == NULL) return head;
        if(head->val == head->next->val) head = recursion(head->next);
        else head->next = recursion(head->next);
        return head;
    }
};
```
### `82. Remove Duplicates from Sorted List II`
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
```
输入: 1->2->3->3->4->4->5
输出: 1->2->5
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
          return iterateBrief(head);
    }

ListNode* iteration(ListNode* head)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode *newhead = NULL,*curr = head,*p = NULL;
        while(curr)
        {    
             //curr要么是最后一个，要么和后面的不一样
             if(curr->next == NULL)
             {
                if(newhead == NULL){                  
                    newhead = curr; 
                    p = newhead;
                }
                else{
                    p->next = curr;
                    p = p->next;
                }
                break;
             }
             if(curr && curr->next && curr->val==curr->next->val){
                    while(curr && curr->next && curr->val == curr->next->val) curr = curr->next;
                    curr = curr->next;
             }
             else{
                 if(newhead == NULL){                  
                        newhead = curr; 
                        p = newhead;
                 }
                 else{
                        p->next = curr;
                        p = p->next; 
                 }
                 curr = curr->next;
                 p->next = NULL;
             }
        }
        return newhead;
    }
   
    //精简版
    ListNode* iterateBrief(ListNode* head)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode *curr = head,*p = NULL;
        head = NULL; //后来知道了可以使用傀儡头节点,就不会这么麻烦了
        while(curr && curr->next)
        {    
             //跨过所有重复的节点
             if(curr->val==curr->next->val){
                while(curr->next && curr->val == curr->next->val) curr = curr->next;
                curr = curr->next;
             }
             else{
                 //初始化新的根节点
                 if(head == NULL){                  
                        head = curr; 
                        p = head;
                 }
                 else{  //连接符合要求的节点
                        p->next = curr;
                        p = p->next; 
                 }
                 curr = curr->next;
                 //有可能当前的p就是新的链表的最后一个节点，因此必须清除其后继节点
                 p->next = NULL;
             }     
        }
        //处理最后一个节点
        if(head == NULL) head = curr;
        else p->next = curr;

return head;
    }

//这个解法不对，这是上一个题的:重复的只保留一个，而本题对于重复的一个都不允许保留
    ListNode* iterateBrief2(ListNode* head)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode* curr = head,*post = head;
        while(curr && curr->next)
        {
            post = curr->next;
            if(curr->val == post->val) curr->next = post->next;
            else curr = post;
        }
        return head;
    }
};
```
## 7.4 合并有序链表
### `21. Merge Two Sorted Lists`
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
```
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
          return merge(l1,l2);        
    }
    ListNode* iterate(ListNode* l1,ListNode* l2)
    {
        if(l1 == NULL && l2 == NULL) return NULL;
        if(l1 == NULL && l2) return l2;
        if(l2 == NULL && l1) return l1;
        ListNode* p;
        ListNode dummy(0);// = ListNode(0); //两种初始化方式
        //考虑定义傀儡节点dummy,其后继节点为头节点，避免初始化头节点
        p = &dummy;
        while(l1 || l2)
        {
            if(l1 == NULL || l2 == NULL)
            {
                p->next = l2 ? l2:l1;
                break; 
                //return dummy.next;
            }
            if(l1->val < l2->val) 
            {
                p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next; 
        }
        return dummy.next;
    }
    ListNode* merge(ListNode* la,ListNode* lb)
    {
         if(!la) return lb;
         if(!lb) return la;
         ListNode dummy(0);
         ListNode* p = &dummy;
        
        //迭代
        //  while(la && lb)
        //  {
        //      if(la->val > lb->val){
        //          p->next = lb;
        //          lb = lb->next;
        //      }else{
        //          p->next = la;
        //          la = la->next;
        //      }
        //      p = p->next;
        //  }
        //  p->next = la?la:lb;
        
        //递归
        if(la->val < lb->val){
            p->next = la;
            p = p->next;
            la = la->next;
        }
        else{
            p->next = lb;
            p = p->next;
            lb = lb->next;
        }
        p->next = merge(la,lb);
         
        return dummy.next;
    }
};
```
双向链表：
```
ListNode* merge(ListNode* la,ListNode* lb)
    {
        if(!la) return lb;
        if(!lb) return la;
        ListNode dummy(0);
        ListNode* p = &dummy;
        //p->pre = NULL;
        //迭代
         while(la && lb)
        {
            if(la->val > lb->val){
                p->next = lb;
                lb->pre = p;
                lb = lb->next;
            }else
            {
                p->next = la;
                la->pre = p;
                la = la->next;
            }
            p = p->next;
        }
        //p->next = la?la:lb;
        if(la)
        {
            p->next = la;
            la->pre = p;
        }
        else if(lb)
        {
            p->next = lb;
            lb->pre;
        }
        dummy.next->pre = NULL;
        return dummy.next;
    }
```
### `23. Merge k Sorted Lists`
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
```
输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class MyHeap{
public:
     MyHeap(int k = 20){
         heap.reserve(k);
     }
     ~MyHeap()
     {
         //cout<<"~"<<endl;
     }
     //插入,插入至末尾，由下向上shiftup
     void insert(ListNode* node)
     {
        heap.emplace_back(node); //不同于push_back(),emplace_back()不是拷贝插入，而是引用插入
        int ch = heap.size() - 1;
        while(ch > 0)
        {
            int pa = (ch-1)/2;
            if(heap[pa]->val > heap[ch]->val){
                std::swap(heap[pa],heap[ch]);
                // ListNode* t = heap[pa];
                // heap[pa] = heap[ch];
                // heap[ch] = t;
            }else break;
            ch = pa;
        }
     }
     //删除，首尾交换后，删除尾部，由上至下shiftdown调整
     void pop(){
          if(heap.empty()) return;
          std::swap(heap[0],heap[heap.size()-1]);
          heap.pop_back();
          int len = heap.size();
          int pa = 0,ch1 = 1,ch2 = 2;
          while(ch1 <= len-1 || ch2 <= len-1)
          {
              //选择较小的“子节点”，注意有可能只有一个孩子
              int minch = 0;
              if(ch1<=len-1) minch = ch1;
              if(ch2<=len-1 && heap[ch2]->val<heap[ch1]->val) minch = ch2;
              //很容易写成heap[pa]>heap[minch],除非重载运算符，否则这样逻辑错误
              if(heap[pa]->val > heap[minch]->val){  
                  swap(heap[pa],heap[minch]);
              }
              else break;
              //向下移动
              pa = minch;
              ch1 = 2*pa + 1;
              ch2 = 2*pa + 2;
          }
     }
     //访问
     ListNode *top()
     {
        if(heap.empty()) return NULL;
        return heap[0];
     }
     //是否为空
     bool empty(){
         return heap.empty();
     }
     //显示所有元素
     void show(){
         vector<ListNode*>::iterator iter;
         for(iter = heap.begin();iter!=heap.end();++iter)
            std::cout<<(*iter)->val<<" ";
         std::cout<<endl;
     }
private:
     vector<ListNode*> heap;
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
           // return iterate1(lists);
           //return merge(lists,0,lists.size()-1);
           return mergeByHeap(lists);
    }
    //方法一：直接迭代,效率极低！！！500~700ms
    ListNode* iterate1(vector<ListNode*> &lists)
    {
        if(lists.empty()) return NULL;
        int len = lists.size();
        ListNode dummy(INT_MAX);
        ListNode* pre = &dummy;
        int nullcnt = 0;
        int a = INT_MAX;
        int idx = 0;
        while(nullcnt<len)
        {
            nullcnt = 0;
            for(int i = 0;i<len;i++)
            {
               if(lists[i] != NULL)
               {   
                   if(lists[i]->val <= a)
                   {
                       a = lists[i]->val;
                       idx = i;
                   }
               }
               else nullcnt++;
            }
            //p指向此时最小的节点
            a =INT_MAX;
            pre->next = lists[idx];
            //不为空说明还可能存在未访问的节点
            if(lists[idx]!=NULL)
            {
                lists[idx] = lists[idx]->next;
                pre = pre->next;
                pre->next = NULL;
            }
        }
        return dummy.next;
    }

//方法二：分治法，两两合并，效率提高十倍以上，24ms
    ListNode* merge(vector<ListNode*> &lists,int left,int right)
    {
        if(lists.empty()) return NULL;
        if(left == right) return lists[left];
        int mid = left + (right - left)/2;
        
        //recursion
        ListNode *l1 = merge(lists,left,mid);
        ListNode *l2 = merge(lists,mid+1,right);
        
        //merge two lists
        if(l1 == NULL && l2 == NULL) return NULL;
        if(l1 == NULL && l2) return l2;
        if(l2 == NULL && l1) return l1;
        ListNode* p;
        ListNode dummy(0);// = ListNode(0); //两种初始化方式
        
        //考虑定义傀儡节点dummy,其后继节点为头节点，避免初始化头节点
        p = &dummy;
        while(l1 || l2)
         {
             if(l1==NULL || !l2) {
                 p->next = l2 ? l2:l1;
                 break;
                 //return dummy.next;
             }
             if(l1->val < l2->val) {
                    p->next = l1;
                    l1 = l1->next;
                }else{
                    p->next = l2;
                    l2 = l2->next;
                }
                p = p->next; 
        }
        return dummy.next;
    }
    //方法三：最小堆(或者优先队列)，简单并且效率很高，28ms
    ListNode* mergeByHeap(vector<ListNode*> &lists)
    {
        if(lists.empty()) return NULL;
        ListNode dummy(0);
        ListNode* p;
        MyHeap mheap;
        //入堆，为优先队列，与入堆的顺序无关
        for(int i = 0;i<lists.size();++i)
        {
            p = lists[i];
            while(p){
                mheap.insert(p);
                p = p->next;
            }
        }
        //mheap.show();
        //出队列即可
        p = &dummy;
        while(p)
        {
            p->next = mheap.top();
            mheap.pop();
            p = p->next;
        }
        return dummy.next;
    }
};
```
## 7.5 反转链表
### `206. Reverse Linked List`
反转一个单链表。
```
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return iterate(head);
        // return recursion(head);
    }
private:
    //递归
    ListNode* recursion(ListNode *head)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode *p = recursion(head->next);
        //此时head->next处于最后位置,接上原来的head即可
        head->next->next = head;
        head->next = NULL;
        return p;
    }
    //迭代
    ListNode* iterate(ListNode *head)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode dummy(0);
        dummy.next = head;
        ListNode *p = &dummy;
        ListNode *curr = head;
        //p,curr本身实际上没有变过,p为傀儡头节点,curr就是最后的链表尾节点,变化的一直是其next指针
        ListNode* n == NULL；
        while(curr->next)
        {   //"首尾连接大法!!!", 头插法
            n = curr->next;
            curr->next = n->next;
            n->next = p->next;
            p->next = n;
        }
        return dummy.next;
    }
};
```
双向链表：
```
//迭代
ListNode* iterate(ListNode *head)
{
    if(head == NULL || head->next == NULL) return head;
    ListNode dummy(0);
    dummy.next = head;
    ListNode *p = &dummy;
    ListNode *curr = head;
    //p,curr本身实际上没有变过,p为傀儡头节点,curr就是最后的链表尾节点,变化的一直是其next指针
    while(curr->next)
    {   //"首尾连接大法!!!"
        ListNode *n = curr->next;
        curr->next = n->next;
        n->next->pre = curr;

n->next = p->next;
        p->next->pre = n;
        
        p->next = n;
        n->pre = p;
    }
    dummy.next->pre = NULL;
    return dummy.next;
}
    
```
### `92. Reverse Linked List II`
- 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
- 说明:
1 ≤ m ≤ n ≤ 链表长度。
```
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
          if(!head) return head;
          ListNode dummy(0);
          dummy.next = head;
          //prenode of pm
          ListNode* pre = &dummy;
          for(int i = 1;i<m;i++)
          {
              pre = pre->next;
          }
          //pm points to m postion
          ListNode* pm = pre->next;
          ListNode* p;
        
          for(int i = m;i<n;i++)
          {
             //move to next postion
             p = pm->next;
             //back edge
             pm->next = p->next;
             //add p to the reversed lists
             p->next = pre->next;   
             //front edge
             pre->next = p;          
          }
          return dummy.next;
    }
};
```
### `25. Reverse Nodes in k-Group`
- 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

- k 是一个正整数，它的值小于或等于链表的长度。

- 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
- 说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
```
示例：

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
```

```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
            return func2(head,k);
    }

ListNode* func1(ListNode* head,int k){
        if(k<2 || head==NULL || head->next == NULL) return head;
        ListNode dummy = ListNode(0);
        ListNode* prev = &dummy;
        dummy.next = head;
        //pointers of [start,end]
        ListNode* pstart = head,*pend = prev,*p=NULL;
        while(1)
        {
            for(int i = 0;i<k;i++)
            {
                pend = pend->next;
                //The number of nodes is not a multiple of k,then the left-out nodes remain as it as
                if(!pend) return dummy.next;
            }
            //reverse nodes
            while(p!=pend)
            //for(int i = 0;i<k-1;i++)
            {
                p = pstart->next;
                pstart->next = p->next;
                p->next = prev->next;
                prev->next = p;    
            }
            //prepare for the next reversed group
            pend = pstart;
            prev = pstart;
            pstart = pstart->next;
        }
        return dummy.next;
    }

ListNode* func2(ListNode* head,int k){
        if(k<2 || head==NULL || head->next == NULL) return head;
        ListNode dummy = ListNode(0);
        ListNode* prev = &dummy;
        dummy.next = head;
        //pointers of [start,end]
        ListNode* pstart = head,*pend = prev,*p=NULL;
        while(pend)
        {
            for(int i = 0;i<k;i++)
            {
                if(pend) pend = pend->next;
                //The number of nodes is not a multiple of k,then the left-out nodes remain as it as
                //if(!pend) return dummy.next;
            }
            if(pend)
            {
                //reverse nodes
                while(p!=pend)
                //for(int i = 0;i<k-1;i++)
                {
                    p = pstart->next;
                    pstart->next = p->next;
                    p->next = prev->next;
                    prev->next = p;    
                }
                //prepare for the next reversed group
                pend = pstart;
                prev = pstart;
                pstart = pstart->next;
            }
        }
        return dummy.next;
    }
};
```
### `24. Swap Nodes in Pairs`
- 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

- 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

- 显然,本题就是上一题k=2的特殊情况,不过代码可以更简单一点.
```
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        return func2(head);
    }
    //iteration
    ListNode* func1(ListNode* head)
    {
        if(!head || head->next == NULL) return head;
        ListNode dummy(0);
        ListNode* prev = &dummy;
        prev->next = head;
        ListNode *curr = head,*p = curr->next;
        while(curr && curr->next)
        {
            p = curr->next;
            //reverse the nodes
            curr->next = p->next;
            p->next = prev->next;
            prev->next = p;
            //move to next pairs
            prev = curr;
            curr = curr->next;
        }
        return dummy.next;
    }

//recursion
    ListNode* func2(ListNode* head)
    {
         if(!head || head->next == NULL) return head;
         ListNode* nxt = head->next;
         head->next = func1(nxt->next);
         nxt->next = head;
         return nxt;
    }
};
```
## 7.6 排序链表
### `148. Sort List`
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。链表归并排序!
```
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4

示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
      return mergeSort(head);
    }
    ListNode* mergeSort(ListNode* head){
        if(!head || !head->next) return head;
        ListNode dummy(0);
        dummy.next = head;
        //pointer p to construct the sorted list
        ListNode *p = &dummy;
        //pointers for merge sort
        ListNode *curr = head;
        ListNode *left = NULL,*right = NULL;
        //total nodes number of every group
        int num = 1;
        //length of the list
        int len = 0;
        left = head;
        while(left){
            left = left->next;
            len++;
        }
        //sorting
        while(num<len)
        {
            while(curr)
            {
                left = curr;
                right = cut(curr,num);
                curr = cut(right,num);
        
                p->next = merge(left,right);
                while(p->next) p = p->next;
            }
            //for the next merge sort
            num*=2;
            p = &dummy; 
            curr = p->next;
        }
         return dummy.next;
    }

private:
    ListNode* cut(ListNode* head,int num)
    {
        if(!head) return head;
        int i = 1;
        ListNode* p = head;
        ListNode* nxt;
        while(i<num && p)
        {
            p = p->next;
            i++;
        }
        if(!p) return NULL;
        nxt = p->next;
        p->next = NULL;
        return nxt;
    }

ListNode* merge(ListNode* la,ListNode* lb)
    {
        if(!la) return lb;
        if(!lb) return la;
        ListNode dummy(0);
        ListNode* p = &dummy;
    
        //iteration
        while(la && lb)
        {
            if(la->val > lb->val)
            {
                p->next = lb;
                lb = lb->next;
            }
            else
            {
                p->next = la;
                la = la->next;
            }
            p = p->next;
        }
        p->next = la?la:lb;
        
        //recursion
        // if(la->val < lb->val){
        //     p->next = la;
        //     la = la->next;
        //     p = p->next;
        // }
        // else{
        //     p->next = lb;
        //     lb = lb->next;
        //     p = p->next;
        // }
        // p->next = merge(la,lb);

return dummy.next;
    }
};
```
### `147. Insertion Sort List`
 - 对链表进行插入排序。
 - 插入排序算法：
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可 以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
```
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
          return insertionSort(head);
    }

ListNode *insertionSort(ListNode* head){
        if(!head || head->next == NULL) return head;
        ListNode dummy = ListNode(0);
        //pointers q to construct the sorted list
        ListNode *curr = head,*q = NULL;
        while(curr)
        {
            q = &dummy;
            while(q->next && q->next->val < curr->val) q = q->next;
            //insertion
            ListNode *nxt = curr->next;
            curr->next = q->next;
            q->next = curr;
            curr = nxt;
        }
        return dummy.next;
    }
};
```
## 7.7 旋转链表
`48.rotate list`
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
```
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        return rotate(head,k);
    }
private:
    ListNode* rotate(ListNode* head,int k)
    {
       if(!head || head->next == NULL) return head;
       ListNode dummy(0);
       dummy.next = head;
       
       //因为我们需要得到最后一个节点，所以从1开始计数
       int len = 1; 
       ListNode *p = head;
       while(p->next){
           p = p->next;
           len++;
       }
       p->next = head;//构建循环链表

int step = len - k%len;
       p = &dummy;
       while(step)
       {
           p = p->next;
           step--;

}
       dummy.next = p->next; //对应位置作为头节点

p->next = NULL;//对应位置后继节点为空，即要断开

return dummy.next;
    }

};
```
## 7.8 重排链表
`143. Reorder List`
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
```
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
         reorder3(head);
    }
private:
    //下面两种速度太慢了，O(n^2),基本思路为递归处理,或者每次迭代都去找最后一个节点tail插入到相应位置
    void reorder(ListNode* head)
    {
        if(head == NULL || head->next == NULL || head->next->next == NULL) return; //实际上第三个条件可以不用判断
        ListNode* p = head;
        while(p->next && p->next->next) p = p->next;
        ListNode *tail = p->next;
        p->next = NULL;
        //insert tail
        p = head->next;
        head->next = tail;
        tail->next = p;

//recursion
        reorder(p);
    }
    void reorder2(ListNode* head){
        if(head == NULL || head->next == NULL || head->next->next == NULL) return; 
        ListNode dummy(0);
        dummy.next = head;
        ListNode *p;
        ListNode *tail = NULL;
        while(head && head->next && head->next->next)
        {
            p = head;
            //second to last node
            while(p->next && p->next->next) p = p->next;
            tail = p->next;
            //if(head->next == tail) break;
            p->next = NULL;
            //insert tail
            p = head->next;
            head->next = tail;
            tail->next = p;

//next iteration
            head = p;
        }
    }
     //这种方法思路是：先快慢指针找到中点，然后断开，然后反转后一个链表，最后合在一起即可，时间复杂度大大降低，O(n)
    void reorder3(ListNode *head)
    {
         if(!head || head->next == NULL || head->next->next == NULL) return;
         ListNode dummy(0);
         dummy.next = head;
         //快慢指针寻找中点
         ListNode *fast = head,*slow = head;
         ListNode *p = NULL,*q = NULL;
         while(fast && fast->next && fast->next->next){
             fast = fast->next->next;
             slow = slow->next;
         }
         //比如[1,2,3,4],此时slow位于第一段子链表的最后一个节点
         ListNode* lb = slow->next;
         slow->next = NULL;
         
         //反转lb
         ListNode dummy_lb(0);
         dummy_lb.next = lb;
         p = &dummy_lb;
         q = lb;
         while(q->next)
         {
              ListNode* nxt = q->next;
              q->next = nxt->next;
              nxt->next = p->next;
              p->next = nxt;
         }
        //合并head 和lb
        lb = p->next;
        //这里还可以写成lb = dummy_lb.next 但是不能写成lb=&dummy_lb,除了逻辑错误外，还会报stack use after scope错误，这是因为dummy_lb是直接声明的，
        //是放在栈里的，出了函数生命周期就结束了,因此不能放进链表中，而new出来的是放在堆里的，函数执行结束还存在
        p = &dummy;
        while(lb || head)
        {
            if(head){
                 p->next = head;
                 head = head->next;
                 p = p->next;
            }
            if(lb){
               p->next = lb;
               lb = lb->next;
               p = p->next;
            }        
       }  
    }
};
```
## 7.9 分隔链表
`86. Partition List`
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。
```
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
         return partitionList(head,x);
    }
private:
    ListNode* partitionList(ListNode* head,int x)
    {
        if(head == NULL || head->next == NULL) return head;
        ListNode dummy1(0),dummy2(0);
        //一定要明确"解耦合"的重要性,也就是说不要在原来的链表上直接修改(比如各种insert,delete之类的操作)得到最终结果,那样很麻烦,而是应该像这样使用p1,p2来构建(construct!!!)结果
        ListNode *p1 = &dummy1,*p2 = &dummy2;
        ListNode* curr = head;
        while(curr)
        {
            if(curr->val < x){
                p1->next = curr;
                p1 = p1->next;
            }else{
                p2->next = curr;
                p2 = p2->next;
            }
            curr = curr->next;
        }
        p1->next = dummy2.next;
        p2->next = NULL;  //虽然很简单，但是这一步不能忘了啊！！！
        return dummy1.next;
    }
};
```
## 7.10 回文链表
```
请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == NULL) return true;
        stack<int> stk;
        ListNode* fast = head;
        ListNode* slow = head;
        stk.push(slow->val);
        while(fast->next != NULL && fast->next->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            stk.push(slow->val);
        }
        //如果总节点个数是偶数，则slow需要移动一下
        if(fast->next!=NULL)
        {
            slow = slow->next;
        }
        //使用慢指针slow开始判断
        while(slow != NULL)// && (!stk.empty()))
        {
            int temp = stk.top();
            stk.pop();
            if(slow->val != temp)
            {
                return false;
            }
            slow = slow->next;
        }
        return true;
    }
};
```

## 7.11 两数相加
### `2. Add Two Numbers`
- 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

- 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

- 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
```
示例：
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;
        ListNode *p1 = l1,*p2 = l2;
        ListNode dummy(0);
        ListNode *p = &dummy;
        int res = 0;
        int carry = 0;
        while(p1 || p2 || carry)
        {
            int a = 0,b = 0;
            if(p1)
            {
                a = p1->val;
                p1 = p1->next;
            }
            if(p2)
            {
                b = p2->val;
                p2 = p2->next;
            }
            res = a + b + carry;
            carry = res/10;
            res = res%10;

p->next = new ListNode(res);
            p = p->next;
        }
        //循环判断while(p1||p2)如果改成了while(p1||p2||carry),则不需要再像这样单独处理最高位
        // if(carry)
        // {
        //     p->next = new ListNode(carry);
        //     p = p->next;
        // }
        return dummy.next;
    }
};
```
### `445. Add Two Numbers II`
- 给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
- 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
- 进阶:
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。
```
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
```
```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //   return addtwonumbers(l1,l2);
        return addByRecursion(l1,l2);
    }
private:
   //法一：双栈法
   ListNode* addtwonumbers(ListNode *l1,ListNode *l2)
   { 
       if(l1 == NULL) return l2;
       if(l2 == NULL) return l1;
       stack<ListNode*> stk1,stk2; //the data type can also be int
       ListNode dummy(0);
       while(l1 || l2)
       {
           if(l1){
               stk1.push(l1);
               l1 = l1->next;
           }
           if(l2){
               stk2.push(l2);
               l2 = l2->next;
           }
       }
       //computation the result
        int carry = 0;
        ListNode *pa=NULL,*pb=NULL;
        int a = 0,b=0;
        ListNode *p = NULL,*q = NULL;
        p = &dummy;
        while(!stk1.empty() || !stk2.empty())
        {
            if(!stk1.empty()){
               pa = stk1.top();
               stk1.pop();
               a = pa->val;
            }else a = 0;
            if(!stk2.empty()){
               pb = stk2.top();
               stk2.pop();
               b = pb->val;
            }else b = 0;
            int sum = a + b + carry;
             
             carry = sum/10;
             sum = sum%10;
             
             //insertion next to the head;
             pa = new ListNode(sum);
             q = p->next;
             p->next = pa;
             pa->next = q;
        }
        //Carry may occur at the highest level
        if(carry){
             pa = new ListNode(carry);
             q = p->next;
             p->next = pa;
             pa->next = q;
        }
        return p->next;
   }

//法二:递归法(虽然容易理解,但是感觉有点麻烦啊!!!,还是用栈简单直接)
   ListNode* addByRecursion(ListNode *l1,ListNode *l2)
   {
       if(l1 == NULL) return l2;
       if(l2 == NULL) return l1;
       //将较短的链表用0补齐,然后再递归计算
        int len1 = 0,len2 = 0;
        ListNode *p1 = l1,*p2 = l2;
        ListNode dummy(0);
        ListNode *p = &dummy;
        while(p1 || p2)
        {
            if(p1 == NULL)
            {
                p->next = new ListNode(0);
                p = p->next;
                if(p2 && p2->next == NULL)
                {
                    p->next = l1;
                    l1 = dummy.next;
                }
            }
            if(p2 == NULL)
            {
                p->next = new ListNode(0);
                p = p->next;
                if(p1 && p1->next == NULL)
                {
                    p->next = l2;
                    l2 = dummy.next;
                }
            }
            if(p1) p1 = p1->next;
            if(p2) p2 = p2->next;
        }
        ListNode* ret =  recursion(l1,l2);
        //处理下最高位
        if(ret->val >= 10)
        {
            ListNode * h = new ListNode(ret->val/10);
            ret->val %=10;
            h->next = ret;
            return h;
        }
        return ret;
   }

ListNode * recursion(ListNode *l1,ListNode *l2)
   {
        //前提是已经保证补齐
        if(l1 == NULL && l2 == NULL) return NULL;
        if(l1->next==NULL && l2->next == NULL)
            return new ListNode(l1->val + l2->val);
    
        ListNode *ret = new ListNode(l1->val+l2->val);
        ListNode *p = recursion(l1->next,l2->next);
        ret->val += p->val/10;
        p->val %=10;
        ret->next = p;
        
        return ret;
   }
};
```
## 7.12 复制带随机指针的链表
`138. Copy List with Random Pointer`
- 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

- 要求返回这个链表的 深拷贝。

- 我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 `[val, random_index]` 表示：
`val`:一个表示 Node.val 的整数。
`random_index`:随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
```
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
```
```
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        return deepCopyFunc2(head);
    }
private:
    //映射法
    Node* deepCopyFunc(Node *head)
    {
        if(head == NULL) return head;
        Node dummy(0);
        Node *p = &dummy;
        Node *q = head;
        //建立新旧结点的一 一对应关系
        unordered_map<Node*,Node*> m;
        while(q)
        {
            Node *r = new Node(q->val);
            p->next = r;

r->random = q->random;
            m[q] = r;

p = p->next;
            q = q->next;
        }
        q = dummy.next;
        while(q)
        {
            if(q->random) q->random = m[q->random];
            q = q->next;
        }
        return dummy.next;
    }

//有丝分裂法
    Node* deepCopyFunc2(Node *head)
    {
        if(!head) return nullptr;
        Node dummy(0);
        Node *p = head;
        //copy original list inplace
        while(p)
        {//1 -> 1' -> 2 ->2' ->3 ->3' ......
            Node *r = new Node(p->val);
            //insertionhhk
            Node *tmp = p->next;
            p->next = r;
            r->next = tmp;
            
            p = p->next->next;
        }

//dummy.next : new head
        dummy.next = head->next;

//copy "random pointer"
        p = head;
        Node *q = head->next;
        while(p)
        {
            if(p->random){
                p->next->random = p->random->next;
            }
            p = p->next->next;
        }
        
        p = head;
        // Node *ret = head->next;

//1' -> 2' -> 3' ......
        // while(p->next && q->next)
        // {
        //     Node *nq = q->next;            
        //     p->next = nq;
        //     q->next = nq->next;

//     p = p->next;
        //     q = q->next;
        // }
        // p->next = NULL;
        // q->next = NULL;

//the above "while loop" can be this:
        while(p->next){
            Node *nq = p->next;
            p->next = p->next->next;
            p = nq;
        }
        return dummy.next;
    }
};
```
## 7.13 LRU缓存
```
设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
```
```
class LRUCache {
private:
    //基本思想是哈希+双向链表
    //为了提高查询速度，使用hash保存前述链表的迭代器
    unordered_map<int,list<pair<int,int>>::iterator> mp;
    //为了做到插入删除O(1),使用保存键值对的链表
    list<pair<int,int>> l;
    int cap;
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    int get(int key) {
        //如果查询到，则将其移到链表头
        if(mp.find(key)!=mp.end())
        {
            int res = (*mp[key]).second;
            l.erase(mp[key]);
            l.push_front(make_pair(key,res));
            mp[key] = l.begin();
            return res;
        }
        //未查询到
        return -1;
    }    
    void put(int key, int value) {
        //直接放到链表头
        if(mp.find(key)!=mp.end())
        {
            l.erase(mp[key]);
            l.push_front(make_pair(key,value));
            mp[key] = l.begin();
        }
        else
        {
            //超出容量限制，则去掉最后一个
            if(l.size()==cap)
            {
                mp.erase(l.back().first);
                l.pop_back();
            }
            l.push_front(make_pair(key,value));
            mp[key] = l.begin();
        }
    }
};
/**
 * 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);
 */

```
## 7.14 实现Trie(前缀树)
```
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true
说明:

你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。

链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree
```
```
class Trie {
private:
    bool is_string_tail = false;
    //保存26个字母对应的Trie
    Trie* letters[26] = {nullptr};
public:
    /** Initialize your data structure here. */
    Trie(){}
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie* root = this;
        for(char c:word)
        {
            if(root->letters[c - 'a'] == nullptr)
            {
                root->letters[c - 'a'] = new Trie();
            }
            root = root->letters[c - 'a'];
        }
        root->is_string_tail = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie* root = this;
        for(char c:word)
        {
            //字母找不到，直接false
            if(root->letters[c - 'a'] == nullptr) return false;
            root = root->letters[c - 'a'];
        }
        //到这里说明已经查找到了需要的字符串，但有可能是前缀,所以不能直接返回true
        //而是要返回最后一个节点的is_string_tail
        return root->is_string_tail;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie* root = this;
        for(char c:prefix)
        {
            //字母找不到，直接false
            if(root->letters[c - 'a'] == nullptr) return false;
            root = root->letters[c - 'a'];
        }
        //到这里说明已经查找到了需要的字符串，是前缀或者是单词,直接返回true
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */
```
# 8.字符串(String)
## 8.1 二进制求和
`67. Add Binary`
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
```
示例 1:
输入: a = "11", b = "1"
输出: "100"

示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
```
```
class Solution {
public:
    string addBinary(string a, string b) {
        return addBinaryStack(a,b);
    }
private:
    string addBinaryStack(string a,string b)
    {
        if(a.empty()) return b;
        if(b.empty()) return a;
        int i = a.size()-1,j = b.size()-1;
        int tmp1 = 0,tmp2 = 0;
        int carry = 0;
        int sum = 0;
        stack<int> stk;
        while(i>=0 || j>=0)
        {
            if(i>=0){
                tmp1 = a[i] -'0';
                i--;
            }else tmp1 = 0;
            if(j>=0){
                tmp2 = b[j]-'0';
                j--;
            }else tmp2 = 0;
        
            sum = tmp1 + tmp2 + carry;
            carry = sum/2;
            sum = sum%2;
            //you can also insert "sum" into string object to return directly
            stk.push(sum);
        }
        //the highest level
        if(carry){
            stk.push(carry);
        }
        string ret;
        while(!stk.empty())
        {
            int t = stk.top();
            ret.push_back(t+'0');
            stk.pop();
        }
        return ret;
    }
};
```
## 8.2 基本计算器
### `224. Basic Calculator`
- 实现一个基本的计算器来计算一个简单的字符串表达式的值。

- 字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格  。
- 说明:
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
```
示例 1:
输入: "1 + 1"
输出: 2

示例 2:
输入: " 2-1 + 2 "
输出: 3

示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
```
```
class Solution {
public:
    int calculate(string s) {
        return calculatorByStack(s);
    }
private:
    //方法一:双栈法:数字栈+符号栈
    int calculatorByStack(string s)
    {
        if(s.empty()) return 0;
        int res = 0;
        stack<int> stk;
        stk.push(0);
        stack<char> stkop;
        stkop.push('+');
        int len = s.size();
        int i;
        char ch = '0';
        char op = '+';
        long int num = 0;
        for(i = 0;i<len;i++)
        {
            ch = s[i];
            if(ch != ' ')
            {
                //如果是数字
                if(ch >= '0' && ch <= '9')
                {
                    num = ch - '0';
                    while(i<len-1 && s[i+1]>='0' && s[i+1]<='9'){
                        i++;
                        num = num*10 + s[i]-'0';
                    }
                    int tmp = stk.top();
                    stk.pop();
                    op = stkop.top();
                    stkop.pop();
                    switch(op)
                    {
                        case '+':
                            tmp+=num;
                            stk.push(tmp);
                            break;
                        case '-':
                            tmp-=num;
                            stk.push(tmp);
                            break;
                        case '(':
                            stk.push(tmp);
                            stk.push(0);
                            break;
                        case ')':
                            //正常情况下，数字前面不可能出现')'
                            break;    
                    }
                }
                else
                {//不是数字，为"(",")"，"+","-"
                    if(ch == '+' || ch =='-')
                    {
                        //int tmp = stk.top();
                        stkop.push(ch);
                    }
                    else if(ch == '('){
                        stk.push(0);
                        stkop.push('+');
                    }else if(ch == ')')
                    {
                        int tmp = stk.top();
                        stk.pop();
                        op = stkop.top();
                        stkop.pop();

if(stk.empty()){
                            res+=tmp;
                        }else{
                            int t = stk.top();
                            stk.pop();
                            t = op == '+' ? t+tmp:t-tmp;
                            stk.push(t);
                        }
                    }

}
            }
        }
        //最外面一层不会出现")",因此要单独处理
        while(!stk.empty()){
            res+=stk.top();
            stk.pop();
        }
     return res;
    }
    //方法二：分治法：使用递归
    int calculatorByRecursion(string s)
    {
        if(s.empty()) return 0;
        int res = 0;
        int len = s.size();

return res;
    }
    
};
```
### `227. Basic Calculator II`
实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格  。 整数除法仅保留整数部分。
```
示例 1:
输入: "3+2*2"
输出: 7

示例 2:
输入: " 3/2 "
输出: 1

示例 3:
输入: " 3+5 / 2 "
输出: 5
```
```
class Solution {
public:
    int calculate(string s) {
        return calculator2(s);
    }
private:
    //因为条件相对简单，所以可以直接迭代,不需要栈
    int calculator2(string s)
    {
        if(s.empty()) return 0;
        int res = 0,tmp_res = 0;
        long num = 0; //很恶心，不用long会溢出

int len = s.size();
        int i = 0;
        char ch = '0';
        char op = '+';
        for(i = 0;i<len;i++)
        {
            ch = s[i];
            if(ch!=' ')
            {
                //数字
                if(ch >= '0' && ch <= '9')
                {
                    num = ch -'0';
                    while(i<len-1 && s[i+1] >='0' && s[i+1] <= '9')
                    {
                        i++;
                        num = num*10 + s[i]-'0';
                    }
                    switch(op)
                    {
                        case '+':
                            tmp_res+=num;
                            break;
                        case '-':
                            tmp_res-=num;
                            break;
                        case '*':
                            tmp_res*=num;
                            break;
                        case '/':
                            tmp_res/=num;
                            break;
                    }
                }else //操作符
                {
                    if(ch == '+' || ch == '-')
                    {
                        res +=tmp_res;
                        tmp_res = 0;
                    }
                    op = s[i];
                }
            }
        }
        return res + tmp_res;
    }

};
```
## 8.3 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
```
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
```
```
class Solution {
public:
    string replaceSpace(string s){
        if(s.empty()) return s;
        int space_cnt = 0;
        for(int i = 0;i<s.size();++i)
        {
            if(s[i] == ' ')
             ++space_cnt;
        }
        if(space_cnt!=0)
        {
            int i = s.size()-1, j = 0;
            while(space_cnt)
            {
                s.push_back(' ');
                s.push_back(' ');
                --space_cnt;
            }
            j = s.size()-1;
            for(;i>=0;--i)
            {
                if(s[i] == ' ')
                {
                    s[j] = '0';
                    s[j-1] = '2';
                    s[j-2] = '%';
                    j-=3;
                }
                else
                {
                    s[j] = s[i];
                    --j;
                }
            }
        }
        return s;
    }
};
```
## 8.4 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"、"-1E-16"及"12e+5.4"都不是。
```
class Solution {
public:
    bool isNumber(string s) {
        /*大写E不能通过，小写e可以*/
        if(s.empty()) return false;
        bool isNum = false;
        int i = 0;
        //忽略首部空格
        while(i<s.size() && s[i] == ' ')
            ++i;
        //整数部分
        if(s[i] == '+' || s[i] == '-')
            ++i;

while(i<s.size() && s[i] >='0' && s[i] <='9')
        {
            isNum = true;
            ++i;
        }
        
        //.345 ,这样的数字,小数点后面必须有数字,否则i == t
        if(s[i] == '.')
        {
            ++i;
            int t = i;
            while(i<s.size() && s[i] >='0' && s[i] <='9')
            {
                ++i;
            }
            isNum = isNum  || i>t;
        }
        //+12e-12这种的
        if(s[i] == 'e')
        {
            if(i==0 || (i==1 && s[i] == '.'))
            {
                //e前面没有数字,e9不是数字
                //.e9也不算
                isNum = false;
            }
            else
            {
                ++i;
                if(s[i] =='+' || s[i] =='-') //-1e-16是数字
                    ++i;
                int t = i;
                while(i<s.size() && s[i] >='0' && s[i] <='9')
                {
                    ++i;
                }
                isNum = isNum && i>t;
            }
        }
        //因为字符串前后可以存在任意空格，中间不可以,所以定义下字符串结束的位置
        int tail = s.size()-1;
        while(tail > 0 && s[tail] == ' ')
            --tail;
        return isNum && i == tail+1; //这里i==tail+1 保证中间出现空格,就一定为false
    }
};
```
## 8.5 反转字符串中的元音字母
```
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1:

输入: "hello"
输出: "holle"
示例 2:

输入: "leetcode"
输出: "leotcede"
```
```
class Solution {
public:
    Solution()
    {
        vowels = {'a','e','i','o','u','A','E','I','O','U'};
    }
    string reverseVowels(string s) {
        return func2(s);
    }
    //更简洁的写法
    string func2(string s)
    {
        if(s.size()==0) return string();
        if(s.size()==1) return s;
        int i = 0,j = s.size()-1;
        while(i<j)
        {
            if(vowels.find(s[i])==vowels.end())
            {
                i++;
            }
            else if(vowels.find(s[j])==vowels.end())
            {
                j--;
            }
            else
            {
                char temp = s[i];
                s[i++] = s[j];
                s[j--] = temp;
            }
        }
        return s;
    }
    
    //稍微麻烦点的写法
    string func1(string s)
    {
        if(s.size()==0) return string();
        if(s.size()==1) return s;
        int i = 0,j=s.size()-1;
        while(i<s.size()-1 && vowels.find(s[i]) == vowels.end())
        {
            i++;
        }
        while(j>0 &&vowels.find(s[j]) == vowels.end())
        {
            j--;
        }
        while(i<j)
        {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            while(i<s.size()-1 &&vowels.find(s[i]) == vowels.end())
            {
                i++;
            }
            j--;
            while(j>0 && vowels.find(s[j]) == vowels.end())
            {
                j--;
            }
        }
        return s;
    }
private:
    set<char> vowels;
};
```
## 8.6 验证回文字符串
```
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True
示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。
```
```
class Solution {
public:
    bool validPalindrome(string s) {
        if(s.size()<=1) return true;
        for(int i = 0,j = s.size()-1;i<j;i++,j--)
        {
            if(s[i]!=s[j])
                return isPalindrome(s,i+1,j) || isPalindrome(s,i,j-1);
        }
        return true;
    }
private:
    bool isPalindrome(string s,int i,int j)
    {
        while(i < j)
        {
            if(s[i++] != s[j--])
                return false;
        }
        return true;
    }
};
```
## 8.7 验证回文串
```
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:

输入: "race a car"
输出: false
```
```
class Solution {
public:
    bool isPalindrome(string s) {
        if(s.size()<=1) return true;
        int i = 0,j = s.size()-1;
        while(i < j)
        {
            if(!((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= '0' && s[i]<='9')))
            {
                i++;
            }
            else if(!((s[j] >= 'a' && s[j] <= 'z') || (s[j] >= 'A' && s[j] <= 'Z') || (s[j] >= '0' && s[j]<='9')))
            {
                j--;
            }
            else
            {
                //测试样例"0P"，0和P刚好差32，但是不是回文。坑啊,所以如果有数字的话，不要用'a'-'A'这种方式
                //使用toupper或者tolower，包含bai于ctype头文件中，如果c是小du写英文字母，则转换为zhi大写，其他字符dao不变
                //if((s[i] != s[j]) && ((s[i] + 'a'-'A') != s[j]) && (s[i] != (s[j] + 'a'-'A')))
                if((s[i] != s[j]) && (toupper(s[i]) != s[j]) && (s[i] != toupper(s[j])))
                    return false;
                i++;
                j--;
            }
        }
        return true;
    }
};
```
## 8.8 有效的括号
```
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true
```
```
class Solution {
public:
    bool isValid(string s) {
        if(s.empty()) return true;
        stack<char> stk;
        int i = 0;
        stk.push(s[i++]);
        //有可能出现"()[]{}"这样的，所以栈可以为空
        while(!stk.empty() || i<s.size())
        {
            if(i>=s.size())
            {
                return false;
            }
            else
            {   //基本思路：遇到左括号入栈，右括号出栈并判断
                switch(s[i])
                {
                case '(':
                    stk.push(s[i++]);
                    break;
                case ')':
                    if(!stk.empty() && stk.top()=='(')
                    {
                        stk.pop();
                        i++;
                    }
                    else return false;
                    break;
                case '{':
                    stk.push(s[i++]);
                    break;
                case '}':
                    if(!stk.empty() && stk.top() == '{')
                    {
                        stk.pop();
                        i++;
                    }
                    else return false;
                    break;
                case '[':
                    stk.push(s[i++]);
                    break;
                case ']':
                    if(!stk.empty() && stk.top() == '[')
                    {
                        stk.pop();
                        i++;
                    }
                    else return false;
                    break;
                }
            }
        }
        return true;
    }
};
```
另外一种更简洁的写法(前提是输入s中只包含'(',')','{','}','[',']' )：
```
class Solution {
public:
    bool isValid(string s) {
        //另外一种简单的写法：
        stack<char> stack1;//建立一个存放char字符类型的栈stack1
        int len = s.length();
        for (int i = 0; i < len; i++)
        {
            if (stack1.empty() && (s[i] == '}' || s[i] == ']' || s[i] == ')'))//当栈为空时,遇到反括号,直接返回false
            {
                return false;
            }
            if (s[i] == '}' || s[i] == ']' || s[i] == ')')
            {
                if (s[i] - stack1.top() == 1 || s[i] - stack1.top() == 2) //'(',')'的ASCLL码差1，'[',']'还有'{', '}'相差2               
	            {
                    stack1.pop();
                }
                else
                {
                    return false;
                }
            }
            else
            {
                stack1.push(s[i]);
            }
        }
        return stack1.empty();
    }
};
```

## 8.9 字母异位词分组
```
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

链接：https://leetcode-cn.com/problems/group-anagrams
```
```
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;    
        if(strs.empty()) return res;
        //将排序后的字符串作为key，对应的字符串作为val，放入到对应的vector中即可
        unordered_map<string,vector<string>> cache;
        for(auto str:strs)
        {
            string tmp = str;
            sort(tmp.begin(),tmp.end());
            if(cache.find(tmp)!=cache.end())
            {
                cache[tmp].push_back(str);
            }
            else
            {
                //pair需要<>来指定类型,make_pair则不需要
                // cache.insert(std::make_pair(tmp,vector<string>(1,str)));
                //cache.insert(pair<string,vector<string>>(tmp,vector<string>(1,str)));
                //cache[tmp] = vector<string>(1,str);
                cache[tmp] = {str};
            }
        }
        //取出所有的vector即可
        for(auto t:cache)
        {
            res.push_back(t.second);
        }
        return res;
    }
};
```
## 8.10 最小覆盖子串
```
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
链接：https://leetcode-cn.com/problems/minimum-window-substring
```
```
class Solution {
public:
    string minWindow(string s, string t) {
       //双指针滑动窗口+计数统计的思路
        int mp[256] = {0};
        for (char c : t) mp[c] += 1; //mp保存查询字符串t中各个字符的数量
        int start = 0, end = 0; //双指针，或者叫滑动窗口，窗口区间[start,end]左闭右闭
        int n = s.length(), m = t.length();
        int cnt = 0;//cnt表示当前区间[start,end]中找到了多少个满足要求的字符
        int res = -1;
        string ans = "";
        while (end < n) {
            char c = s[end];
            mp[c] -= 1; //现在mp中保存的是t中还未被匹配到的字符的数量，负数则表示t中没有该字符
            if (mp[c] >= 0) cnt += 1; //显然，一开始end不断增加，必然找到第一个区间，使得cnt==m
            while (cnt == m) {
                if (res == -1 || res > end - start + 1) {
                    ans = s.substr(start, end - start + 1);//记录最短的ans
                    res = end - start + 1; //记录当前找到的子串长度
                }
                //然后开始让start不断增加
                c = s[start];
                mp[c] += 1;
                if (mp[c] >= 1) cnt -= 1; 
                start += 1;
            }
            end += 1;
        }
        return ans;
    }
}
```
## 8.11 字符串解码
```
给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

链接：https://leetcode-cn.com/problems/decode-string
```
```
class Solution {
public:
    string decodeString(string s) {
    /* 思路：如果遇到 ']'，就找到 '['并将之间的字符连接起来，
    * 再将'['前面的数字连接起来作为出现次数再次压入到结果中去，
    * 遇到数字、字母、'['就直接压栈，最后将栈里的字符串弹出连接起来 */
    string res;
    if(s.empty()) return res;
    for(char c:s)
    {
        if(c == ']')
        {
            //寻找当前的子串
            string tmpstr;
            while(!res.empty() && res.back() != '[')
            {
                tmpstr.push_back(res.back());
                res.pop_back();
            }
            res.pop_back();
            std::reverse(tmpstr.begin(),tmpstr.end());
            //子串重复的次数
            string tmpcnt;
            while(!res.empty() && res.back() >= '0' && res.back() <='9')
            {
                tmpcnt.push_back(res.back());
                res.pop_back();
            }
            std::reverse(tmpcnt.begin(),tmpcnt.end());
            //拼接到结果中去
            int cnt = std::stoi(tmpcnt);
            string retstr;
            while(cnt--)
            {
                retstr += tmpstr;
            }
            res.append(retstr);
        }
        else 
        {
            res.push_back(c);
        }
    }
    return res;
    }
};
```
## 8.12 字符串解码(腾讯2020校招)
```
小Q想要给他的朋友发送一个神秘字符串，但是他发现字符串的过于长了，于是小Q发明了一种压缩算法对字符串中重复的部分进行了压缩

对于字符串中连续的m个相同字符串S将会压缩为 [m | S ] (m为一个整数且1<=m<=100)，例如字符串ABCABCABC将会被压缩为[3|ABC]，现在小Q的同学收到了小Q发送过来的字符串，你能帮助他进行解压缩么？

输入描述:
输入第一行包含一个字符串s，代表压缩后的字符串。
S的长度<=1000;
S仅包含大写字母、[、]、|;
解压后的字符串长度不超过100000;
压缩递归层数不超过10层;

输出描述:
输出一个字符串，代表解压后的字符串。

输入样例:
HG[3|B[2|CA]]F
输出样例:
HGBCACABCACABCACAF
```
```
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
	string str;
	cin >> str;
	stack<int> s;
	for (int right = 0; right < str.length(); right++){
		//遇到 '[' 或 '|' 时入栈, 思路和上一道题比较类似，都是使用stack实现
		if (str[right] == '[' || str[right] == '|')
			s.push(right);
		if (str[right] == ']'){
			//出栈
			int k    = s.top();  //k记录的是'|'的位置
			s.pop();
			int left = s.top();  //left记录的是'['的位置
			s.pop();
			int num = stoi(str.substr(left + 1, k- left));
			//s1记录的是重复部分
			string s1 = str.substr(k + 1, right - k - 1);
			string s2;
			for (int i = 0; i < num; i++)
				s2 += s1;
			str = str.replace(left, right - left + 1, s2);
			//计算新的right的位置
			right = left+s2.size()-1;
		}
	}
	cout << str;
}
//https://www.cnblogs.com/eisuto/archive/2020/03/11/12464469.html
```
## 8.13 判断IP是否合法
```
bool isIPAddressValid(const char* pszIPAddr)
{
    if(!pszIPAddr) return false;
    int length = sizeof(pszIPAddr);
    int validSegSize = 0; //记录一共有多少个分段
    int oneSeg = 0; //记录每个分段的数值
    int segLen = 0; //记录是否分段有数值
    for(int i = 0;i < length;++i)
    {
        //依次计算每个分段的数值
        if(pszIPAddr[i] >= '0' && pszIPAddr[i] <= '9')
        {
            oneSeg = oneSeg*10 + (pszIPAddr[i] - '0');
            ++segLen;
        }
        else if(pszIPAddr[i] == '.')
        {
            if(oneSeg <= 255 && segLen > 0)
            {
                validSegSize++;
            }
            else return false;
                
            oneSeg = 0;
            segLen = 0;
        }
        else
        {
            return false;
        }
    }
    //判断最后一个分段的合法性
    if(oneSeg <= 255 && segLen >0)
    {
        validSegSize++;
    }
    //判断是否一共有四个合法的分段
    return validSegSize == 4;
}
```
# 9 数学(Math)
## 9.1 数值的整数次方
实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。
```
示例 1:
输入: 2.00000, 10
输出: 1024.00000

示例 2:
输入: 2.10000, 3
输出: 9.26100

示例 3:
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
```
```
class Solution {
public:
    double myPow(double x, int n) {
        //如果输入底数为0
        if(x - 0.0 < 1e-9 && 0.0 - x < 1e-9)
        {
            if(n==0)
                throw std::exception();
            else return 0;
        }
        //底数不为0,指数为0
        if(n == 0) return 1;
        //底数不为0,指数不为0
        double result = 1;
        int tmp = n;
        while(n)
        {
            if(n &0x01) result*= x;
            x *=x;
            n /= 2; //负数移位不做特殊处理将可能会死循环
        }
        return tmp>0? result:1.0/result;
    }
};
```
## 9.2 最大公约数与最小公倍数
- 求a,b的最大公约数:
```
//辗转相除法, 两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
int gcd1(int a,int b)
{
    int c = a%b; //若a<b,一样成立
    while(c)
    {
        a = b;
        b = c;
        c = a%b;
    }
    return b;
}
//更相减损书,两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
int gcd2(int a,int b)
{
    int c = abs(a-b);
    while(c)
    {
        a = b;
        b = c;
        c = abs(a-b);
    }
    return b;
}
```
- 求a,b的最小公倍数
按照如下关系求解即可:`a,b的最小公倍数 = $a*b/c$, 其中c为a,b的最大公约数`
证明:
```
 a = cm;
 b = cn;
 则a*b/c = c*c*m*n/c = cmn;
```

## 9.3 蜗牛爬井问题
有一口井深度为len米，一只蜗牛从井底开始爬，白天爬m米，晚上掉n米。
len，m，n均为整数。例如：一口井深10米，蜗牛白天爬4米，晚上掉3米，总共7天就可以到达井口。
暴力计算代码，时间为O(len/(m-n))：
```
int climb(int len,int m,int n)
{
	if(m<=n) return -1;
	int ndays = 1, s= 0;
    while (1){
        s += m;
        if (s<len) {
            s -= n;
            ndays++;
        } else {
            return ndays;
            break;
        }
    }
    return -1;
}
```
实际上前面蜗牛爬的过程我们完全不需要关心，因此优化代码：
```
#include <iostream>
using namespace std;
//井深len米，蜗牛每天爬m米，晚上掉n米，返回需要爬的天数，-1表示无法爬出去
int climb(int len,int m,int n)
{
	if(m<=n) return -1;
	if(len <= m) return 1;
	//之前已经爬了这么多天(最后一天最多爬m米)，“+1”表示再加上今天
	int ndays =int((len - m)/(m-n))+1; 
	//之前已经爬了的距离
	int s= (ndays-1)*(m-n);
    while (1){
        s += m;//加上今天将会爬的距离m
        if (s<len) {//未到终点，加一天
            s -= n;
            ndays++;
        } else { //大于len则直接可以返回了
            return ndays;
            break;
        }
    }
    return -1;
}

int main()
{
	cout<<climb(10,4,3)<<endl;
    return 0;
}
```
# 10. 图
## 10.1 课程表
```
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
```
```
示例 1:

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

提示：

输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法https://www.cnblogs.com/liushang0419/archive/2011/05/06/2039386.html。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
```
```
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses,0);
        vector<vector<int>> graph(numCourses,vector<int>());
        for(int i = 0;i<prerequisites.size();++i)
        {
            //统计入度
            indegree[prerequisites[i][0]]++;
            //记录出度
            graph[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        //入队列
        queue<int> que;
        for(int i=0;i<indegree.size();++i)
        {
            if(indegree[i] == 0)
                que.push(i);
        }
        //bfs
        int cnt = 0;
        while(!que.empty())
        {
            int temp = que.front();
            que.pop();
            ++cnt;
            for(int i = 0;i<graph[temp].size();++i)
            {
                indegree[graph[temp][i]]--;
                if(indegree[graph[temp][i]] == 0)
                {
                    que.push(graph[temp][i]);
                }
            }
        }
        return cnt == numCourses;
    }
};
```
## 10.2 打开转盘锁
```
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为  '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
```
```
示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:

输入: deadends = ["0000"], target = "8888"
输出：-1

提示：

死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
```
```
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        //死锁点
        set<string> deads(deadends.begin(),deadends.end());
        //已经访问过的点
        set<string> visited;
        int steps = 0;
        queue<string> que;
        //初始化起点
        que.push("0000");
        visited.insert("0000");
        string curr;
        string upstr,downstr;
        //广度优先搜索
        while(!que.empty())
        {
            int sz = que.size();
            for(int i = 0;i<sz;++i)
            {
                curr = que.front();
                que.pop();
                //if(deads.find(curr) != deads.end())
                if(deads.count(curr)) 
                    continue;
                if(curr == target) return steps;
                //从curr附近扩散
                for(int j = 0;j<4;++j)
                {
                    upstr = curr;
                    downstr = curr;
                    //上旋
                    if(curr[j] == '9') upstr[j] = '0';
                    else upstr[j]+=1;
                    if(visited.find(upstr) == visited.end())
                    {
                        que.push(upstr);
                        visited.insert(upstr);
                    }
                    //下旋
                    if(curr[j] == '0') downstr[j] = '9';
                    else downstr[j]-=1;
                    if(visited.count(downstr) == 0)
                    {
                        que.push(downstr);
                        visited.insert(downstr);
                    }
                }
            }
            ++steps;
        }
        return -1;
    }
};
```

lee-romantic 's Blog

导航

最近发表

友情链接