leetcode课程

发表于   |   分类于   |     |   阅读次数

目录

1 链表(回到目录)

例1-a,链表逆序-a 206

已知链表的头节点head,将链表逆序。（不可以申请额外的空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution
{
    public:
    ListNode* reverseList(ListNode* head)
    {
        ListNode* new_head=NULL;
        while(head)
        {
            ListNode* next=head->next;//备份head->next;
            head->next=new_head;//更新head->next;
            new_head=head;//移动new_head;
            head=next;//遍历链表
        }
        return new_head;
    }
}

例1-b,链表逆序-b 92

已知链表头节点指针head,将链表从位置m到n逆序。（不申请额外空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) 
    {
        int list_len=n-m+1;
        ListNode* pre_head=NULL;
        ListNode* result=head;
        while(head && --m)
        {
            pre_head=head;
            head=head->next;
        }
        ListNode* modify_list_tail=head;
        ListNode* new_head=NULL;
        while(head && list_len)
        {
            ListNode* next=head->next;
            head->next=new_head;
            new_head=head;
            head=next;
            list_len--;
        }
        modify_list_tail->next=head;
        if(pre_head)
        {
            pre_head->next=new_head;
            
        }
        else
        {
            result=new_head;
        }   
        return result;
        
    }
};

例2，求两个链表的交点。160(回到目录)

已知链表A的头节点指针headA，链表B的头节点指针headB，两个链表相交，求两个链表交点对应的节点。

方法一：使用std中的set函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        std::set<ListNode*> node_set;
        while(headA)
        {
            node_set.insert(headA);
            headA=headA->next;
        }
        while(headB)
        {
            if(node_set.find(headB)!=node_set.end())
            {
                return headB;
            }
            headB=headB->next;
        }
        return NULL;
    }
    
};

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        int lenA=compute_len(headA);
        int lenB=compute_len(headB);
        int t=0;
        if(lenB>lenA)
        {
            t=lenB-lenA;
            while(headB && t)
            {
                headB=headB->next;
                t--;
            }
            while(headA && headB)
            {
                if(headA==headB) return headA;
                headA=headA->next;
                headB=headB->next;
            }
        }
        else
        {
            t=lenA-lenB;
            while(headA && t)
            {
                headA=headA->next;
                t--;
            }
            while(headA && headB)
            {
                if(headA==headB) return headB;
                headA=headA->next;
                headB=headB->next;
            }
        }
        return NULL;
    }
private:
    int compute_len(ListNode* head)
    {
        int len=0;
        while(head)
        {
            len++;
            head=head->next;
        }
        return len;
    }
};

例3，链表求环。

已知链表中可能存在环，若有环返回环起始节点，否则返回NULL.

方法一：使用set函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        std::set<ListNode*> node_set;
        while(head)
        {
            if(node_set.find(head)!=node_set.end())
                return head;
            node_set.insert(head);
            head=head->next;
        }
        return NULL;
    }
};

方法二

  • 步骤：
    • 利用快慢指针求出相遇节点
    • 相遇节点和头节点同时出发，相等时就是环的入口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* fast=head;
        ListNode* slow=head;
        ListNode* meet=NULL;
        while(fast)
        {
            slow=slow->next;
            fast=fast->next;
            if(!fast)
            {
                return NULL;
                break;
            }
            fast=fast->next;
            if(fast==slow)
            {
                meet=fast;
                break;
            }
        }
        if(meet==NULL)
            {
                return NULL;
            }
        while(head && meet)
        {
            if(head==meet)
            {
                return head;
            }
            head=head->next;
            meet=meet->next;
        }
        
        return NULL;
    }
};

例4，链表划分。

已知链表头指针head与数值x，将所有小于X的节点放在大于等于x的节点前，且保持这些节点的原来的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    ListNode* partition(ListNode* head, int x) 
    {
        ListNode less_head(0);
        ListNode more_head(0);
        ListNode* less_ptr= &less_head;
        ListNode* more_ptr= &more_head;
        while(head)
        {
            if(head->val <x)
            {
                less_ptr->next=head;
                less_ptr=head;
            }
            else
            {
                more_ptr->next=head;
                more_ptr=head;
            }
            head=head->next;
        }
        less_ptr->next=more_head.next;
        more_ptr->next=NULL;
        return less_head.next;
    }
};

例5，链表的深度拷贝。。。。。不想做了

例6-a,排序链表的合并（2个）

已知两个已排序的链表头节点指针$L_1$和$L_2$,将这两个链表合并，合并之后仍为有序的，返回合并后的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) 
    {
        ListNode temp(0);
        ListNode* ptr=&temp;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                ptr->next=l1;
                l1=l1->next;
            }
            else
            {
                ptr->next=l2;
                l2=l2->next;
            }
            ptr=ptr->next;
        }
        if(l1)
        {
            ptr->next=l1;
        }
        if(l2)
        {
            ptr->next=l2;
        }
        return temp.next;
    }
};

例6-b,K个排序链表的合并

已知k个已排序链表头节点指针，将这k个链表合并，合并后仍为有序的，返回合并后的头节点。

方法一：将所有的节点放在一个vector,然后再排序，最后相连。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        vector<ListNode*> node_vec;
        for(int i=0;i<lists.size();i++)
        {
            node_vec.push_back(lists[i]);
            
        }
        if(node_vec.size()==0)
        {
            return NULL;
        }
        sort(node_vec.begin(),node_vec.end(),cmp);
        for(int i=1;i<node_vec.size();i++)
        {
            node_vec[i-1]->next=node_vec[i];
        }
        node_vec[node_vec.size()-1]->next=NULL;
        return node_vec[0];
    }
private:
    bool cmp(const ListNode* a,const ListNode* b)
    {
        return a->val < b->val;
    }
};

方法二：使用分治法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        if(lists.size()==0) return NULL;
        if(lists.size()==1) return lists[0];
        if(lists.size()==2) return mergeTwoLists(lists[0],lists[1]);
        
        int mid=lists.size()/2;
        vector<ListNode*> sublists_1;
        vector<ListNode*> sublists_2;
        for(int i=0;i<mid;i++)
        {
            sublists_1.push_back(lists[i]);
        }
        for(int i=mid;i<lists.size();i++)
        {
            sublists_2.push_back(lists[i]);
        }
        ListNode* l1=mergeKLists(sublists_1);
        ListNode* l2=mergeKLists(sublists_2);
        return mergeTwoLists(l1,l2);
    }
