Skip to content

Commit 79a5d42

Browse files
awangdevawangdev
committed
Day4
1 parent 8e24d98 commit 79a5d42

40 files changed

Lines changed: 1692 additions & 543 deletions

‎Java/Add Two Numbers II.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,9 @@
11
方向相反。巧用stack.
2+
3+
做加法都一样：
4+
1. carrier
5+
2. carrier = (rst + carrier) / 10
6+
3. rst = (rst + carrier) % 10
27
```
38
/*
49
You have two numbers represented by a linked list, where each node contains a single digit.

‎Java/Anagrams.java‎

Lines changed: 54 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,23 @@
1+
hashtable 的做法。
2+
toCharArray
3+
Arrays.sort
4+
Stirng.valueOf(char[])
5+
6+
7+
8+
http://www.jiuzhang.com/solutions/anagrams/
9+
做法不太一样 lOl
10+
1. take each string, count the occurrance of the 26 letters. save in int[]count.
11+
2. hash the int[] count and output a unique hash value.
12+
hash = hash * a + num
13+
a = a * b.
14+
3. save to hashmap in the same way as we do.
15+
16+
这一步把for s: strs
17+
里面的时间复杂度降到了O(L). L = s.length()
18+
19+
而普通的，for 里面的时间复杂度是 Llog(L)
20+
```
121
/*
222
Given an array of strings, return all groups of strings that are anagrams.
323
@@ -12,47 +32,41 @@
1232
Tags Expand
1333
String Hash Table
1434
15-
Thoughts:
16-
Sorry char array, add to hashtable.
17-
If exist in hashtable, add to final result
18-
Note: rst does not have duplicates.
35+
1936
*/
20-
import java.util.*;
21-
public class Anagrams {
22-
/**
23-
* @param strs: A list of strings
24-
* @return: A list of strings
25-
*/
26-
public List<String> anagrams(String[] strs) {
27-
List<String> rst = new ArrayList<String>();
28-
if (strs == null || strs.length == 0) {
29-
return rst;
30-
}
31-
HashMap<String, String> map = new HashMap<String, String>();
32-
for (int i = 0; i < strs.length; i++) {
33-
char[] array = strs[i].toCharArray();
34-
Arrays.sort(array);
35-
String s = new String(array);
36-
if (map.containsKey(s)) {
37-
if (!rst.contains(map.get(s))) {//The first appearnce of this anagrams
38-
rst.add(map.get(s));
39-
}
40-
rst.add(strs[i]);
41-
} else {
42-
map.put(s, strs[i]);
43-
}
44-
}
45-
return rst;
46-
}
47-
}
4837

