Leetcode Hacking Practice -- Solution in C++ Part 5 (發表於11年前)

webdriver

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

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.

webdriver

推薦答案來了 (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;

        }

    }

};

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.

webdriver

推薦答案來了 (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;

    }

};

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

webdriver

推薦答案來了 (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));

        }

    }

};

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.

webdriver

推薦答案來了 (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;

    }

};

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.