Leetcode Hacking Practice -- Solution in C++ Part 5

文章内容

LeetCode (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 -&gt; Code solution using the Online Judge system.
2. Read -&gt; Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -&gt; 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

点击: 0 | 评论: 51 | 分类: 缺省 | 论坛: IT人生 | 论坛帖子

分享:

分享到微信

文章评论

webdriver

无题

算法问题: Sudoku Solver
问题描述:
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

2014-09-25 00:29:19 | 引用

无题

推荐答案来了 (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-09-25 00:31:00 | 引用

webdriver

无题

算法问题: 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-09-25 00:32:50 | 引用

无题

推荐答案来了 (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-09-25 00:33:00 | 引用

webdriver

无题

算法问题: 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-09-25 00:33:20 | 引用

无题

推荐答案来了 (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-09-25 00:33:31 | 引用

webdriver

无题

算法问题: 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-09-25 00:33:51 | 引用

无题

推荐答案来了 (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-09-25 00:34:01 | 引用

webdriver

无题

算法问题: 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.

2014-09-25 00:34:41 | 引用

无题

推荐答案来了 (in C++) ...

1. Recursive solution 2.Iterative way (queue).

代码:


/**

 * Definition for binary tree

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    bool isSymmetric(TreeNode *root) {

        return isSymmetric_1(root);

    }

    

    bool isSymmetric_1(TreeNode *root) {

        if (!root) return true;

        return isSymmetricRe(root->left, root->right);

    }



    bool isSymmetricRe(TreeNode *t1, TreeNode *t2)

    {

        if (!t1 && !t2) return true;

        if (!t1 || !t2 || t1->val != t2->val) return false;

        return isSymmetricRe(t1->left, t2->right) &&

               isSymmetricRe(t1->right, t2->left);

    }



    bool isSymmetric_2(TreeNode *root) {

        if (!root) return true;

        queue<TreeNode *> q;

        q.push(root->left);

        q.push(root->right);

        while (!q.empty())

        {

            TreeNode *t1 = q.front(); q.pop();

            TreeNode *t2 = q.front(); q.pop();

            if (!t1 && !t2) continue;

            if (!t1 || !t2 || t1->val != t2->val)

                return false;

            q.push(t1->left);

            q.push(t2->right);

            q.push(t1->right);

            q.push(t2->left);

        }

        return true;

    }

};

2014-09-25 00:35:01 | 引用

webdriver

发表评论

回到顶部▲