private:
    ListNode* mergeTwoLists(ListNode* l1,ListNode* l2)
    {
        ListNode temp(0);
        ListNode* ptr= &temp;
        while(l1 && l2)
        {
            if(l1->val < l2->val)
            {
                ptr->next=l1;
                l1=l1->next;
            }
            else
            {
                ptr->next=l2;
                l2=l2->next;
            }
            ptr=ptr->next;
        }
        if(l1)
        {
            ptr->next=l1;
        }
        if(l2)
        {
            ptr->next=l2;
        }
        return temp.next;
    }
};

补充对比：分治算法之归并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution
{
public:
    void merge_sort_two_vec(vector<int> &sub_vec1,vector<int> &sub_vec2,vector<int> &vec)
    {
        int i=0;
        int j=0;
        while(i<sub_vec1.size() && j<sub_vec2.size())
        {
            if(sub_vec1[i]<=sub_vec2[j])
            {
                vec.push_back(sub_vec1[i]);
                i++;
            }
            else
            {
                vec.push_back(sub_vec2[j]);
                j++;
            }
            for(;i<sub_vec1.size();i++)
            {
                vec.push_back(sub_vec1[i]);
            }
            for(;j<sub_vec2[j];j++)
            {
                vec.push_back(sub_vec2[j]);
            }
        }
        
    }
    
    void merge_sort(vector<int> &vec)
    {
        if(vec.size()<2)
        {
            return;
        }
        vector<int> sub_vec1;
        vector<int> sun_vec2;
        int mid=vec.size()/2;
        for(int i=0;i<mid;i++)
        {
            sub_vec1.push_back(vec[i]);
        }
        for(int i=mid;i<vec.size();i++)
        {
            sub_vec2.push_back(vec[i]);
        }
        merge_sort(sub_vec1);
        merge_sort(sub_vec2);
        vec.clear;
        merge_sort_two_vec(sub_vec1,sub_vec2);
    }
};

2 栈 队列 堆(回到目录)

例1，使用队列实现栈

使用两个队列设计一个栈。

思路：两个队列中，一个做真正的数据队列，一个用作临时队列。并且只是修改push操作，其他操作不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    /** Push element x onto stack. */
    void push(int x) {
        queue<int> temp_queue;
        temp_queue.push(x);
        while(!data_queue.empty())
        {
            temp_queue.push(data_queue.front());
            data_queue.pop();
        }
        while(!temp_queue.empty())
        {
            data_queue.push(temp_queue.front());
            temp_queue.pop();
        }
    }
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int x=data_queue.front();
        data_queue.pop();
        return x;
    }
    
    /** Get the top element. */
    int top() {
        return data_queue.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return data_queue.empty();
    }
private:
    queue<int> data_queue;
};

例2，使用栈实现队列

使用两个栈设计一个队列

思路：两个栈中，一个做真正的数据栈，一个用作临时栈。并且只是修改push操作，其他操作不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
    }
    /** Push element x to the back of queue. */
    void push(int x) {
        stack<int> temp_stack;
        while(!data_stack.empty())
        {
            temp_stack.push(data_stack.top());
            data_stack.pop();
        }
        temp_stack.push(x);
        while(!temp_stack.empty())
        {
            data_stack.push(temp_stack.top());
            temp_stack.pop();
        }
    }
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int x=data_stack.top();
        data_stack.pop();
        return x;
    }
    /** Get the front element. */
    int peek() {
        return data_stack.top();
    }
    /** Returns whether the queue is empty. */
    bool empty() {
        return data_stack.empty();
    }
private:
    stack<int> data_stack;
};

例1例2总结

把握核心：



- 队列实现栈：新来的元素压到队头！
- 栈实现队列：新来的元素压到栈底！

例3，包含min函数的栈

设计一个栈，支持以下操作，这些操作的算法复杂度为常数级，O(1)。

  • push(x):将x压入栈中
  • pop():弹出栈顶元素
  • top():返回栈顶元素
  • getMin():返回栈内最小的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        data_stack.push(x);
        if(min_stack.empty())
        {
            min_stack.push(x);
        }
        else
        {
            if(x>min_stack.top())
            {
                x=min_stack.top();
            }
            min_stack.push(x);
        }
    }
    
    void pop() {
        data_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return data_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
private:
    stack<int> data_stack;
    stack<int> min_stack;
};

例4，合法的出栈序列

已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，等待后面的数字入栈出栈后，该数字再出栈，求该数字序列的出栈序列是否合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool IsPopOrder(queue<int> &order)
    {
        stack<int> s;
        int n=order.size();
        for(int i=1;i<=n;i++)
        {
            s.push(i);
            while(s.top()=order.front() && !s.empty())
            {
                s.pop();
                order.pop();
            }
        }
        if(!s.empty())
        {
            return false;
        }
        return true;
    }
};

例6，数组中第K大的数字

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例1:

1
2
3
4
5
6
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int,vector<int>,greater<int> >small_heap;
        for(int i=0;i<nums.size();i++)
        {
            if(small_heap.size()<k)
            {
                small_heap.push(nums[i]);
            }
            else if(small_heap.top()<nums[i])
            {
                small_heap.pop();
                small_heap.push(nums[i]);
            }
        }
        return small_heap.top();
    }
};

例7，设计一个数据结构，该数据结构可以动态的维护一组数据，且支持如下操作：

（1） 添加元素
（2） 返回数据的中位数

补充内容

3 贪心算法（回到目录）

例1，分糖果。已知一些孩纸和糖果，每个孩子都有需求因子g,每个糖果有大小s,当糖果的大小s>=g时，代表糖果可以满足该孩子；求使用这些糖果，最多能满足多少个孩子？(每个孩子最多使用一个糖果)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) 
    {
        if(g.size()==0 || s.size()==0)
        {
            return 0;
        }
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int child=0;
        int cookie=0;
        while(child<g.size() && cookie<s.size())
        {
            if(g[child]<=s[cookie])
            {
                child++;
            }
            cookie++;
        }
        return child;
        
    }
};

