Leetcode个人刷题思路和自我督促贴

jaly50 · 2014-11-23 03:15:47

注册一亩三分地论坛，查看更多干货！

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 jaly50 于 2014-12-29 12:30 编辑

开个贴子自我督促一下哈~
顺便分享一下自己的思路，欢迎讨论~

2楼：Anagrams
3楼：Wildcard Matching
4-5楼：Jump Game II
6楼：Flatten Binary Tree to Linked List

7楼：Insert Interval
8楼：Construct Binary Tree from Preorder and Inorder Traversal

9楼：Construct Binary Tree from Postorder and Inorder Traversal

10楼:Validate Binary Search Tree

11楼： Simplify Path

12楼：Set Matrix Zeroes
13楼：Permutation Sequence
14楼： Restore IP Addresses

15楼： Subsets II

16楼：Partition List

18楼：Recover Binary Search Tree

19楼： Interleaving String

20楼 Minimum Window Substring

21楼 Largest Rectangle in Histogram

22楼 Maximal Rectangle

23楼 Excel Sheet Column Title

24楼 Maximum Gap

25楼 Fraction to Recurring Decimal

jaly50 · 2014-12-22 10:01:48

import java.util.Arrays;
/*
* Date:12/21/2014 Sun 5:59 PM
* @author: Scarlett Chen
*/
public class SurroundedRegion {
boolean [] hasEdge;
int[] union;
/*
* 一开始用了recursive dfs, 还发生了stackoverflow.QAQ .
* 最后用了algorithm1的unionfind写的~！感觉自己代码实现能力有提高呢！.
*/
public void solve(char[][] board) {
int n = board.length;
if (n<1) return;
int m = board[0].length;
hasEdge = new boolean[n*m];
union = new int[n*m];
int pos;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
pos = i*m +j;
hasEdge[pos] = (i==0 ||j==0||i==n-1||j==m-1) ? true : false;
union[pos] = pos;
if (i>0 && board[i][j]== board[i-1][j]) {
union(pos, pos-m);
}
if (j>0 && board[i][j] == board[i][j-1]) {
union(pos, pos-1);
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
pos = i*m+j;
if (board[i][j]=='O' && !hasEdge[findRoot(pos)]) {
board[i][j] = 'X';
}
}
}
for (int i=0; i<board.length; i++)
System.out.println(Arrays.toString(board[i]));
}
private void union(int x, int y) {
int rootX = findRoot(x);
int rootY = findRoot(y);
union[rootX] = rootY;
boolean hasedge = hasEdge[rootX] || hasEdge[rootY];
hasEdge[rootY] = hasedge;
}
private int findRoot(int x) {
if (union[x]==x) return x;
else return findRoot(union[x]);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
SurroundedRegion sr = new SurroundedRegion();
char[][] board = new char[][] {{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O' ,'X' ,'X'}};
sr.solve(board);
}
//Failed
//Limitation in recursion depth
//sometimes we need to use stack to do bfs or dfs.
boolean[][] withEdge;
char[][] board;
int n;
int m;
public void solve_fail(char[][] board) {
n= board.length;
this. board = board;
if (n<1) return;
m = board[0].length;
withEdge = new boolean[n][m];
for (int i=0; i<n; i++) {
Arrays.fill(withEdge[i], false);
}
for (int i=0; i<n; i++) {
if (board[i][0]=='O') {
if (!withEdge[i][0]) {
dfs(i,0);
}
}
if (board[i][m-1]=='O') {
if (!withEdge[i][m-1]) {
dfs(i,m-1);
}
}
}
for (int j=0; j<m; j++) {
if (board[0][j]=='O') {
if (!withEdge[0][j]) {
dfs(0,j);
}
}
if (board[n-1][j]=='O') {
if (!withEdge[n-1][j]) {
dfs(n-1,j);
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<board[0].length; j++) {
if (board[i][j]=='O' && !withEdge[i][j]) {
board[i][j] = 'X';
}
}
}
}
public void dfs(int row, int col) {
withEdge[row][col] = true;
if (row>0 && board[row-1][col]=='O' && !withEdge[row-1][col]) {
dfs(row-1, col);
}
if (row<n-1 && board[row+1][col]=='O' && !withEdge[row+1][col]) {
dfs(row+1, col);
}
if (col>0 && board[row][col-1]=='O' && !withEdge[row][col-1]) {
dfs(row, col-1);
}
if (col<board[0].length-1 && board[row][col+1]=='O' && !withEdge[row][col+1]) {
dfs(row, col+1);
}
}
}

复制代码

jaly50 · 2014-12-28 13:06:07

import java.util.HashMap;
import java.util.Map;
/*
* LeetCode 155 Minimum Window Substring
* Given a string S and a string T,
* find the minimum window in S which will contain all the characters in T in complexity O(n).
* @author: Scarlett Chen
* @date: 12/27/2014 Sat 8:36 PM
* Time: o(2n)
* space: o(n)
* 思路：记录minWindow的开始点sb,每次匹配完T的值后，删掉第一个点，继续往后找，直到T再次匹配完全。
* 每次完全匹配时，更新minWindown是否有更小。
*/
public class MinWindow {
public static String minWindow(String S, String T) {
Map<Character,Integer> map = new HashMap<Character, Integer>();
String minWindow = S;
if (T.length()> S.length()) return "";
if (T.equals(S)) return minWindow;
int count = T.length();
for (int i=0; i<count; i++) {
char ch = T.charAt(i);
if (map.containsKey(ch)) {
map.put(ch, map.get(ch)-1);
}
else map.put(ch, -1);
}
int sb = -1;
boolean ansExist = false;
for (int i=0; i<S.length(); i++ ) {
char ch = S.charAt(i);
if (map.containsKey(ch)) {
System.out.println(ch);
//First beginning of the window
if (sb==-1) sb = i;
map.put(ch, map.get(ch)+1);
if (map.get(ch)<=0)
count--;
while (count==0) {
ansExist = true;
minWindow =i-sb+1 <minWindow.length() ? S.substring(sb,i+1): minWindow;
ch = S.charAt(sb);
// if (map.containsKey(ch)) must contain, since sb is the begining of the minwindow
map.put(ch, map.get(ch)-1);
if (map.get(ch)<0) count++;
sb++;
while (sb <= S.length()-T.length() && !map.containsKey(S.charAt(sb)))
sb++;
if (sb>S.length()-T.length()) return minWindow;
}
}
}
return ansExist? minWindow: "";
}
public static void main(String[] args) {
System.out.println(minWindow("bdab","ab"));
}
}

复制代码

jaly50 · 2014-11-23 03:18:52

/*
* Author: Scarlett
* Date: 11/21/2014 Fri 11:12 PM
* LeetCode: 110 Anagrams
* thought: HashMap
* If only using HashMap, it will TLE. Since map[i].equals(map[j]) cost m time. (m is the length of a string)
* Way to improve: To calculate total ASCii in one String, check whether TotalASCII[i]==totalASCII[b], it only cost 1 time.
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
// Same length? Duplicated group with different length? First step is to clarify the scope.
//TLE QAQ 是不是str如果按长度排序，就可以再少点time consuming
public class Anagrams {
public List<String> anagrams_buxiele(String[] strs) {
List<String> list = new ArrayList<String>();
return list;
}
public List<String> anagrams(String[] strs) {
List<String> list = new ArrayList<String>();
Arrays.sort(strs,new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
if (o1.length()<o2.length()) return -1;
else if (o1.length()>o2.length()) return 1;
return 0;
}});
int len = strs.length;
//To reduce time, judging whether they are same total accil QAQ
//it works!!! GREAT!!!!!
int[] totalAC = new int[len];
Arrays.fill(totalAC, 0);
//Make every String a map
Map<Character,Integer>[] map =new HashMap[len];
for (int i=0; i<len; i++) {
map[i] = new HashMap<Character,Integer>();
char[] s =strs[i].toCharArray();
for (char ch:s) {
totalAC[i] += ch-'0';
if (map[i].containsKey(ch) ) {
map[i].put(ch,map[i].get(ch)+1);
}
else map[i].put(ch,1);
}
}
//Try some methods to reduce consuming time QAQ
//Mark strings which are already in the groups
boolean[] mark = new boolean[len];
Arrays.fill(mark, false);
// To detect whether they are anagrams by compare map
for (int i=0; i<len; i++) {
if (!mark[i])
for (int j=i+1; j<len; j++) {
if (strs[i].length()!=strs[j].length()) break;
if (totalAC[i] !=totalAC[j]) continue;
if (map[i].equals(map[j])) {
if (!mark[i]) list.add(strs[i]);
list.add(strs[j]);
mark[i] = true;
mark[j] = true;
}
}
}
return list;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Anagrams a = new Anagrams();
String[] strs = new String[]{"dog","cat","god","tac"};
System.out.println(a.anagrams(strs));
}
}

复制代码

jaly50 · 2014-11-23 03:19:41

本帖最后由 jaly50 于 2014-12-14 11:19 编辑

/*
* LeetCode 141 Wild Card
* Author: Scarlett Chen
* Time: 12/13/2014 Sat 10:17 PM
* 二十天以前不会写，参考了别人的答案。
* 今天用那个dp的思路。发现还有很多细节需要注意
*/
import java.util.HashMap;
import java.util.Map;
//https://oj.leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution
public class Wildcard {
public boolean isMatch(String s, String p) {
int len1 = s.length();
int len2 = p.length();
int j=0;
int i=0;
int prej=-1, prei=0;
// p串是零的情况
if (len1!=0 && len2==0) return false;
while (i<len1) {
char cs = s.charAt(i);
char cp;
//直接不匹配没有＊号的情况
if (j==-1) return false;
if (j<len2) cp = p.charAt(j);
else cp = ' ';
if (cs==cp || cp=='?') {
i++;
j++;
}
else if (cp=='*') {
prej = j;
prei = i;
j++;
}
else {
j = prej;
i = ++prei;
}
}
//注意这里不只一个值要注意，要看看是不是后面都是＊号，才能放过它。
while (j<len2) {
if (p.charAt(j)=='*') j++; else return false;
}
return true;
}

复制代码

jaly50 · 2014-11-26 11:35:00

/*
* LeetCode Jump Game II
*
* 需要思考，但是实现很容易。一次过~
* Date:11/25/2014 Tue 10:25 PM
* 思路：dp
* 在i的位置上，每次可以跳子距离（0，A[i]) ，就可以算f[i到i+A[i]]的次数了
* f[i+j] = min (f[i+j], f[i]+1) (j is in [1,A[i]])
* 再加点优化, if i<j, A[i]>A[j]+distance(i,j), 那么f[j]就不用算
*
*/

jaly50 · 2014-11-26 11:35:21

public int jump(int[] A) {
int[] f = new int[A.length];
Arrays.fill(f,Integer.MAX_VALUE);
f[0]=0;
int max=0;
for (int i=0; i<A.length; i++) {
max = Math.max(A[i],max);
if (A[i]<max) {
max = max-1;
continue;
}
for (int j=1; j<=A[i] && i+j<A.length; j++) {
f[i+j] = Math.min(f[i+j], f[i]+1);
if (i+j==A.length-1)
return f[i+j];
}
}
return f[A.length-1];
}

复制代码

jaly50 · 2014-11-26 23:35:08

/*
* LeetCode 124 Flatten Binary Tree to Linked List
* Author: Scarlett Chen
* Date:11/26/2014 Wed 10:32 AM
* in place的意思大概是不要clone tree吧
* 如果我new TreeNode(root.val)，就会过不了（1,2)...虽然不知道为什么
* 所以我就先把root的左右孩子先放栈里，然后脱离它与孩子们的关系，再让它放到我的树里。就不复制了。
* 思路：栈，深搜
*/
import java.util.Stack;
public class Flatten {
public void flatten(TreeNode root) {
TreeNode result;
TreeNode head = new TreeNode(-1);
result = head;
Stack<TreeNode> tree = new Stack<TreeNode>();
if (root!=null) tree.push(root);
while (!tree.isEmpty()) {
root = tree.pop();
if (root.right!=null) tree.push(root.right);
root.right = null;
if (root.left!=null) tree.push(root.left);
root.left = null;
result.right = root;
result.left = null;
result = result.right;
}
root = head.right;
}
}

复制代码

jaly50 · 2014-11-29 15:37:56

/*
* Author: Scarlett
* LeetCode:Insert Interval
* date:11/29/2014 Sat 2:33 AM
* 设(x,y)为newInterval, （a,b)为当前比较的interval
* 要考虑的情况包括： (x<a,y<a);(x<a,a<y<b);(x<a,y>b);(a<x<b,a<y<b);(a<x<b,y>b);(x>b)
* 一开始先把newinterval加进list里
* 注意list不能边改边删，所以要复制list再进行遍历
*/

复制代码

/*
* Be careful for the null list~~~!!
* 要想清楚，要分情况！！
*/

复制代码

public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
intervals.add(0,newInterval);
List<Interval> copy = new LinkedList<Interval>(intervals);
Interval pre=newInterval;
for (int i=1; i<copy.size(); i++) {
Interval list = copy.get(i);
if (pre.start < list.start) {
if (pre.end < list.start) {
return intervals;
}
else if (list.start<=pre.end && list.end >=pre.end ) {
list.start = pre.start;
intervals.remove(pre);
return intervals;
}
else if (pre.end > list.end) {
intervals.remove(list);
continue;
}
}
else if (list.start<=pre.start && list.end>=pre.start) {
if (list.start <=pre.end && list.end >=pre.end) {
intervals.remove(pre);
return intervals;
}
else if (pre.end >list.end) {
pre.start = list.start;
intervals.remove(list);
continue;
}
}
else if (pre.start > list.end) {
int a = intervals.indexOf(pre);
int b =intervals.indexOf(list);
intervals.set(a, list);
intervals.set(b, pre);
continue;
}
}
return intervals;
}

复制代码

jaly50 · 2014-11-29 16:18:52

/*
* 一次过。但是难免边写边改。。如果在白板上写，还需要注意多一些。
* 不喜欢用长名字命名，但是短名字常常含义不清。唉。
* LeetCode 127:Construct Binary Tree from Preorder and Inorder Traversal
* 思路：递归，二分
* Date:11/29/2014 Sat 3:15 AM
*
*/

复制代码

public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder.length==0) return null;
TreeNode root = new TreeNode(preorder[0]);
if (preorder.length==1) return root;
int i=0;
int[] inorderLeft, inorderRight,preorderLeft,preorderRight;
//To find the root at int[] inorder, to divide it to two part
for (int in=0; in<inorder.length; in++) {
if (inorder[in] == preorder[0])
{ i = in; break;}
}
inorderLeft = Arrays.copyOfRange(inorder,0,i);
int leftLen = inorderLeft.length;
inorderRight = Arrays.copyOfRange(inorder, i+1, inorder.length);
preorderLeft = Arrays.copyOfRange(preorder, 1,1+leftLen);
preorderRight = Arrays.copyOfRange(preorder, i+1, preorder.length);
root.left = buildTree(preorderLeft,inorderLeft);
root.right = buildTree(preorderRight, inorderRight);
return root;
}

