Leetcoder: 2013

2013年10月25日星期五

Leetcoder - Reverse Integer

Reverse digits of an integer.

Example1: x =  123, return  321

Example2: x = -123, return -321

click to show spoilers.

Have you thought about this? Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

public class Solution {
public int reverse(int x) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int y = 0;
boolean neg = false;
if(x<0) {
x *= -1;
neg = true;
}
while(x!=0) {
y *=10;
int t = x%10;
x = (x-t)/10;
y += t;
}
if(neg) {
y *= -1;
}
return y;
}
}

public class Solution {
    public int reverse(int x) {
        if (x==0) {
            return 0;
        }
        boolean neg = x<0;
        long x2 = x;
        if(neg) {
            x2 = -x2;
        }
        long y = 0;
        while (x2!=0) {
            y *= 10;
            y += x2%10;
            x2 = x2/10;
        }
        if(neg) {
            y = -y;
        }
        if (y>Integer.MAX_VALUE || y<Integer.MIN_VALUE) {
            return 0;
        }
        return (int)y;
    }
}

public class Solution {
    public int reverse(int x) {
        int y;
        if(x == Integer.MAX_VALUE || x == Integer.MIN_VALUE) return 0;
        if(x < 0) y = -x;
        else y = x;
        long reverse = 0;
        while(y != 0){
            reverse = reverse * 10 + y % 10;
            y = y / 10;
        }
        if(reverse > Integer.MAX_VALUE) return 0;
        if(x < 0) reverse = - reverse;
        return (int)reverse;
    }
}

===================

public class Solution {
    public int reverse(int x) {
        if (x == 0) {
            return 0;
        } 
        int sign = 1;
        if (x < 0) {
            if (x == Integer.MIN_VALUE) return 0;
            sign = -1;
            x = -x;
        }
        int res = 0;
        while (x != 0) {
            int digit = x % 10;
            if (Integer.MAX_VALUE / 10 < res || (Integer.MAX_VALUE / 10 == res && Integer.MAX_VALUE % 10 < digit) ) {
                return 0;
            }
            res = res * 10 + digit;
            x = x / 10;
        }
        return res * sign;
    }
}

Leetcoder - Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
// Note: The Solution object is instantiated only once and is reused by each test case.
if(root==null) {
return 0;
}
return visitNext(root, 0);
}

public int visitNext(TreeNode node, int maxDepth) {
if(node==null) {
return maxDepth;
} else {
int dL = visitNext(node.left, maxDepth+1);
int dR = visitNext(node.right, maxDepth+1);
return dL>dR?dL:dR;
}
}
}

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
return (root==null)? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
}

Leetcoder - Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Note: The Solution object is instantiated only once and is reused by each test case.
return checkNode(p, q);
}

public boolean checkNode(TreeNode p, TreeNode q) {
if(p==null && q==null) {
return true;
}
if(p!=null && q!=null && p.val==q.val) {
boolean sameL = checkNode(p.left, q.left);
if(sameL) {
return checkNode(p.right, q.right);
} else {
return false;
}
} else {
return false;
}
}
}

2013年10月22日星期二

Leetcoder - Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

public class Solution {
public int singleNumber(int[] A) {
// Note: The Solution object is instantiated only once and is reused by each test case.
int ret = 0;
for (int k : A) {
ret ^= k;
}
return ret;
}
}

2013年9月19日星期四

Leetcoder - Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxPathSum(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
int max = root.val;

return getSum(root, max)[0];
}

public int[] getSum(TreeNode node, int max) {
int[] vals = new int[2];
vals[0] = max;
vals[1] = node.val;
int leftSum = 0;
int rightSum = 0;
int sum = node.val;
if(node.left!=null) {
int[] leftV = getSum(node.left, max);
leftSum = leftV[1] + node.val;
if(leftV[0]>max) {
max = leftV[0];
}
if(leftV[1]>0) {
sum += leftV[1];
}
}
if(node.right!=null) {
int[] rightV = getSum(node.right, max);
rightSum = rightV[1] + node.val;
if(rightV[0]>max) {
max = rightV[0];
}
if(rightV[1]>0) {
sum += rightV[1];
}
}
if(leftSum>vals[1]) {
vals[1] = leftSum;
}
if(rightSum>vals[1]) {
vals[1] = rightSum;
}
if(sum>max) {
vals[0] = sum;
} else {
vals[0] = max;
}
return vals;
}
}

public class Solution {

    private int maxSum = 0;

