LinkedList

链表翻转、两个链表代表的数求和（两种形式）、找到链表的倒数第k个节点（删除链表的倒数第k个节点）

445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

1 2	Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 8 -> 0 -> 7

题目大意

给定两个非空的链表，链表的每个节点代表非负整数的一位，链表的靠前的位置代表着高位。返回两个链表所代表的数相加的结果，结果以链表形式返回。

如果不能改变输入的链表即不能翻转链表该如何操作。

思路

翻转链表，按顺序加起来，然后构造链表即可；(但是题目要求不允许改变链表)；
空间换时间，遍历两个链表用数组存起来，使用数组相加，同时生成结果链表，生成结果链表的时候可以逆序直接生成结果链表；

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		vector<int> vec1, vec2, vec3;
		ListNode *res = NULL, *p = NULL;
		while (l1 != NULL){
			vec1.push_back(l1->val);
			l1 = l1->next;
		}
		while (l2 != NULL){
			vec2.push_back(l2->val);
			l2 = l2->next;
		}
		int len1 = vec1.size(), len2 = vec2.size(), c = 0;
		for (int i=len1-1, j=len2-1; i>=0 || j>=0 || c > 0; --i, --j){
			int sum = c;
			if (i >= 0) sum += vec1[i];
			if (j >= 0) sum += vec2[j];
			c = sum / 10;
			p = new ListNode(sum % 10);
			p->next = res;
			res = p;
		}
		return res;
    }
};

翻转链表，熟悉下链表翻转

// reverse the linked list
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode *l1_r = reverse(l1);
		ListNode *l2_r = reverse(l2);
		
		int c = 0;
		ListNode *res = NULL, *p = NULL;
		while ((l1_r!=NULL) || (l2_r!=NULL) || c>0){
			int sum = c;
			if (l1_r != NULL) {
				sum += l1_r->val;
				l1_r = l1_r->next;
			}
			if (l2_r != NULL) {
				sum += l2_r->val;
				l2_r = l2_r->next;
			}
			
			c = sum / 10;
			p = new ListNode(sum % 10);
			p->next = res;
			res = p;		
		}
		return res;
    }
    ListNode* reverse(ListNode* node){
		if (node == NULL || node->next == NULL) return node;
		ListNode *p = NULL, *q = node;
		while (q != NULL){
			ListNode *tmp = q->next;
			q->next = p;
			p = q;
			q = tmp;
		}
		return p;
    } 
};

2.Add Two Numbers

题目大意

用一个链表给出一个非负数，链表的头是数的低位，尾部是高位，求两个链表所代表数的和的链表形式。

思路

比445简单多了，直接遍历链表相加，返回即可。

考虑

如果是有符号数，得考虑大小再做减法

代码

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head, *p, *q;
        head = new ListNode(0);
        p = head;
        int sum = 0, carry = 0;
        while (l1 || l2 || carry){
            sum =carry;
            if (l1){
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2){
                sum += l2->val;
                l2 = l2->next;
            }
            carry = sum / 10;
            sum = sum % 10;
            p->next = new ListNode(sum);
            p = p->next;
        }
        /*
        if (!head->next || !head->next->next)
            return head->next;
        p = NULL;
        q = head->next;
        delete head;
        while (q){
            ListNode* tmp = q->next;
            q->next = p;
            p = q;
            q = tmp;
        }
        return p;
        */
        return head->next;
    }
};

19.Remove Nth Node From End of List

题目大意

删除链表的倒数第n个节点

思路

使用双指针法，第一个指针访问第n个节点，然后同时移动两个指针，当第一个指针到达尾部时，第二个指针指向的就是倒数第n个节点。

需要考虑边界条件

head节点为空
n大于链表节点数目
当链表只有一个节点且需要删除当前节点的情况(有指向head的头结点时会更好处理)

使用一个指向head的头节点会比较好处理一些。

代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 考虑head为空
        if (!head) return head;
        ListNode *bak, *low = head, *fast = head;
        for (int i=0; i<n; ++i){
            if (!fast)
                return head;
            fast = fast->next;
        }
        if (fast == NULL){
            bak = head->next;
            delete head;
            return bak;
        }
        while(fast->next){
            fast = fast->next;
            low = low->next;
        }
        fast = low->next;
        low->next = low->next->next;
        delete fast;
        return head;
    }
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 考虑head为空
        if (!head) return head;
        ListNode *pre;
        pre = new ListNode(0);
        pre->next = head;
        ListNode *low = pre, *fast = pre;
        for (int i=0; i!=n; ++i){
            // 考虑n超过范围
            if (!fast)
                return head;
            fast = fast->next;
        }
        // fast肯定不会为空，只是保险
        while (fast && fast->next){
            low = low->next;
            fast = fast->next;
        }
        fast = low->next;
        low->next = low->next->next;
        // 记得释放删除节点的内存
        delete fast;
        low = pre->next;
        delete pre;
        return low;
    }
};

92.Reverse Linked List II

题目大意

给定一个单链表，翻转m到n的位置，链表从1开始标号。要求in-place and one-pass。

思路

使用额外空间：
- fast指针先指到m位置，遍历到n，将值push到栈中；
- low从m位置开始，依次将栈中值pop出来存储到对应的节点位置
直接操作
- pre指向(m-1)位置，pStart指向m位置，那么依次开始逆序
- tmp = pStart->next;
- pStart->next = tmp->next;
- tmp->next = pre->next;
- pre->next = tmp;

代码

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == NULL) return head;
        ListNode preHead(0);
        ListNode *pre = &preHead;
        pre->next = head;
        
        ListNode *p=pre, *pstart=NULL, *t=NULL;
        
        for (int i=0; i<m-1; ++i)
            p = p->next;
        pstart = p->next;
        for (int i=0; i<n-m; ++i){
            t = pstart->next;
            pstart->next = t->next;
            t->next = p->next;
            p->next = t;
        }
        return pre->next;
    }
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (!head || !head->next) 
            return head;
        n -= m;
        ListNode *root=NULL, *pre=NULL, *pStart=NULL;
        ListNode preNode(0);
        root = &preNode;
        root->next = head;
        pre = root;
        
        while (--m){
            pre = pre->next;
        }
        pStart = pre->next;
        while (n--){
            ListNode *t = pStart->next;
            pStart->next = t->next;
            t->next = pre->next;
            pre->next = t;
        }
        return root->next;
    }
};

21.Merge Two Sorted Lists

题目大意

将两条排序好的链表合并，要求返回的新链表的节点是由旧链表而来。

思路

归并排序的思路

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *pre = NULL;
        ListNode prenode(0);
        pre = &prenode;
        ListNode *cur = pre;
        
        while (l1 && l2){
            if (l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        
        if (l1){
            cur->next = l1;
        }
        if (l2){
            cur->next = l2;
        }
        return pre->next;
    }
};

23.Merge k Sorted Lists

题目大意

合并k条排好序的链表

思路

普通思路
- 转换为k次两个链表的合并
- 时间复杂度为$O(k^2n)$
复杂度为$O(log(k)n)$
- 比较k个链表的当前最小值时，使用堆排序维护顺序，这样的话就不需要重复进行排序了

代码

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *tmp=NULL;
        for (int i=0; i!=lists.size(); ++i){
            tmp = mergeTwoLists(tmp, lists[i]);
        }
        return tmp;
    }
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
        if (!l1 && !l2)
            return l1;
        ListNode* pre=NULL;
        ListNode preHead(0);
        pre = &preHead;
        ListNode* head = pre;
        while (l1 && l2){
            if (l1->val > l2->val){
                head->next = l2;
                l2 = l2->next;
            }else {
                head->next = l1;
                l1 = l1->next;
            }
            head = head->next;
        }
        if (l1)
            head->next = l1;
        if (l2)
            head->next = l2;
        return pre->next;
    }
};

// priority_queue的比较
struct cmp
{
    bool operator()(ListNode* a, ListNode* b){
      	// 	小顶堆
        return (a->val > b->val);
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *pre=NULL, *cur=NULL, *tmp=NULL;
        ListNode preHead(0);
        pre = &preHead;
        cur = pre;
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for (int i=0; i!=lists.size(); ++i){
            if (lists[i]){
                q.push(lists[i]);
            }
        }
        while (!q.empty()){
            tmp = q.top();
            q.pop();
            cur->next = tmp;
            cur = cur->next;
            if (tmp->next)
                q.push(tmp->next);
        }
        return pre->next;
    }
};

138.Copy List with Random Pointer

题目大意
- 给定一条带有随机指针的链表，随机指针随机指向链表中的某个节点，要求返回该链表的深拷贝。
思路
- 1
  - 先对仅仅对链表的普通关系进行复制，同时用一个map存储原来链表节点和复制链表节点的对应关系
  - 再遍历一遍普通链表，对非空的random指针在复制链表中复制，指向的节点有map确定
- 2
  - 对原有链表复制一个节点插入到当前节点后面
  - 复制random pointer
  - 拆分
代码

class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode* pre=NULL;
        RandomListNode preHead(0);
        pre = &preHead;
        RandomListNode *cur1=head, *cur2 = pre;
        map<RandomListNode*, RandomListNode*> cache;
        while (cur1){
            cur2->next = new RandomListNode(cur1->label);
            cache[cur1] = cur2->next;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        cur1 = head;
        cur2 = pre->next;
        while (cur1){
            if (cur1->random){
                cur2->random = cache[cur1->random];
            }
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return pre->next;
    }
};

// method 2
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head) return head;
        RandomListNode *cur = head, *tmp=NULL, *cur1=NULL, *res=NULL;
        // step 1
        while (cur){
            tmp = cur->next;
            cur->next = new RandomListNode(cur->label);
            cur = cur->next;
            cur->next = tmp;
            cur = cur->next;
        }
        // step 2
        cur = head;
        while (cur){
            if (cur->random){
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        // step 3
        res = head->next;
        cur1 = head->next;
        cur = head;
        while (cur){
            tmp = cur1->next;
            if (tmp){
                cur1->next = tmp->next;
                cur1 = cur1->next;
            }
            cur->next = tmp;
            cur = cur->next;
        }
        return res;
    }
};

160.Intersection of Two Linked Lists

题目大意
- 给定两个有公共部分的单链表，找出单链表的交叉点
思路
- 将两个单链表当做循环链表
  - 如果两个链表长度相同，那么两个指针相遇的位置即为交叉点
  - 如果长度不同，一个大圈一个小圈，循环遍历，一定有某个时刻会相遇到交叉点
  - 在两条链表后面加入一个空节点，如果两个链表相遇在空节点，说明两个链表没有交点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *a = headA, *b = headB;
        if (a == NULL || b == NULL) return NULL;
        while(a!=b){
            if (a == NULL){
                a = headA;
            }else{
                a = a->next;
            }
            if (b == NULL){
                b = headB;
            }else{
                b = b->next;
            }
        }
        return a;
    }
};

141.Linked List Cycle

142.Linked List Cycle II

题目大意

判断一个链表是否有环
如果一个链表有环，找到环的入口

思路

有环
1. 使用快慢指针
2. 如果相遇则有环，否则fast到达尾部(NULL)
入口
1. 相遇位置为(km)
2. 开始节点到入口(n-m)
3. 相遇位置到入口需要走的路径长度为(m - (km-(n-m))) = n - km
4. 所以必然会相遇在入口节点

// 141
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head==NULL) return false;
        ListNode *fast=head, *slow=head;
        while (fast!=NULL){
            if (fast->next!=NULL)
                fast = fast->next->next;
            else
                return false;
            slow = slow->next;
            if (slow == fast)
                return true;
        }
        return false;
    }
};

