-
楼主 / webdriver
- 时间: 2014-9-25 00:27LeetCode (used to call i has 1337 code) is a social platform for preparing IT technical interviews. We strive to provide you with the best learning experience in preparing interviews for companies in the IT industry.
To be successful in a technical interview, we believe it is mainly repeating these three important steps:
Code. Read. Discuss.
We strive to provide you the LeetCode platform as the ultimate solution for preparing technical interviews.
1. Code -> Code solution using the Online Judge system.
2. Read -> Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -> Discuss your thoughts about the problem with other LeetCoders.
We hope that through our platform, you will grow into a LeetCoder. Not only will you be successful in all of your interviews, and most importantly, you will be a better coder in general !
This is Part 5 （第五部分）
第一部分： www.westca.com/Forums/...inese.html
第二部分： www.westca.com/Forums/...inese.html
第三部分： www.westca.com/Forums/...inese.html
第四部分： www.westca.com/Forums/...inese.html -
-
- 时间: 2014-9-25 00:29
-
-
- 时间: 2014-9-25 00:31推荐答案来了 (in C++) ...
back-tracking..
代码:
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solveSudoku(BOARDTYPE &board) {
solveSudokuRe(board, 0, 0);
}
bool solveSudokuRe(BOARDTYPE &board, int row, int col) {
getNextEmpty(board, row, col);
if (row == 9) return true;
vector<bool> avail(9, true);
getAvailable(board, avail, row, col);
for (int i = 0; i < 9; ++i)
{
if (!avail[i]) continue;
board[row][col] = i + '1';
if (solveSudokuRe(board, row, col)) return true;
}
board[row][col] = '.';
return false;
}
void getNextEmpty(BOARDTYPE &board, int &row, int &col) {
do {
if (board[row][col] == '.') return;
row = (col == 8) ? row + 1 : row;
col = (col + 1) % 9;
} while (row < 9);
}
void getAvailable(BOARDTYPE &board, vector<bool> &avail, int row, int col) {
for (int i = 0; i < 9; ++i) {
if (board[row][i] != '.') avail[board[row][i]-'1'] = false;
if (board[i][col] != '.') avail[board[i][col]-'1'] = false;
int box_i = row/3*3 + i/3, box_j = col/3*3 + i%3;
if (board[box_i][box_j] != '.') avail[board[box_i][box_j]-'1'] = false;
}
}
}; -
- 时间: 2014-9-25 00:32算法问题: Sum Root to Leaf Numbers
问题描述:
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25. -
- 时间: 2014-9-25 00:33推荐答案来了 (in C++) ...
1. Recursion (add to sum when reaching the leaf).
2. Iterative solution.
代码:
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sumNumbers(TreeNode *root) {
return sumNumbers_1(root);
}
int sumNumbers_1(TreeNode *root) {
int sum = 0;
sumNumbersRe(root, 0, sum);
return sum;
}
void sumNumbersRe(TreeNode *node, int num, int &sum) {
if (!node) return;
num = num * 10 + node->val;
if (!node->left && !node->right) {
sum += num;
return;
}
sumNumbersRe(node->left, num, sum);
sumNumbersRe(node->right, num, sum);
}
int sumNumbers_2(TreeNode *root) {
if (!root) return 0;
int res = 0;
queue<pair<TreeNode *, int>> q;
q.push(make_pair(root, 0));
while(!q.empty())
{
TreeNode *node = q.front().first;
int sum = q.front().second * 10 + node->val;
q.pop();
if (!node->left && !node->right)
{
res += sum;
continue;
}
if (node->left)
q.push(make_pair(node->left, sum));
if (node->right)
q.push(make_pair(node->right, sum));
}
return res;
}
};
-
- 时间: 2014-9-25 00:33算法问题: Surrounded Regions
问题描述:
Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region .
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X -
- 时间: 2014-9-25 00:33推荐答案来了 (in C++) ...
Traverse from the boarder to the inside and mark all the 'O's that are not surrounded by 'X' as 'V' (visited).
1. DFS.
2. BFS (queue).
代码:
class Solution {
public:
typedef vector<vector<char> > BOARDTYPE;
void solve(BOARDTYPE &board) {
if (board.empty() || board[0].empty()) return;
int N = board.size(), M = board[0].size();
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
if (i == 0 || j == 0 || i == N-1 || j == M-1)
bfs(board, i, j); // you may call dfs or bfs here!
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
board[i][j] = (board[i][j] == 'V') ? 'O' : 'X';
}
void dfs(BOARDTYPE &board, int row, int col) {
int N = board.size(), M = board[0].size();
if (row < 0 || row >= N || col < 0 || col >= M) return;
if (board[row][col] != 'O') return;
board[row][col] = 'V';
dfs(board, row+1, col);
dfs(board, row-1, col);
dfs(board, row, col+1);
dfs(board, row, col-1);
}
void bfs(BOARDTYPE &board, int row, int col) {
if (board[row][col] != 'O') return;
int N = board.size(), M = board[0].size();
queue<pair<int, int>> q;
q.push(make_pair(row, col));
while (!q.empty())
{
int i = q.front().first, j = q.front().second;
q.pop();
if (i < 0 || i >= N || j < 0 || j >= M) continue;
if (board[i][j] != 'O') continue;// important to recheck!
board[i][j] = 'V';
q.push(make_pair(i-1, j));
q.push(make_pair(i+1, j));
q.push(make_pair(i, j-1));
q.push(make_pair(i, j+1));
}
}
};
-
- 时间: 2014-9-25 00:33算法问题: Swap Nodes in Pairs
问题描述:
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. -
- 时间: 2014-9-25 00:34推荐答案来了 (in C++) ...
1. Iterative solution with constant space.
2. Recursive solution with O(n) space (for practice).
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *swapPairs(ListNode *head) {
return swapPairs_1(head);
}
ListNode *swapPairs_1(ListNode *head) {
ListNode dummy(0), *cur = &dummy;
cur->next = head;
while (cur->next && cur->next->next)
{
ListNode *move = cur->next->next;
cur->next->next = move->next;
move->next = cur->next;
cur->next = move;
cur = move->next;
}
return dummy.next;
}
ListNode *swapPairs_2(ListNode *head) {
if (!head || !head->next) return head;
ListNode *first = head, *second = head->next;
first->next = second->next;
second->next = first;
first->next = swapPairs(first->next);
return second;
}
};
-
- 时间: 2014-9-25 00:34算法问题: Symmetric Tree
问题描述:
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3
Note:
Bonus points if you could solve it both recursively and iteratively.
Leetcode Hacking Practice -- Solution in C++ Part 5