例2，摇摆序列。一个整数序列，如果两个相邻的元素的差恰好正负(负正)交替出现，则该序列被称为摇摆序列。一个小于2个元素的序列直接为摇摆序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        if(nums.size()<2) return nums.size();
        static const int BEGIN=0;
        static const int UP=1;
        static const int DOWN=2;
        
        int STATE=BEGIN;
        int max_length=1;
        for(int i=1;i<nums.size();i++)
        {
            switch(STATE)
            {
                case BEGIN:
                    if(nums[i-1]<nums[i])
                    {
                        STATE=UP;
                        max_length++;
                    }
                    if(nums[i-1]>nums[i])
                    {
                        STATE=DOWN;
                        max_length++;
                    }
                    break;
                case UP:
                    if(nums[i-1]>nums[i])
                    {
                        STATE=DOWN;
                        max_length++;
                    }
                    break;
                case DOWN:
                    if(nums[i-1]<nums[i])
                    {
                        STATE=UP;
                        max_length++;
                    }
            }   
                
        }
        return max_length;
    }
};

例3，移除k个数字。已知一个使用字符串表示的非负整数num，将num中的k个数字移除，求移除k个数字后，获得的最小的可能的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    string removeKdigits(string num, int k) 
    {
        vector<int> S;
        string result="";
        for(int i=0;i<num.length();i++)
        {
            int number=num[i]-'0';
            while(S.size()!=0 && k>0 && S[S.size()-1]>number)
            {
                S.pop_back();
                k--;
            }
            if(number !=0 || S.size()!=0)
            {
                S.push_back(number);
            }
        }
            while(k>0 && S.size()!=0)
            {
                S.pop_back();
                k--;
            }
            for(int i=0;i<S.size();i++)
            {
                result.append(1,'0'+S[i]);
            }
            if(result=="")
            {
                result='0';
            }
        return result;
    }
};

例4-a，一组数据存储了非负整数，数组中的第i个元素a[i]，代表了可以从数组第i个位置最多向前跳跃a[i]步；已知数组各元素的情况下，求是否可以从数组中的第0个位置跳跃到最后一个元素的位置？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        vector<int> index;
        int jump=0;
        for(int i=0;i<nums.size();i++)
        {
            index.push_back(nums[i]+i);
        }
        int max_index=index[0];
        while(jump<=max_index && jump<index.size())
        {
            if(max_index<index[jump])
            {
                max_index=index[jump];
            }
            jump++;
        }
        if(jump==index.size())
        {
            return true;
        }
        return false;
    }
};

(还要复习)例4-b,一个数组存储了非负整数，数组中的第i个元素a[i]，代表了可以从数组第i个位置最多向前跳跃a[i]步；已知数组各元素的情况下，确认可以从第0位置跳跃到数组最后一个位置，求最少需要跳跃几次？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int jump(vector<int>& nums) 
    {
        if(nums.size()<2)
            return 0;
        int current_max_index=nums[0];
        int pre_max_index=nums[0];
        int jump_min=1;
        for(int i=1;i<nums.size();i++)
        {
            if(i>current_max_index)
            {
                jump_min++;
                current_max_index=pre_max_index;
            }
                         
            if(pre_max_index<nums[i]+i)
            {
                pre_max_index=nums[i]+i;
            }
        }
        return jump_min;
    }
};

例5，射击气球。已知在一个平面上有一定数量的气球，平面可以看作一个坐标系，在平面的x轴的不同位置安排弓箭手向y轴射击，弓箭可以向y轴走无穷远；给定气球的宽度（xstart,xend）,问至少需要多少弓箭手，将全部气球打爆？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool cmp(const pair<int, int> &a,const pair<int, int> &b)
    {
        return a.first<b.first;
    }
class Solution {
public:
    int findMinArrowShots(vector<pair<int, int>>& points) 
    {     
        if(points.size()==0) return 0;
        sort(points.begin(),points.end(),cmp);
        int shot_count=1;
        int shot_begin=points[0].first;
        int shot_end=points[0].second;
        for(int i=1;i<points.size();i++)
        {
            if(points[i].first<=shot_end)
            {
                shot_begin=points[i].first;
                if(shot_end>points[i].second)
                {
                    shot_end=points[i].second;
                }
                
            }
            else
            {
                shot_count++;
                shot_begin=points[i].first;
                shot_end=points[i].second;
            }
        }
        return shot_count;
    }
};

(还要复习)例6，最优加油方法。已知一条公路上，有个起点和终点，这之间有n个加油站；已知从这n个加油站到终点的距离d与各个加油站的加油量1,起点位置至终点的距离L与起始时刻油箱中的汽油量P;假设使用1个单位的汽油即走1个单位的距离，油箱没有上限，最少加几次油，可以从起点开至终点？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool cmp(pair<int,int> &a,pair<int,int> &b)
{
    return a.first>b.first;
}
int get_minimum_stop(int L,int P,vector<pair<int,int> > &stop)
{
    priority_queue<int> Q;
    int result=0;
    stop.push_back(make_pair(0,0));
    sort(stop.begin(),stop.end(),cmp);
    for(int i=0;i<stop.size();i++)
    {
        int dis=L-stop[i].first;
        while(!Q.empty() && P<dis)
        {
            P +=Q.top();
            Q.pop();
            result++;
        }
        if(Q.empty && P<dis)
        {
            return -1;
        }
        P=P-dis;
        L=stop[i].first;
        Q.push(stop[i].second);
    }
    return result;
}

4 递归 回溯与分治（回到目录）

[toc]

例1-a，求子集。已知一组数(其中无重复元素)，求这组数可以组成的所有子集。结果中不可以有重复的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution
{
public:
    vector<vector<int> >subsets(vector<int> &nums)
    {
        vector<vector<int> > result;
        vector<int> item;
        result.push_back(item);
        generate(0,nums,item,result);
        return result;
    }
private:
    void generate(int i,vector<int> &nums,vector<int> &item, vector<vector<int> >&result)
    {
        if(i>=nums.size()) return;
        item.push_back(nums[i]);
        result.push_back(item);
        generate(i+1,nums,item,result);
        item.pop_back();
        generate(i+1,nums,item,result);
    }
};

另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {//for循环
public:
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<vector<int> >res;
        vector<int> item;
        res.push_back(item);
        //sort(nums.begin(),nums.end());//解答错误不是没有排序的问题
        generate(res,item,nums,0);
        
        return res;
    }
private:
    void generate(vector<vector<int> > &res, vector<int> &item, vector<int> &nums, int begin)
    {
        if(begin>=nums.size())
        {
            return;
        }
        for(int i=begin;i<nums.size();i++)
        {
            item.push_back(nums[i]);
            res.push_back(item);
            generate(res,item,nums,i+1);
            item.pop_back();
        }
    }
};

例1-b,求子集2。已知一组数(其中有重复元素)，求这组数可以组成的所有子集。结果中无重复的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        vector<vector<int> >result;
        vector<int> item;
        set<vector<int> > res_set;
        sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,item,result,res_set);
        return result;
        
    }