复制代码

jaly50 · 2014-11-29 16:37:35

/*
* 在leetcode上直接写一次过的～
* 代码也比前一题漂亮多了！
* 题目是通过后序和中序遍历建树，和前一题基本一样。。
* LeetCode:Construct Binary Tree from Inorder and Postorder Traversal
* Date:11/29/2014 Sat 3:37 AM
* Author:Scarlett
*/
public TreeNode buildTree(int[] inorder, int[] postorder) {
int len = inorder.length;
if (len ==0) return null;
TreeNode root = new TreeNode(postorder[len-1]);
if (len==1) return root;
int indexOfRoot = 0;
for (int i=0; i<len; i++) {
if (inorder[i] ==postorder[len-1]) {
indexOfRoot = i;
}
}
int[] inorderLeft, inorderRight, postorderLeft, postorderRight;
inorderLeft = Arrays.copyOfRange(inorder,0,indexOfRoot);
inorderRight = Arrays.copyOfRange(inorder,indexOfRoot+1,len);
postorderLeft = Arrays.copyOfRange(postorder,0,indexOfRoot);
postorderRight = Arrays.copyOfRange(postorder,indexOfRoot,len-1);
root.left = buildTree(inorderLeft, postorderLeft);
root.right = buildTree(inorderRight, postorderRight);
return root;
}

