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

zhuli19901106

Minimum Adjustment Cost
题意：给定一个数组，你可以随意改变每个元素，要求改好之后相邻两元素的差值不大于target。
解法：刚拿到这题真是毫无思路，后来才注意到下面给的提示，所有元素都不大于100，这其实就是在提示我们可以用比较暴力的做法，于是就有了下面的DP。如果不加这个限制条件，这种近乎穷举的做法必然是不可行的。
代码：

#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
/**
* @param A: An integer array.
* @param target: An integer.
*/
int MinAdjustmentCost(vector<int> A, int target) {
const int MAXV = 100;
int n = A.size();
if (n <= 1) {
return 0;
}
vector<vector<int> > dp;
dp.resize(n, vector<int>(MAXV + 1, INT_MAX));
int i, j, k;
for (i = 1; i <= MAXV; ++i) {
dp[0][i] = abs(i - A[0]);
}
int ll, rr;
for (i = 1; i < n; ++i) {
for (j = 1; j <= MAXV; ++j) {
ll = max(1, j - target);
rr = min(MAXV, j + target);
for (k = ll; k <= rr; ++k) {
dp[i][j] = min(dp[i][j], dp[i - 1][k]);
}
dp[i][j] += abs(j - A[i]);
}
}
int ans = INT_MAX;
for (i = 1; i <= MAXV; ++i) {
ans = min(ans, dp[n - 1][i]);
}
return ans;
}
private:
int abs(int x) {
return x >= 0 ? x : -x;
}
};

复制代码

复杂度：懒得算。不知为何，对这题有种厌恶感。就像当年讨厌考试一样，总觉得是为了考而考。做不出来不觉得可惜，AC了也毫无成就感。

zhuli19901106

Backpack
题意：背包问题，给定N件物品和一个容量M，看最满能装多满。
解法：请看代码。
代码：

class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
int backPack(int m, vector<int> A) {
vector<bool> dp;
dp.resize(m + 1, false);
dp[0] = true;
int n = A.size();
int i, j;
for (i = 0; i < n; ++i) {
for (j = m; j >= A[i]; --j) {
if (dp[j - A[i]]) {
dp[j] = true;
}
}
}
i = m;
while (!dp[i]) {
--i;
}
return i;
}
};

复制代码

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

zhuli19901106

Balanced Binary Tree
题意：给定一棵二叉树，判断是否为平衡二叉树。
解法：左子树和右子树的高度差不超过1，则平衡。当然，空树也算平衡。递归解决。
代码：

#include <unordered_map>
using namespace std;
/**
* 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 root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
bool isBalanced(TreeNode *root) {
um.clear();
if (root == NULL) {
return true;
}
um[NULL] = 0;
height(root);
return balance(root);
}
private:
unordered_map<TreeNode *, int> um;
int height(TreeNode *root) {
if (root == NULL) {
return 0;
}
return um[root] = max(height(root->left), height(root->right)) + 1;
}
bool balance(TreeNode *root) {
if (root == NULL) {
return true;
}
return balance(root->left) && balance(root->right) &&
abs(um[root->left] - um[root->right]) <= 1;
}
};

复制代码

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

zhuli19901106

Binary Tree Maximum Path Sum
题意：给定一棵二叉树，如果把这棵树看成一个无向图，起点和终点任选，求从一个节点到另一个节点的所有路径中，和最大的。求出最大和。
解法：这题代码比较简洁。其中singlePath表示从节点root出发，往下走能得到的最大和。doublePath表示经过root节点的路径的最大和。其余请参见代码。
代码：

#include <algorithm>
#include <climits>
#include <unordered_map>
using namespace std;
/**
* 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 root: The root of binary tree.
* @return: An integer
*/
int maxPathSum(TreeNode *root) {
ans = INT_MIN;
um.clear();
if (root == NULL) {
return ans;
}
um[NULL] = 0;
singlePath(root);
doublePath(root);
return ans;
}
private:
int ans;
unordered_map<TreeNode *, int> um;
void singlePath(TreeNode *root) {
if (root == NULL) {
return;
}
singlePath(root->left);
singlePath(root->right);
um[root] = max(um[root->left], um[root->right]) + root->val;
um[root] = max(um[root], root->val);
}
void doublePath(TreeNode *root) {
if (root == NULL) {
return;
}
ans = max(ans, um[root->left] + um[root->right] + root->val);
ans = max(ans, root->val);
doublePath(root->left);
doublePath(root->right);
}
};