private:
    void generate(int i, vector<int> &nums,vector<int> & item, vector<vector<int> > &result, set<vector<int> > &res_set)
    {
        if(i>=nums.size())
            return;
        item.push_back(nums[i]);
        
        if(res_set.find(item)==res_set.end())
        {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i+1,nums,item,result,res_set);
        item.pop_back();
        generate(i+1,nums,item,result,res_set);
    }
    
};

例1-c,组合数之和。已知一组数（其中有重复元素），求这组数可以组成的所有子集中，子集的各个元素和为整数target的子集，结果中无重复元素。

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& nums) 
    {
        vector<vector<int> >result;
        vector<int> item;
        set<vector<int> > res_set;
        sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,nums,item,result,res_set);
        vector<vector<int> >target_result;
        for(int i=0;i<result.size();i++)
        {
            int sum=0;
            for(int j=0;j<result[i].size();j++)
            {
                sum=sum+result[i][j];
            }
            if(sum==target)
            {
                target_result.push_back(result[i]);
            }
        }
        return target_result;
        
    }
private:
    void generate(int i, vector<int> &nums,vector<int> & item, vector<vector<int> > &result, set<vector<int> > &res_set)
    {
        if(i>=nums.size())
            return;
        item.push_back(nums[i]);
        
        if(res_set.find(item)==res_set.end())
        {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i+1,nums,item,result,res_set);
        item.pop_back();
        generate(i+1,nums,item,result,res_set);
    }
    
};

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& nums) 
    {
        vector<vector<int> >result;
        vector<int> item;
        set<vector<int> > res_set;
        sort(nums.begin(),nums.end());
        result.push_back(item);
        generate(0,0,nums,item,result,res_set);
        return result;
        
    }
private:
    void generate(int i, int sum, vector<int> &nums,vector<int> & item, vector<vector<int> > &result, set<vector<int> > &res_set)
    {
        if(i>=nums.size() || sum>target)
            return;
        sum=sum+nums[i];
        item.push_back(nums[i]);
        
        if(res_set.find(item)==res_set.end() && sum==target)
        {
            result.push_back(item);
            res_set.insert(item);
        }
        generate(i+1,nums,item,result,res_set);
        sum=sum-nums[i];
        item.pop_back();
        generate(i+1,nums,item,result,res_set);
    }
    
};

例2，生成括号，已知n组括号，开发一个程序，生成这n组括号所有合法的组合可能。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<string> generateParenthesis(int n) 
    {
        vector<string> &result;
        generate("",n,n,result);
        return result;
        
    }
private:
    void generate(string item,int left,int right,vector<string> &result)
    {
        if(left==0 && right==0)
        {
            result.push_back(item);
            return;
        }
        if(left>0)
        {
            generate(item+'(',left-1,right,result);
            
        }
        if(left<right)
        {
            generate(item+')',left,right-1,result);
        }
    }
};

例3，N皇后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
public:
    vector<vector<string> > solveNQueens(int n) 
    {
        vector<vector<string> >result;
        vector<string> location;
        vector<vector<int> > mark;
        for(int i=0;i<n;i++)
        {
            mark.push_back((vector<int>());
            for(int j=0;j<n;j++)
            {
                mark[i].push_back(0);
            }
            location.push_back("");
            location[i].append(n,'.');
        }
        generate(0,n,location,result,mark);
        return result;
            
    }
        
private:
    void put_down_the_queen(int x,int y,vector<vector<int> > &mark)
    {
        static const int dx[]={-1,-1,-1,0,1,1,1,0};
        static const int dy[]={-1,0,1,1,1,0,-1,-1};
        mark[x][y]=1;
        for(int i=1;i<mark.size();i++)
        {
            for(int j=0;j<8;j++)
            {
                int new_x=x+i*dx[j];
                int new_y=y+i*dy[j];
                if(new_x>=0 && new_x<mark.size() && new_y>=0 && new_y<mark.size())
                {
                    mark[new_x][new_y]=1;
                }
            }
        }
    }
    void gegerate(int k,int n,vector<string> &location,vector<vector<string> >&result,vector<vector<int> > &mark)
    {
        if(k==n)
        {
            result.push_back(location);
            return;
            
        }
        for(int i=0;i<n;i++)
        {
           if(mark[k][i]==0)
           {
               vector<vector<int> >temp_mark=mark;
               location[k][i]='Q';
               put_down_the_queen(k,i,mark);
               generate(k+1,n,location,result,mark);
               mark=temp_mark;
               location[k][i]='.';
           }
        }
    }
};

例4，求逆序数。已知数组nums,求新数组count，count[i]代表了在nums[i]右侧且比nums[i]小的元素个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution
{
public:
   vector<int> countSmaller(vector<int> &nums)
   {
       vector<int> count;
       vector<pair<int,int> > vec;
       for(int i=0;i<nums.size();i++)
       {
           vec.push_back(make_pair(nums[i],i));
           count.push_back(0);
       }
       merge_sort(vec,count);
       return count;
   }
private:
    void merge_sort_two_vec(vector<pair<int,int> > &sub_vec1,vector<pair<int,int> > &sub_vec2,vector<pair<int,int> > &vec,vector<int> &count)
    {
        int i=0;
        int j=0;
        while(i<sub_vec1.size() && j<sub_vec2.size())
        {
            if(sub_vec1[i].first<=sub_vec2[j].first)
            {
                count[sub_vec1[i].second] +=j;
                vec.push_back(sub_vec1[i]);
                i++;
            }
            else
            {
                vec.push_back(sub_vec2[j]);
                j++;
            }
        }
        for(;i<sub_vec1.size();i++)
        {   
            count[sub_vec1[i].second] +=j;
            vec.push_back(sub_vec1[i]);
        }
        for(;j<sub_vec2.size();j++)
        {
            vec.push_back(sub_vec2[j]);
        }
    }
    void merge_sort(vector<pair<int,int> > &vec,vector<int> &count)
    {
        if(vec.size()<2)
        {
            return;
        }
        int mid=vec.size()/2;
        vector<pair<int,int> > sub_vec1;
        vector<pair<int,int> > sub_vec2;
        for(int i=0;i<mid;i++)
        {
            sub_vec1.push_back(vec[i]);
        }
        for(int i=mid;i<vec.size();i++)
        {
            sub_vec2.push_back(vec[i]);
        }
        merge_sort(sub_vec1,count);
        merge_sort(sub_vec2,count);
        vec.clear();
        merge_sort_two_vec(sub_vec1,sub_vec2,vec,count);
    }
};