复制代码

jaly50 · 2014-12-13 06:38:43

/*
* LeetCode 136 Validate Binary Search Tree
* Author: Scarlett
* 这道题很容易陷入一个小陷阱，就是只测试是否root.left <root<root.right,但其实BST的要求是必须root.left的最右儿子也要小于root的值。
* 所以一开始写了fail的版本。
*
* 后来想着用DFS来做，每次记录前一个访问过的结点的值，必须小于当前结点。就可以满足BST的条件了。
* 但是前一个访问过的点的值pre，在每个访问点上从call左子树到call右子树之间是会变化的。
* 因此又想了很久要怎么储存，进入了一些误区，还考虑过了应该是primitive or reference...要不要static...
*/
public class IsValidBST {
Long pre;
public boolean isValidBST(TreeNode root) {
if (root ==null) return true;
boolean ans = true;
pre = new Long((long)(Integer.MIN_VALUE) -1);
return isValidNode(root, ans);
}
private boolean isValidNode(TreeNode root, boolean ans) {
if (!ans) return ans;
//System.out.println("At first, root= "+root.val+" pre= "+pre);
if (root.left!=null) ans &= isValidNode(root.left,ans);
if (pre < root.val) {
pre =new Long(root.val);
}
else return false;
//System.out.println("root= "+root.val+" pre= "+pre);
if (root.right!=null) ans &= isValidNode(root.right,ans);
//System.out.println("root= "+root.val+" pre= "+pre);
return ans;
}
public boolean isValidBST_fail(TreeNode root) {
if (root == null) return true;
boolean ans = true;
if (root.left !=null) {
ans &= isValidBST(root.left);
ans &= root.val > root.left.val;
}
if (root.right !=null) {
ans &= isValidBST(root.right);
ans &= root.val < root.right.val;
}
return ans;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
IsValidBST is = new IsValidBST();
TreeNode root = new TreeNode(3);
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
TreeNode c = new TreeNode(4);
root.left = a;
root.right = c;
a.right = b;
System.out.println(is.isValidBST(root));
}
}

复制代码

[Leetcode] Leetcode个人刷题思路和自我督促贴

注册一亩三分地论坛，查看更多干货！

评分

相关帖子

浏览过的版块