分享我的Lintcode题解，目前进度244/248

zhuli19901106

Sort Letters by Case
题意：给定一个只有字母的字符串，把小写放前面，大写放后面。
解法：其实还是数组划分。
代码：

#include <cctype>
using namespace std;
class Solution {
public:
/**
* @param chars: The letters array you should sort.
*/
void sortLetters(string &letters) {
string &s = letters;
int n = s.length();
int i = 0;
int j = n - 1;
while (true) {
while (i <= j && islower(s[i])) {
++i;
}
while (i <= j && isupper(s[j])) {
--j;
}
if (i >= j) {
break;
}
swap(s[i++], s[j--]);
}
}
};

复制代码

复杂度：时间O(N)，空间O(1)。

zhuli19901106

Palindrome Partitioning II
题意：给定一个字符串，允许你把它分割成一些回文串。请问最少能分成几段？
解法：很典型的DP题目。dp{i}{j}表示s{i...j}最少能分成几段。
代码：

#include <vector>
using namespace std;
class Solution {
public:
/**
* @param s a string
* @return an integer
*/
int minCut(string s) {
int n = s.length();
if (n <= 1) {
return 0;
}
vector<vector<bool> > pal;
pal.resize(n, vector<bool>(n, false));
int i, j;
for (i = 0; i < n; ++i) {
pal[i][i] = true;
}
for (i = 0; i < n - 1; ++i) {
pal[i][i + 1] = s[i] == s[i + 1];
}
for (i = 2; i < n; ++i) {
for (j = 0; j + i < n; ++j) {
pal[j][j + i] = s[j] == s[j + i] && pal[j + 1][j + i - 1];
}
}
vector<int> dp;
dp.resize(n);
for (i = 0; i < n; ++i) {
dp[i] = i + 1;
if (pal[0][i]) {
dp[i] = 1;
continue;
}
for (j = 0; j < i; ++j) {
if (pal[j + 1][i]) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1] - 1;
}
};

复制代码

复杂度：时间O(N ^ 2)，空间O(N ^ 2)。

zhuli19901106

Minimum Path Sum
题意：Frequently Ask Question
解法：Frequently Answered Question
代码：

#include <algorithm>
using namespace std;
class Solution {
public:
/**
* @param grid: a list of lists of integers.
* @return: An integer, minimizes the sum of all numbers along its path
*/
int minPathSum(vector<vector<int> > &grid) {
vector<vector<int> > &a = grid;
int n, m;
n = a.size();
if (n == 0) {
return 0;
}
m = a[0].size();
if (m == 0) {
return 0;
}
int i, j;
for (i = 1; i < n; ++i) {
a[i][0] += a[i - 1][0];
}
for (i = 1; i < m; ++i) {
a[0][i] += a[0][i - 1];
}
for (i = 1; i < n; ++i) {
for (j = 1; j < m; ++j) {
a[i][j] += min(a[i][j - 1], a[i - 1][j]);
}
}
return a[n - 1][m - 1];
}
};

复制代码

复杂度：时间O(N * M)，空间O(1)。

zhuli19901106

Merge k Sorted Lists
题意：给定K个有序链表，把它们归并成一个有序链表。
解法：借助最小堆进行归并。把K个链表的表头放进堆中，每次选取最小的一个拿出来，并把它向前移一位。
代码：

#include <queue>
using namespace std;
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
struct Comp {
bool operator () (ListNode *&x, ListNode *&y)
{
return x->val > y->val;
}
};
class Solution {
public:
/**
* @param lists: a list of ListNode
* @return: The head of one sorted list.
*/
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode *, vector<ListNode *>, Comp> pq;
for (auto &it: lists) {
if (it != NULL) {
pq.push(it);
}
}
ListNode *h, *t;
ListNode *p, *q;
h = t = NULL;
while (!pq.empty()) {
p = pq.top();
q = p->next;
pq.pop();
if (q != NULL) {
pq.push(q);
}
if (h != NULL) {
t->next = p;
t = t->next;
} else {
h = t = p;
}
t->next = NULL;
}
return h;
}
};

复制代码

复杂度：时间O(K * log(K))空间O(K)。

