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

jaly50 · 2014-12-13 07:40:04

import java.util.Arrays;
import java.util.Stack;
/*
* LeetCode: 137 Simplify Path
* Author: Scarlett
* 字符串处理题，要用到string.split
* 主要是处理 . 和..的情况
* 用stack增加和删除路径
*
* 第一遍没过是因为没有考虑 //的情况下，split会分配给它一个 length=0的string ---要注理掉
*/
public class SimplifyPath {
public String simplifyPath(String path) {
if (path==null || path.length()==0) return path;
Stack<String> s = new Stack<String>();
String[] pos = path.split("/");
// System.out.println(Arrays.toString(pos));
for (int i =0 ; i< pos.length; i++) {
if (pos[i].equals(".") || pos[i].length()==0) {
continue;
}
else if (pos[i].equals("..")) {
if (!s.isEmpty()) s.pop();
}
else {
s.push(pos[i]);
}
}
StringBuffer ans = new StringBuffer();
while (!s.isEmpty()) {
ans.insert(0, '/'+s.pop());
}
if (ans.length()==0) ans.append('/');
return ans.toString();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
SimplifyPath s = new SimplifyPath();
System.out.println(s.simplifyPath("/..."));
}
}

复制代码

jaly50 · 2014-12-13 09:02:54

import java.util.Arrays;
/*
* Leetcode 137 Set Matrix Zeroes
* Author: Scarlett
* 要求：Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
这道题常见的误区可能是会在matrix里直接改值，这样会导致错误。比如我因为matrix[1][2]==0，
就把row[1] col[2]全设零，那么当数组遍历到 matrix[other number][2]时，也会把相应行全设为零。这就不是我们要的。
O(mn)的方法很直接，就是再设一个boolean或int二维数组，用original的数组去判断是否修改，用新数组存改后的值
o(m+n)的方法就是下面第一个，用两个boolean数组(长度分别为m和n)判断该行或该列是否已被设为零
O(1)的方法，这个不错：https://oj.leetcode.com/discuss/16190/is-there-any-constant-space-solution-with-just-one-pass
*/
public class SetMatrixZeroes {
/*
* extra space: o(m+n)
* 用两个boolean数组(长度分别为m和n)判断该行或该列是否已被设为零
* Date: 12/12/2014 Fri 7:15 PM
*/
public void setZeroes_OmPlusN(int[][] matrix) {
int n = matrix.length;
if (n==0) return;
int m = matrix[0].length;
boolean[] rowIsZero = new boolean[n];
boolean[] colIsZero = new boolean[m];
Arrays.fill(rowIsZero, false);
Arrays.fill(colIsZero, false);
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (matrix[i][j]==0) {
rowIsZero[i] = true;
colIsZero[j] = true;
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (rowIsZero[i] || colIsZero[j]) {
matrix[i][j] = 0;
}
}
}
return;
}
/* 本来以为constant space solution可以用位运算，放两个字符串，分别代表row和col，每个数的每一位都代表具体的某一行或某一列，值可能有0或1
其实就是利用了发现o(m+n)的方法里多的数组的值其实只有0和1 才能再进一步升级为位运算
* 于是试图用bit operation写...
发现n和m的长度超出20位...要用string的话。。我觉得就和上面那个O(m+n)没有什么本质区别了
宣告失败= =
*/
public void setZeroes_bitOperation_fail(int[][] matrix) {
int n = matrix.length;
if (n==0) return;
int m = matrix[0].length;
long rowIsZero = 0;
long colIsZero = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (matrix[i][j]==0) {
rowIsZero |= 1<<i;
colIsZero |= 1<<j;
}
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if ((rowIsZero & 1<<i) !=0 || (colIsZero &1<<j) !=0) {
matrix[i][j] = 0;
}
}
}
return;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}

复制代码

jaly50 · 2014-12-13 11:03:13

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

/*
* LeetCode 139 Permutation Sequence
* Author: Scarlett
* Date: 12/12/2014 Fri 9:55 PM
* 得到长度为n的第k个排列。
* 我的方法是研究k个排列的规律，比如 1-6之间，就只有最后3位变化。
* 所以我先把 k=k-max(x!<k) （1<x<n）, 同时得到x位的新值，把x后面的值往后挪。重复这样做，就可以得到第K个值。
* 有点儿算是十进制换成二进制的思路呢。如65>64,就先把第6位的值改为1。
* 更复杂一点点，因为这里不只有1和0两种变化。
* 2！=2 ，3！=6 如果k是5的话，就要减去2次的2，于是第三位的值就会加两次，变成3.
*
* 和别人的思路差不多，但是人家用recursive的方法，清楚简单多了：https://oj.leetcode.com/discuss/5568/does-anyone-have-better-idea-share-accepted-python-code-here
*/
public class PermutationSequence {
public String getPermutation(int n, int k) {
StringBuffer ans = new StringBuffer();
for (int i=1; i<=n; i++)
ans.append(i);
k= k-1; //The current one is the first one. So we make it begin from 0
while (k>0) {
int pos =1;
int maxValue = 1;
//求最大阶乘
while (maxValue * pos <= k) {
maxValue = maxValue * pos++;
}
char posValue, newPosValue;
posValue = ans.charAt(n-pos);
newPosValue= posValue;
int posOld, posNew;
posOld = n-pos;
posNew = posOld;
//算算有多少 (x-1)!的变化，当前位的值就要从后面几个拿。
//其实是取商和取余的过程= =
while (k>=maxValue) {
k = k - maxValue;
posNew++;
}
newPosValue = ans.charAt(posNew);
ans.deleteCharAt(posNew);
ans.insert(posOld,newPosValue);
// System.out.println("maxValue= "+maxValue+" k="+k+" pos= "+ pos+" s1= "+newPosValue+" s2= "+posValue+" --> "+ans.toString());
}
return ans.toString();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
char v ='1';
//System.out.println(++v);
PermutationSequence p = new PermutationSequence();
System.out.println(p.getPermutation(3, 1));
System.out.println(p.getPermutation(3, 4));
}
}