// 142
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head==NULL) return head;
        ListNode *slow=head, *fast=head;
        while (fast!=NULL){
            if (fast->next!=NULL)
                fast = fast->next->next;
            else
                return NULL;
            slow = slow->next;
            if (slow == fast)
                break;
        }
        if (fast == NULL)
            return fast;
        fast = head;
        while (fast!=slow){
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

287. Find the Duplicate Number

题目大意

给定一个包含n+1个整数（[1,n]）的数组，假设只有一个重复数字，要求找到这个重复的数字。

思路

本身这个题目不算难，用hash或者排序都可以做，但是要求不能改变原数组、空间复杂度为O(1)、时间复杂度低于o(n^2)，这样就不好做了。

142. Linked List Cycle II类似于这道题的解法。
双指针方法
1. 设置low指针和fast指针，low每次走一步，fast每次走两步；
2. 存在环必然会相遇，设相遇时low走了k步，环的长度为r，则2k-k = nr；
3. 环入口到相遇位置距离为m，数组开始位置到环入口位置的距离为s，则k - s =m, nr - s = m, s = (n-1)r + (r-m)
4. 由上式可知，相遇后，如果fast再从0位置开始，low在相遇位置开始，low和fast都以一步为步长前进，则会相遇到环入口，而环入口上一个位置则为重复的数。
5. 指针从不同位置开始，结果会略微不同，需要注意。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = nums[0], fast = nums[nums[0]];
        /* 整数是1到n，而重复的指针下一步会指到相同的位置，
		 *所以必然会形成一个循环，因此可以通过步长不同的指针去找到这个循环 
		 *如果是这样开始的话，2k-k-1=nr, k-s=m, nr-1-s=m, -> s = (n-1)r+(r-m)+1
		 * 所以fast需要从0开始，而不能从nums[0]开始 
		 */ 
        while (low != fast){
			low = nums[low];
			fast = nums[nums[fast]];
			cout << low << " " << fast << endl;
        }
        /*可以证明，low在第一次meet的位置，fast从第一个位置开始 
         *同时以一步移动，最后会相遇在相同的那个数
         */
        fast = 0;
        while (low != fast){
			low = nums[low];
			fast = nums[fast];
			cout << low << " " << fast << endl; 
        }
        return fast;
    }
};

// 和循环链表找入口的题下标保持一致
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int low = nums[0], fast = nums[0];
        while (true){
            low = nums[low];
            fast = nums[nums[fast]];
            if (low == fast)
                break;
        }
        low = nums[0];
        while (low != fast){
            low = nums[low];
            fast = nums[fast];
        }
        return low;
    }
};

234. Palindrome Linked List

题目大意

给定一个单链表，判断是否是回文链表。要求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:
    bool isPalindrome(ListNode* head) {
        int n = 0, count=0;
        ListNode *t = head;
        while (t){
            n++;
            t = t->next;
        }
        ListNode *p1=NULL, *p2 = head;
        count = n / 2;
        while (count > 0){
            ListNode *tmp = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = tmp;
            count--;
        }
        if (n % 2){
            p2 = p2->next;   
        }
        while (p1 != NULL && p2 != NULL){
            if (p1->val != p2->val)
                return false;
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};

BinaryTree

572.Subtree of Another Tree

题目大意

给定两棵二叉树s和t，判断t是否是a的子树。

思路

二叉树问题基本都可以用递归解决

isSubtree：看看s和t是否是相同的，是就return true，否则，判断s->left和t或者s->right和t是否是相同的；
isSame：如果s->val == t->val 则递归判断left和right，否则直接返回false；

代码

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (!s && !t) return true;
        if ((s && !t) || (!s && t)) return false;
        if (isSame(s, t))
            return true;
        else{
            return isSubtree(s->left, t) || isSubtree(s->right, t);
        }
    }
private:
    bool isSame(TreeNode* s, TreeNode* t){
        if (!s && !t) return true;
        if ((s && !t) || (!s && t)) return false;
        if (s->val == t->val)
            return isSame(s->left, t->left) && isSame(s->right, t->right);
        else
            return false;
    }
};

144.Binary Tree Preorder Traversal

145.Binary Tree Postorder Traversal

题目大意

前序和后序遍历二叉树

思路

基础的二叉树前序、中序和后序遍历没什么好说的，但是这两个题目提供了新的思路，值得思考

前序遍历
- 不再沿着左子树一直搜索下去，每次将右节点和左节点入栈，下一次循环时，左节点出栈继续该过程，因此也达到了先序遍历的目的
- 中序不适合此种方式，因为栈中没有存储所有的左子节点，所以没办法等到最后一个最深处的左子节点被访问以后再访问父节点，所以无法完成中序遍历
后序遍历
- 以往的思路是，对当前节点做一个标记，如果是第二次访问，则该访问该节点，否则不访问该节点，继续入栈，但是如果节点本身无法做标记就没办法做了；
- 思路是先序遍历是 root-left-right，如果root-right-left这样遍历的话，结果反过来就是left-right-root，就是后序遍历的结果(可以递归去思考为什么reverse就是后序的结果)
- root-right-left有两种思路
  - 原来的先序遍历，先入栈右节点
  - 1中提到的先序遍历，同样先入栈左节点
- 补充一种做法：使用pre节点记录回溯时上一次访问的节点（两种情况，一种是遇到叶子节点会回溯，一种是第二次访问某个节点需要继续向上回溯），如果是当前节点的右节点，说明该节点是第二次访问，访问该节点，出栈即可。

代码

preorder

// new way to preoder binary tree
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) return res;
        stack<TreeNode*> ss;
        ss.push(root);
        while (!ss.empty()){
            root = ss.top();
            res.push_back(root->val);
            ss.pop();
            if (root->right) ss.push(root->right);
            if (root->left) ss.push(root->left);
        }
        return res;
    }
};

void nPreOrder(Node *bt){
	if (bt == NULL) return;
	stack<Node*> s;
	// 如果栈为空但是bt不为空则需要继续遍历
	while (!ss.empty() || bt){
		while (bt != NULL){
			cout << bt->val << " ";
			s.push(bt);
			bt = bt->lchild;
		}
		if (s.empty()) return;
		bt = s.top();
        bt = bt->rchild;
        s.pop();
	}
}

postorder

class Solution2 {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        stack<TreeNode*> ss;
        ss.push(root);
        while (!ss.empty()){
            root = ss.top();
            result.push_back(root->val);
            ss.pop();
            if (root->left) ss.push(root->left);
            if (root->right) ss.push(root->right);
        }
            
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        stack<TreeNode*> ss;
        while (!ss.empty() || root){
            while (root){
                result.push_back(root->val);
                ss.push(root);
                root = root->right;
            }
            if (!ss.empty()){
                root = ss.top();
                ss.pop();
            }
            if(root)
                root = root->left;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> s;
        // 用来记录上次访问的节点是什么，从而判断当前节点是不是第一次访问
        TreeNode* pre=NULL;
        while (root || !s.empty()){
            while (root){
                s.push(root);
                root = root->left;
            }
            if (s.empty()) break;
            root = s.top();
            if (root->right && root->right != pre){
                root = root->right;
            }else{
                // 包含两种情况，1. 是叶子节点 2. 是第二次访问的节点
                res.push_back(root->val);
                pre = root;
                s.pop();
                root = NULL;
            }
        }
        return res;
    }
};

二叉树路径和为某一值

112.Path Sum

题目大意
- 给定一棵二叉树和某个值，判断二叉树是否存在某条路径使得路径和为给定值。路径的起点为根节点，终点为叶子节点。
思路
- 递归
- 非递归
  - 非递归的方法，因为在遍历完左子树和右子树时才能pop掉当前节点，所以和后序遍历很相似
  - 三种后序遍历方法
    - 标记节点是第几次访问，如果是第二次访问，则visit该节点。如果节点无法标记做没法做
    - 使用left-right-root的reverse是root-right-left，稍微修改先序遍历代码，得到root-right-left的访问结果，再翻转即可
    - 使用pre节点，记录回溯时刻当前节点的上一次访问的节点，如果是右子树，那么是第二次访问，visit，否则是第一次访问，继续保留在栈中
  - 显然，这个问题只能用第三种方法做。
代码

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        stack<TreeNode*> ss;
        TreeNode* pre=NULL;
        int s = 0;
        while (root || !ss.empty()){
            while (root){
                s += root->val;
                ss.push(root);
                root = root->left;
            }
            if (ss.empty()) break;
            root = ss.top();
            if ((!root->left && !root->right) && s==sum)
                return true;
            if (root->right && root->right != pre){
                root = root->right;
            }else{
                pre = root;
                s -= root->val;
                ss.pop();
                root = NULL;
            }
        }
        return false;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if ((root->val == sum) && (!root->left && !root->right)) return true;
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
};

113.Path Sum II

题目大意
- 给定一颗二叉树和给定值，要求找到所有的和为给定值的路径，路径定义和上题一样
思路
- 有了上题基础，直接递归思路，设置两个引用参数，用于存储路径即可
代码

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> tmp;
        if (!root) return res;
        findPath(res, tmp, root, sum);
        return res;
    }
private:
    void findPath(vector<vector<int>>& res, vector<int>& tmp, TreeNode* root, int sum){
        if (!root) return;
        if ((root->val == sum) && (!root->left && !root->right)){
            tmp.push_back(root->val);
            res.push_back(tmp);
            tmp.pop_back();
            return;
        }
        tmp.push_back(root->val);
        findPath(res, tmp, root->left, sum-root->val);
        findPath(res, tmp, root->right, sum-root->val);
        tmp.pop_back();
    }
};

437. Path Sum III

题目大意
- 给定二叉树和给定值，求和为给定值的路径个数，路径的起始和结束不一定是跟节点和叶子节点，但是肯定是自上而下的。
思路
- 这道题和求解Binary Tree Maximum Path Sum ,相当于遍历二叉树每个节点，以每个节点作为起始点，搜索是否存在相应的路径
代码

class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (!root) return 0;
        return totalPath(root, sum, 0) + pathSum(root->left, sum) + pathSum(root->right, sum);
        
    }
private:
    int totalPath(TreeNode* root, int sum, int s){
        if (!root) return 0;
        int total = 0;
        if (s+root->val == sum)
            total++;
        return total + totalPath(root->left, sum, s+root->val) + totalPath(root->right, sum, s+root->val);
    }
};

255.Verify Preorder Sequence in Binary Search Tree

题目大意
- 给定一个序列，判断是否是搜索二叉树的后序遍历（剑指offer上是后序）
思路
- 序列的最后一个数是根节点，将n-1的序列分为小于和大于两部分，如果找到分界点后，大于的部分出现了小于根节点的数则不符合要求；
- 递归左子树和右子树

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return false;
        int n = sequence.size(), i=0, j=0;
        bool flagLeft=true, flagRight=true;
        for (; i!=n-1; ++i){
            if (sequence[i] > sequence[n-1])
                break;
        }
        j = i;
        for (; j!=n-1; ++j){
            if (sequence[j] < sequence[n-1])
                return false;
        }
        vector<int> left(sequence.begin(), sequence.begin()+i);
        vector<int> right(sequence.begin()+i, sequence.end()-1);
        if(!left.empty()) 
            flagLeft = VerifySquenceOfBST(left);
        if (!right.empty())
            flagRight = VerifySquenceOfBST(right);
        return (flagLeft && flagRight);
    }

114.Flatten Binary Tree to Linked List

题目大意
- 将一棵二叉树转换为链表，要求in-place
思路
- 递归：先将链表的末端（右侧）完成，递归到最左侧
- 非递归
  - 遍历所有节点
  - 保存好root右子树的
  - root右子树指向左子树

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root)
            return;
        flatten(root->right);
        flatten(root->left);
        root->right = pre;
        root->left = NULL;
        pre = root;
    }
private:
    TreeNode* pre;
};

class Solution {
public:
    void flatten(TreeNode* root) {
        if (!root) return;
        while (root){
            if (!root->left){
                root = root->right;
            }else{
                TreeNode* tmp = root->left;
                while (tmp->right){
                    tmp = tmp->right;
                }
                tmp->right = root->right;
                root->right = root->left;
                root->left = NULL;
                root = root->right;
            }
        }
    }
};

二叉搜索树与双向链表

题目大意
1. 将一棵二叉搜索树转换为双向链表
思路
1. 很上一题很相似，都是二叉树转换为链表，上题是先序遍历，该题是中序遍历
2. 分为三个部分，根节点、左节点和右节点
  - 将左子树排序好返回最大的链表节点
  - 将根节点插入到链表中(最后一个节点)
  - 将右节点当做根节点递归
代码

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if(!pRootOfTree) return pRootOfTree;
        TreeNode* last = NULL;
        convertNode(pRootOfTree, &last);
        TreeNode* tmp = last;
        while (tmp != NULL && tmp->left != NULL)
            tmp = tmp->left;
        return tmp;
    }