预备知识。归并排序。

已知两个排序数组，将这两个数组合并为一个排序数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void merge_sortedTwoVec(vector<int> &sub_vec1,vectoer<int> &sub_vec2,vector<int> vec)
{
    int i=0;
    int j=0;
    while(i<sub_vec1.size() && j<sub_vec2.size()) //注意这里不能用for(;i<sub_vec1.size(),j<sub_vec2.size();)!!!!
    {
        if(sub_vec1[i]<=sub_vec2[j])
        {
            vec.push_back(sub_vec1[i]);
            i++;
        }
        else
        {
            vec.push_back(sub_vec2[j]);
            j++;
        }
        for(;i<sub_vec1.size();i++)
        {
            vec.push_back(sub_vec1[i]);
        }
        for(j<sub_vec2.size();j++)
        {
            vec.push_back(sub_vec2[j]);
        }
    }
}

对一个数组进行归并排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void merge_vec(vector<int> &vec)
{
    if(vec.size())<2) return;
    int mid=vec.size()/2;
    vector<int> vec1;
    vector<int> vec2;
    for(int i=0;i<mid;i++)
    {
        vec1.push_back(vec[i]);
    }
    for(int j=mid;j<vec.size();j++)
    {
        vec2.push_back(vec[j]);
    }
    merge_vec(vec1);
    merge_vec(vec2);
    vec.clear();
    merge_sortedTwoVec(vec1,vec2,vec);
}

5 二叉树与图（回到目录）

二分查找的两种方法

方法1（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool binary_search(vector<int> &sort_array,int begin,int end,int target)
{
    if(begin>end) return false;
    int mid=(begin+end)/2;
    if(target==sort_array[mid])
    {
        return ture;
    }
    else if(target<sort_array[mid])
    {
        return binary_search(sort_array,begin,mid-1,target);
    }
    else if(target>sort_array[mid])
    {
        return binary_search(sort_array,mid+1,end,target);
    }
    
}

方法2（循环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool binary_search(vector<int> &sort_array,int target)
{
    int begin=0;
    int end=sort_array.size()-1;
    while(begin<=end)
    {
        int mid=(begin+end)/2;
        if(target==sort_array[mid])
        {
            return true;
        }
        else if(target<sort_array[mid])
        {
            end=mid-1;
        }
        else if(target>sort_array[mid])
        {
            begin=mid+1;   
        }
    }
    return false;
}

例1，插入位置。给定一个排序数组nums(无重复元素)与目标值target，如果target在nums里出现，则返回target所在下标，如果target未在nums中出现，则返回target应该插入的位置的数组下标，使得将target插入数组后，数组仍然有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int index=-1;
        int begin=0;
        int end=nums.size()-1;
        while(index==-1)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                index=mid;
            }
            else if(target<nums[mid])
            {
                if(mid==0 || target>nums[mid-1])
                {
                    index=mid;
                }
                end=mid-1;
            }
            else if(target>nums[mid])
            {
                if(mid==nums.size()-1 || target<nums[mid+1])
                {
                    index=mid+1;
                }
                begin=mid+1;
            }
        }
        return index;
    }
};

例2，区间查找。给定一个排序数组nums(有重复元素)与目标值target，如果target在nums里出现，则返回target所在区间的左右断电下标（[左，右]），如果target在nums里未出现，则返回[-1,-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> result;
        result.push_back(left_bound(nums,target));
        result.push_back(right_bound(nums,target));
        return result;
    }
private:
    int left_bound(vector<int> &nums,int target)
    {
        int begin=0,end=nums.size()-1;
        while(begin<=end)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                if(nums[mid-1]<target || mid==0)
                {
                    return mid;
                }
                end=mid-1;
            }
            else if(target<nums[mid])
            {
                end=mid-1;
            }
            else if(target>nums[mid])
            {
                begin=mid+1;
            }
        }
        return -1;
    }
    
int right_bound(vector<int> &nums,int target)
{
    int begin=0,end=nums.size()-1;
    while(begin<=end)
    {
        int mid=(begin+end)/2;
        if(target==nums[mid])
        {
            if(nums[mid+1]>target || mid==nums.size()-1)
            {
                return mid;
            }
            begin=mid+1;
        }
       else if(target<nums[mid])
        {
            end=mid-1;
        }
        else if(target>nums[mid])
        {
            begin=mid+1;
        }
    }
    return -1;
}
};

例3，旋转数组。给定一个排序数组nums(没有重复元素)，且nums可能以某个未知下标旋转，给定目标值target,求target是否在nums中出现，若出现返回所在下标，未出现返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int begin=0;
        int end=nums.size()-1;
        while(begin<=end)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                return mid;
            }
            else if(target<nums[mid])
            {
                if(nums[begin]<nums[mid])
                {
                    if(target>=nums[begin])
                    {
                        end=mid-1;
                    }
                    else
                    {
                        begin=mid+1;
                    }
                }
                else if(nums[begin]>nums[mid])
                {
                    end=mid-1;
                }
                else if(nums[begin]==nums[mid])
                {
                    begin=mid+1;
                }
            }
            else if(target>nums[mid])
            {
                if(nums[begin]<nums[mid])
                {
                    begin=mid+1;
                }
                else if(nums[begin]>nums[mid])
                {
                    if(target>=nums[begin])
                    {
                        end=mid-1;
                    }
                    else
                    {
                        begin=mid+1;
                    }
                }
                else if(nums[begin]==nums[mid])
                {
                    begin=mid+1;
                }
            }
        }
        return -1;
    }
};

例4，二叉查找树编码和解码。给定一个二叉查找树，实现对该二叉树编码与解码功能。编码即将该二查找树转为字符串，解码即将字符串转为二叉查找树。不限制使用何种编码算法，只需保证当对二叉查找树调用编码功能后可再调用解码功能将其复原。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        string data;
        BST_preorder(root,data);
        return data;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        if(data.length()==0)
        {
            return NULL;
        }
        vector<TreeNode*> node_vec;
        int val=0;
        for(int i=0;i<data.length();i++)
        {
            if(data[i]=='#')
            {
                node_vec.push_back(new TreeNode(val));
                val=0;
            }
            else
            {
                val=val*10+data[i]-'0';     
            }
        }
        for(int i=1;i<node_vec.size();i++)
            {
                BST_insert(node_vec[0],node_vec[i]);
            }
        return node_vec[0];
    }
