26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

---

对一个已排序的数组，去掉其中的重复元素并返回新数组长度，相当于实现unique函数。多提一点，unique函数只去掉连续重复元素中的重复元素，并不保证unique之后的数组中没有重复元素，这点很重要，可以看cplusplus的例子，数组

10 20 20 20 30 30 20 20 10

unique之后的结果是

10 20 30 20 10 ?  ?  ?  ?

前面3个重复的20只取了一个，但是隔了两个30之后又出现了两次20，此时还是取了一个20，尽管前面已经出现过20了。所以为了实现对任意数组去重的目的，需要先sort再unique。
回到本题，思路很简单，初始化两个指针i,j，i指向不重复元素的最后一个下标，j遍历数组，如果nums[j]==nums[i]，说明重复，j++；否则把nums[j]放到nums[i+1]，i++。完整代码如下：

class Solution {
public:
    int removeDuplicates(vector<int>& nums)
    {
        if (nums.size() <= 1)
            return nums.size();
        int i = 0, j = i + 1;
        while (j < nums.size()) {
            if (nums[j] != nums[i]) {
                nums[i + 1] = nums[j];
                i++;
            }
            j++;
        }
        return i + 1;
    }
};

本代码提交AC，用时32MS。

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

---

交换链表的每两个相邻节点。样例不保证是偶数个节点，也可能出现奇数个节点，此时最后一个节点就不要交换了。 交换过程中需要使用3个指针，当前指针ln1，当前指针的下一个指针ln2以及ln1的副本ln3用于更改ln1的next。具体怎么变换的，在纸上画一画就知道了，下面是完整代码。

class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode *ln1 = head, *ln2 = ln1->next, *ln3 = ln1, *new_head = ln2;
        bool first = true;
        while (ln1) {
            ln2 = ln1->next;
            if (ln2 == NULL)
                break;
            ln1->next = ln2->next;
            ln2->next = ln1;
            if (!first) { // 第一次不需要更改ln3的指向
                ln3->next = ln2;
            }
            first = false;
            ln3 = ln1;
            ln1 = ln1->next;
        }
        return new_head;
    }
};

本代码提交AC，用时4MS，只击败了1.83%，郁闷，我这已经是O(n)的时间复杂度，O(1)的空间复杂度，不知道还可以怎样优化。

更漂亮的递归版本：

class Solution {
public:
    ListNode* swapPairs(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* second = head->next;
        head->next = swapPairs(head->next->next);
        second->next = head;
        return second;
    }
};

本代码提交AC，用时6MS，无语了。

23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

---

归并k个已排序的链表。 之前是归并2个已排序的链表，现在变成多个了。其实就是多路归并，思路之前都知道，不同思路的区别就在于怎样找到所有链表当前位置的最小值，可以直接线性查找，也可以用败者树、胜者树或者堆。我一开始用线性查找，不出意外的TLE了，后来改用建堆的方法，顺利通过。 写代码越来越懒了，直接上STL，需要注意的是STL中的make_heap默认建的是大顶堆，我们需要传自己的比较函数进去以便构建小顶堆。

typedef struct Node {
    ListNode* ln;
    int idx;
    bool operator<(const Node& p) const { return this->ln->val < p.ln->val; }
    bool operator>(const Node& p) const { return this->ln->val > p.ln->val; }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        ListNode *ans = new ListNode(0), *head = ans;
        vector<Node> vn;
        for (int i = 0; i < lists.size(); i++) {
            if (lists[i] != NULL) {
                Node nd;
                nd.ln = lists[i];
                nd.idx = i;
                vn.push_back(nd);
                lists[i] = lists[i]->next;
            }
        }
        if (vn.size() == 0)
            return NULL;
        make_heap(vn.begin(), vn.end(), greater<Node>());
        while (true) {
            Node tmp = vn.front();
            ans->next = tmp.ln;
            ans = ans->next;
            pop_heap(vn.begin(), vn.end(), greater<Node>());
            vn.pop_back();
            if (lists[tmp.idx] != NULL) {
                tmp.ln = lists[tmp.idx];
                vn.push_back(tmp);
                push_heap(vn.begin(), vn.end(), greater<Node>());
                lists[tmp.idx] = lists[tmp.idx]->next;
            }
            if (vn.empty())
                break;
        }
        return head->next;
    }
};

