Skip to content

Commit ae4b5ea

Browse files
Serena211Serena211
committed
may.10
1 parent 8f67344 commit ae4b5ea

8 files changed

Lines changed: 252 additions & 0 deletions

File tree

‎bin/Class99_Mix/CountAndSay.class‎

1.83 KB
Binary file not shown.

‎bin/Class99_Mix/IsomorphicString1.class‎

1.6 KB
Binary file not shown.

‎bin/Class99_Mix/ReplacementsOfAAndB.class‎

1.17 KB
Binary file not shown.

‎bin/Class99_Mix/SquareRoot1.class‎

1.13 KB
Binary file not shown.

‎src/Class99_Mix/CountAndSay.java‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package Class99_Mix;
2+
3+
/*
4+
* Given a sequence of number: 1, 11, 21, 1211, 111221, …
5+
* The rule of generating the number in the sequence is as follow:
6+
* 1 is "one 1" so 11.
7+
* 11 is "two 1s" so 21.
8+
* 21 is "one 2 followed by one 1" so 1211.
9+
*
10+
* Find the nth number in this sequence.
11+
*
12+
* Assumptions:
13+
* n starts from 1, the first number is "1".
14+
*/
15+
public class CountAndSay {
16+
public String countAndSay(int n) {
17+
if (n <= 0) {
18+
return "";
19+
}
20+
String input = String.valueOf(n);
21+
int slow = 0;
22+
int fast = 1;
23+
int count = 1;
24+
StringBuilder sb = new StringBuilder();
25+
while (fast < input.length()) {
26+
if (input.charAt(slow) == input.charAt(fast)) {
27+
while (fast < input.length() && input.charAt(slow) == input.charAt(fast)) {
28+
count++;
29+
fast++;
30+
}
31+
sb.append(String.valueOf(count)).append(input.charAt(slow));
32+
} else {
33+
if (count == 1) {
34+
sb.append(String.valueOf(count)).append(input.charAt(slow));
35+
}
36+
slow = fast++;
37+
count = 1;
38+
}
39+
}
40+
if (slow == input.length() - 1) {
41+
sb.append(String.valueOf(1)).append(input.charAt(slow));
42+
}
43+
return sb.toString();
44+
}
45+
public String countAndSay2(int n) {
46+
if (n <= 0) {
47+
return "";
48+
}
49+
String res = "1";
50+
int index = 1;
51+
while (index < n) {
52+
StringBuilder temp = new StringBuilder();
53+
int count = 1;
54+
for (int i = 1; i < res.length(); i++) {
55+
if (res.charAt(i) == res.charAt(i - 1)) {
56+
count++;
57+
} else {
58+
temp.append(count).append(res.charAt(i - 1));
59+
count = 1;
60+
}
61+
}
62+
temp.append(count).append(res.charAt(res.length() - 1));
63+
res = temp.toString();
64+
index++;
65+
}
66+
return res;
67+
}
68+
public static void main(String[] args) {
69+
CountAndSay sol = new CountAndSay();
70+
System.out.println(sol.countAndSay2(6));
71+
}
72+
73+
}

‎src/Class99_Mix/IsomorphicString1.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package Class99_Mix;
2+
3+
import java.util.HashMap;
4+
5+
/*
6+
* Two Strings are called isomorphic if the letters in one String can be remapped to
7+
* get the second String. Remapping a letter means replacing all occurrences of it
8+
* with another letter. The ordering of the letters remains unchanged. The mapping is
9+
* two way and no two letters may map to the same letter, but a letter may map to
10+
* itself. Determine if two given String are isomorphic.
11+
*
12+
* Assumptions:
13+
* The two given Strings are not null.
14+
*
15+
* Examples:
16+
* "abca" and "xyzx" are isomorphic since the mapping is 'a' <-> 'x', 'b' <-> 'y',
17+
* 'c' <-> 'z'.
18+
*
19+
* "abba" and "cccc" are not isomorphic.
20+
*/
21+
public class IsomorphicString1 {
22+
// method 1: use array[0 -255]
23+
// to be continue;
24+
25+
// method 2: use hashmap
26+
public boolean isomorphic(String s, String t) {
27+
HashMap<Character,Character> mapS = new HashMap<Character, Character>();
28+
HashMap<Character,Character> mapT = new HashMap<Character, Character>();
29+
if (s.length() != t.length()) {
30+
return false;
31+
}
32+
for (int i = 0; i < s.length(); i++) {
33+
Character curS = mapS.get(s.charAt(i));
34+
if (curS != null && curS != t.charAt(i)) {
35+
return false;
36+
}
37+
mapS.put(s.charAt(i), t.charAt(i));
38+
Character curT = mapT.get(t.charAt(i));
39+
if (curT != null && curT != s.charAt(i)) {
40+
return false;
41+
}
42+
mapT.put(t.charAt(i), s.charAt(i));
43+
44+
}
45+
return true;
46+
// for (int i = 0; i < t.length(); i++) {
47+
// char temp = t.charAt(i);
48+
// Character cur = mapT.get(temp);
49+
// if (cur == null) {
50+
// System.out.println(s.charAt(i) + ", " + t.charAt(i));
51+
// mapT.put(t.charAt(i), s.charAt(i));
52+
// } else {
53+
// if (cur != s.charAt(i)) {
54+
// return false;
55+
// }
56+
// }
57+
// }
58+
// return true;
59+
}
60+
public static void main(String[] args) {
61+
IsomorphicString1 sol = new IsomorphicString1();
62+
System.out.println(sol.isomorphic("aabc", "bbaa"));
63+
}
64+
65+
}