private:
    void change_int_to_str(int val,string &str_val)
    {
        string temp;
        while(val)
        {
            temp +=val%10+'0';
            val=val/10;
        }
        for(int i=temp.length()-1;i>=0;i--)
        {
            str_val += temp[i];
        }
        str_val += '#';
    }
  void BST_preorder(TreeNode* node,string &data)
    {
        if(!node)
        {
            return;
        }
        string str_val;
        change_int_to_str(node->val,str_val);
        data=data+str_val;
        BST_preorder(node->left,data);
        BST_preorder(node->right,data);
    }
    void BST_insert(TreeNode* node,TreeNode* insert_node)
    {
        if(insert_node->val < node->val)
        {
            if(node->left)
            {
                BST_insert(node->left,insert_node);
            }
            else
            {
                node->left=insert_node;
            }
        }
        else
        {
            if(node->right)
            {
                BST_insert(node->right,insert_node);
            }
            else
            {
                node->right=insert_node;
            }
        }
    }
};

6 二分查找与二叉查找树（回到目录）

二分查找的两种方法

方法1（递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool binary_search(vector<int> &sort_array,int begin,int end,int target)
{
    if(begin>end) return false;
    int mid=(begin+end)/2;
    if(target==sort_array[mid])
    {
        return ture;
    }
    else if(target<sort_array[mid])
    {
        return binary_search(sort_array,begin,mid-1,target);
    }
    else if(target>sort_array[mid])
    {
        return binary_search(sort_array,mid+1,end,target);
    }
    
}

方法2（循环）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool binary_search(vector<int> &sort_array,int target)
{
    int begin=0;
    int end=sort_array.size()-1;
    while(begin<=end)
    {
        int mid=(begin+end)/2;
        if(target==sort_array[mid])
        {
            return true;
        }
        else if(target<sort_array[mid])
        {
            end=mid-1;
        }
        else if(target>sort_array[mid])
        {
            begin=mid+1;   
        }
    }
    return false;
}

例1，插入位置。给定一个排序数组nums(无重复元素)与目标值target，如果target在nums里出现，则返回target所在下标，如果target未在nums中出现，则返回target应该插入的位置的数组下标，使得将target插入数组后，数组仍然有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) 
    {
        int index=-1;
        int begin=0;
        int end=nums.size()-1;
        while(index==-1)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                index=mid;
            }
            else if(target<nums[mid])
            {
                if(mid==0 || target>nums[mid-1])
                {
                    index=mid;
                }
                end=mid-1;
            }
            else if(target>nums[mid])
            {
                if(mid==nums.size()-1 || target<nums[mid+1])
                {
                    index=mid+1;
                }
                begin=mid+1;
            }
        }
        return index;
    }
};

例2，区间查找。给定一个排序数组nums(有重复元素)与目标值target，如果target在nums里出现，则返回target所在区间的左右断电下标（[左，右]），如果target在nums里未出现，则返回[-1,-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution 
{
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        vector<int> result;
        result.push_back(left_bound(nums,target));
        result.push_back(right_bound(nums,target));
        return result;
    }
private:
    int left_bound(vector<int> &nums,int target)
    {
        int begin=0,end=nums.size()-1;
        while(begin<=end)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                if(nums[mid-1]<target || mid==0)
                {
                    return mid;
                }
                end=mid-1;
            }
            else if(target<nums[mid])
            {
                end=mid-1;
            }
            else if(target>nums[mid])
            {
                begin=mid+1;
            }
        }
        return -1;
    }
    
int right_bound(vector<int> &nums,int target)
{
    int begin=0,end=nums.size()-1;
    while(begin<=end)
    {
        int mid=(begin+end)/2;
        if(target==nums[mid])
        {
            if(nums[mid+1]>target || mid==nums.size()-1)
            {
                return mid;
            }
            begin=mid+1;
        }
       else if(target<nums[mid])
        {
            end=mid-1;
        }
        else if(target>nums[mid])
        {
            begin=mid+1;
        }
    }
    return -1;
}
};

例3，旋转数组。给定一个排序数组nums(没有重复元素)，且nums可能以某个未知下标旋转，给定目标值target,求target是否在nums中出现，若出现返回所在下标，未出现返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int begin=0;
        int end=nums.size()-1;
        while(begin<=end)
        {
            int mid=(begin+end)/2;
            if(target==nums[mid])
            {
                return mid;
            }
            else if(target<nums[mid])
            {
                if(nums[begin]<nums[mid])
                {
                    if(target>=nums[begin])
                    {
                        end=mid-1;
                    }
                    else
                    {
                        begin=mid+1;
                    }
                }
                else if(nums[begin]>nums[mid])
                {
                    end=mid-1;
                }
                else if(nums[begin]==nums[mid])
                {
                    begin=mid+1;
                }
            }
            else if(target>nums[mid])
            {
                if(nums[begin]<nums[mid])
                {
                    begin=mid+1;
                }
                else if(nums[begin]>nums[mid])
                {
                    if(target>=nums[begin])
                    {
                        end=mid-1;
                    }
                    else
                    {
                        begin=mid+1;
                    }
                }
                else if(nums[begin]==nums[mid])
                {
                    begin=mid+1;
                }
            }
        }
        return -1;
    }
};

例4，二叉查找树编码和解码。给定一个二叉查找树，实现对该二叉树编码与解码功能。编码即将该二查找树转为字符串，解码即将字符串转为二叉查找树。不限制使用何种编码算法，只需保证当对二叉查找树调用编码功能后可再调用解码功能将其复原。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        string data;
        BST_preorder(root,data);
        return data;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        if(data.length()==0)
        {
            return NULL;
        }
        vector<TreeNode*> node_vec;
        int val=0;
        for(int i=0;i<data.length();i++)
        {
            if(data[i]=='#')
            {
                node_vec.push_back(new TreeNode(val));
                val=0;
            }
            else
            {
                val=val*10+data[i]-'0';     
            }
        }
        for(int i=1;i<node_vec.size();i++)
            {
                BST_insert(node_vec[0],node_vec[i]);
            }
        return node_vec[0];
    }