本代码提交AC，用时420MS。

二刷。更简单的是直接使用STL的优先队列，代码如下：

struct LNNode {
	ListNode* ln;
	LNNode() :ln(NULL) {};
	bool operator<(const LNNode& ln_) const{ // 注意两个const都不能少
		return ln->val > ln_.ln->val;
	}
};
class Solution {
public:
	ListNode* mergeKLists(vector<ListNode*>& lists) {
		priority_queue<LNNode> pq;
		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				LNNode cur;
				cur.ln = lists[i];
				pq.push(cur);
			}
		}
		ListNode* root = new ListNode(0);
		ListNode* ans = root;
		while (!pq.empty()) {
			LNNode cur = pq.top();
			pq.pop();
			root->next = cur.ln;
			root = root->next;
			if (cur.ln->next) {
				LNNode nxt;
				nxt.ln = cur.ln->next;
				pq.push(nxt);
			}
		}
		return ans->next;
	}
};

本代码提交AC，用时32MS。

或者不用定义新的类，直接用原来的ListNode*，但新增一个比较函数，代码如下：

struct cmp {
	bool operator()(ListNode* l1, ListNode* l2) {
		return l1->val > l2->val;
	}
};

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

本代码提交AC，用时32MS。

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

---

要求产生所有包含n对括号的合法字符串。 这一看就是递归的题，我开始用DFS来解，假设□表示所有n-1对括号的合法字符串，则要产生所有n对括号的合法字符串，有三种可能的情况，可以把新的括号对加在原有字符串的前面，后面或者包住之前的字符串，即”()□”、”□()”和”(□)”。但是有一个问题，即如果□是”()()()()”这样的形式，则新增的括号放在前面和后面是同一种，所以需要判断□是否对称。 第一版代码如下：

typedef struct Par_Pair {
    string par;
    bool is_symmetric;
};
class Solution {
public:
    void dfs(int step, vector<Par_Pair>& ans)
    {
        if (step == 1) {
            Par_Pair pp;
            pp.par = "()";
            pp.is_symmetric = true;
            ans.push_back(pp);
            return;
        }
        dfs(step – 1, ans);
        int sz = ans.size();
        for (int i = 0; i < sz; i++) {
            if (ans[i].is_symmetric) {
                Par_Pair pp;
                pp.is_symmetric = false;
                pp.par = "(" + ans[i].par + ")";
                ans.push_back(pp);
                ans[i].par = "()" + ans[i].par;
            }
            else {
                Par_Pair pp;
                pp.is_symmetric = false;
                pp.par = "()" + ans[i].par;
                ans.push_back(pp);
                pp.par = ans[i].par + "()";
                ans.push_back(pp);
                ans[i].par = "(" + ans[i].par + ")";
            }
        }
    }
    vector<string> generateParenthesis(int n)
    {
        vector<Par_Pair> ans;
        dfs(n, ans);
        vector<string> rs;
        for (int i = 0; i < ans.size(); i++)
            rs.push_back(ans[i].par);
        return rs;
    }
};

本代码提交WA，当n=4时，会漏掉”(())(())”这种情况，这种情况是两个”(())”；同时会重复”()(())()”这种情况，因为n=3时”()(())”和”(())()”是不同合法字符串，且不对称，当n=4时，增加一对括号，可以在前或后，导致出现重复。

看网上题解，用递归方法，真是漂亮。不是考虑同时增加一对括号，而是左右括号分别考虑。在放置括号时，为了合法，总是使剩余的左括号数少于右括号数，且当左右括号数相等时，先放置左括号。

其实自己枚举下剩余左右括号的数目left和right的大小关系，只有<、=、>三种关系，考虑下每种关系合法的放置操作即可。