private:
    void convertNode(TreeNode* node, TreeNode** last){
        if (node == NULL)
            return;
        TreeNode* cur = node;
        if (node->left)
            convertNode(node->left, last);
        cur->left = *last;
        if (*last)
            (*last)->right = cur;
        *last = cur;
        if (cur->right)
            convertNode(cur->right, last);
    }
};

104.Maximum Depth of Binary Tree

111.Minimum Depth of Binary Tree

题目大意

题目很简单，得到一颗二叉树的最大深度和最小深度。深度的定义是根节点到叶子节点的路径长度。

思路

递归思路
- 1 + 以当前节点为根节点的最小或最大深度
层次遍历
- 如果节点是左右子树均为NULL，则为叶子节点
- 最小，第一次遇到叶子节点即返回深度
- 最大，遍历所有，返回最大深度即可

代码

min

class Solution1 {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (!root->left) return 1+minDepth(root->right);
        if (!root->right) return 1+minDepth(root->left);
        return 1+min(minDepth(root->right), minDepth(root->left));
    }
};

// 使用队列，用额外的空间存储层数相关信息
class Solution2 {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<map<TreeNode*, int> > q;
        int layer = 0;
        TreeNode* cur = root;
        while (cur != NULL || !q.empty()){
            if (cur != NULL){
                if (cur->left != NULL){
                    map<TreeNode*, int> m1;
                    m1[cur->left] = layer++;
                    q.push(m1);
                }
                if (cur->right != NULL){
                    map<TreeNode*, int> m2;
                    m2[cur->right] = layer++;
                    q.push(m2);
                }
            }
            if (!q.empty()){
                map<TreeNode*, int> m;
                m = q.front();
                cur = (m.begin())->first;
                layer = m[cur];
                q.pop();
                if (!(cur->left || cur->right)) 
                    return m[cur];
                
            }
        }
        return layer;
    }
};

// 比较巧妙的记录层数信息，每一次都遍历完队列中的节点，这些节点都是属于同一层的c
class Solution3 {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<TreeNode*> q;
        TreeNode* cur = root;
        q.push(cur);
        int layer = 0;
        while (!q.empty()){
            ++layer;
            int k = q.size();
            for (int i=0; i!=k; ++i){
                cur = q.front();
                q.pop();
                if (cur->left) q.push(cur->left); // if we judge the push TreeNode is not NULL, 
                                                  // then you couldn't judge the node is not NULL outspace
                if (cur->right) q.push(cur->right);
                if (!(cur->left || cur->right))
                    return layer;
            }
        }
        return 0;
    }
};

max

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (!root->left) return 1+maxDepth(root->right);
        if (!root->right) return 1+maxDepth(root->left);
        return 1+max(maxDepth(root->left), maxDepth(root->right));

    }
};

class Solution1 {
public:
    int maxDepth(TreeNode* root) {
        if (root == NULL) return 0;
        queue<TreeNode*> q;
        TreeNode* cur = root;
        q.push(cur);
        int layer = 0;
        while(!q.empty()){
           layer++;
           int k = q.size();
           for (int i=0; i!=k; ++i){
               cur = q.front();
               q.pop();
               if (cur->left) q.push(cur->left);
               if (cur->right) q.push(cur->right);
           }
        }
        return layer;

    }
};

222.Count Complete Tree Nodes

题目大意

给定一颗完全二叉树，求节点个数。要求复杂度低于O(n)

思路

如果左子树右子树高度相等，那么不需要判断直接根据高度计算。否则，递归计算左子树和右子树的节点数。

因为一定存在较多满二叉树，所以时间复杂度低于O(n)。仔细想想，不存在太坏的情况。

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        TreeNode *l=root, *r=root;
        int lh=0, rh = 0;
        while(l) {
            l = l->left;
            lh++;
        }
        while(r) {
            r = r->right;
            rh++;
        }
        if (lh == rh) return pow(2, lh) - 1;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

236.Lowest Common Ancestor of a Binary Tree

题目大意

找到一棵二叉树两点节点最近公共祖先。

思路

遍历找到分别到两个节点的路径，比较两个路径，第一个不同节点的上一个节点则为公共祖先
如果root为p则返回root，如果root为q则返回root，如果root为空则返回空(其实也就是返回了p或q是否在子树里)
1. 否则，递归左、右子树
2. 如果q、p在同一个子树那么返回的就是公共祖先，否则如果p和q分别在两个子树，则root是公共祖先

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return root;
        if (root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if (left && right)
            return root;
        if (!left)
            return right;
        else
            return left;
    }
};

235.Lowest Common Ancestor of a Binary Search Tree

题目大意

给定一个二叉搜索树及两个节点，找到节点的最近公共祖先。

思路

利用BST的特点，如果p和q的值跟root比一大一小，则root为最近公共祖先，否则递归左子树或者右子树。

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val < root->val && q->val < root->val)
            return lowestCommonAncestor(root->left, p, q);
        if (p->val > root->val && q->val > root->val)
            return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};

124.Binary Tree Maximum Path Sum

题目大意

给定一棵二叉树，找到最大的路径和。路径可以试从child-root-child

思路

类比求数组的最大连续子数组和

用res记录最大路径和，每一层递归记录以root为中间节点的最大和(root->val + max(0, left) + max(0, right))

返回的是root-child的单向最大和，因为需要和parent组成child-root-child路径

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        findMax(root, res);
        return res;
    }
private:
    int findMax(TreeNode* root, int& res){
        if (root==NULL) return 0;
        int left = findMax(root->left, res);
        int right = findMax(root->right, res);
        
        if (left < 0) left = 0;
        if (right < 0) right = 0;
        if (root->val + left + right > res) res = root->val + left + right;
        return root->val + max(left, right);
    }
};

root-child的最大路径和

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        findMax(root, res);
        return res;
    }
private:
    int findMax(TreeNode* root, int& res){
        if (root==NULL) return 0;
        int left = findMax(root->left, res);
        int right = findMax(root->right, res);
        
        if (left < 0) left = 0;
        if (right < 0) right = 0;
        int cur = root->val + max(left, right);
       	res = max(res, cur);
        return res;
    }
};

116. Populating Next Right Pointers in Each Node

117. Populating Next Right Pointers in Each Node II

题目大意

给定一棵满二叉树，在水平方向上的前一个节点有next指针指向下一个节点；

如果是一颗普通二叉树呢

思路

满二叉树
1. 当前节点的left指向right
2. 当前root节点的right的next指向root->next的left节点
3. 递归左子树和右子树
普通二叉树
1. root的right要指向的节点隔了好几个节点（while(root->next)找到root->next->left或者root->next->right不为空的节点）
2. 上面的循环要求右子树先形成next，所以先递归右子树

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root==NULL) return;
        if (root->next){
            if (root->right && root->next->left)
                root->right->next = root->next->left;
        }
        if (root->left && root->right){
            root->left->next = root->right;
        }
        connect(root->left);
        connect(root->right);
    }
};

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
        int flag = 0;
        TreeLinkNode* tmp = root;
        // 因为二叉树不是完全二叉树，可能水平方向隔了很多个节点才有下一个节点，所以需要一直循环root->next
        // 直到找到下一个节点或者null
        TreeLinkNode* left = tmp->right ? tmp->right : tmp->left;
        while (tmp->next){
            TreeLinkNode* right = tmp->next->left ? tmp->next->left : tmp->next->right;
            if (left && right){
                left->next = right;
                flag = 1;
            }
            if (flag == 1)
                break;
            tmp = tmp->next;
        }
        if (root->left && root->right){
            root->left->next = root->right;
        }
        
        // 可能root右侧隔了很多个空节点才有节点，所以先调整好右边，在到左边 一直循环next找下去
        connect(root->right);
        connect(root->left);
    }
};

Tree

208.Implement Trie (Prefix Tree)

题目大意

实现一棵字典树

思路

一个trie node，用于存储当前的字母以及当前字母是否为单词的结束

class TrieNode {
public:
    TrieNode* next[26];
    bool is_word;
    
    TrieNode(bool word = false){
        memset(next, 0, sizeof(next));
        is_word = word;
    }
};

class Trie {
public:
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        TrieNode* p = root;
        for (int i=0; i!=word.size(); ++i){
            if (p->next[word[i]-'a'] == NULL){
                p->next[word[i]-'a'] = new TrieNode();
            }
             p = p->next[word[i]-'a'];
        }
        p->is_word = true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        if (word.empty()) return true;
        TrieNode* p = root;
        for (int i=0; i!=word.size(); ++i){
            if (p->next[word[i]-'a'] != NULL)
                p = p->next[word[i]-'a'];
            else
                return false;
        }
        return p->is_word;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        TrieNode* p = root;
        for (int i=0; i!=prefix.size(); ++i){
            if (p->next[prefix[i]-'a'] != NULL)
                p = p->next[prefix[i]-'a'];
            else
                return false;
        }
        return true;
    }
private:
    TrieNode* root;
};

/**
 * 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);
 */

116. Populating Next Right Pointers in Each Node

题目大意

给定一棵满二叉树，要求每个节点有个next指针，指向右侧的节点

思路

递归处理，对于每个节点root，需要做两件事情

将右子树的next指向next的左子树 root->right->next = root->next->left
将左子树next指向右子树

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root==NULL) return;
        if (root->next){
            if (root->right && root->next->left)
                root->right->next = root->next->left;
        }
        if (root->left && root->right){
            root->left->next = root->right;
        }
        connect(root->left);
        connect(root->right);
    }
};

117. Populating Next Right Pointers in Each Node II

题目大意

将上题中的满二叉树改为普通二叉树

思路

两个问题

水平方向上当前节点next需要指向的节点可能隔了好几个空节点，怎么办
- 可以考虑一直root->next循环，直到找到非空的节点
如何保证水平方向右边的next指针是已经建立好的（这样才可以循环找到非空节点）
- 先递归右子树，再递归左子树

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (root == NULL) return;
        int flag = 0;
        TreeLinkNode* tmp = root;
        // 因为二叉树不是完全二叉树，可能水平方向隔了很多个节点才有下一个节点，所以需要一直循环root->next
        // 直到找到下一个节点或者null
        TreeLinkNode* left = tmp->right ? tmp->right : tmp->left;
        while (tmp->next){
            TreeLinkNode* right = tmp->next->left ? tmp->next->left : tmp->next->right;
            if (left && right){
                left->next = right;
                flag = 1;
            }
            if (flag == 1)
                break;
            tmp = tmp->next;
        }
        if (root->left && root->right){
            root->left->next = root->right;
        }
        
        // 可能root右侧隔了很多个空节点才有节点，所以先调整好右边，在到左边 一直循环next找下去
        connect(root->right);
        connect(root->left);
    }
};

stack&queue

155.min stack

题目大意
- 实现一个栈，包括push、pop、top、和min方法，min方法是返回栈中最小值
思路
- 用一个数组存排序好的栈中的数，这种方法略笨重，时间复杂度也高；
- 两个栈ss和m_ss，ss用来存储栈数据，m_ss用来存储当前的最小值(用栈来实现很巧妙)
  - m_ss入栈的时候永远是当前的最小值，如果新压入栈数大于栈顶元素则压入栈顶元素，否则压入该元素
  - 出栈时，如果当前数是最小值，那么m_ss出栈了，m_ss栈顶位置是之前的最小值；如果当前数不是最小值，则m_ss出栈不影响之后的最小值。
代码

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        ss.push(x);
        if (m_ss.empty() || m_ss.top() > x)
            m_ss.push(x);
        else
            m_ss.push(m_ss.top());
    }
    
    void pop() {
        assert(!ss.empty());
        ss.pop();
        m_ss.pop();
    }
    
    int top() {
        assert(!ss.empty());
        return ss.top();
    }
    
    int getMin() {
        assert(!m_ss.empty());
        return m_ss.top();
    }
private:
    stack<int> ss;
    stack<int> m_ss;
};

// 数组版本
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        ss.push(x);
        insert(x);
    }
    
    void pop() {
        int tmp = ss.top();
        ss.pop();
        remove(tmp);
    }
    
    int top() {
        if (!ss.empty())
            return ss.top();
        else
            return INT_MIN;
    }
    
    int getMin() {
        if (!ss.empty())
            return minVec[0];
        else
            return INT_MIN;
    }