zhuli19901106

本帖最后由 zhuli19901106 于 2015-7-26 20:50 编辑

又被吞掉一题：Merge k Sorted Lists

此处要特别提一下，这道题和下面这题在思路上是有关联的，有兴趣的同学可以做一下：
http://ac.jobdu.com/problem.php?pid=1534
关键词：杨氏矩阵，Young Tableau

此处特别感谢mgccl提供的O(K)时间的算法，实现用的是Haskell。比常见的O(K * log(K))更优化，可以参见他的博客。
http://www.chaoxuprime.com/posts/2014-04-02-selection-in-a-sorted-matrix.html

zhuli19901106

Linked List Cycle
题意：给定一个单链表，判断是否有环。
解法1：用哈希。
代码1：

#include <unordered_set>
using namespace std;
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
bool hasCycle(ListNode *head) {
if (head == NULL) {
return NULL;
}
unordered_set<ListNode *> us;
ListNode *p = head;
while (p != NULL) {
if (us.find(p) != us.end()) {
return true;
}
us.insert(p);
p = p->next;
}
return false;
}
};

复制代码

复杂度1：时间O(N)，空间O(N)。

解法2：追赶法。
代码2：

// The running pointers
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
bool hasCycle(ListNode *head) {
if (head == NULL) {
return NULL;
}
ListNode *p1, *p2;
p1 = head;
p2 = head->next;
while (p2 != NULL) {
p1 = p1->next;
p2 = p2->next;
if (p2 == NULL) {
return false;
}
p2 = p2->next;
if (p1 == p2) {
return true;
}
}
return false;
}
};

复制代码

复杂度2：时间O(N ^ 2)，空间O(1)。

zhuli19901106

Linked List Cycle II
题意：hard难度。给定一个单链表，判断是否有环。如果有，返回进入环的第一个节点；如果没有，返回NULL。
解法1：用哈希。
代码1：

// O(n) time and O(n) space
#include <unordered_set>
using namespace std;
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode *> us;
ListNode *p = head;
while (p != NULL) {
if (us.find(p) != us.end()) {
break;
}
us.insert(p);
p = p->next;
}
return p;
}
};

复制代码

复杂度1：时间O(N),空间O(N)。

解法2：这个题目碰见好几次了，第一次碰见的时候觉得这解法非常巧妙。关键思路在于如果你从头开始遍历，先到达了p->next，后到达p，那么这个节点p有什么特殊之处？
代码2：

/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
ListNode *detectCycle(ListNode *head) {
ListNode *p1, *p2;
p1 = head;
while (p1 != NULL) {
p2 = head;
while (true) {
if (p2 == p1->next) {
return p2;
}
if (p2 == p1) {
break;
}
if (p2 == NULL) {
return NULL;
}
p2 = p2->next;
}
p1 = p1->next;
}
return NULL;
}
};

复制代码

复杂度2：时间O(N ^ 2)，空间O(1)。

zhuli19901106

Convert Sorted List to Binary Search Tree
题意：给定一个有序链表，把它转换为平衡BST。
解法1：递归解决。还是对半分，中间作为根节点。不过链表没法随机访问，所以找到中点需要O(N)时间。
代码1：

/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: a tree node
*/
TreeNode *sortedListToBST(ListNode *head) {
if (head == NULL) {
return NULL;
}
ListNode *p;
int len = 0;
p = head;
while (p != NULL) {
p = p->next;
++len;
}
return convert(head, len);
}
private:
TreeNode *convert(ListNode *head, int len) {
if (len == 0) {
return NULL;
}
if (len == 1) {
return new TreeNode(head->val);
}
if (len == 2) {
TreeNode *h = new TreeNode(head->val);
h->right = new TreeNode(head->next->val);
return h;
}
int i;
ListNode *p = head;
for (i = 1; i <= (len - 1) / 2; ++i) {
p = p->next;
}
TreeNode *r = new TreeNode(p->val);
r->left = convert(head, (len - 1) / 2);
r->right = convert(p->next, len / 2);
return r;
}
};

复制代码

复杂度1：时间O(N * log(N))，空间O(N)。