private:
    void change_int_to_str(int val,string &str_val)
    {
        string temp;
        while(val)
        {
            temp +=val%10+'0';
            val=val/10;
        }
        for(int i=temp.length()-1;i>=0;i--)
        {
            str_val += temp[i];
        }
        str_val += '#';
    }
  void BST_preorder(TreeNode* node,string &data)
    {
        if(!node)
        {
            return;
        }
        string str_val;
        change_int_to_str(node->val,str_val);
        data=data+str_val;
        BST_preorder(node->left,data);
        BST_preorder(node->right,data);
    }
    void BST_insert(TreeNode* node,TreeNode* insert_node)
    {
        if(insert_node->val < node->val)
        {
            if(node->left)
            {
                BST_insert(node->left,insert_node);
            }
            else
            {
                node->left=insert_node;
            }
        }
        else
        {
            if(node->right)
            {
                BST_insert(node->right,insert_node);
            }
            else
            {
                node->right=insert_node;
            }
        }
    }
};

7 哈希表与字符串（回到目录）

例1，最长回文串。已知一个只包括大小写字符的字符串，求用该字符串中的字符可以生成的最长回文字符串长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int longestPalindrome(string s) 
    {
        int char_map[128]={0};
        int max_length=0;
        int flag=0;
        for(int i=0;i<s.length();i++)
        {
            char_map[s[i]]++;
        }
        for(int i=0;i<128;i++)
        {
            if(char_map[i]%2==0)
            {
                max_length=max_length+char_map[i];
            }
            else
            {
                max_length=max_length+char_map[i]-1;
                flag=1;
            }
        }
        return max_length+flag;
        
    }
};

补充，leetcode 5:最长回文子串

超出时间限制的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    string longestPalindrome(string s) 
    {
        string res;
        if(s.empty() || s.length()==1)
        {
            return s;
        }
        
        for(int i=0;i<s.length();i++)
        {
            for(int j=s.length()-1;j>i;j--)
            {
                string temp=s.substr(i,j-i+1);
                if(isPalindrome(temp))
                {
                    if(temp.length()>res.length())
                    {
                        res=temp;
                        break;
                    }
                }
            }
        }
        if(res.empty() && !s.empty())
        {
            res=s[0];
        }
        return res;
    }
private:
    bool isPalindrome(string str)
    {
        bool res=true;
        for(int ii=0,jj=str.length()-1;ii<jj;ii++,jj--)
        {
            if(str[ii] !=str[jj])
            {
                res=false;
                break;
            }
        }
        return res;
    }
};

例2，已知字符串pattern与字符串str，确认str是否与pattern匹配。str与pattern匹配代表字符串str中的单词与pattern中的字符一一对应。（其中pattern中只包含小写字符，str中的单词只包含小写字符，使用空格分隔）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    bool wordPattern(string pattern, string str) 
    {
        map<string,char> word_map;
        char used[128]={0};
        string word;
        int pos=0;
        str.push_back(' ');
        for(int i=0;i<str.length();i++)
        {
            if(str[i]==' ')
            {
                if(pos==pattern.length())
                {
                    return false;
                }
                if(word_map.find(word)==word_map.end())
                {
                    if(used[pattern[pos]])
                    {
                        return false;
                    }
                    else
                    {
                        word_map[word]=pattern[pos];
                        used[pattern[pos]]=1;
                    }
                }
                else
                {
                    if(word_map[word]!=pattern[pos])
                    {
                        return false;
                    }
                }
                word="";
                pos++;
                
            }
            else
            {
                word=word+str[i];
            }
        }
        if(pos!=pattern.length())
        {
            return false;
        }
        return true;
    }
};

例3，同字符词语分组。已知一组字符串，将所有anagram(由叠倒字母顺序而构成的字)放在一起输出。

例如：[“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

返回：[[“ate,”eat],”tea”],[“nat”,”tan”],[“bat”]]
方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {  
        map<string,vector<string> > anagram;
        vector<vector<string> >res;
        for(int i=0;i<strs.size();i++)
        {
            string str=strs[i];
            sort(str.begin(),str.end());
            if(anagram.find(str)==anagram.end())
            {
                vector<string> item;
                anagram[str]=item;
            }
            anagram[str].push_back(strs[i]);
        }
        map<string,vector<string> > ::iterator it;
        for(it=anagram.begin();it!=anagram.end();it++)
        {
            res.push_back((*it).second);
        }
        return res;
    }
};

方法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {  
        map<vector<int>,vector<string> >anagram;
        vector<vector<string> > res;
        for(int i=0;i<strs.size();i++)
        {
            vector<int> vec;
            change_to_vec(strs[i],vec);
            if(anagram.find(vec)==anagram.end())
            {
                vector<string> item;
                anagram[vec]=item;
            }
            anagram[vec].push_back(strs[i]);
        }
        map<vector<int>,vector<string> >::iterator it;
        for(it=anagram.begin();it!=anagram.end();it++)
        {
            res.push_back((*it).second);
        }
        return res;
    }
private:
    void change_to_vec(string &str,vector<int> &vec)
    {
        for(int i=0;i<26;i++)
        {
            vec.push_back(0);
        }
        for(int i=0;i<str.length();i++)
        {
            vec[str[i]-'a']++;
        }
    }
};

例4，无重复字符的最长字串。已知一个字符串，求用该字符串的无重复字符的最长字串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        int begin=0;
        int result=0;
        int char_map[128]={0};
        string word="";
        for(int i=0;i<s.length();i++)
        {
            char_map[s[i]]++;
            if(char_map[s[i]]==1)
            {
                word += s[i];
                if(result<word.length())
                {
                    result=word.length();
                }
            }
            else
            {
                while(begin<i && char_map[s[i]]>1)
                {
                    char_map[s[begin]]--;
                    begin++;
                }
                word="";
                for(int j=begin;j<=i;j++)
                {
                    word += s[j];
                }
            }
        }
        return result;
    }
};

例5，重复的DNA序列。将DNA序列看作是只包含[‘A’,’C’,’G’,’T’]4个字符的字符串，给一个DNA字符串，找到所有长度为10的且出现超过1次的子串。

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) 
    {
        vector<string> result;
        map<string,int> str_map;
        for(int i=0;i<s.length();i++)
        {
            string subStr=s.substr(i,10);
            str_map[subStr]++;
            
        }
        map<string,int> ::iterator it;
        for(it=str_map.begin();it!=str_map.end();it++)
        {
            if(it->second >1)
            {
                result.push_back(it->first);
            }
        }
        return result;
    }
};