private:
    void insert(int x){
        int low = findIndex(x);
        minVec.insert(minVec.begin()+low, x);
    }
    
    void remove(int x){
        int low = findIndex(x);
        minVec.erase(minVec.begin()+low, minVec.begin()+low+1);
    }
    
    int findIndex(int x){
        int low=0, high=minVec.size()-1, mid=0;
        while (low<=high){
            mid = low + (high - low) / 2;
            if (minVec[mid] < x)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return low;
    }
    
    stack<int> ss;
    vector<int> minVec;
};

Dfs&bfs

22.Generate Parentheses

题目大意
- 给定一个数n，表示是括号的个数，输出包含n个括号的组合
思路
- 这种排列组合类的题，dfs是万能，需要考虑
  - 左括号和右括号的个数
  - 当前字符串中加入右括号时，右括号个数不能大于左括号个数

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        dfs(res, "", n, n);
        return res;
    }
private:
    void dfs(vector<string>& res, string tmp, int left, int right){
        if (left==0 && right==0){
            res.push_back(tmp);
            return;
        }
        if (left > 0)
            dfs(res, tmp+"(", left-1, right);
        if (right > 0 && right > left)
            dfs(res, tmp+")", left, right-1);
    }
};

51. N-Queens

52. N-Queens II

问题描述
- $n\times n$的棋盘，放上n个皇后，要求每一行、每一列、45度和135度方向均不能存在两个皇后，问有多少种放法，以及输出每种放置方法。
回溯法
- 每一层放置一个皇后，遍历n个位置，如果该位置合法，进入下一行放置下一个皇后
- dfs思路

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> chess(n, string(n, '.'));
        dfs(res, chess, 0, n);
        return res;
    }
private:
    void dfs(vector<vector<string>>& res, vector<string>& chess, int row, int n){
        if (row == n){
            res.push_back(chess);
            return;
        }
        for (int col=0; col!=n; ++col){
            if (isvalid(chess, row, col, n)){
                chess[row][col] = 'Q';
                dfs(res, chess, row+1, n);
                chess[row][col] = '.';
            }
        }
    }
    bool isvalid(vector<string>& chess, int row, int col, int n){
        for (int i=0; i!=row; ++i){
            if (chess[i][col] == 'Q')
                return false;
        }
        for (int x=row-1, y=col-1; x>=0 && y>=0; --x, --y){
            if (chess[x][y] == 'Q')
                return false;
        }
        for (int x=row-1, y=col+1; x>=0 && y<n; --x, ++y){
            if (chess[x][y] == 'Q')
                return false;
        }
        return true;
    }

};

class Solution {
public:
    int totalNQueens(int n) {
        int res=0;
        vector<string> chess(n, string(n, '.'));
        dfs(res, chess, 0, n);
        return res;
    }
private:
    void dfs(int& res, vector<string>& chess, int row, int n){
        if (row == n){
            res++;
            return;
        }
        for (int col=0; col!=n; ++col){
            if (isvalid(chess, row, col, n)){
                chess[row][col] = 'Q';
                dfs(res, chess, row+1, n);
                chess[row][col] = '.';
            }
        }
    }
    bool isvalid(vector<string>& chess, int row, int col, int n){
        for (int i=0; i!=row; ++i){
            if (chess[i][col] == 'Q')
                return false;
        }
        for (int x=row-1, y=col-1; x>=0 && y>=0; --x, --y){
            if (chess[x][y] == 'Q')
                return false;
        }
        for (int x=row-1, y=col+1; x>=0 && y<n; --x, ++y){
            if (chess[x][y] == 'Q')
                return false;
        }
        return true;
    }
};

trick

54.Spiral Matrix

题目大意
- 给定一个二维数组，要求螺旋打印数组中的数
思路
- 每一圈的左上角的点都是(start, start)，start 2 < m && start 2<n
- 每一圈，有四个方向，有相应的限制条件，在相应限制条件下打印即可
代码

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (matrix.empty() || matrix[0].empty()) return res;
        int row=matrix.size(), col=matrix[0].size();
        int start=0, endRow=0, endCol=0;
        while (start*2<row && start*2<col){
            endRow = row - start - 1;
            endCol = col - start - 1;
            for (int i=start; i<=endCol; ++i)
                res.push_back(matrix[start][i]);
            if (start < endRow){
                for (int i=start+1; i<=endRow; ++i)
                    res.push_back(matrix[i][endCol]);
            }
            if (start < endRow && start < endCol){
                for (int i=endCol-1; i>=start; --i)
                    res.push_back(matrix[endRow][i]);
            }
            if (start < endRow-1 && start < endCol){
                for (int i=endRow-1; i>start; --i)
                    res.push_back(matrix[i][start]);
            }
            start++;
        }
        return res;
        
    }
};

169.Majority Element

题目大意
- 给定一个长度为n的数组，找出数组中出现次数大于n/2的数
思路
- 排序
- majority element的次数
- 随机找个数，判断是否为majority element
- Bit Manipulation
  - 计算每一位是否是majority
代码

// 2
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int result = nums[0], times = 1;
        for (int i=1; i!=nums.size(); ++i){
            if (result != nums[i]){
                times--;
                if (times < 0){
                    result = nums[i];
                    times = 1;
                }
            }
            else
                times++;
        }
        return result;
    }
};

// 4
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int major = 0, n = nums.size();
        for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
            int bitCounts = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] & mask) bitCounts++;
                if (bitCounts > n / 2) {
                    major |= mask;
                    break;
                }
            }
        } 
        return major;
    } 
};

229.Majority Element II

题目大意
- 给定一个长度为n的数组，找出数组中出现次数大于n/3的数
- 要求线性时间复杂度，空间复杂度为O(1)
思路
- Moore Majority Voting
- 使用res1和res2记录当前两个数，count1和count2记录当前两个数出现的次数
- 可行性分析
  - 如果存在两个满足条件的数，那么剩下的数出现次数将少于n/3，所以最后剩下的两个数一定是次数大于n/3的数
  - 如果只存在一个满足条件的数a，则a出现次数t大于n/3，最多能减少的次数为(n-t)/2 < n/3，所以a必然能保留到最后(333331212)

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> res;
        int res1=0, count1=0, res2=0, count2=0;
        for (int i=0; i!=nums.size(); ++i){
            if (nums[i] == res1)
                count1++;
            else if (nums[i] == res2)
                count2++;
            else if (count1 == 0){
                res1 = nums[i];
                count1 = 1;
            }
            else if (count2 == 0){
                res2 = nums[i];
                count2 = 1;
            }
            else{
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i=0; i!=nums.size(); ++i){
            if (nums[i] == res1)
                count1++;
            if (nums[i] == res2)
                count2++;
        }
        if (count1 > nums.size()/3) res.push_back(res1);
        if (count2 > nums.size()/3 && res2 != res1) res.push_back(res2);
        return res;
    }
};

347.Top K Frequent Elements

题目大意
- 给定一个数组，找出出现频率最多的k个数
思路
- 先统计每个数出现次数
- 使用优先级队列排序，使优先级队列的大小为(n-k)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> cache1;
        vector<int> res, tmp;
        for (int i=0; i!=nums.size(); ++i){
            cache1[nums[i]]++;
        }
        priority_queue<pair<int, int>> q;
        for (map<int, int>::iterator it=cache1.begin(); it!=cache1.end(); ++it){
            q.push(make_pair(it->second, it->first));
            if (q.size() > cache1.size()-k){
                res.push_back(q.top().second);
                q.pop();
            }
        }
        return res;
    }
};

215.Kth Largest Element in an Array

题目大意
- 找到数组中第k大的元素
思路
- 堆
  - 维护一个k大小的最小堆(优先级队列)
  - 遍历完所有元素，堆顶元素即为k大的元素
- partition

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int> > q;
        for (int i=0; i!=nums.size(); ++i){
            q.push(nums[i]);
            if (q.size() > k) q.pop();
        }
        return q.top();
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int s = 0, e = nums.size()-1, index = 0;
        while (true){
            index = partition(nums, s, e);
            if (index == nums.size()-k)
                break;
            else if (index < nums.size()-k){
                s = index+1;
            }else{
                e = index-1;
            }
        }
        return nums[index];
    }
private:
    int partition(vector<int>& nums, int s, int e){
        int tmp = nums[s];
        while (s < e){
        	// 注意快排时，交换以后s和e需要改变，否则遇到有重复数的数组会进入死循环
            while(s < e && nums[e] > tmp) --e;
            if (s < e)
                nums[s++] = nums[e];
            while(s < e && nums[s] < tmp) ++s;
            if (s < e)
                nums[e--] = nums[s];
        }
        nums[s] = tmp;
        return s;
    }
};

179.Largest Number

题目大意
- 给定一个数组，将数组中的数拼接成一个大数，求其中最大的数
思路
- 将数组中的数按照拼接的大小顺序排序
- 注意，拼接后的数可能会非常大，是一个大数问题，需要用字符串表示

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string> new_nums;
        string res = "";
        for (int i=0; i!=nums.size(); ++i)
            new_nums.push_back(to_string(nums[i]));
        sort(new_nums.begin(), new_nums.end(), compare);
        for (int i=0; i!=new_nums.size(); ++i)
            res += new_nums[i];
        while (res.size() > 1 && res[0] == '0')
            res.erase(0, 1);
        return res;
    }
  	// 给sort用的函数，必须是static或者在类外定义，否则sort无法访问
    bool static compare(string a, string b){
        return (a+b) > (b+a);
    }
};

264.Ugly Number II

题目大意
- 因子分解只有2、3和5的数称为丑数，给定n，求第n个丑数是多少。默认1为第一个丑数
思路
- 新的丑数都是由旧的丑数乘以2或3或5得到的
- 记录2或3或5乘到的位置，每次选取最小的即可

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n <= 1) return 1;
        vector<int> dp(1, 1);
        int l2=0, l3=0, l5=0;
        for (int i=0; i!=n; ++i){
            int tmp = min(dp[l2]*2, min(dp[l3]*3, dp[l5]*5));
            if (tmp == dp[l2]*2) l2++;
            if (tmp == dp[l3]*3) l3++;
            if (tmp == dp[l5]*5) l5++;
            dp.push_back(tmp);
        }
        return dp[n-1];
    }
};

315.Count of Smaller Numbers After Self

题目大意
- 给定一个数组，返回一个数组，每个位置表示在该数右边比该数小的个数
思路
- 暴力， $O(n^2)$
- 巧妙使用归并排序
  - 学习到递归形式的归并排序，简单好写
  - 每一趟归并排序时，数组两部分都是有序的，所以左侧的较大的数的逆序数是建立在较小数的基础上，比如a[2]是在a[1]的逆序数上开始进行累加，避免了重复计算
  - 该题要求返回每个位置的逆序数，所以不能直接对原数组进行归并排序，采用了对原数组的index进行归并排序；

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n=nums.size();
        vector<int> res(n, 0), index(n, 0);
        for (int i=0; i!=n; ++i)
            index[i] = i;
        mergeCount(nums, res, index, 0, n);
        return res;
    }
private:
    void mergeCount(vector<int>& nums, vector<int>& res, vector<int>& index, int s, int n){
        if (s < n-1){
            int count = 0, mid = s + (n - s) / 2;
            
            mergeCount(nums, res, index, s, mid);
            mergeCount(nums, res, index, mid, n);
            //cout << "== " << s << " " << n << endl;
            int id1 = s, id2 = mid;
            // 避免需要另一个vector存储排序好的数组
            vector<int> tmp;
            while (id1<mid || id2<n){
                if (id2 == n || (id1 < mid && nums[index[id1]] <= nums[index[id2]])){
                    tmp.push_back(index[id1]);
                    //cout << 'a' << id1 << " " << index[id1] << " " << count << endl;
                    res[index[id1]] += count;
                    id1++;
                }else{
                    tmp.push_back(index[id2++]);
                    count++;
                    //cout << 'b' << id2 << " " << count << endl;
                }
            }
            move(tmp.begin(), tmp.end(), index.begin()+s);
        }
    }
};