    public int maxPathSum(TreeNode root) {
        if(root==null) return 0;
        maxSum = root.val;
        getPathSum(root);
        return maxSum;
    }

    private int[] getPathSum(TreeNode root) {
        int[] sums = new int[2];
        sums[0] = root.val;
        sums[1] = root.val;
        if(root.left==null && root.right==null) {
            maxSum = Math.max(maxSum, root.val);
            return sums;
        }
        if(root.left!=null) {
            int[] leftSum = getPathSum(root.left);
            sums[0] = Math.max(0, Math.max(leftSum[0], leftSum[1])) + root.val;
        }
        if(root.right!=null) {
            int[] rightSum = getPathSum(root.right);
            sums[1] = Math.max(0, Math.max(rightSum[0], rightSum[1])) + root.val;
        }
        maxSum = Math.max(maxSum, Math.max(sums[0]+sums[1]-root.val, Math.max(sums[0], sums[1])));
        return sums;
    }
}

===========

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {

int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
max = Integer.MIN_VALUE;
helper(root);
return max;
}

private int helper(TreeNode node) {
if (node == null) {
return 0;
}
int left = Math.max(0, helper(node.left));
int right = Math.max(0, helper(node.right));

max = Math.max(max, left + right + node.val);

return node.val + Math.max(left, right);
}
}

2013年9月18日星期三

Leetcoder - Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.

public class Solution {
public boolean isPalindrome(String s) {
// Start typing your Java solution below
// DO NOT write main() function
if(s.isEmpty()) {
return true;
}
int left = 0;
int right = s.length()-1;
s = s.toLowerCase();
loop: while(left<right) {
while(!(s.charAt(left)>='a' && s.charAt(left)<='z') && !(s.charAt(left)>='0' && s.charAt(left)<='9')) {
left++;
if(left>=right) {
break loop;
}
}
while(!(s.charAt(right)>='a' && s.charAt(right)<='z') && !(s.charAt(right)>='0' && s.charAt(right)<='9')) {
right--;
if(right<=left) {
break;
}
}
if(s.charAt(left)!=s.charAt(right)) {
return false;
} else {
left++;
right--;
}
}
return true;
}
}
===========

public class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.isEmpty()) {
return true;
}
int start = 0;
int end = s.length() - 1;
s = s.toLowerCase();
while (start <= end) {
while (start <= end && !Character.isLetterOrDigit(s.charAt(start))) {
start += 1;
}
while (start <= end && !Character.isLetterOrDigit(s.charAt(end))) {
end --;
}
if (start <= end) {
if (s.charAt(start) == s.charAt(end)) {
start += 1;
end -= 1;
} else {
return false;
}
}
}
return true;
}
}

2013年9月17日星期二

Leetcoder - Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

public class Solution {
public int ladderLength(String start, String end, HashSet<String> dict) {
// Start typing your Java solution below
// DO NOT write main() function
// breadth first, graph search, find the shortest path
dict.remove(start);
dict.add(end);

ArrayList<String> fronties = new ArrayList<String>();
fronties.add(start);

boolean find = false;
int level = 1;
loop: while (true) {
level++;
HashSet<String> newFronties = new HashSet<String>();
for (String str : fronties) {
ArrayList<String> nexts = new ArrayList<String>();
for (int i = 0; i < str.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (str.charAt(i) != c) {
StringBuilder sb = new StringBuilder();
sb.append(str.subSequence(0, i)).append(c)
.append(str.substring(i + 1));
if (dict.contains(sb.toString())) {
nexts.add(sb.toString());
}
}
}
}
for (String next : nexts) {
if (next.equals(end)) {
break loop;
} else {
newFronties.add(next);
}
}
}
if (fronties.size() == 0) {
level = 0;
break;
}
dict.removeAll(newFronties);
fronties.clear();
fronties.addAll(newFronties);
}
return level;
}
}

public class Solution {
public int ladderLength(String start, String end, Set<String> dict) {
ArrayList<String> frontie = new ArrayList<String>();
frontie.add(start);
int step = 1;
dict.add(end);
while(frontie.size()!=0 && dict.size()!=0) {
ArrayList<String> newFrontie = new ArrayList<String>();
for(String str : frontie) {
for(int i=0;i<str.length();i++) {
int c = str.charAt(i);
for(int j='a';j<'z';j++) {
if(j==c) continue;
String newStr = str.substring(0,i) + ((char) j) + str.substring(i+1);
if(dict.contains(newStr)) {
if(newStr.equals(end)) return step+1;
dict.remove(newStr);
newFrontie.add(newStr);
}
}
}
}
frontie = newFrontie;
step++;
}
return 0;
}
}