复制代码

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

zhuli19901106

Validate Binary Search Tree
题意：给定一棵二叉树，判断是不是BST。
解法：既可以中序遍历然后判断序列是否有序，也可以像下面这样直接判断求出中序的前驱和后继。道理都是一样的。
代码：

/**
* 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 root: The root of binary tree.
* @return: True if the binary tree is BST, or false
*/
bool isValidBST(TreeNode *root) {
if (root == NULL) {
return true;
}
int lmin, rmax;
return validate(root, lmin, rmax);
}
private:
bool validate(TreeNode *root, int &lmin, int &rmax) {
int ll, lr, rl, rr;
if (root->left != NULL) {
if (!validate(root->left, ll, lr) || lr >= root->val) {
return false;
}
} else {
ll = lr = root->val;
}
lmin = ll;
if (root->right != NULL) {
if (!validate(root->right, rl, rr) || rl <= root->val) {
return false;
}
} else {
rl = rr = root->val;
}
rmax = rr;
return true;
}
};

复制代码

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

zhuli19901106

Partition List
题意：给定一个单链表和一个值target。把所有小于target的节点放前面，大于等于的放后面。要求两部分内部的相对顺序不能变。
解法：其实相对顺序不变不说也一样，因为最直观的解法就是逐个节点访问，按照大小分成两条链，然后再首尾合并即可。
代码：

/**
* 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.
* @param x: an integer
* @return: a ListNode
*/
ListNode *partition(ListNode *head, int x) {
if (head == NULL) {
return head;
}
ListNode *h1, *t1, *h2, *t2;
ListNode *p;
h1 = t1 = NULL;
h2 = t2 = NULL;
while (head != NULL) {
p = head;
head = head->next;
if (p->val < x) {
if (h1 == NULL) {
h1 = t1 = p;
t1->next = NULL;
} else {
t1->next = p;
t1 = t1->next;
t1->next = NULL;
}
} else {
if (h2 == NULL) {
h2 = t2 = p;
t2->next = NULL;
} else {
t2->next = p;
t2 = t2->next;
t2->next = NULL;
}
}
}
if (t1 != NULL) {
t1->next = h2;
return h1;
} else {
return h2;
}
}
};

复制代码

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

zhuli19901106

Maximum Depth of Binary Tree
题意：求二叉树的深度。
解法：递归解决。
代码：

#include <algorithm>
using namespace std;
/**
* 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 root: The root of binary tree.
* @return: An integer
*/
int maxDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};

复制代码

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

zhuli19901106

Sort List
题意：利用归并排序的思想，把一个单链表排序。要求常数空间复杂度哦。
解法：这题有意思，尤其是空间复杂度O(1)的要求。让我想起数组归并排序的非递归实现。这题思想也类似，不过实现很是复杂，我调都调了半天。现场面试碰见这种题，还要求O(1)空间的话，那就悬了。
代码：