49-
public static void main(String[] args){
50-
Anagrams test = new Anagrams();
51-
String[] t = {"", ""};
52-
List<String> rst = test.anagrams(t);
53-
for (String s : rst) {
54-
System.out.println(s);
55-
}
56-
System.out.println("Done");
38+
/*
39+
40+
Recap 12.09.2015
41+
Feels like put into a hashmap of each string's sorted version. <String, ArrayList<Sting>>
42+
compare each string. If match, add into it.
43+
reurn all that has >= 2 items
44+
*/
45+
public class Solution {
46+
public List<String> anagrams(String[] strs) {
47+
List<String> rst = new ArrayList<String>();
48+
if (strs == null || strs.length == 0) {
49+
return rst;
50+
}
51+
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
52+
for (int i = 0; i < strs.length; i++) {
53+
char[] arr = strs[i].toCharArray();
54+
Arrays.sort(arr);
55+
String s = String.valueOf(arr);
56+
if (!map.containsKey(s)) {
57+
ArrayList<String> list = new ArrayList<String>();
58+
map.put(s, list);
59+
}
60+
map.get(s).add(strs[i]);
61+
}
62+
//check instance occurs >= 2
63+
for (Map.Entry<String, ArrayList<String>> entry : map.entrySet()) {
64+
if (entry.getValue().size() >= 2) {
65+
rst.addAll(entry.getValue());
66+
}
67+
}
68+
return rst;
5769
}
5870
}
71+
72+
```

‎Java/Binary Representation.java‎

Lines changed: 76 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,15 @@
1+
主要就是要分两半。
2+
3+
Integer那一半好弄，Loop里面 num%2, num/2就好。
4+
Decimal那边复杂点，bit == 1的数学条件是：
5+
当下num * 2 - 1 >= 0...
6+
然后循环时候还要 num * 2 - 1, 或者 num * 2
7+
8+
因为num是 double, 小于0的小数，所以其实这样做下去很可能无限循环。
9+
10+
所以题目也才有了32BIT的要求！
11+
12+
```
113
/*
214
Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return ERROR.
315
@@ -10,6 +22,10 @@ Given a (decimal - e.g. 3.72) number that is passed in as a string, return the b
1022
Tags Expand
1123
String Cracking The Coding Interview Bit Manipulation
1224
25+
*/
26+
27+
/*
28+
1329
Thoughts:
1430
Expan the value for binary representation:
1531
8, 4, 2, 1, 0.5, 0.25 ... etc
@@ -23,65 +39,76 @@ Given a (decimal - e.g. 3.72) number that is passed in as a string, return the b
2339
Checkfloat first: if float part is '0' or "", can just move on the integer part.
2440
2541
Note: str.split("\\.")
26-
Note2: use a set to prevent infinite loop on float: for example: 2x - 1 = x -> x = 1. that will cause infinite loop.
42+
Note2: use a set to prevent infinite loop on float:
43+
for example: 2x - 1 = x -> x = 1. that will cause infinite loop.
44+
2745
*/
2846
public class Solution {
2947
/**
3048
*@param n: Given a decimal number that is passed in as a string
3149
*@return: A string
3250
*/
3351
public String binaryRepresentation(String n) {
34-
if (n.length() == 0 || n.equals("0")) {
35-
return "0";
36-
}
37-
if (n.indexOf(".") == -1) {
38-
return parseInteger(n);
39-
}
40-
String[] strs = n.split("\\.");
41-
String decimal = parseDecimal(strs[1]);
42-
if (decimal.equals("ERROR")) {
43-
return decimal;
44-
}
45-
if (decimal.length() == 0 || decimal.equals("0")) {
46-
return parseInteger(strs[0]);
47-
} else {
48-
return parseInteger(strs[0]) + "." + decimal;
49-
}
52+
if (n.length() == 0 || n.equals("0")) {
53+
return "0";
54+
}
55+
//If no '.', no decimal, just parseInteger
56+
if (n.indexOf(".") == -1) {
57+
return parseInteger(n);
58+
}
59+
//Split the string by '.'
60+
String[] strs = n.split("\\.");
61+
//Deal with decimal first.
62+
String decimal = parseDecimal(strs[1]);
63+
//If not applicable, it won't work, don't need to calculate integer part. Just return ERROR.
64+
if (decimal.equals("ERROR")) {
65+
return decimal;
66+
}
67+
//Deal with integer part
68+
if (decimal.length() == 0 || decimal.equals("0")) {
69+
return parseInteger(strs[0]);
70+
} else {
71+
return parseInteger(strs[0]) + "." + decimal;
72+
}
5073
}
5174

5275
public String parseInteger(String n) {
53-
if (n.length() == 0 || n.equals("0")) {
54-
return n;
55-
}
56-
int num = Integer.parseInt(n);
57-
String rst = "";
58-
while (num != 0) {
59-
rst = num % 2 + rst;
60-
num = num / 2;
61-
}
62-
return rst;
76+
if (n.length() == 0 || n.equals("0")) {
77+
return n;
78+
}
79+
int num = Integer.parseInt(n);
80+
String rst = "";
81+
while (num != 0) {
82+
rst = num % 2 + rst;//mod(2) -> binary representation
83+
num = num / 2;//小时候转换二进制也是这样。
84+
}
85+
return rst;
6386
}
64-
87+
// A little bit math, but implemtable.
6588
public String parseDecimal(String n) {
66-
if (n.length() == 0 || n.equals("0")) {
67-
return "";
68-
}
69-
double num = Double.parseDouble("0." + n);
70-
HashSet<Double> set = new HashSet<Double>();
71-
String rst = "";
72-
while (num > 0) {
73-
if (rst.length() > 32 || set.contains(num)) {
74-
return "ERROR";
75-
}
76-
set.add(num);
77-
if (num * 2 >= 1) {
78-
rst = rst + "1";
79-
num = num * 2 - 1;
80-
} else {
81-
rst = rst + "0";
82-
num = num * 2;
83-
}
84-
}
85-
return rst;
89+
if (n.length() == 0 || n.equals("0")) {
90+
return "";
91+
}
92+
//A doublem must be able to catch it. If not, that is way bigger than 32 bit.
93+
double num = Double.parseDouble("0." + n);
94+
//Check existance
95+
HashSet<Double> set = new HashSet<Double>();
96+
String rst = "";
97+
while (num > 0) {
98+
if (rst.length() > 32 || set.contains(num)) {
99+
return "ERROR";
100+
}
101+
set.add(num);
102+
//For decimal: binary code on one spot == 1, means: num * 2 - 1 > 0
103+
if (num * 2 >= 1) {
104+
rst = rst + "1";
105+
num = num * 2 - 1;
106+
} else {
107+
rst = rst + "0";
108+
num = num * 2;
109+
}
110+
}
111+
return rst;
86112
}
87-
}
113+
}
114+
```

0 commit comments

Comments
 (0)