复制代码

jaly50 · 2014-12-13 12:50:52

import java.util.ArrayList;
import java.util.List;
/*
* LeetCode 140 Restore IP Addresses
* Author: Scarlett chen
* Date: 12/12/2014 Fri 11:48 PM
* 完成今天5题刷题任务：D
* 这题用搜索...比较经典简单直接~
* 第一次没有过：是少考虑了不能“00”的情况
* 其他情况要考虑的是：每个field不能多于3位数，也不能少于1位数；数字必须在0到255之间。
*/
public class RestoreIP {
List<String> ans;
public List<String> restoreIpAddresses(String s) {
ans = new ArrayList<String>();
int len = s.length();
if (len >12 || len<4) {
return ans;
}
search(1,len,s,"");
return ans;
}
private void search(int curField, int digitsLeft, String s, String path) {
int fieldsLeft = 4 - curField;
if (fieldsLeft <0 ) {
ans.add(path.substring(0, path.length()-1));
}
for (int i=1; i<=3; i++) {
//Make the leftDigits is enough for leftFields,but not too much
if (digitsLeft-i < fieldsLeft) {
break;
}
else
if (3 * fieldsLeft + i < digitsLeft) {
continue;
}
else {
String fieldValue = s.substring(0, i);
if (fieldValue.length()>1) {
if (fieldValue.charAt(0)=='0') continue;
}
int value = Integer.parseInt(fieldValue);
if (value >=0 && value <=255)
search(curField+1,digitsLeft-i, s.substring(i), path+fieldValue+".");
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
RestoreIP ri = new RestoreIP();
System.out.println(ri.restoreIpAddresses("2502510035"));
}
}

复制代码

jaly50 · 2014-12-15 02:39:01

/*
* Time:12/14/2014 Sun 1:34 PM
* Author: Scarlett Chen
* LeetCode 145 Subsets II
* 题本身不难，比非duplicate就是多两行判重的代码～
* 要注意的就是path加了以后，要记得删掉～因为它是object，在method里call的时候不会自己变值
*
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SubSet2 {
List<List<Integer>> ans;
int[] num;
int len;
public List<List<Integer>> subsetsWithDup(int[] num) {
Arrays.sort(num);
ans = new ArrayList<List<Integer>>();
this.num = num;
this.len = num.length;
ans.add(new ArrayList<Integer>());
List<Integer> path= new ArrayList<Integer>();
for (int i=0; i < len; i++) {
for (int count=1; count<=len-i; count++) {
if (i>0 && num[i]==num[i-1]) continue;
path = new ArrayList<Integer>();
search(i,count,path);
}
}
return ans;
}
private void search (int index, int countLeft, List<Integer> path) {
if (countLeft==1) {
path.add(num[index]);
// System.out.println("Ans "+path);
ans.add(new ArrayList<Integer>(path));
path.remove(path.size()-1);
return;
}
else {
path.add(num[index]);
for (int i=index+1; i<len; i++) {
if (i>index+1 && num[i]==num[i-1]) continue;
// System.out.println(path+ " countLeft="+countLeft);
search(i, countLeft-1, path);
}
path.remove(path.size()-1);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
SubSet2 s= new SubSet2();
//System.out.println(s.subsetsWithDup(new int[]{}));
//System.out.println(s.subsetsWithDup(new int[]{1}));
//System.out.println(s.subsetsWithDup(new int[]{1,2}));
//System.out.println(s.subsetsWithDup(new int[]{2,1,1}));
System.out.println(s.subsetsWithDup(new int[]{1,2,3}));
}
}

复制代码

jaly50 · 2014-12-15 05:27:26

/*
* LeetCode Partition List
* Author: Scarlett Chen
* Time:12/14/2014 Sun 4:25 PM
* 解法就是再建一个list放较大值，最后再拼接
* 需要注意的就是把一个数挪给较大的list时，要让turn.next=null
*/
public class Partition {
public ListNode partition(ListNode head, int x) {
if (head==null || head.next==null) return head;
ListNode second = new ListNode(-1);
ListNode first= new ListNode(-1);
ListNode secondHead = second;
ListNode firstHead = first;
first.next = head;
while (first.next!=null) {
if (first.next.val < x) {
first = first.next;
}
else {
ListNode turn = first.next;
first.next = turn.next;
turn.next = null;
second.next = turn;
second = second.next;
}
}
first.next = secondHead.next;
return firstHead.next;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Partition p = new Partition();
ListNode head =new ListNode(1);
head.next = new ListNode(1);
p.print(p.partition(head, 0));
}
private void print(ListNode head) {
// TODO Auto-generated method stub
while (head!=null) {
System.out.print(head.val+" ");
head = head.next;
}
}
}

复制代码

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-22 11:08:28

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/*
* LeetCode: 148 Clone Graph
* @author:Scarlett Chen
* @date: 12/21/2014 Sun 7:04 PM
* clone一个无向图，用栈一个一个访问结点，用hashmap记录clone的结点
* 最近写代码都是一次过，真是不好意思嘿嘿嘿~~ 不过还是用了ide,如果没有提示的话，常常记不得如stack or map 的method的name
*/
public class CloneGraph {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
//To traverse the original nodes
Stack<UndirectedGraphNode> stack = new Stack<UndirectedGraphNode>();
//To record lable and its cloned Graph
Map<Integer,UndirectedGraphNode> clone = new HashMap<Integer,UndirectedGraphNode>();
if (node==null) return node;
stack.push(node);
clone.put(node.label, new UndirectedGraphNode(node.label));
while (!stack.isEmpty()) {
UndirectedGraphNode root = stack.pop();
UndirectedGraphNode cloneRoot = clone.get(root.label);
for (UndirectedGraphNode nei:root.neighbors) {
UndirectedGraphNode cloneNei;
//说明该结点已加入栈中
if (clone.containsKey(nei.label)) {
cloneNei = clone.get(nei.label);
}
else {
cloneNei = new UndirectedGraphNode(nei.label);
clone.put(nei.label, cloneNei);
stack.push(nei);
}
cloneRoot.neighbors.add(cloneNei);
}
}
return clone.get(node.label);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}

复制代码

jaly50 · 2014-12-24 16:46:19

/*
* LeetCode 149 Recover Binary Search Tree
* @author: Scarlett Chen
* @date: 12/24/2014 Wed 12:43 AM
* 这道题告诉我们要巧用全局变量！
* 以及理解一下~两个互相交换的node,在dfs中，第一个一定是和它下一个对比才被发现错的！第二个和它上一个对比发现错的！---利用这个规律就很好写了！
*/
public class RecoverBST {
TreeNode prev;
TreeNode first;
TreeNode second;
public void recoverTree(TreeNode root) {
first = null;
second = null;
prev = new TreeNode(Integer.MIN_VALUE);
if (root==null) return;
dfs(root);
if (first!=null && second!=null)
swap(first,second);
}
private void dfs(TreeNode root) {
if (root.left!=null) dfs(root.left);
if (prev.val > root.val) {
if (first == null)
first = prev;
second = root;
}
prev = root;
if (root.right!=null) dfs(root.right);
}
public void swap(TreeNode first, TreeNode second) {
int temp = first.val;
first.val = second.val;
second.val = temp;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
TreeNode head = new TreeNode(0);
TreeNode b = new TreeNode(1);
head.left = b;
RecoverBST rb = new RecoverBST();
rb.recoverTree(head);
}
}

复制代码

jaly50 · 2014-12-25 04:52:37

import java.util.Arrays;
/*
* LeetCode 152 Interleaving String
* DP o(n^2)
* @author: Scarlett.chen
* @date:12/24/2014 Wed 12:50 PM
* 注意边界值，len1==0等情况
* 以及f[i][j]表示s1的前i个和s2的前j个，是不是能构成s3的前i+j个
*/
public class InterLeaving {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
if (len3!=len2+len1) return false;
if (len1==0) return s2.equals(s3);
if (len2 == 0) return s1.equals(s3);
boolean[][] f = new boolean[len1+1][len2+1];
for (int i=0; i<=len1; i++) Arrays.fill(f[i], false);
f[0][0] = true;
for (int i=0; i<=len1; i++) {
for (int j=0; j<=len2; j++) {
if (i>0 && s1.charAt(i-1) == s3.charAt(i-1+j)) {
f[i][j] = f[i-1][j] ||f[i][j];
}
if (j>0 && s2.charAt(j-1) == s3.charAt(i+j-1)) {
f[i][j] = f[i][j-1] ||f[i][j];
}
}
}
return f[len1][len2];
}
public static void main(String[] args) {
// TODO Auto-generated method stub
InterLeaving il = new InterLeaving();
System.out.println(il.isInterleave("ab", "aa", "abaa"));
}
}

复制代码

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

浏览过的版块