数组中的逆序对

题目大意
- 返回数组中逆序对个数
思路
- 归并排序

class Solution {
public:
    int InversePairs(vector<int> data) {
        int n = data.size();
        vector<int> tmp(n, 0);
        return mergeCount(data, tmp, 0, n)%1000000007 ;
    }
private:
    long long mergeCount(vector<int>& data, vector<int>& tmp, int s, int n){
        int length = n - s;
        long long count = 0, left = 0, right = 0;
        if (length > 1){
            int mid = s + length / 2;
            left = mergeCount(data, tmp, s, mid);
            right = mergeCount(data, tmp, mid, n);

            int s1 = mid-1, s2 = n-1, i=n-1;
            while (s1 >= s && s2 >= mid){
                if (data[s1] > data[s2]){
                    count = count + s2 - mid + 1;
                    tmp[i--] = data[s1--];
                }else
                    tmp[i--] = data[s2--];
            }
            while (s1 >= s)
                tmp[i--] = data[s1--];
            while (s2 >= mid)
                tmp[i--] = data[s2--];
            for (int k=s; k!=n; ++k)
                data[k] = tmp[k];
        }
        return left+right+count;
    }
};

补充
- 取余和取模
  1. 步骤
    - c = a / b
    - r = a - c * b
  2. 区别
    - 取余 c取的时候往0方向取
    - 取模 c取的时候往负无穷方向取

1.Two Sum

题目大意

给定一个整数数组和一个目标和，返回数组中加起来和是目标和的两个数的下标。

思路

如果暴力搜索的话，需要 $O(n^2)$ 复杂度，可以遍历过程中，用map存储，key是值，value是下标。如果能够在map中找到(target-nums[i])，则将对应的下标和i返回即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> cache;
        vector<int> res;
        for (int i=0; i!=nums.size(); ++i){
            if (cache.find(target - nums[i]) != cache.end()){
                res.push_back(cache[nums[i]]);
                res.push_back(i);
                return res;
            }
            cache[nums[i]] = i;
        }
    return res;
    }
};

191.Number of 1 Bits

题目大意

给定一个32位无符号整数，求该整数二级制形式1的个数。

思路

遍历每一位，记录1的个数即可。

不要使用除操作，耗时较久，使用移位和与操作。

如果是有符号整数，可能会导致循环无法结束，可以左移1来遍历。

n & (n-1)的操作能够将最右边的1变为0，可以将所有的1都变为0，需要的次数即为1的个数。

代码

class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int sum = 0;
        while (n){
            if (n & 1)
                ++sum;
            n = n >> 1;
        }
        return sum;
    }
};

class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int sum = 0;
        while (n){
            ++sum;
            n = (n-1) & n;
        }
        return sum;
    }
};

// consider signed int
class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned int sum = 0, flag = 1;
        while (flag){
            if (flag & n)
                ++sum;
            flag = flag << 1;
        }
        return sum;
    }
};

231.Power of Two

326.Power of Three

342.Power of Four

题目大意

给定一个整数，求是否是2、3、4的整数次方。

思路

基础思路
- 一直除2(3,4)，直到有余数，判断此时n是否为1即可，如果不为1，说明不是整数次幂；
不用循环的解法
- 2
  - n & (n-1) == 0 则为整数幂
  - $2^{30}$%n == 0，因为$2^{30-k} 2^k = 2^{30}$，所以如果整除n，则为2的整数幂
- 3
  - $3^{19}$%n == 0，因为$3^{19-k} 3^k = 3^{19}$，所以如果整除n，则为3的整数幂
- 4
  - 满足三个条件
    - n > 0
    - n & (n - 1) == 0
    - (n - 1) % 3 == 0：在满足1、2前提下，只会出现2的整数幂和4的整数幂，而$4^n - 1 = (2^k-1)(2^k+1)$ ，而连续出现的三个数必定有一个是整除3的，而肯定不是$2^k$，$4^n-1$一定整除3，同时，$2^{2k+1}-1$必定不能整除3(为什么)

代码

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n > 0 && (n & (n-1) == 0));
    }
};

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n<=0) return false;
        while (!(n%3)){
            n = n / 3;
        }
        return (n==1);
    }
};

class Solution {
public:
    bool isPowerOfThree(int n) {
        int a = pow(3,19);
        return ((n>0) && ( a % n == 0));
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        if (num <= 0) return false;
        while (!(num % 4)){
            num = num / 4;
        }
        return (num == 1);
    }
};

class Solution {
public:
    bool isPowerOfFour(int num) {
        return (num > 0 && !(num & (num - 1)) && ((num - 1) % 3 == 0));
    }
};

523.Continuous Subarray Sum

题目大意

给定一个非负的数组，找到连续的子数组的和为k的整数倍

思路

要求时间复杂度为O(n)
考虑如果0~i位置元素和除以k的余数为res，如果0~j位置元素和除以k的余数也为res，同时i+1<j，那么i+1~j即为和可以整除k的子数组
考虑k为0的情况

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        map<int, int> cache;
        cache[0] = -1;
        int sum = 0, res = 0;
        for (int i=0; i!=nums.size(); ++i){
            sum += nums[i];
            // 如果k==0，那么只有0才满足要求
            if (k == 0) res = sum;
            else res = sum % k;
            if (cache.find(res) != cache.end()){
                if (cache[res]+1 < i)
                    return true;
            }else
                cache[res] = i;
        }
        return false;
    }
};

135.Candy

题目大意

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

* Each child must have at least one candy.
* Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

思路

一个人分多少糖果取决于左边和右边的人，而左右边的人又有所依赖；
考虑每次只保证一侧是合法的，遍历两次即可
- 第一遍，从左到右，如果右边大于左边则给右边糖果个数+1
- 第二遍，从右到左，如果左边大于右边则给左边糖果+1

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> cache(n, 1);
        for (int i=1; i!=n; ++i){
            if (ratings[i] > ratings[i-1])
                cache[i] = cache[i-1] + 1;
        }
        for (int i=n-2; i>=0; --i){
            if (ratings[i] > ratings[i+1] && cache[i] <= cache[i+1])
                cache[i] = cache[i+1] + 1;
        }
        return accumulate(cache.begin(), cache.end(), 0);
    }
};

骰子和概率

题目大意

返回n个骰子随机投，每种和的概率

思路

dfs
使用两个数组记录，n个骰子和的概率是在n-1个骰子和概率基础上计算的
- n个骰子，和为m的次数是n-1个骰子和为m-1、m-2…m-6的和
- 类似dp

void printProb(int n){
    int maxSum = n * 6, flag = 0;
    vector<vector<int>> cache(2, vector<int>(maxSum+1, 0));

    for (int i=1; i<=6; ++i)
        cache[flag][i] = 1;

    flag = 1 - flag;
    for (int k=2; k<=n; ++k){
        for (int i=1; i<k; ++i)
           cache[flag][i] = 0;
        for (int i=k; i<=k*6; ++i){
            cache[flag][i] = 0;
            for (int j=1; j<=i && j<=6; ++j){
                cache[flag][i] += cache[1-flag][i-j];
            }
        }
        flag = 1 - flag;
    }    
    int total = pow(6, n), p = 0;
    for (int i=n; i!=maxSum+1; ++i){
        cout << i << " " << (double)cache[1-flag][i] / total << endl;
        p += (double)cache[1-flag][i];
    }
    cout << "total: " << p << endl;
}

扑克牌的顺子

题目大意

判断抽取的牌是否为顺子，A为1，J为11，Q为12，K为13，大小王是0，可以替代任何数

思路

先排序，判断0的个数，和gap的个数，如果gap的个数大于0的个数，则返回false

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        if (numbers.empty()) return false;
        sort(numbers.begin(), numbers.end());
        int zeroNum = 0, gapNum = 0;
        for (int i=0; i!= numbers.size(); ++i){
            if (numbers[i] == 0)
                zeroNum++;
            if (i!=0 & numbers[i-1]!=0){
                if (numbers[i-1] == numbers[i])
                    return false;
                else
                    gapNum += numbers[i] - numbers[i-1] - 1;
            }
        }
        return zeroNum >= gapNum;
    }
};

73.Set Matrix Zeroes

题目大意

给定一个二维数组，将有0的位置的行和列置为0

思路

遍历每一行，记录每一个列出现0的位置，同时记录该行是否有0，如果有零，遍历完该行，将改行置为0
最后将记录的列置为0

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if (matrix.empty()) return;
        int m=matrix.size(), n=matrix[0].size(), flag=0;
        set<int> zeros;
        for (int i=0; i!=m; ++i){
            for (int j=0; j!=n; ++j){
                if (matrix[i][j] == 0){
                    flag = 1;
                    zeros.insert(j);
                }
            }
            if (flag){
                for (int k=0; k!=n; ++k)
                    matrix[i][k] = 0;
            }
            flag = 0;
        }
        for (set<int>::iterator it=zeros.begin(); it!=zeros.end(); ++it){
            for (int j=0; j!=m; ++j)
                matrix[j][*it] = 0;
        }
    }
};

239.Sliding Window Maximum

题目大意

给定一个数组和一个窗口大小，问当窗口在数组上滑动时，返回每个窗口最大值组成的数组。

思路

剑指offer上的原题啊

暴力法，暴力滑过各个窗口取得最大值，时间复杂度是O(nk)，每个窗口计算时重复比较了很多数
堆
- 用一个堆记录当前值的排序顺序，每滑动一个窗口，往堆中插入一个数，堆顶元素即使当前窗口的最大值
- 问题在于，如何弹出已经超过该窗口的元素。堆中元素包含下标，如果堆顶元素的小标超过了当前窗口的最小小标值，那么就pop掉。
- 时间复杂度O(nlogk)
双端队列
- 队列中存储的是降序排列的元素，自然队列头部是当前窗口的最大值，如果当前要插入的元素大于尾部数据，则弹出尾部数据，直到找到比该元素大的数插入；
- 问题在于，如何判断某个元素是否已经超过了该窗口，此时，可以考虑队列中存储下标，如果下标超过了当前窗口的最小下标，那么就需要pop掉；

struct cmp{
    bool operator()(pair<int, int>& a, pair<int, int>& b){
        return a.first < b.first;
    }
};
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;
        vector<int> res;
        for (int i=0; i!=nums.size(); ++i){
            q.push(make_pair(nums[i], i));
            while (q.top().second < res.size())
                q.pop();
            if (i+1 >= k) res.push_back(q.top().first);
        }
        return res;
    }
};

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        vector<int> res;
        for (int i=0; i!=nums.size(); ++i){
            // 如果队首元素超过了结果的长度(第几个窗口)，那么需要弹出
            if (!q.empty() && q.front() < res.size()) q.pop_front();
            // 维护双端队列是一个降序，front位置永远是当前窗口的最大值
            while (!q.empty() && nums[q.back()] < nums[i]) q.pop_back();
            q.push_back(i);
            if (i>=k-1) res.push_back(nums[q.front()]);
        }
        return res;
    }
};

152. Maximum Product Subarray

题目大意

给定一个数组，返回连续子数组的最大积

思路

只要中间没有零，那么连续子数组越长越好，同时恰好使得子数组负数个数为偶数，此时最大；

front和back记录遍历过程中正向遍历和逆向遍历的每一步的最大值，除非遇到零。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int front = 1, back = 1, res = INT_MIN;
        int n = nums.size();
        for (int i=0; i!=n; ++i){
            front *= nums[i];
            back *= nums[n-i-1];
            res = max(res, max(front, back));
            front = front == 0 ? 1 : front;
            back = back == 0 ? 1 : back;
        }
        return res;
    }
};

3. Longest Substring Without Repeating Characters

题目大意

给定一个字符串，找到没有重复字符的最长字符串的长度

思路

用256大小的数组记录每个字符在字符串中出现的位置，如果没有出现用-1表示。

用start记录，没有重复字符的字符串的开始下标；遍历字符串，如果当前字符曾经出现过，且出现的位置在start以后，那么start将变为从该字符串上一次出现的位置。遍历过程中记录长度的最大值。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> cache(256, -1);
        int res = 0, start = -1;
        for (int i=0; i<s.size(); ++i){
            if (cache[s[i]] > start)
                start = cache[s[i]];
            cache[s[i]] = i;
            res = max(res, i - start);
        }
        return res;
    }
};

