# LeetCode 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]);
}

10 20 20 20 30 30 20 20 10


unique之后的结果是

10 20 30 20 10 ?  ?  ?  ?


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;
}
};

# LeetCode Swap Nodes in Pairs

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.

class Solution {
public:
{
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;
}
}
};

class Solution {
public:
{
return second;
}
};

# LeetCode 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

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;
}
}
};

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;
}
};

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;
}
};

# LeetCode Generate Parentheses

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:

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

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;
}
};

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;
}
};

# LeetCode 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;
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;
}
};

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;
}
};

# LeetCode 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();
}
};

# LeetCode 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.

Could you do this in one pass?

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

class Solution {
public:
{
return NULL;
while (n–) {
faster = faster->next;
}
if (faster == NULL)
while (faster->next) {
faster = faster->next;
slower = slower->next;
}
slower->next = slower->next->next;
}
};

# LeetCode Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].


Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

class Solution {
public:
void dfs(string& digits, int step, vector<string>& alphabeta, vector<string>& ans, bool is_first)
{
if (step == digits.size())
return;
string cur = alphabeta[digits[step] – ‘0’];
if (is_first) {
for (int i = 0; i < cur.size(); i++)
ans.push_back(cur.substr(i, 1));
is_first = false;
}
else {
int sz = ans.size(); //size要提前抽出来
for (int i = 0; i < sz; i++) {
string tmp = ans[i];
ans[i] = ans[i] + cur.substr(0, 1);
for (int j = 1; j < cur.size(); j++)
ans.push_back(tmp + cur.substr(j, 1));
}
}
dfs(digits, step + 1, alphabeta, ans, is_first);
}
vector<string> letterCombinations(string digits)
{
vector<string> alphabeta = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> ans;
dfs(digits, 0, alphabeta, ans, true);
return ans;
}
};

class Solution {
private:
void dfs(string& digits, int step, vector<string>& alphabeta, vector<string>& ans, string& candidate)
{
if (step == digits.size()) {
ans.push_back(candidate);
return;
}
int idx = digits[step] – ‘0’;
for (int i = 0; i < alphabeta[idx].size(); ++i) {
candidate.push_back(alphabeta[idx][i]);
dfs(digits, step + 1, alphabeta, ans, candidate);
candidate.pop_back();
}
}
public:
vector<string> letterCombinations(string digits)
{
if (digits == "")
return {};
vector<string> alphabeta = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
vector<string> ans;
string candidate = "";
dfs(digits, 0, alphabeta, ans, candidate);
return ans;
}
};