// Let's make it strictly O(1) in space
/**
* 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: You should return the head of the sorted linked list,
using constant space complexity.
*/
ListNode *sortList(ListNode *head) {
if (head == NULL) {
return head;
}
int tlen = 0;
ListNode *p1, *p2;
p1 = head;
while (p1 != NULL) {
p1 = p1->next;
++tlen;
}
ListNode *h1, *t1;
ListNode *h2, *t2;
ListNode *h3, *t3;
ListNode *h, *t;
int len = 1;
int i;
while (len < tlen) {
// Set all pointers to NULL
h = t = NULL;
while (true) {
h1 = h2 = t1 = t2 = NULL;
i = 0;
// Get two sublists
while (head != NULL && i < len) {
if (h1 == NULL) {
h1 = t1 = head;
head = head->next;
} else {
t1->next = head;
head = head->next;
t1 = t1->next;
}
t1->next = NULL;
++i;
}
i = 0;
while (head != NULL && i < len) {
if (h2 == NULL) {
h2 = t2 = head;
head = head->next;
} else {
t2->next = head;
head = head->next;
t2 = t2->next;
}
t2->next = NULL;
++i;
}
if (h1 == NULL && h2 == NULL) {
break;
}
// Merge them into one sorted list
p1 = h1;
p2 = h2;
h3 = t3 = NULL;
while (p1 != NULL && p2 != NULL) {
if (p1->val < p2->val) {
if (h3 == NULL) {
h3 = t3 = p1;
p1 = p1->next;
} else {
t3->next = p1;
p1 = p1->next;
t3 = t3->next;
}
} else {
if (h3 == NULL) {
h3 = t3 = p2;
p2 = p2->next;
} else {
t3->next = p2;
p2 = p2->next;
t3 = t3->next;
}
}
t3->next = NULL;
}
while (p1 != NULL) {
if (h3 == NULL) {
h3 = t3 = p1;
p1 = p1->next;
} else {
t3->next = p1;
p1 = p1->next;
t3 = t3->next;
}
t3->next = NULL;
}
while (p2 != NULL) {
if (h3 == NULL) {
h3 = t3 = p2;
p2 = p2->next;
} else {
t3->next = p2;
p2 = p2->next;
t3 = t3->next;
}
t3->next = NULL;
}
// Add the list to tail
if (h == NULL) {
h = h3;
t = t3;
} else {
t->next = h3;
t = t3;
}
}
head = h;
len <<= 1;
}
return head;
}
};

复制代码

复杂度：时间O(N * log(N))，空间O(1)。空间O(N)的解法更容易实现，此处就不写了。

zhuli19901106

Reorder List
题意：给定一个单链表，把它变成1->n->2->n-1->...的形式。
解法：把链表分成前后两段A和B，然后把B段反转，然后交替归并，即ABABABAB...。得到的就是期望结果。
代码：

/**
* 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: void
*/
void reorderList(ListNode *head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode *h1, *h2;
ListNode *p1, *p2;
p1 = p2 = head;
h1 = head;
while (true) {
p2 = p2->next;
if (p2 == NULL) {
break;
}
p2 = p2->next;
if (p2 == NULL) {
break;
}
p1 = p1->next;
}
h2 = p1->next;
p1->next = NULL;
h2 = reverseList(h2);
ListNode *h, *t;
h = t = h1;
h1 = h1->next;
t->next = NULL;
while (h1 != NULL && h2 != NULL) {
t->next = h2;
h2 = h2->next;
t = t->next;
t->next = NULL;
t->next = h1;
h1 = h1->next;
t = t->next;
t->next = NULL;
}
while (h1 != NULL) {
t->next = h1;
h1 = h1->next;
t = t->next;
t->next = NULL;
}
while (h2 != NULL) {
t->next = h2;
h2 = h2->next;
t = t->next;
t->next = NULL;
}
}
private:
ListNode *reverseList(ListNode *head) {
if (head == NULL) {
return head;
}
ListNode *h, *p;
h = head;
head = head->next;
h->next = NULL;
while (head != NULL) {
p = head->next;
head->next = h;
h = head;
head = p;
}
return h;
}
};

复制代码

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

zhuli19901106

Remove Duplicates from Sorted Array
题意：给定一个单链表，去掉重复的值。
解法：略。
代码：

/**
* 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: head node
*/
ListNode *deleteDuplicates(ListNode *head) {
if (head == NULL) {
return head;
}
ListNode *p = head;
ListNode *q;
while (p->next != NULL) {
if (p->val == p->next->val) {
q = p->next;
p->next = q->next;
delete q;
continue;
}
p = p->next;
}
return head;
}
};

复制代码

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

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

浏览过的版块