‎src/Class99_Mix/ReplacementsOfAAndB.java‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package Class99_Mix;
2+
3+
/*
4+
* Given a string with only character 'a' and 'b', replace some of the characters
5+
* such that the string becomes in the forms of all the 'b's are on the right side
6+
* of all the 'a's.
7+
*
8+
* Determine what is the minimum number of replacements needed.
9+
*
10+
* Assumptions:
11+
* The given string is not null.
12+
*
13+
* Examples:
14+
* "abaab", the minimum number of replacements needed is 1 (replace the first 'b' with
15+
* 'a' so that the string becomes "aaaab").
16+
*/
17+
public class ReplacementsOfAAndB {
18+
public int minReplacements(String input) {
19+
if (input.isEmpty()) {
20+
return 0;
21+
}
22+
int[] M = new int[input.length() + 1];
23+
M[1] = 0;
24+
int count = 1;
25+
for (int i = 2; i < M.length; i++) {
26+
if (input.charAt(i - 1) != input.charAt(i - 2) && input.charAt(i - 1) == 'a') {
27+
if (count != 1) {
28+
M[i] = count;
29+
count = 1;
30+
} else {
31+
M[i] = M[i - 1] + 1;
32+
}
33+
} else {
34+
if (input.charAt(i - 1) == input.charAt(i - 2) && input.charAt(i - 1) == 'b') {
35+
count++;
36+
} else {
37+
M[i] = M[i - 1];
38+
}
39+
}
40+
}
41+
if (count != 1) {
42+
M[input.length()] = M[input.length() - 1];
43+
}
44+
return M[input.length()];
45+
}
46+
47+
public static void main(String[] args) {
48+
ReplacementsOfAAndB sol = new ReplacementsOfAAndB();
49+
System.out.println(sol.minReplacements("abaabb"));
50+
}
51+
52+
}

‎src/Class99_Mix/SquareRoot1.java‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package Class99_Mix;
2+
3+
/*
4+
* Given an integer number n, find its integer square root.
5+
*
6+
* Assumption:
7+
* n is guaranteed to be >= 0.
8+
*
9+
* Example:
10+
* Input: 18, Return: 4
11+
* Input: 4, Return: 2
12+
*/
13+
public class SquareRoot1 {
14+
// method 1: math
15+
public int sqrt(int x) {
16+
17+
return (int)Math.floor(Math.sqrt(x + 0.0));
18+
}
19+
// method 2: use dp O(n)
20+
// http://www.programcreek.com/2012/02/java-calculate-square-root-without-using-library-method/
21+
public int sqrt2(int x) {
22+
if (x <= 0) {
23+
return 0;
24+
}
25+
// int[] M = new int[x + 1];
26+
// M[1] = 1;
27+
// for (int i = 2; i < M.length; i++) {
28+
// if (i >= Math.pow(M[i - 1],2) && i <Math.pow(M[i - 1] + 1,2)) {
29+
// M[i] = M[i - 1];
30+
// } else {
31+
// M[i] = M[i - 1] + 1;
32+
// }
33+
// }
34+
// return M[x];
35+
int lastSqrt = 1;
36+
for (int i = 2; i <= x; i++) {
37+
if (i >= Math.pow(lastSqrt + 1, 2)) {
38+
lastSqrt += 1;
39+
}
40+
}
41+
return lastSqrt;
42+
}
43+
// method 3: use equation
44+
// Equation: newSqrt = (sqrt + num/sqrt) / 2;
45+
// num = t^2 ==> num / t = t ==> t + num/t = 2 * t ==> (t + num / t) / 2 = t
46+
public static double sqrt3(int number) {
47+
// initial t and squareRoot with any num, t != squareRoot;
48+
double t = 1;
49+
double squareRoot = t / 2.0;
50+
while (t != squareRoot) {
51+
t = squareRoot;
52+
squareRoot = (t + (number / t)) / 2.0;
53+
}
54+
55+
return squareRoot;
56+
}
57+
public static void main(String[] args) {
58+
SquareRoot1 sol = new SquareRoot1();
59+
System.out.println(sol.sqrt3(15));
60+
}
61+
62+
}

0 commit comments

Comments
 (0)