472. Concatenated Words

题目大意

给定一个字符串数组，找出由两个或两个以上数组中字符串拼接而成的字符串。

思路

先将所有字符串存储在集合中，判断数组中每个字符串是否为拼接字符串：dp[i]表示前i个字符串是否为拼接字符串，如果dp[n]=1则该字符串是拼接字符串
先将所有字符串存储在集合中，使用DFS判断数组中每个字符串是否为拼接字符串
1. 当前可以选择cur到之后的所有的位置作为子字符串
2. 从第一步选择的位置开始继续循环选择
3. 如果恰好选择完毕且最后的子串存在数组中则返回true，否则返回false
字典树

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        set<string> cache(words.begin(), words.end());
        vector<string> results;
        for (auto word : words){
            int n = word.size();
            vector<int> dp(n+1);
            dp[0] = 1;
            for (int i=0; i<n; ++i){
                if (dp[i] == 0)
                    continue;
                for (int j=i+1; j<=n; ++j){
                    if (j - i < n && cache.count(word.substr(i, j-i))){
                        dp[j] = 1;
                    }
                }
                if (dp[n] == 1){
                    results.push_back(word);
                    // 防止一个字符串可以有不同的组合方式，所以结果会有重复
                    break;
                }
            }
        }
        return results;
    }
};

math

233.Number of Digit One

题目大意
- 给定一个数n，求出1-n所有数中1出现的个数
思路
- 考虑每一位上为1的情况
- 例如考虑百位为1的情况，n为32198，a为321，b为98
  - 如果百位(a%10) >=2, 那么有(a/10+1)*m个1；
  - 如果(a%10)==1，那么(a/10*m)+b+1个1；
  - 如果(a%10)==0, 那么(a/10*m)个1；
  - 综合起来(a+8)/10*m+(a%10==1?b+1:0);

class Solution {
public:
    int countDigitOne(int n) {
        int count = 0, a = 0, b = 0;
        for (long m=1; m<=n; m*=10){
            a = n / m;
            b = n % m;
            count += (a+8)/10*m + ((a%10==1)?b+1:0);
        }
        return count;
    }
};

69.Sqrt(x)

题目大意

求一个数的开根号，返回floor(sqrt(x))

思路

二分法
牛顿法
- $f(x) = f(x_k) + f^-(x_k)(x - x_k)$
- $x = x_k - \frac{f(x_k)}{f^-(x_k)}$

// binary
class Solution {
public:
    int mySqrt(int x) {
        long low = 0, high = x, mid = 0;
        while (low <= high){
            mid = low + (high - low) / 2;
            // mid * mid 考虑越界问题
            if (mid * mid < x)
                low = mid + 1;
            else if (mid * mid > x)
                high = mid - 1;
            else return mid;
        }
        return high;
    }
};

// newton
class Solution {
public:
    int mySqrt(int x) {
        long res = x;
        while (res*res > x){
            res = (res + x / res) / 2;
        }
        return res;
    }
};

50.Pow(x, n)

题目大意

实现标准库中的pow运算。

思路

考虑一些边界条件以及优化

指数为负的情况；
底为零指数为负的情况，不能做除法；
int的指数变负为正时，考虑最大的负数变为整数会越界；
提高效率，将$2^{2k+1}$装换为$2^k$的平方乘2

代码

class Solution {
public:
    double myPow(double x, int n) {
        // float和double类型的比较不能直接比较
        // 考虑底为零的情况
        if ((x - 0.0) < 0.0000001 && (x - 0.0) > -0.000000001)
            return x;
        double res = 1.0;
        // 考虑为负的情况
        if (n < 0){
            x = 1 / x;
            // 考虑越界
            if (n == INT_MIN){
                res *= x;
                n += 1;
            }
            n = -n;
        }
        while (n){
            // & 和 移位运算替代取余和除法
            if (n & 1)
                res *= x;
            n >>= 1;
            x *= x;
        }
        return res;
    }
};

372.Super Pow

题目大意

计算$a^b$%1337, b非常大，用vector的形式给出。

思路

ab % k = (a % k)(b % k) % k
f(a,b)表示$a^b$%k, 则f( f( a, b / 10), 10) * f(a, b % 10) % k，这样就转化为一个递归问题了

class Solution {
public:
    int superPow(int a, vector<int>& b) {
        if (a == 0) return 0;
        if (b.empty()) return 1;
        int x = b.back();
        b.pop_back();
        return mypow(superPow(a, b), 10) * mypow(a, x) % base;
    }
private:
    const int base = 1337;
    int mypow(int a, int k){
        // 相当于拆分到每个底相乘，每个底都对base取模
        a %= base;
        int res = 1;
        for (int i=0; i!=k; ++i){
            res = (res * a) % base;
        }
        return res;
    }
};

约瑟夫环

题目大意

0-n-1个人围成一个圈，从0喊到m-1，m-1的人被淘汰。然后从下一个人开始继续，请问最后活下来的是哪个人

思路

推导

f(n,m)表示n个小朋友，第m个人出局剩下的最后一个人;g(n-1, m)表示淘汰了f(n,m)中第m个人后按照规则剩下的那个人；
f(n,m) = g(n-1,m) = (f(n-1, m) + m) % n 下标差了m

递推公式f(n,m) = (f(n-1, m) + m)% n

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if (n < 1 || m < 1)
            return -1;
        int last = 0;
        for (int i=2; i<=n; ++i)
            last = (last + m ) % i;
        return last;
    }
};

382.Linked List Random Node

题目大意

一个非常大的链表，随机返回链表上的一个节点值，要求O(n)

思路

蓄水池算法。

需要选取k个随机数
- 选择前k个数，对于第i个来的数，以$\frac{k}{k+i}$的概率是否选择该数，然后再以$\frac{1}{k}$的概率替换池子中的一个数
- 直到i到最后一个数，池子里的数就是随机出来的k个数

class Solution {
ListNode* root;
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head) {
        root = head;
    }
    
    /** Returns a random node's value. */
    int getRandom() {
        if (root == NULL)
            return -1;
        ListNode* tmp = root;
        int res = tmp->val, count = 1;
        tmp = tmp->next;
        while (tmp){
            if (rand() % (1 + count++) == 0){
                res = tmp->val;
            }
            tmp = tmp->next;
        }
        return res;
    }
};

29. Divide Two Integers

题目大意

给定两个整数，输出除的结果，要求不能使用加、减和取余操作

思路

整体思路是判断结果正负号，将负数变为整数，使用移位和减法操作实现除法。

溢出
1. 因为负数要换成正数，所以针对出现负数的情况讨论溢出问题
除数较小时使用移位操作加速计算
1. 除数左移时候也需要考虑是否会溢出的问题

class Solution {
public:
    int divide(int dividend, int divisor) {
        // 几种可能越界的情况
        if (dividend == INT_MIN && divisor == INT_MIN)
            return 1;
        else if (divisor == INT_MIN)
            return 0;
        if (dividend == INT_MIN && divisor == -1)
            return INT_MAX;
        if (dividend == INT_MIN && divisor == 1)
            return INT_MIN;
        
        int is_minus = 0, res = 0, count = 1;
        if (divisor < 0){
            divisor = -divisor;
            is_minus = ~is_minus;
        }
        if (dividend < 0){
            // 考虑被除数的越界问题
            if (dividend == INT_MIN)
            {
                dividend += divisor;
                res++;
            }
            dividend = - dividend;
            is_minus = ~is_minus;
        }
        
        while (dividend > 0){
            int t = divisor;
            count = 1;
            // 使用移位加速计算
            while (dividend >> 1 > t){
                t = t << 1;
                count = count << 1;
            }
            dividend -= t;
            res += count;
        }
        // 不能整除 取整
        if (dividend < 0)
            res--;
        // 负数 返回负数
        if (is_minus)
            return -res;
        // 整数 直接返回
        else
            return res;
    }
};

两个数相除返回字符串形式

题目大意

两个整数相除，返回字符串形式，循环小数用括号+循环位替代。

4 / 2 -> 2 , 2 / 4 -> 0.5 , 1 / 3 -> 0.(3)

思路

整数部分直接除取整，小数部分乘10除取整，余数再循环。

string divide2int(int a, int b){
    string res = "";
    int zs, xs, last, count = 0;
    if (a == INT_MIN && b == -1){
        res = to_string(INT_MAX);
        return res;
    }

    // get zhengshu
    zs = a / b;
    res += to_string(zs);
    a = a - b * zs;
    if (a == 0) 
        return res;
    // 需要计算小数部分
    last = a;
    res += '.';
    map<int, int> cache;
    string tmp = "";
    while (a && count < 10){
        // 有循环小数
        if (cache.find(a) != cache.end()){
            tmp = string(tmp.begin(), tmp.begin()+cache[a]) + '(' + string(tmp.begin()+cache[a], tmp.end()) + ')';
            break;
        }
        cache[a] = count;
        xs = a * 10 / b;
        a = a * 10 % b;
        count++;
        tmp += to_string(xs);
        last = a;
    } 
    res += tmp;
    return res;
}

Binary Search

34.Search for a Range

题目大意

给定一个升序数组和一个目标值，找到目标所在的区间，如果不存在就返回[-1,-1]

思路

二分搜索，改变=的位置即可找到上界和下界；

使用low<=high的条件，low是左边的位置，high是右边的位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2, -1);
        if (nums.empty()) return res;
        int low = binarySearch(nums, target, 1);
        if (low >=0 && low < nums.size() && nums[low] == target)
            res[0] = low;
        else
            res[0] = -1;
        int high = binarySearch(nums, target, 0);
        if (high >= 0 && high < nums.size() && nums[high] == target)
            res[1] = high;
        return res;
    }
private:
    int binarySearch(vector<int>& nums, int target, int left){
        int low=0, high=nums.size()-1, mid=0;
        while (low <= high){
            mid = low + (high - low) / 2;
            if ((left && nums[mid] >= target) || (!left && nums[mid] > target))
                high = mid - 1;
            else
                low = mid + 1;
        }
        // low是高一位的点，high是低一位的点
        if (left) return low;
        else return high;
    }
};

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2, -1);
        if (nums.empty()) return res;
        int low = 0, high = nums.size()-1, mid;
        while (low < high){
            mid = low + (high - low) / 2;
            if (nums[mid] >= target)
                high = mid;
            else
                low = mid + 1;
        }
        if (nums[low] != target) return res;
        res[0] = low;
        while (low < nums.size() && nums[low] == target) low++;
        res[1] = low-1;
        return res;
    }
};

153.Find Minimum in Rotated Sorted Array

154.Find Minimum in Rotated Sorted Array II

题目大意

在一个没有重复数字的循环排序数组里，找到最小的数；
在一个有重复数字的循环排序数组里，找到最小的数；

思路

使用二分查找；
将mid和high位置比较；
如果是有重复数字，将high自减；

代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.empty()) return 0;
        int low = 0, high = nums.size() - 1, mid = 0;
        while (low < high){ // 正常情况下，查找会用=的条件，然后low指向恰好大的位置，high指向恰好小的位置；
            mid = low + (high - low) / 2;
            if (nums[mid] < nums[high]) //不能和low比较，因为mid取值时是取整，可能会取到和low相同的值,此时比值只会相等，
                                        //但是却有两种情况[1,2]和[2,1]，无法区分
                high = mid; //此处不能+1,可能mid处是最小值
            else
                low = mid + 1; // low如果不加1的话最后不能收敛
        }
        return nums[high];
    }
};

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums.empty()) return 0;
        int low = 0, high = nums.size()-1, mid = 0; // 内置类型在函数内部不会进行初始化
        while (low < high){
            mid = low + (high - low) / 2;
            if (nums[mid] < nums[high])
                high = mid;
            else if (nums[mid] > nums[high])
                low = mid + 1;
            else
                --high;
        }
        return nums[high];
    }
};

162.Find Peak Element

题目大意

给定一个山峰数组，即先升序后降序。求数组的山峰。

思路

二分