解法2：用O(N)的时间把链表变成数组，然后用数组建立BST。这两步都是O(N)，所以总体是线性算法。其实这种思路最实用，如果1+1<3，为何非要选3呢。一步到位不一定最好。
代码2：

/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: a tree node
*/
TreeNode *sortedListToBST(ListNode *head) {
if (head == NULL) {
return NULL;
}
ListNode *p = head;
vector<int> A;
while (p != NULL) {
A.push_back(p->val);
p = p->next;
}
return sortedArrayToBST(A);
}
TreeNode *sortedArrayToBST(vector<int> &A) {
if (A.empty()) {
return NULL;
}
return convert(A, 0, A.size() - 1);
}
private:
TreeNode* convert(vector<int> &a, int ll, int rr) {
int mm = (ll + rr) / 2;
TreeNode* root = new TreeNode(a[mm]);
if (ll < mm) {
root->left = convert(a, ll, mm - 1);
}
if (rr > mm) {
root->right = convert(a, mm + 1, rr);
}
return root;
}
};

复制代码

复杂度2：时间O(N)，空间O(N)。

zhuli19901106

Climbing Stairs
题意：斐波那契。
解法：略。
代码：

class Solution {
public:
/**
* @param n: An integer
* @return: An integer
*/
int climbStairs(int n) {
if (n < 2) {
return 1;
}
int a1, a2, a3;
a1 = a2 = 1;
int i;
for (i = 2; i <= n; ++i) {
a3 = a1 + a2;
a1 = a2;
a2 = a3;
}
return a3;
}
};

复制代码

复杂度：时间O(N)，空间O(1)。

zhuli19901106

Copy List with Random Pointer
题意：给定一个单链表，把它复制一份。特别之处在于每个节点还有一个随机指针，此指针指向链表中某个节点或者NULL。复制时务必让新链表保留同样的指向关系。
解法1：用哈希。哈希真乃丧心病狂的万能数据结构。
代码1：

// O(n) solution with hashing
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
typedef RandomListNode RLN;
class Solution {
public:
/**
* @param head: The head of linked list with a random pointer.
* @return: A new head of a deep copy of the list.
*/
RLN *copyRandomList(RLN *head) {
if (head == NULL) {
return head;
}
int n, i;
RLN *p;
unordered_map<RLN *, int> um;
vector<RLN *> v;
p = head;
n = 0;
while (p != NULL) {
um[p] = n++;
v.push_back(new RLN(p->label));
p = p->next;
}
for (i = 0; i < n - 1; ++i) {
v[i]->next = v[i + 1];
}
p = head;
for (i = 0; i < n; ++i) {
v[i]->random = p->random != NULL ? v[um[p->random]] : NULL;
p = p->next;
}
return v[0];
}
};

复制代码

复杂度1：时间O(N)，空间O(N)。

解法2：还是直接读代码吧。我这次终于独立写出来了，前两次都是bug层出不穷，虽然这次也不那么顺利，但对这种巧妙的思路逐渐理解。说穿了，也就是在这些链表的指针间进行各种轮换，看起来就跟变魔术一样，各种花式技巧。（就是为了面试欺负小朋友才出这种题）
代码2：

// Whimsical solution
/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
/**
* @param head: The head of linked list with a random pointer.
* @return: A new head of a deep copy of the list.
*/
RandomListNode *copyRandomList(RandomListNode *head) {
if (head == NULL) {
return head;
}
RandomListNode *p, *q;
RandomListNode *h;
p = head;
while (p != NULL) {
q = p->random;
p->random = new RandomListNode(p->label);
p->random->next = q;
p = p->next;
}
p = head;
while (p != NULL) {
q = p->random;
q->random = q->next ? q->next->random : NULL;
p = p->next;
}
h = head->random;
p = head;
while (p != NULL) {
q = p->random;
p->random = q->next;
q->next = p->next ? p->next->random : NULL;
p = p->next;
}
return h;
}
};

复制代码

复杂度2：时间O(N)，空间O(1)，脑细胞O(你妹)。

分享我的Lintcode题解，目前进度244/248

浏览过的版块