===============

public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
Queue<String> queue = new LinkedList<String>();
queue.add(beginWord);
int step = 2;
while (queue.size() != 0 && wordDict.size() != 0) {
int count = queue.size();
while (count-- > 0) {
String str = queue.poll();
char cs[] = str.toCharArray();
for (int i = 0; i < str.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == str.charAt(i)) {
continue;
}
cs[i] = c;
String next = new String(cs);
if (next.equals(endWord)) {
return step;
}
if (wordDict.contains(next)) {
wordDict.remove(next);
queue.add(next);
}
}
cs[i] = str.charAt(i);
}
}
step++;
}
return 0;
}
}

Leetcoder - Word Ladder II

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

All words have the same length.
All words contain only lowercase alphabetic characters.

public class Solution {
public ArrayList<ArrayList<String>> findLadders(String start, String end,
HashSet<String> dict) {
// breadth first, graph search, find the shortest path
dict.remove(start);
dict.add(end);
HashMap<String, ArrayList<String>> backTrack = new HashMap<String, ArrayList<String>>();

ArrayList<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
ArrayList<String> fronties = new ArrayList<String>();
fronties.add(start);

boolean find = false;
while (true) {
HashSet<String> newFronties = new HashSet<String>();
for (String str : fronties) {
HashSet<Integer> skip = new HashSet<Integer>();
if(backTrack.containsKey(str)) {
for(String p : backTrack.get(str)) {
for(int i=0;i<p.length();i++) {
if(p.charAt(i)!=str.charAt(i)) {
skip.add(i);
}
}
}
}
ArrayList<String> nexts = new ArrayList<String>();
for (int i = 0; i < str.length(); i++) {
if(skip.contains(i)) {
continue;
}
for (char c = 'a'; c <= 'z'; c++) {
if (str.charAt(i) != c) {
StringBuilder sb = new StringBuilder();
sb.append(str.subSequence(0, i)).append(c)
.append(str.substring(i + 1));
if (dict.contains(sb.toString())) {
nexts.add(sb.toString());
}
}
}
}
for (String next : nexts) {
ArrayList<String> preNode = backTrack.get(next);
if (preNode == null) {
preNode = new ArrayList<String>();
backTrack.put(next, preNode);
}
preNode.add(str);
if (next.equals(end)) {
find = true;
} else {
newFronties.add(next);
}
}
}
if (find || fronties.size() == 0) {
break;
}
dict.removeAll(newFronties);
fronties.clear();
fronties.addAll(newFronties);
}
if (find) {
ArrayList<String> initPath = new ArrayList<String>();
initPath.add(end);
this.findPath(initPath, backTrack, paths, end);
}
return paths;
}

private void findPath(ArrayList<String> tmp, HashMap<String, ArrayList<String>> backTrack,
ArrayList<ArrayList<String>> paths, String next) {
ArrayList<String> parents = backTrack.get(next);
if (parents != null) {
for (String p : parents) {
tmp.add(p);
this.findPath(tmp, backTrack, paths, p);
tmp.remove(tmp.size()-1);
}
} else {
ArrayList<String> path = new ArrayList<String>();
for(int i=tmp.size()-1;i>=0;i--) {
path.add(tmp.get(i));
}
paths.add(path);
}
}
}

=============

public class Solution {
public List<List<String>> findLadders(String start, String end, Set<String> wordList) {
List<List<String>> res = new ArrayList<>();
if (start == null || end == null || wordList == null || wordList.size() == 0) {
return res;
}
HashMap<String, List<String>> map = new HashMap<>();
wordList.add(end);
HashSet<String> queue = new HashSet<String>();
queue.add(start);
boolean find = false;
while (!queue.isEmpty() && !wordList.isEmpty() && !find) {
int count = queue.size();
HashSet<String> nextLevel = new HashSet<String>();
for (String word : queue) {
for (int i = 0; i < word.length(); i++) {
char cs[] = word.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
if (word.charAt(i) == c) {
continue;
}
cs[i] = c;
String nextWord = new String(cs);
if (end.equals(nextWord)) {
find = true;
}
if (wordList.contains(nextWord)) {
List<String> pres = map.get(nextWord);
if (pres == null) {
pres = new ArrayList<String>();
map.put(nextWord, pres);
}
pres.add(word);
nextLevel.add(nextWord);
}
}
cs[i] = word.charAt(i);
}
}
for (String str : nextLevel) {
wordList.remove(str);
}
queue = nextLevel;
}
if (!find) {
return res;
}
helper(start, map, new ArrayList<String>(), end, res);
return res;
}