nums[mid] < nums[mid+1] : low = mid + 1 (因为循环条件是low<high，所以只有low==high时mid才会越界，此时已经跳出循环了)
nums[mid] > nums[mid+1] : high = mid

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        // nums.push_back(INT_MIN);
        int low =0, high = nums.size()-1, mid;
        while (low < high){
            mid = low + (high - low) / 2;
            // 只有low和high相等时才会出现mid=high的情况，此时已经跳出循环
            if (nums[mid] < nums[mid+1])
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }
};

33.Search in Rotated Sorted Array

81.Search in Rotated Sorted Array II

题目大意

在一个循环排序数组中，查找是否存在某个数。

思路

二分

nums[low] <= nums[mid] 此时 low到mid是递增区间
1. 如果 nums[low] <= target < nums[mid] : high = mid - 1
2. low = mid + 1 （此时，target位于mid+1和high之间）
nums[low] > nums[mid] 此时 mid到high是递增区间
1. 如果 nums[mid] < target <= nums[high] : low = mid + 1
2. high = mid - 1;
如果有重复的数，导致 nums[mid] == nums[low] == nums[high] 无法判断，则low++ high— 继续循环

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int low=0, high=nums.size()-1, mid;
        while (low <= high){
            mid = low + (high - low) / 2;
            if (nums[mid] == target) return mid;
            // 在没有重复情况下，nums[mid]==nums[low]意味着收敛到low和mid之间了，不应该再去mid和high之间了
            if (nums[mid] >= nums[low]){
                // 考虑target和边界相等的情况，此时target就是落在这个区间内
                if (nums[low] <= target && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }else{
                if (nums[mid] < target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
};

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if (nums.empty()) return false;
        int low=0, high=nums.size()-1, mid;
        while(low <= high){
            mid = low + (high - low) / 1;
            if (nums[mid] == target) return true;
            if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
                low++;
                high--;
            }
            else if (nums[low] <= nums[mid]){
                if (nums[low] <= target && target < nums[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            }else{
                if (nums[mid] < target && target <= nums[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return false;
    }
};

Bit Operation

136.Single Number

题目大意

给定一个数组，只有一个数出现一次，其他都出现两次，返回只出现一次的数

思路

异或
相同的数异或为0，最后只剩下单独的数

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i=0; i!=nums.size(); ++i){
            res ^= nums[i];
        }
        return res;
    }
};

137.Single Number II

题目大意

给定一个数组，只有一个数出现一次，其他都出现三次，返回出现一次的数

思路

对每一位进行计数，只需要 00、01和10即可，循环为00-01-10-00
对于出现三次的位一定会被消除，所以，最后剩下的就是只出现一次的数
只有三种情况，只需要ones和twos两位即可满足计数要求
更新规则
1. ones ^ nums[i]，当nums[i]是1时，ones需要更新，此时，如果twos == 1，ones更新为0(10-00)，否则ones更新为1(00-01)
2. twos ^ nums[i]，当nums[i]是1时，twos需要更新，此时，如果ones == 0，twos变为1，否则不变
对于出现次数是5的情况同样处理

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for (int i=0; i!=nums.size(); ++i){
            ones = ones^nums[i] & ~twos;
            twos = twos^nums[i] & ~ones;
        }
        return ones;
    }
};

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int tmp=0, res=0;
        for (int i=0; i!=32; ++i){
            tmp = 0;
            for (auto num:nums){
                tmp += (num >> i) & 1;
            }
            res |= (tmp % 3) << i;
        }
        return res;
    }
};

260.Single Number III

题目大意

给定一个数组，有两个数字出现次数是1次，其他数字均出现两次，求出现1次的两个数

思路

先异或，找到两个出现次数为1的数字的不同的位
找到两个数字某个不同的位(diff & ~(diff - 1))
根据这个位将原数组分为两部分，必然两个数会分开
两个数组分别异或，找到两个出现1次的数

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int diff = 0;
        vector<int> res(2, 0);
        for (int i=0; i!=nums.size(); ++i)
            diff ^= nums[i];
        diff &= ~(diff-1);
        for (int i=0; i!=nums.size(); ++i){
            if (nums[i] & diff)
                res[0] ^= nums[i];
            else
                res[1] ^= nums[i];
        }
        return res;
    }
};

string

151.Reverse Words in a String

题目大意

给定一个包含词的字符串，将词顺序翻转

思路

三个指针i，j，l。i是头指针，j是要将nums[i]移动到的位置，l是上一次的位置，翻转的时候要用
首先要去除多余的空格
如果前面有word需要加空格

class Solution {
public:
    void reverseWords(string &s) {
        int i=0, j=0, l=0, n=s.size();
        int count=0;
        
        while (i<n){
            while (i<n && s[i]==' ') i++;
            if (i==n) break;
            if (count) s[j++] = ' ';
            l = j;
            while (i<n && s[i]!=' '){
                s[j++] = s[i++];
            }
            reverse_str(s, l, j-1);
            count++;
        }
        s.resize(j);
        reverse_str(s, 0, j-1);
    }
private:
    void reverse_str(string &s, int i, int j){
        if (i<0 || i >= s.size() || j<0 || j >=s.size())
            return;
        while (i < j){
            char t = s[i];
            s[i++] = s[j];
            s[j--] = t;
        }
    }
};

左旋转字符串

题目大意

给定一个字符串和n，将字符串前n位左移。如给定abcde和2，则返回cdeab

思路

可以理解为，前n个字符是一个单词，后面的字符为另一个单词，相当于翻转单词的问题

class Solution {
public:
    string LeftRotateString(string str, int n) {
        if (str.size()>0 && n>0 && n<str.size()){
            reverseString(str, 0, n-1);
            reverseString(str, n, str.size()-1);
            reverseString(str, 0, str.size()-1);
        }
        return str;
    }
private:
    void reverseString(string &input, int left, int right){
        while (left<right){
            char tmp = input[left];
            input[left++] = input[right];
            input[right--] = tmp;
        }
    }
};

DP

最长公共子序列

题目大意

给定两个字符串，找到最长公共子序列。子序列的不一定需要是连续的

思路

动态规划，dp[i][j]记录s前i个字符串和t前j个字符串的最长公共子序列；

