LeetCode(98) -- 130, 131, 134

P130. Surrounded Regions (Medium)

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

My Solution

class Solution {
    boolean capture = true;
    int m;
    int n;

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        m = board.length;
        n = board[0].length;
        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O') {
                    capture = true;
                    List<Integer> visited = new ArrayList<>();
                    dfs(board, i, j, visited);
                    if (capture) {
                        for (Integer visitedIndex : visited) {
                            int r = visitedIndex / n;
                            int c = visitedIndex % n;
                            board[r][c] = 'X';
                        }
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'V') {
                    board[i][j] = 'O';
                }
            }
        }
    }

    private void dfs(char[][] board, int i, int j, List<Integer> visited) {
        board[i][j] = 'V';
        visited.add(i * n + j);
        if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
            capture = false;
            return;
        }
        if (board[i - 1][j] == 'O') {
            dfs(board, i - 1, j, visited);
        }
        if (board[i + 1][j] == 'O') {
            dfs(board, i + 1, j, visited);
        }
        if (board[i][j - 1] == 'O') {
            dfs(board, i, j - 1, visited);
        }
        if (board[i][j + 1] == 'O') {
            dfs(board, i, j + 1, visited);
        }
    }
}

15%

Solution

一看答案猛然发现这个非常接近围棋的规则!

public class Solution {
    protected Integer ROWS = 0;
    protected Integer COLS = 0;

    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        this.ROWS = board.length;
        this.COLS = board[0].length;

        List<Pair<Integer, Integer>> borders = new LinkedList<Pair<Integer, Integer>>();
        for (int r = 0; r < this.ROWS; ++r) {
            borders.add(new Pair(r, 0));
            borders.add(new Pair(r, this.COLS - 1));
        }
        for (int c = 0; c < this.COLS; ++c) {
            border.add(new Pair(0, c));
            border.add(new Pair(this.ROWS - 1, c));
        }
        for (Pair<Integer, Integer> pair : borders) {
            this.DFS(board, pair.first, pair.second);
        }

        for (int r = 0; r < this.ROWS; ++r) {
            for (int c = 0; c < this.COLS; ++c) {
                if (board[r][c] == 'O') {
                    board[r][c] = 'X';
                }
                if (board[r][c] == 'E') {
                    board[r][c] = 'O';
                }
            }
        }
    }

    protected void DFS (char[][] board, int row, int col) {
        if (board[row][col] != 'O') {
            return;
        }
        board[row][col] = 'E';
        if (col < this.COLS - 1) {
            this.DFS(board, row, col + 1);
        }
        if (row < this.ROWS - 1) {
            this.DFS(board, row + 1, col);
        }
        if (col > 0) {
            this.DFS(board, row, col - 1);
        }
        if (row > 0) {
            this.DFS(board, row - 1, col);
        }
    }
}

class Pair<U, V> {
    public U first;
    public V second;

    public Pair(U first, V second) {
        this.first = first;
        this.second = second;
    }
}

The Best Solution

class Solution {
    public void solve(char[][] board) {
        // start with lateral... Mark them as Z
        // paint invalid O to Z
        // then paint all O to X, 
        // paint Z to O
        if (board.length == 0 || board[0].length == 0) {
            return;
        }
        // invalid O to Z
        for (int i = 0; i < board.length; i++) { // scan col
            if (board[i][0] == 'O') {
                explore(board, i, 0);
            }
            if (board[i][board[0].length - 1] == 'O') {
                explore(board, i, board[0].length - 1);
            }
        }

        for (int j = 0; j < board[0].length; j++) { // scan row, can ignore overlaps
            if (board[0][j] == 'O') {
                explore(board, 0, j);
            }
            if (board[board.length - 1][j] == 'O') {
                explore(board, board.length - 1, j);
            }
        }
        paint(board, 'O', 'X');
        paint(board, 'Z', 'O');
    }
    
    private void explore(char[][] board, int i, int j) {
        // in bound
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != 'O') {
            return;
        }
        
        board[i][j] = 'Z';
        if (i - 1 >= 0) {
            explore(board, i - 1, j);
        }
        if (i + 1 < board.length) {
            explore(board, i + 1, j);
        }
        if (j - 1 >= 0) {
            explore(board, i, j - 1);
        }
        if (j + 1 < board[0].length) {
            explore(board, i, j + 1);
        }
    }
    
    private void paint(char[][] board, char from, char to) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == from) {
                    board[i][j] = to;
                }
            }
        }        
    }
}

这两种解法都是从边上出发，因为只有那些在边上的区域才能被保留。

P131. Palindrome Partitioning (Medium)

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Discuss

class Solution {
    List<List<String>> ans = new ArrayList<>();
    ArrayList<String> currList = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backTrack(s, 0);
        return ans;
    }

    public void backTrack(String s, int l) {
        if (currList.size() > 0 && l >= s.length()) {
            List<String> r = new ArrayList<>(currList);
            ans.add(r);
        }
        for (int i = l; i < s.length(); i++) {
            if (isPalindrome(s, l, i)) {
                if (l == i) {
                    currList.add(Character.toString(s.charAt(i)));
                } else {
                    currList.add(s.substring(l, i + 1));
                }
                backTrack(s, i + 1);
                currList.remove(currList.size() - 1);
            }
        }
    }

    public boolean isPalindrome(String str, int l, int r) {
        if (l == r) {
            return true;
        }
        while (l < r) {
            if (str.charAt(l) != str.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

P134. Gas Station (Medium)

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

My Solution

总油量应该要大于等于总消耗。这个如果brute force, 时间复杂度应该是n^2,勉强能接受。

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        start:
        for (int i = 0; i < n; i++) {
            int tank = gas[i];
            for (int j = i; j < n + i; j++) {
                if (tank - cost[j % n] < 0) {
                    continue start;
                }
                tank = tank - cost[j % n] + gas[(j + 1) % n];
            }
            return i;
        }
        return -1;
    }
}

9% 比较慢

The Best Solution

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0;
        int total = 0;
        int curr = 0;
        for(int i = 0; i < gas.length; i++){
            total += gas[i] - cost[i];
            curr += gas[i] - cost[i];
            if(curr < 0){
                start = i + 1;
                curr = 0;
            }
        }
        return total >= 0 ? start : -1;
    }
}

这个太聪明了。在任何一个点，如果累加它们的差之后，结果成了负的，那起始点一定会在这个以后。