private void helper(String start, HashMap<String, List<String>> map, List<String> curList, String word, List<List<String>> res) {
if (word.equals(start)) {
List<String> newList = new ArrayList<String>(curList);
newList.add(word);
Collections.reverse(newList);
res.add(newList);
} else {
curList.add(word);
List<String> pres = map.get(word);
for (String pre : pres) {
helper(start, map, curList, pre, res);
}
curList.remove(curList.size() - 1);
}
}
}

2013年9月15日星期日

Leetcoder - Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

public class Solution {
public int longestConsecutive(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
HashMap<Integer, int[]> cache = new HashMap<Integer, int[]>();
int max = 0;
for(int n : num) {
if(cache.containsKey(n)) {
continue;
}
int[] mid = new int[2];
boolean hasLeft = false;
boolean hasRight = false;
int leftBound = 0;
int rightBound = 0;
if(cache.containsKey(n-1)) {
int low = cache.get(n-1)[0];
mid[0] = low+1;
leftBound = n - low -1;
hasLeft = true;
}
if(cache.containsKey(n+1)) {
int high = cache.get(n+1)[1];
mid[1] = high+1;
rightBound = n + high + 1;
hasRight = true;
}
if(hasLeft) {
cache.get(leftBound)[1] += mid[1] + 1;
}
if(hasRight) {
cache.get(rightBound)[0] += mid[0] + 1;
}
cache.put(n, mid);
if(mid[0]+mid[1]+1>max) {
max = mid[0] + mid[1]+1;
}
}
return max;
}
}

public class Solution {
public int longestConsecutive(int[] num) {
int longest = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0;i < num.length;i++){
// if there is no duplicates, these two lines can be commented
if(map.containsKey(num[i])) continue;
map.put(num[i],1);

int end = num[i];
int begin = num[i];
if(map.containsKey(num[i]+1))
end = num[i] + map.get(num[i]+1);
if(map.containsKey(num[i]-1))
begin = num[i] - map.get(num[i]-1);
longest = Math.max(longest, end-begin+1);
map.put(end, end-begin+1);
map.put(begin, end-begin+1);
}
return longest;
}
}

=========

public class Solution {
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
// the max length of the sequence containing this element
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 1;
for (int i = 0; i < nums.length; i++) {
int n = nums[i];
if (map.containsKey(n)) {
continue;
}
int start = n;
int end = n;

if (map.containsKey(n + 1)) {
end = map.get(n + 1) + n;
}
if (map.containsKey(n - 1)) {
start = n - map.get(n - 1);
}
int len = end - start + 1;
max = Math.max(max, len);
map.put(start, len);
map.put(end, len);
map.put(n, len);
}
return max;
}
}

Leetcoder - 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.

/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int sumNumbers(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root==null) {
return 0;
}
return getSum(root, 0, 0);
}

public int getSum(TreeNode node, int currentVal, int sum) {
currentVal = currentVal * 10 + node.val;
if(node.left==null && node.right==null) {
sum += currentVal;
}
if(node.left!=null) {
sum = getSum(node.left, currentVal, sum);
}
if(node.right!=null) {
sum = getSum(node.right, currentVal, sum);
}
return sum;
}
}

Leetcoder - 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

public class Solution {

public void visit(int i, int j, char[][] board, boolean visited[][], boolean exempt[][], Stack<int[]> tovisit) {
if(i<0 || i>=row || j<0 || j>=column) {
return;
}
if(visited[i][j]) {
return;
}
visited[i][j] = true;
if(board[i][j] == 'O') {
int cell[] = new int[2];
cell[0] = i;
cell[1] = j;
tovisit.add(cell);
exempt[i][j] = true;
}
}

int row;
int column;

public void solve(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
// O in 4 boards cannot be captured
row = board.length;
if(row==0) {
return;
}
column = board[0].length;
if(column==0) {
return;
}
boolean[][] visited = new boolean[row][column];

boolean[][] exempt = new boolean[row][column];

Stack<int[]> tovisit = new Stack<int[]>();

for(int i=0;i<row;i++) {
visit(i, 0, board, visited, exempt, tovisit);
visit(i, column-1, board, visited, exempt, tovisit);
}

for(int j=1;j<column-1;j++) {
visit(0, j, board, visited, exempt, tovisit);
visit(row-1, j, board, visited, exempt, tovisit);
}

while(!tovisit.isEmpty()) {
int[] cell = tovisit.pop();
int i = cell[0];
int j = cell[1];
visit(i+1, j, board, visited, exempt, tovisit);
visit(i-1, j, board, visited, exempt, tovisit);
visit(i, j+1, board, visited, exempt, tovisit);
visit(i, j-1, board, visited, exempt, tovisit);
}

for(int i=0;i<row;i++) {
for(int j=0;j<column;j++) {
if(board[i][j]=='O' && !exempt[i][j]) {
board[i][j] = 'X';
}
}
}
}
}