dp[i][j]=dp[i-1][j-1] if(A[i-1]==B[j-1])
dp[i][j]=max(dp[i-1][j], dp[i][j-1]) if (A[i-1] != B[j-1])

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    int longestCommonSubsequence(string &A, string &B) {
        // write your code here
        int m = A.size(), n = B.size();
        vector<vector<int> > dp(m+1, vector<int>(n+1, 0));
        
        for (int i=1; i<=m; ++i){
            for (int j=1; j<=n; ++j){
                // 注意下标和dp下标区别
                if (A[i-1] == B[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
};

最长公共子串

题目大意

给定两个字符串s和t，求s和t的最大公共子串的长度。

思路

同上使用动态规划，dp[i][j]记录s前i个字符串和t前j个字符串的最长公共子串；

dp[i][j]=dp[i-1][j-1] if(A[i-1]==B[j-1])
dp[i][j]=0 if (A[i-1] != B[j-1])

同时，使用res记录全程最大的子串。

class Solution {
public:
    /**
     * @param A: A string
     * @param B: A string
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &A, string &B) {
        // write your code here
        int m = A.size(), n = B.size(), res = 0;
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        
        for (int i=1; i<=m; ++i){
            for (int j=1; j<=n; ++j){
                if (A[i-1] == B[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    res = max(res, dp[i][j]);
                }
            }
        }
        return res;
    }
};

322.Coin Change

题目大意

给定一些钱币面值和总钱数，求能够凑出总钱数的最小钱币数。

思路

动态规划，dp[count] = min(dp[count-1], dp[count-2]…) + 1

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, -1);
        dp[0] = 0;
        int coins_len = coins.size(), cur = INT_MAX, last;
        for (int i=1; i<=amount; ++i){
            int tmp = INT_MAX;
            for (int j=0; j!=coins_len; ++j){
                last = i - coins[j];
                if (last >= 0 && dp[last] > -1){
                    tmp = min(tmp, dp[last]);
                }
            }
            if (tmp != INT_MAX)
                dp[i] = tmp + 1;
        }
        return dp[amount];
    }
};

62.Unique Paths

题目大意

给定一个m n的矩阵，求左上角到达右下角的路径数量有多少

思路

动态规划，dp[i][j] = dp[i-1][j] + dp[i][j-1]

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n));
        for (int i=0; i!=m; ++i)
            dp[i][0] = 1;
        for (int j=0; j!=n; ++j)
            dp[0][j] = 1;
        for (int i=1; i!=m; ++i){
            for (int j=1; j!=n; ++j)
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
        return dp[m-1][n-1];
    }
};

416.Partition Equal Subset Sum

题目大意

给定一个(非空、正数)数组，判断是否能将数组分为两个部分，两个部分和相等。

思路

使用动态规划，数组和为sum，则dp[i]记录是否有一部分元素和为i，返回dp[sum/2]即可。(如果数组有负数，那么dp数组就没有范围限制了)

dp[0] = true, 如果dp[i-num[k]]为true，则dp[i] = true

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;
        sum = sum >> 1;
        vector<bool> dp(sum+1, false);
        dp[0] = true;
        for (int i=0; i!=nums.size(); ++i){
            // 必须从sum开始，否则会nums[i]会被重复使用，比如2、4、6。。。
            for (int j=sum; j>0; --j){
                if (j-nums[i] >=0 && dp[j-nums[i]])
                    dp[j] = true;
            }
        }
        return dp[sum];
    }
};

698.Partition to K Equal Sum Subsets

题目大意

给定一个数组，判断是否能分成和相等的k部分。

思路

使用dfs，先找到一组元素使得和为sum/k，然后再递归剩下的元素是否能分为k-1组，递归结束条件为k==1(存在k-1组和为sum / k的数组那么剩下的一组必然为sum / k)

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k) return false;
        sum = sum / k;
        vector<int> visited(nums.size(), 0);
        return dfs(nums, visited, 0, 0, k, sum);
    }
private:
    bool dfs(vector<int>& nums, vector<int>& visited, int start, int sum, int k, int target){
        if (k==1) return true;
        // 新的part，从头开始考虑
        if (sum == target) return dfs(nums, visited, 0, 0, k-1, target);
        // 找到和为target的数组，如果前面的不可以，则后面不需要再考虑这些数了
        for (int i=start; i<nums.size(); ++i){
            if (visited[i]) continue;
            visited[i] = 1;
            if (dfs(nums, visited, i+1, sum+nums[i], k, target)) return true;
            visited[i] = 0;
        }
        return false;
    }
};

5.Longest Palindromic Substring

题目大意

求字符串的最长回文字符串。

思路

动态规划
1. 暴力法：遍历所有子串，判断是否为回文子串。在判断子串是否为回文子串过程中，有很多重复的判断，此处可以用动态规划
2. dp[i][j]表示i到j是否为回文串，此时dp[i][j]可以通过dp[i+1][j-1]和判断s[i] == s[j]来计算
  1. 提前计算dp[i][i]和dp[i][i+1]位置的对称性
  2. 奇数和偶数回文串两种情况
3. 在此过程中，记录最长的回文串的开始位置和长度
Manacher算法
1. https://articles.leetcode.com/longest-palindromic-substring-part-ii/
2. 将字符串aaxsd变成^#a#a#x#s#d#$，#的目的是将奇数长度和偶数长度的回文字符串都变成奇数长度的回文字符串，^和$是为了防止越界问题。
3. 使用p[i] 记录i位置回文串的单边长度，在计算过程中，可以利用对称性简化计算
  1. 中心位置是c，对称半径是r
  2. 如果i位于半径r内，可以通过对称位置计算
    1. 如果对称位置的回文长度没有超过r-i那么p[i] = p[mirror_i]
    2. 如果超过了，则p[i] = r-c，同时从r位置继续判断是否为回文串
  3. 如果在半径外，直接计算

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2) return s;
        int max_len = 1, start=0;
        int n=s.size();
        vector<vector<int>> dp(n, (vector<int>(n)));
        for (int i=0; i!=n; ++i){
            dp[i][i] = 1;
            if (i+1<n && s[i]==s[i+1]){
                dp[i][i+1] = 1;
                if (max_len < 2){
                    start = i;
                    max_len = 2;
                }
            }
        }
            
        for (int i=n-2; i>=0; --i){
            for (int j=i+2; j<n; ++j){
                if (dp[i+1][j-1] && s[i]==s[j]){
                    dp[i][j] = 1;
                    if (j - i >= max_len){
                        start = i;
                        max_len = j - i + 1;
                    }
                }
            }
        }
        return s.substr(start, max_len);
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2) return s;
        string t = preprocess(s);
        int len = t.size();
        vector<int> p(len);
        int c = 0, r = 0;
        
        for (int i=0; i!=len; ++i){
            int mirror = 2 * c - i;
            
            p[i] = r > i ? min(r-i, p[mirror]) : 0;
            
            while (t[i+1+p[i]] == t[i-1-p[i]])
                p[i]++;
            
            if (p[i] + i > r){
                c = i;
                r = p[i] + i;
            }
        }
        
        int max_pos=0, max_len=0;
        for (int i=0; i!=len; ++i){
            if (max_len < p[i]){
                max_len = p[i];
                max_pos = i;
            }
        }
        
        return s.substr((max_pos-1-max_len)/2, max_len);
    }
private:
    string preprocess(string s){
        string res = "@";
        for (int i=0; i!=s.size(); ++i){
            res += "#";
            res += s[i];
        }
        res += "#$";
        return res;
    }
};

300.Longest Increasing Subsequence

题目大意

给定一个数组，找到最长的递增子序列。

思路

动态规划，$O(n^2)$时间复杂度，$O(n)$空间复杂度
1. dp[i]表示前 i 个数的最长递增子序列
2. 每次更新时，遍历0到 i-1的数，如果比nums[j]大，则可以构成新的递增子序列，序列长度为dp[j]+1，将最大值作为dp[i]
3. 遍历过程中记录最大值
$O(nlogn)$时间复杂度，$O(n)$空间复杂度
1. 遍历过程中维护一个S数组，数组维护的是各个长度LIS的最小尾部
2. 遍历数组，找到S中不小于nums[i]的最小值，
  1. 如果找到了，则替换该值，
  2. 如果比S中最大值还大，直接append即可
3. 最后，S的长度就是最长递增子序列的长度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size(), len, max_len=1;
        vector<int> dp(n, 1);
        for (int i=1; i<n; ++i){
            len = 0;
            for (int j=0; j<i; ++j){
                if (nums[i] > nums[j]){
                    len = max(len, dp[j]);
                }
            }
            dp[i] = len + 1;
            max_len = max(dp[i], max_len);
        }
        return max_len;
    }
};

// nlogn
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int>::iterator it = nums.begin(), tmp;
        for (int i=0; i!=nums.size(); ++i){
            tmp = lower_bound(nums.begin(), it, nums[i]);
            *tmp = nums[i];
            if (tmp == it){
                it++;
            }
        }
        return it - nums.begin();
    }
};

674. Longest Continuous Increasing Subsequence

题目大意

给定一个数组，找到最长的连续升序序列

思路

遍历，因为是连续序列，所以尽可能记录升序序列的长度，如果断了就重新计数，在此过程中记录最大值即可

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        int max_len=1, len=1, n = nums.size();
        for (int i=0; i<n-1; ++i){
            if (nums[i] < nums[i+1])
                len++;
            else
                len = 1;
            max_len = max(max_len, len);
        }
        return max_len;
    }
};

198.House Robber

题目大意

给定一个正数数组，要求相邻的数不能同时取得，问选取的数和最大是多少。

思路

dp[i] = max(dp[i-1], dp[i-2]+nums[i])动态规划值
只需要用a、b两个数，存储奇数和偶数位置的最大结果 a = max(a+nums[i], b) && b = max(b+nums[i], b)

class Solution {
public:
    int rob(vector<int>& nums) {
        int a = 0, b = 0;
        for (int i=0; i!=nums.size(); ++i){
            if (i%2){
                a = max(b, a+nums[i]);
            }else{
                b = max(a, b+nums[i]);
            }
        }
        return max(a, b);
    }
};

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        vector<int> dp(n+1);
        dp[1] = nums[0];
        for (int i=2; i<=n; ++i){
            if (i-1>=0){
                dp[i] = max(dp[i], dp[i-1]);
            }
            if (i-2>=0){
                dp[i] = max(dp[i], dp[i-2]+nums[i-1]);
            }
        }
        return dp[n];
    }
};

213. House Robber II

题目大意

给定一个正数数组，要求相邻的数以及首尾的数不能同时取得，问选取的数和最大是多少。

思路

乍看上去，首尾的情况不太好处理。如果分两次遍历，一次掐头，一次去尾。取两次的最大值即可。

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size();
        // 对于数组长度为1的情况后面的函数无法处理，需要简单处理下边界
        if (n == 1) return nums[0];
        return max(find(nums, 0, n-1), find(nums, 1, n));
    }
private:
    int find(vector<int>& nums, int s, int e){
        int a = 0, b = 0;
        for (int i=s; i<e; ++i){
            if (i%2){
                a = max(a+nums[i], b);
            }else{
                b = max(b+nums[i], a);
            }
        }
        return max(a, b);
    }
};

337. House Robber III

题目大意

小区的布局变成了二叉树的形式，父亲和孩子不能同时被偷。问最多能偷多少。

思路

思路略微不同，每个位置有被偷或者不被偷两种情况，存储两种情况的最大收获值(上面两题都是存储存在i个位置，能够偷的最大收获是多少)。res[0] = left[1] + right[1] + root->val和res[1] = max(left[0], left[1]) + max(right[0], right[1])

class Solution {
public:
    int rob(TreeNode* root) {
        pair<int, int> res = dfs(root);
        return max(res.first, res.second);
    }
private:
    pair<int, int> dfs(TreeNode* root){
        if (root==NULL) return make_pair(0, 0);
        pair<int, int> res;
        pair<int, int> left = dfs(root->left);
        pair<int, int> right = dfs(root->right);
        res.first = left.second + right.second + root->val;
        res.second = max(left.first, left.second) + max(right.first, right.second);
        return res;
    }
};

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

题目大意

给定一个数组，下标为i的数表示股票在第i天的价格。如果最多只能操作一次（买、卖一次），请问最多能挣多少钱。

思路

从头到尾遍历，dp[i-1][0]为前 i-1 天的最低价位，如果第i天价位不高于dp[i-1][0], 则dp[i][0] = prices[i]；

否则，计算出第i天卖出的最大利润 profit=prices[i] - dp[i-1][0]，前i天能达到的最大利润为dp[i][1] = max(profit, dp[i-1][1])。

其实因为这个情况很简单，所以可以考虑不用数组去做，只需要一个记录之前的股票最小值，以及之前的利润最大值即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int res=0, last=prices[0];
        for (int i=0; i<prices.size(); ++i){
            if (last < prices[i]){
                res = max(res, prices[i] - last);
            }else{
                last = prices[i];
            }
        }
        return res;
    }
};

122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目大意

可以完成尽可能多次的交易，请问最大获益是多少。

思路

这种情况很简单，用贪心去做，只要能赚钱我就交易即可。

即，只要上一天的价格低于当天的价格，就在上一天买入在当天卖出。

两种情况：

若第三天的价格高于当天价格，那么在今天买入第三天卖出，效果和贪心是一样的；

若第三天价格低于当天价格，那么就应该在当天卖出；所以应该用贪心的思路做。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int res=0, last=prices[0];
        for (int i=0; i<prices.size(); ++i){
            if (last < prices[i]){
                res += prices[i]-last;
                last = prices[i];
            }else{
                last = prices[i];
            }
        }
        return res;
    }
};

123. Best Time to Buy and Sell Stock III

题目大意

只能完成两次交易，那么最大收益是多少。

思路

第一种思路：

想了很久，画了一条曲线，其实两次交易相当于在中间找到一个局部最高点，在这个最高点后面又找到一个局部最低点，而我们可以去遍历所有的数，将每个数作为最高点（前一次卖出）和最低点（后一次买入）的分割点，在遍历的过程中记录收益的最大值即可。

思路很简单，分割以后，分别用题I的解法去做就可以了。但是，此时会重复遍历很多次，第i天为分割点，为了找到第一次交易的最大收益，需要遍历前i天，而这前i天中有i-1天是上一次已经遍历过的了，所以这种方法会超时。

第二种思路：

如上面的分析，这种重复的情况可以用一个dp数组去存储第i天为分割点时，前i天的股票最大收益和后n-i+1天的最大收益，这样就不需要进行重复计算了，时间效率大大提高。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size(), res=0;
        vector<int> left_dp(n), right_dp(n), left_max(n), right_max(n);
        
        // 从前往后遍历第一次卖得位置
        for (int i=0; i<n; ++i){
            if (i>0 && left_dp[i-1] < prices[i]){
                left_max[i] = max(left_max[i-1], prices[i]-left_dp[i-1]);
                left_dp[i] = left_dp[i-1];
            }else{
                if (i>0)
                    left_max[i] = left_max[i-1];
                left_dp[i] = prices[i];
            }
        }
        // 从后往前遍历第二次买的位置
        for (int i=n-1; i>=0; --i){
            if (i<n-1 && right_dp[i+1] > prices[i]){
                right_max[i] = max(right_max[i+1], right_dp[i+1] - prices[i]);
                right_dp[i] = right_dp[i+1];
            }else{
                if (i<n-1)
                    right_max[i] = right_max[i+1];
                right_dp[i] = prices[i];
            }
        }
        // 根据第一次卖得位置和第二次买的位置求得最佳的分割点
        for (int i=0; i!=n; ++i){
            res = max(res, left_max[i]+right_max[i]);
        }
        return res;
    }
};

188. Best Time to Buy and Sell Stock IV

题目大意

最多k次交易，请问最大收益是多少。

思路

不会做。参考大神的思路，使用循环引用的动态规划。

must_sell[i][k] 表示第i天必须卖出且至多交易k次的最大收益。
global_max[i][k] 表示截止到第i天至多交易k次的最大收益。

状态转移方程：

must_sell[i][k] = max(global_max[i-1][k-1] + profit, must_sell[i-1][k] + profit)

(第i天卖出且至多交易k次的最大收益为：前i-1天至多交易k-1次的最大收益和第i-1天必须卖出至多交易k次的最大收益的较大值加上第i天卖出的收益。）

global_max[i][k] = max(global_max[i-1][k], must_sell[i][k])

(前i天至多交易k次的最大收益为：前i-1天至多交易k次的最大收益和第i天必须卖出至多交易k次的最大收益的较大者。)

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size(), res=0;
        if (n == 0 || k == 0) return 0;
        // 当可以交易的次数足够多
        if (k > n / 2){
            for (int i=1; i!=n; ++i){
                if (prices[i-1] < prices[i]){
                    res+= prices[i] - prices[i-1];
                }
            }
            return res;
        }
        // must_sell[i][k] 必须卖出prices[i]且交易次数最多是k的 最大收益
        vector<vector<int>> must_sell(n, vector<int>(k+1));
        // global_sell[i][k] 进行到prices[i](不一定卖出)且交易次数最多是k的 最大收益
        vector<vector<int>> global_sell(n, vector<int>(k+1));
        
        for (int i=1; i<n; ++i){
            int profit = prices[i] - prices[i-1];
            for (int kk=1; kk<k+1; ++kk){
                must_sell[i][kk] = max(global_sell[i-1][kk-1] + profit, must_sell[i-1][kk] + profit);
                global_sell[i][kk] = max(global_sell[i-1][kk], must_sell[i][kk]);
            }
        }
        return global_sell[n-1][k];
        
    }
};c

72. Edit Distance

题目大意

计算两个字符串之间的编辑距离。word1通过删除、插入和替换三种操作变为word2，操作需要的次数即为编辑距离。

思路

动态规划

if str[i-1]==str[j-1]: dp[i][j] = dp[i-1][j-1]

if str[i-1]!=str[j-1]: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for (int i=0; i<=m; ++i)
            dp[i][0] = i;
        for (int i=0; i<=n; ++i)
            dp[0][i] = i;
        for (int i=1; i<=m; ++i){
            for (int j=1; j<=n; ++j){
                if (word1[i-1] == word2[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else{
                    dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1;
                }
            }
        }
        return dp[m][n];
    }
};