Skip to content

Commit fe48a15

Browse files
idfidf
committed
str
1 parent 211494c commit fe48a15

4 files changed

Lines changed: 187 additions & 0 deletions

File tree

‎src/AddBinary/Solution.java‎

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package AddBinary;
2+
3+
import java.util.ArrayList;
4+
import java.util.Collections;
5+
import java.util.List;
6+
import java.util.stream.Collectors;
7+
8+
/**
9+
* User: Danyang
10+
* Date: 1/28/2015
11+
* Time: 0:17
12+
*
13+
* Given two binary strings, return their sum (also a binary string).
14+
15+
For example,
16+
a = "11"
17+
b = "1"
18+
Return "100".
19+
*/
20+
public class Solution {
21+
/**
22+
* Reverse
23+
* @param a
24+
* @param b
25+
* @return
26+
*/
27+
public String addBinary(String a, String b) {
28+
List<Integer> ret = new ArrayList<>();
29+
if(a.length()>b.length()) {
30+
String t = a; a = b; b = t;
31+
}
32+
List<Integer> lst_a = a.chars().map(e -> e-'0').boxed().collect(Collectors.toList());
33+
List<Integer> lst_b = b.chars().map(e -> e-'0').boxed().collect(Collectors.toList());
34+
Collections.reverse(lst_a);
35+
Collections.reverse(lst_b);
36+
int carry = 0;
37+
for(int i=0; i<lst_b.size(); i++) {
38+
int s = carry+lst_b.get(i);
39+
if(i<lst_a.size())
40+
s += lst_a.get(i);
41+
ret.add(s%2);
42+
carry = s/2;
43+
}
44+
while(carry!=0) {
45+
ret.add(carry%2);
46+
carry -= 1;
47+
}
48+
Collections.reverse(ret);
49+
return ret.stream().map(Object::toString).collect(Collectors.joining());
50+
}
51+
}

‎src/CountandSay/Solution.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package CountandSay;
2+
3+
/**
4+
* User: Danyang
5+
* Date: 1/28/2015
6+
* Time: 10:37
7+
*
8+
* The count-and-say sequence is the sequence of integers beginning as follows:
9+
1, 11, 21, 1211, 111221, ...
10+
11+
1 is read off as "one 1" or 11.
12+
11 is read off as "two 1s" or 21.
13+
21 is read off as "one 2, then one 1" or 1211.
14+
Given an integer n, generate the nth sequence.
15+
16+
Note: The sequence of integers will be represented as a string.
17+
*/
18+
public class Solution {
19+
public String countAndSay(int n) {
20+
String ret = "1";
21+
for(int i=0; i<n-1; i++)
22+
ret = trans(ret);
23+
return ret;
24+
}
25+
26+
/**
27+
* Two pointers
28+
* Notice:
29+
* 1. initial condition of j
30+
* @param s
31+
* @return
32+
*/
33+
String trans(String s) {
34+
StringBuilder sb = new StringBuilder();
35+
char[] cs = s.toCharArray();
36+
int i = 0;
37+
int j = 0;
38+
while(i<cs.length && j<cs.length) {
39+
for(; j<cs.length && cs[i]==cs[j]; j++);
40+
sb.append(j-i).append(cs[i]);
41+
i = j;
42+
}
43+
return sb.toString();
44+
}
45+
}

‎src/RestoreIPAddresses/Solution.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package RestoreIPAddresses;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
import java.util.stream.Collectors;
6+
7+
/**
8+
* User: Danyang
9+
* Date: 1/28/2015
10+
* Time: 10:58
11+
*
12+
* Given a string containing only digits, restore it by returning all possible valid IP address combinations.
13+
14+
For example:
15+
Given "25525511135",
16+
17+
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
18+
*/
19+
public class Solution {
20+
/**
21+
* Notice:
22+
* 1. zero heading
23+
* @param s
24+
* @return
25+
*/
26+
public List<String> restoreIpAddresses(String s) {
27+
List<String> ret = new ArrayList<>();
28+
dfs(s, 4, new ArrayList<>(), ret);
29+
return ret;
30+
}
31+
32+
void dfs(String seq, int n, List<String> cur, List<String> ret) {
33+
if(n==0) {
34+
if(seq.length()==0)
35+
ret.add(cur.stream().collect(Collectors.joining(".")));
36+
}
37+
else {
38+
for(int i=1; i<=seq.length() && i<=3; i++) {
39+
String sub = seq.substring(0, i);
40+
if(isValidSegment(sub)) {
41+
cur.add(sub);
42+
dfs(seq.substring(i, seq.length()), n-1, cur, ret);
43+
cur.remove(cur.size()-1);
44+
}
45+
}
46+
}
47+
48+
}
49+
50+
boolean isValidSegment(String s) {
51+
if(s.length()>3 || s.length()<1)
52+
return false;
53+
if(s.length()>1 && s.charAt(0)=='0')
54+
return false;
55+
if(Integer.parseInt(s)>255)
56+
return false;
57+
return true;
58+
}
59+
60+
public static void main(String[] args) {
61+
List<String> ret = new Solution().restoreIpAddresses("25525511135");
62+
System.out.println(ret);
63+
}
64+
}

‎src/ValidPalindrome/Solution.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package ValidPalindrome;
2+
3+
/**
4+
* User: Danyang
5+
* Date: 1/28/2015
6+
* Time: 10:46
7+
*
8+
* Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
9+
10+
For example,
11+
"A man, a plan, a canal: Panama" is a palindrome.
12+
"race a car" is not a palindrome.
13+
14+
Note:
15+
Have you consider that the string might be empty? This is a good question to ask during an interview.
16+
17+
For the purpose of this problem, we define empty string as valid palindrome.
18+
*/
19+
public class Solution {
20+
public boolean isPalindrome(String s) {
21+
int[] cs = s.toLowerCase().chars().filter(e -> e>='a' && e<='z' || e>='0' && e<='9').toArray();
22+
for(int i=0; i<cs.length/2; i++)
23+
if(cs[i]!=cs[cs.length-1-i])
24+
return false;
25+
return true;
26+
}
27+
}

0 commit comments

Comments
 (0)