public class Solution {
    public void solve(char[][] board) {
        if(board==null || board.length==0 || board[0].length==0) return;
        int m = board.length;
        int n = board[0].length;

        for(int i=0;i<m;i++) {
            if(board[i][0]=='O') bfs(board, i, 0);
            if(board[i][n-1]=='O') bfs(board, i, n-1);
        }

        for(int j=0;j<n;j++) {
            if(board[0][j]=='O') bfs(board, 0, j);
            if(board[m-1][j]=='O') bfs(board, m-1, j);
        }

        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(board[i][j]=='+') board[i][j] = 'O';
                else if(board[i][j]=='O') board[i][j] = 'X';
            }
        }
    }

    private void bfs(char[][] board, int i, int j) {
        board[i][j] = '+';
        LinkedList<int[]> lst = new LinkedList<int[]>();
        int m = board.length;
        int n = board[0].length;
        int[] idx = new int[2];
        idx[0] = i;
        idx[1] = j;
        lst.add(idx);
        while(lst.size()!=0) {
            int[] tmp = lst.removeFirst();
            int x = tmp[0];
            int y = tmp[1];
            add(x-1, y, board, lst);
            add(x+1, y, board, lst);
            add(x, y-1, board, lst);
            add(x, y+1, board, lst);
        }
    }

    private void add(int i, int j, char[][] board, LinkedList<int[]> lst) {
        int m = board.length;
        int n = board[0].length;
        if(i<0 || i>=m || j<0 || j>=n || board[i][j]!='O') return;
        int[] idx = new int[2];
        idx[0] = i;
        idx[1] = j;
        lst.addFirst(idx);
        board[i][j] = '+';
    }
}

========================================================

public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int row = board.length;
int column = board[0].length;

for (int i = 0; i < row; i++) {
if (board[i][0] == 'O') {
tag(board, i, 0);
}
if (board[i][column - 1] == 'O') {
tag(board, i , column - 1);
}
}
for (int i = 1; i < column - 1; i++) {
if (board[0][i] == 'O') {
tag(board, 0, i);
}
if (board[row - 1][i] == 'O') {
tag(board, row - 1, i);
}
}

for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (board[i][j] == '+') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}

private void tag(char[][] board, int i, int j) {
int row = board.length;
int column = board[0].length;
if (board[i][j] == 'O') {
board[i][j] = '+';
if (i - 1 > 0) tag(board, i - 1, j);
if (i + 1 < row) tag(board, i + 1, j);
if (j - 1 > 0) tag(board, i, j - 1);
if (j + 1 < column) tag(board, i, j + 1);
}
}
}

Leetcoder - Distinct Subsequences (DP)

Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

public class Solution {
public int numDistinct(String S, String T) {
// Start typing your Java solution below
// DO NOT write main() function
if(S.length()<T.length()) {
return 0;
}
int c[][] = new int[S.length()][T.length()];

if(S.charAt(0)==T.charAt(0)) {
c[0][0] = 1;
}
for(int i=1;i<S.length();i++) {
c[i][0] = c[i-1][0];
if(S.charAt(i)==T.charAt(0)) {
c[i][0]++;
}
}

for(int j=1;j<T.length();j++) {
for(int i=j;i<S.length();i++) {
if(S.charAt(i)==T.charAt(j)) {
c[i][j] = c[i-1][j] + c[i-1][j-1];
} else {
c[i][j] = c[i-1][j];
}
}
}
return c[S.length()-1][T.length()-1];
}
}

====================

public class Solution {
public int numDistinct(String s, String t) {
int len1 = s.length();
int len2 = t.length();
int dp[][] = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j -1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[len1][len2];
}
}

Leetcoder - Distinct Subsequences (recursion)

Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).
Here is an example:
S = "rabbbit", T = "rabbit"
Return 3.