class Solution {
public:
    void recur_gen(int left, int right, string s, vector<string>& ans)
    {
        if (left == 0 && right == 0) {
            ans.push_back(s);
            return;
        }
        if (left > 0)
            recur_gen(left – 1, right, s + "(", ans);
        if (right > 0 && left < right)
            recur_gen(left, right – 1, s + ")", ans);
    }
    vector<string> generateParenthesis(int n)
    {
        vector<string> ans;
        string s = "";
        recur_gen(n, n, s, ans);
        return ans;
    }
};

本代码提交AC，用时0MS。

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

---

归并两个有序链表，要求使用原有链表中的节点，所以只需要依次比较大小，改变原有节点的指向。 代码如下

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode *head = new ListNode(0), *l;
        l = head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                l->next = l1;
                l1 = l1->next;
            }
            else {
                l->next = l2;
                l2 = l2->next;
            }
            l = l->next;
        }
        if (l1)
            l->next = l1;
        else if (l2)
            l->next = l2;
        return head->next;
    }
};

本代码提交AC，用时8MS。

二刷。循环的时候用或运算也可以，代码更简洁。

class Solution {
public:
	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
		if (l1 == NULL)return l2;
		ListNode* ans = new ListNode(0);
		ListNode* root = ans;
		while (l1 || l2) {
			int v1 = l1 ? l1->val : INT_MAX;
			int v2 = l2 ? l2->val : INT_MAX;
			if (v1 != INT_MAX && v1 <= v2) {
				root->next = l1;
				root = root->next;
				l1 = l1->next;
			}
			else if (v2 != INT_MAX && v2 < v1) {
				root->next = l2;
				root = root->next;
				l2 = l2->next;
			}
		}
		return ans->next;
	}
};

本代码提交AC，用时8MS。

20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

---

判断一个带括号的字符串是否合法，直接用栈，水题，代码如下。

class Solution {
public:
    bool isValid(string s)
    {
        stack<char> pars;
        for (int i = 0; i < s.size(); i++) {
            if (pars.empty()) {
                pars.push(s[i]);
                continue;
            }
            char t = pars.top();
            if ((t == ‘(‘&& s[i] == ‘)’) || (t == ‘{ ‘&& s[i] == ‘ }’) || (t == ‘[‘&& s[i] == ‘]’))
                pars.pop();
            else
                pars.push(s[i]);
        }
        return pars.empty();
    }
};

本代码提交AC，用时0MS。

19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

---

给定一个链表，要求删除倒数第n个元素。我想到的做法是遍历一遍链表，同时把链表每个元素保存到一个数组中，遍历完之后就知道链表长度，这样就可以计算出倒数第n个元素是哪个元素，然后直接删掉即可。 代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        if (head->next == NULL)
            return NULL;
        vector<ListNode*> nodes;
        ListNode* ln = head;
        while (ln) {
            nodes.push_back(ln);
            ln = ln->next;
        }
        int target = nodes.size() – n;
        if (target == 0) {
            head->next = NULL;
            head = nodes[target + 1];
        }
        else if (target == nodes.size() – 1) {
            nodes[target – 1]->next = NULL;
        }
        else {
            nodes[target – 1]->next = nodes[target + 1];
        }
        return head;
    }
};

本代码提交AC，用时8MS。一看排名倒数，肯定还有更高效的算法，因为这种解法需要保存链表，而且是用vector.push_back的，所以肯定耗时。看题解，原来这是典型的快慢指针题，我这个非ACMer还是反应迟钝呀。

我们维护一个快指针和慢指针，初始的时候快慢都在起点，然后快指针先跑n步，此时快慢指针的距离为n，然后快慢指针同时跑，这样就能保持距离为n，当快指针到达末尾(NULL)的时候，慢指针刚好是在倒数第n的位置，真是巧妙。
但是为了删除倒数第n个节点，需要知道其前一个节点，所以让快指针到达NULL的前面位置停，即faster->next==NULL的时候停下来。
完整代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        if (head == NULL || head->next == NULL)
            return NULL;
        ListNode *slower = head, *faster = head;
        while (n–) {
            faster = faster->next;
        }
        if (faster == NULL)
            return head->next;
        while (faster->next) {
            faster = faster->next;
            slower = slower->next;
        }
        slower->next = slower->next->next;
        return head;
    }
};

本代码提交AC，用时4MS，果然快了不少。