方法2:使用编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int g_hash_map[1048576] = {0};
std::string change_int_to_DNA(int DNA){
	static const char DNA_CHAR[] = {'A', 'C', 'G', 'T'};
	std::string str;		    	
	for (int i = 0; i < 10; i++){
		str += DNA_CHAR[DNA & 3];
		DNA = DNA >> 2;
	}
	return str;
}
class Solution {
public:
    std::vector<std::string> findRepeatedDnaSequences(std::string s) {
    	std::vector<std::string> result;
		if (s.length() < 10){
	    	return result;
	    }
	    for (int i = 0; i < 1048576; i++){
	    	g_hash_map[i] = 0;
	    }	    
    	int char_map[128] = {0};
    	char_map['A'] = 0;
    	char_map['C'] = 1;
    	char_map['G'] = 2;
    	char_map['T'] = 3;    	
    	int key = 0;
    	for (int i = 9; i >= 0; i--){
	    	key = (key << 2) + char_map[s[i]];
	    }
    	g_hash_map[key] = 1;
    	for (int i = 10; i < s.length(); i++){
    		key = key >> 2;
    		key = key | (char_map[s[i]] << 18);
			g_hash_map[key]++;
	    }
	    for (int i = 0; i < 1048576; i++){
    		if (g_hash_map[i] > 1){
	    		result.push_back(change_int_to_DNA(i));
		    }
    	}
    	return result;
    }
};

例6，已知字符串S与字符串T,求S中的最小窗口（区间），使得这个区间中包含了字符T中的所有字符。

例如：S=”ADOBECODEBANC”;T=”ABC”。包含T的子区间中，有“ADOBEC”,”CODEBA”,”BANC”等等；最小窗口的区间是“BANC”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    string minWindow(string s, string t) 
    {
        const int len=128;
        int map_s[len]={0};
        int map_t[len]={0};
        vector<int> vec_t;
        for(int i=0;i<t.length();i++)
        {
            map_t[t[i]]++;
        }
        for(int i=0;i<len;i++)
        {
            if(map_t[i]>0)
            {
                vec_t.push_back(i);
            }
        }
        int window_begin=0;
        string result;
        for(int i=0;i<s.length();i++)
        {
            map_s[s[i]]++;
            while(window_begin<i)
            {
                char begin_char=s[window_begin];
                if(map_t[begin_char]==0)
                {
                    window_begin++;
                }
                else if(map_t[begin_char]<map_s[begin_char])
                {
                    map_s[begin_char]--;
                    window_begin++;
                }
                else
                {
                    break;
                }
            }
            if(is_window_ok(map_s,map_t,vec_t))
            {
                int new_window_len=i-window_begin+1;
                if(result=="" || result.length()>new_window_len)
                {
                    result=s.substr(window_begin,new_window_len);
                }
            }
            
        }
        return result;
    }
private:
    bool is_window_ok(int map_s[],int map_t[],vector<int> &vec_t)
    {
        for(int i=0;i<vec_t.size();i++)
        {
            if(map_t[vec_t[i]>map_s[vec_t[i]]])
            {
                return false;
            }
        }
        return true;
    }
};

8 搜索（回到目录）

9 动态规划（回到目录）

例3，给定一个数组，求这个数组的连续子数组中，最大的那一段的和。如数组【-2，1，-3，4，-1，2，1，-5，4】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        vector<int> dp(nums.size()+6,0);
        dp[0]=nums[0];
        int max_res=dp[0];
        
        for(int i=1;i<nums.size();i++)
        {
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            if(max_res<dp[i])
            {
                max_res=dp[i];
            }
        }
        return max_res;
        
    }
};

例5，给定一个二维数组，其保存了一个数字三角形，求从数字三角形顶端到底端各数字和最小的路径之和，每次可以向下走相邻的两个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) 
    {
        vector<vector<int> > dp;
        for(int i=0;i<triangle.size();i++)
        {
            dp.push_back(vector<int>());
            for(int j=0;j<triangle[i].size();j++)
            {
                dp[i].push_back(0);
            }
        }
        for(int j=0;j<dp[dp.size()-1].size();j++)
        {
            dp[dp.size()-1][j]=triangle[dp.size()-1][j];
        }
        for(int i=dp.size()-2;i>=0;i--)
        {
            for(int j=0;j<dp[i].size();j++)
            {
                dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j];
            }
        }
        return dp[0][0];
    }
};

例6，已知一个未排序的数组，求这个数组的最长上升子序列的长度。例如：【1，3，2，3，1，4】，其中【1，3】，【1，2，3】，【1，2，3，4】都是它的上升子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        if(nums.size()==0) return 0;
        vector<int> dp(nums.size(),0);
        dp[0]=1;
        int res=1;
        for(int i=1;i<dp.size();i++)
        {
            dp[i]=1;
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j] && dp[i]<dp[j]+1)
                {
                    dp[i]=dp[j]+1;
                }
            }
            if(res<dp[i])
            {
                res=dp[i];
            }
        }
        return res;
    }
};

例7，已知一个二维数组，其中存储了非负整数，找到从左上角到右下角的一条路径，使得路径上的和最小。（移动过程中只能向下或者向右）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        if(grid.size()==0) return 0;
        int row=grid.size();
        int col=grid[0].size();
        vector<vector<int> >dp(row,vector<int>(col,0));
        dp[0][0]=grid[0][0];
        for(int j=1;j<col;j++)
        {
            dp[0][j]=grid[0][j]+dp[0][j-1];
            
        }
        for(int i=1;i<row;i++)
        {
            dp[i][0]=grid[i][0]+dp[i-1][0];
            for(int j=1;j<col;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[row-1][col-1];
    }
};

例8，地下城游戏。一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) 
    {
        //int res=0;
        int row=dungeon.size();
        int col=dungeon[0].size();
        vector<vector<int> >dp(row,vector<int>(col,0));
        dp[row-1][col-1]=max(1,1-dungeon[row-1][col-1]);
        for(int j=col-2;j>=0;j--)
        {
            dp[row-1][j]=max(1,dp[row-1][j+1]-dungeon[row-1][j]);
        }
        for(int i=row-2;i>=0;i--)
        {
            dp[i][col-1]=max(1,dp[i+1][col-1]-dungeon[i][col-1]);
        }
        for(int i=row-2;i>=0;i--)
        {
            for(int j=col-2;j>=0;j--)
            {
                int dp_min=min(dp[i+1][j],dp[i][j+1]);
                dp[i][j]=max(1,dp_min-dungeon[i][j]);
            }
        }
        return dp[0][0];
    }
};

10 高级数据结构(回到目录)

-------------本文结束感谢您的阅读-------------
您的小小鼓励，是我不断更新的强大动力！