public class Solution {
public int numDistinct(String S, String T) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>> positions = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<T.length();i++) {
char c = T.charAt(i);
ArrayList<Integer> position = new ArrayList<Integer>();
for(int j = 0;j<S.length();j++) {
char c2 = S.charAt(j);
if(c2==c) {
position.add(j);
}
}
if(position.size()==0) {
return 0;
}
Collections.reverse(position);
positions.add(position);
}
return permuate(positions, 0, -1, 0);
}

private int permuate(ArrayList<ArrayList<Integer>> positions, int idx, int last, int amount) {
ArrayList<Integer> position = positions.get(idx);
for(int p : position) {
if(p>last) {
if(idx==positions.size()-1) {
amount++;
} else {
amount = permuate(positions, idx+1, p, amount);
}
} else {
break;
}
}
return amount;
}
}

Can't go through the time limit...Need DP...

Leetcoder - Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

public class Solution {
public ArrayList<ArrayList<String>> partition(String s) {
// Start typing your Java solution below
// DO NOT write main() function
HashMap<Integer, ArrayList<ArrayList<String>>> groups = new HashMap<Integer, ArrayList<ArrayList<String>>>();

ArrayList<ArrayList<String>> group0 = new ArrayList<ArrayList<String>>();
ArrayList<String> t = new ArrayList<String>();
t.add(s.substring(0, 1));
group0.add(t);
groups.put(0, group0);
boolean cache[][] = new boolean[s.length()][s.length()];
for(int i=1;i<s.length();i++) {
ArrayList<ArrayList<String>> newGroup = new ArrayList<ArrayList<String>>();
String sub = s.substring(i, i+1);
for(ArrayList<String> tuple : groups.get(i-1)) {
ArrayList<String> newTuple = new ArrayList<String>(tuple);
newTuple.add(sub);
newGroup.add(newTuple);
}
for(int j=i-1;j>=0;j--) {
if(s.charAt(i)==s.charAt(j) && (cache[i-1][j+1] || j>=i-2)) {
cache[i][j] = true;
ArrayList<ArrayList<String>> tmp = null;
sub = s.substring(j, i+1);
if(j==0) {
ArrayList<String> newTuple = new ArrayList<String>();
newTuple.add(sub);
newGroup.add(newTuple);
} else {
tmp = groups.get(j-1);
for(ArrayList<String> tuple : tmp) {
ArrayList<String> newTuple = new ArrayList<String>(tuple);
newTuple.add(sub);
newGroup.add(newTuple);
}
}
}
}
groups.put(i, newGroup);
}
return groups.get(s.length() - 1);
}
}
========

public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
if (s == null || s.isEmpty()) return res;
helper(s, 0, new ArrayList<>(), res);
return res;
}

private void helper(String s, int p, List<String> list, List<List<String>> res) {
if (p == s.length()) {
res.add(new ArrayList<>(list));
} else {
for (int i = p; i < s.length(); i++) {
String sub = s.substring(p, i + 1);
if (isPalin(sub)) {
list.add(sub);
helper(s, i + 1, list, res);
list.remove(list.size() - 1);
}
}
}
}

private boolean isPalin(String sub) {
int s = 0;
int e = sub.length() - 1;
while (s <= e) {
if (sub.charAt(s) == sub.charAt(e)) {
s++;
e--;
} else {
return false;
}
}
return true;
}
}

Leetcode - Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

public class Solution {

    public int minCut(String s) {
        int cuts[] = new int[s.length()];
        cuts[0] = 0;
        boolean cache[][] = new boolean[s.length()][s.length()];
        for (int i = 1; i < s.length(); i++) {
            cuts[i] = cuts[i-1]+1;
            for (int j = i - 1; j >= 0; j--) {
                if (s.charAt(i) == s.charAt(j)
                        && (cache[j+1][i - 1] || j>=i-2)) {
                    cache[j][i] = true;
                    if(j==0) {
                        cuts[i] = 0;
                    } else {
                        cuts[i] = Math.min(cuts[i], cuts[j-1] + 1);
                    }
                }
            }
        }
        return cuts[s.length() - 1];
    }
}

============

public class Solution {
public int minCut(String s) {
if(s.length()==0)return 0;
int[] c=new int[s.length()+1];
for(int i=0;i<s.length();i++) {
c[i]=Integer.MAX_VALUE;
}
c[s.length()]=-1;
for(int i=s.length()-1;i>=0;i--){
for(int a=i,b=i;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
for(int a=i,b=i+1;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a--,b++) c[a]=Math.min(c[a],1+c[b+1]);
}
return c[0];
}
}

订阅：博文 (Atom)