Skip to content

Commit 7ecc001

Browse files
xiaoningningxiaoningning
committed
add PuzzleCoding
0 parents  commit 7ecc001

9 files changed

Lines changed: 540 additions & 0 deletions

‎PuzzleCoding/src/AddBinary.java‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
/*
2+
* Given two binary strings, return their sum (also a binary string).
3+
* For example,
4+
* a = "11"
5+
* b = "1"
6+
* Return "100".
7+
*/
8+
public class AddBinary {
9+
public static void main(String[] args){
10+
String s1 = "11";
11+
String s2 = "110";
12+
13+
int result = string2Integer(s1, 2) + string2Integer(s2, 2);
14+
System.out.println(toBinary(result));
15+
result = Integer.parseInt(s1, 2) + Integer.parseInt(s2, 2);
16+
System.out.println(Integer.toBinaryString(result));
17+
18+
19+
}
20+
21+
public static int string2Integer(String s, int code){
22+
int len = s.length();
23+
int result = 0;
24+
for (int i = 0; i < len;++i){
25+
int temp = Integer.valueOf(s.substring(len - i -1, len - i));
26+
result += Math.pow(code,i) * temp;
27+
}
28+
return result;
29+
}
30+
31+
public static String toBinary(int integer) {
32+
StringBuilder builder = new StringBuilder();
33+
int temp = 0;
34+
while (integer>0) {
35+
temp = integer;
36+
integer = (temp>>1);
37+
builder.append(temp%2);
38+
}
39+
return builder.reverse().toString();
40+
}
41+
}

‎PuzzleCoding/src/AddTwoNumber.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
import java.util.ArrayList;
2+
3+
/**
4+
* You are given two linked lists representing two non-negative numbers.
5+
* The digits are stored in reverse order and each of their nodes contain a single digit.
6+
* Add the two numbers and return it as a linked list.
7+
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
8+
* Output: 8 -> 0 -> 7
9+
*/
10+
public class AddTwoNumber {
11+
public static void main(String[] args){
12+
int[] a = {2,4,3};
13+
int[] b = {6,4};
14+
ArrayList<Integer> result = addTwoNumber(a,b);
15+
System.out.println(result);
16+
}
17+
18+
public static ArrayList<Integer> addTwoNumber(int[] n1, int[] n2){
19+
ArrayList<Integer> result = new ArrayList<Integer>();
20+
21+
int l1 = n1.length - 1;
22+
int l2 = n2.length - 1;
23+
int carry = 0;
24+
25+
while (l1>=0 && l2 >=0){
26+
int tmp = n1[l1--]+n2[l2--] + carry;
27+
result.add(0, tmp%10 );
28+
if((tmp+carry)/10 >= 1)
29+
carry = 1;
30+
else
31+
carry = 0;
32+
33+
}
34+
35+
int len = (l1>l2)? l1:l2;
36+
int[] n = (l1>l2)? n1:n2;
37+
while (len >= 0){
38+
int tmp = n[len--] + carry;
39+
result.add(0, tmp%10);
40+
if((tmp+carry)/10 >= 1)
41+
carry = 1;
42+
else
43+
carry = 0;
44+
}
45+
46+
return result;
47+
}
48+
49+
}

‎PuzzleCoding/src/ClimbStairs.java‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
/*
2+
** The problem could be solved by dynamic problem, if we see the stairs as an array,
3+
** we could calculate from back to front. Each steps required in a stair to reach top
4+
** is the sum of next 2 stairs.
5+
**
6+
** Finally, we would recognize it is just Fibonacci Sequence (just step 1 or 2),
7+
* the result is merely the
8+
** nth value in the sequence.
9+
**
10+
*/
11+
public class ClimbStairs {
12+
public static void main(String[] args){
13+
int N = 5;
14+
System.out.println(climbStairs(N));
15+
}
16+
17+
public static int climbStairs(int n){
18+
if(0<n && n<=1) return n ;
19+
else if(n<=0) return 1;
20+
else return climbStairs(n-1) + climbStairs(n-2) + climbStairs(n-3) ; // add the last step 1 or 2 or 3.
21+
}
22+
}

‎PuzzleCoding/src/GenerateParentheses.java‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
2+
public class GenerateParentheses {
3+
public static void main(String[] args){
4+
int N = 3;
5+
generateParentheses(new char[2*N], N, N, 0);
6+
7+
System.out.println(isGoodParentheses("(()][())".toCharArray()));
8+
}
9+
public static void generateParentheses(char[] prefix, int left, int right, int level){
10+
if(left > right || left < 0)
11+
return;
12+
if(left ==0 && right == 0) {
13+
System.out.println(String.valueOf(prefix));
14+
return;
15+
}
16+
else {
17+
if(left>0){
18+
prefix[level] = '(';
19+
generateParentheses(prefix, left-1, right, level+1);
20+
}
21+
if(right> 0){
22+
prefix[level] = ')';
23+
generateParentheses(prefix, left, right-1, level+1);
24+
}
25+
}
26+
27+
}
28+
29+
public static boolean isGoodParentheses(char[] s){
30+
31+
int level1 = 0;
32+
int level2 = 0;
33+
34+
for(int i = 0 ; i < s.length; i++){
35+
if(level1==0)
36+
if(s[i] ==')')
37+
return false;
38+
if(level2==0)
39+
if(s[i] ==']')
40+
return false;
41+
42+
if(s[i] == '(')
43+
level1++;
44+
if(s[i]==')')
45+
level1--;
46+
if(s[i] == '[')
47+
level2++;
48+
if(s[i]==']')
49+
level2--;
50+
51+
}
52+
53+
return (level1==0)&&(level2==0);
54+
}
55+
}

‎PuzzleCoding/src/IntervalComparator.java‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
import java.util.Comparator;
2+
3+
public class IntervalComparator implements Comparator<MergeIntervals> {
4+
public int compare(MergeIntervals in1, MergeIntervals in2) {
5+
if (in1.start <= in2.start && in1.end < in2.end)
6+
return -1;
7+
else if (in1.start == in2.start && in1.end == in2.end)
8+
return 0;
9+
else if (in1.start > in2.start && in1.end < in2.end)
10+
return 0;
11+
else
12+
return 1;
13+
}
14+
}

‎PuzzleCoding/src/MergeIntervals.java‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
import java.util.ArrayList;
2+
import java.util.Collections;
3+
4+
/**
5+
* Given a set of non overlapping intervals
6+
* Example 1 :(1,4) (6,10) (14, 19) and another interval (13, 17) merge them as (1,4) (6,10) (13,19)
7+
* <p/>
8+
* Example 2: (1,5) (6, 15) (20, 21) (23, 26) (27, 30) (35, 40), and the new interval is (14, 33). The
9+
* output should be (1,5) (6, 33) (35, 40).
10+
* This is because the new interval overlaps with (6, 15) (20, 21) (23, 26) (27, 30)
11+
* <p/>
12+
* Given a collection of intervals, merge all overlapping intervals.
13+
* <p/>
14+
* For example,
15+
* Given [1,3],[2,6],[8,10],[15,18],
16+
* return [1,6],[8,10],[15,18].
17+
*/
18+
public class MergeIntervals {
19+
public int start;
20+
public int end;
21+
22+
public MergeIntervals(int s, int e) {
23+
if (s < e) {
24+
start = s;
25+
end = e;
26+
} else {
27+
throw new RuntimeException("start < end");
28+
}
29+
}
30+
31+
public static void main(String[] args) {
32+
ArrayList<MergeIntervals> intervals = new ArrayList<MergeIntervals>();
33+
intervals.add(new MergeIntervals(6, 10));
34+
intervals.add(new MergeIntervals(1, 4));
35+
intervals.add(new MergeIntervals(14, 19));
36+
intervals.add(new MergeIntervals(13, 17));
37+
38+
Collections.sort(intervals, new IntervalComparator());
39+
System.out.println("original intervals");
40+
printIntervals(intervals);
41+
42+
ArrayList<MergeIntervals> result = mergeIntervals(intervals);
43+
System.out.println("merged intervals");
44+
printIntervals(result);
45+
}
46+
47+
public static ArrayList<MergeIntervals> mergeIntervals(ArrayList<MergeIntervals> intervalsArrayList) {
48+
if (intervalsArrayList.size() <= 1) return intervalsArrayList;
49+
50+
ArrayList<MergeIntervals> result = new ArrayList<MergeIntervals>();
51+
result.add(0, intervalsArrayList.get(0));
52+
53+
for (int i = 1; i < intervalsArrayList.size(); i++) {
54+
MergeIntervals prev = result.get(0);
55+
MergeIntervals cur = intervalsArrayList.get(i);
56+
57+
if (prev.end < cur.start) {
58+
result.add(0, cur);
59+
} else {
60+
if (prev.end < cur.end)
61+
prev.end = cur.end;
62+
if (prev.start > cur.start)
63+
prev.start = cur.start;
64+
result.remove(0);
65+
result.add(0, prev);
66+
}
67+
}
68+
69+
return result;
70+
}
71+
72+
public static void printIntervals(ArrayList<MergeIntervals> intervalsArrayList) {
73+
for (int i = 0; i < intervalsArrayList.size(); ++i) {
74+
MergeIntervals in = intervalsArrayList.get(i);
75+
System.out.println("(" + in.start + "," + in.end + ")");
76+
}
77+
}
78+
79+
80+
}
81+

‎PuzzleCoding/src/Queen.java‎

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
import java.util.Arrays;
2+
3+
/**
4+
* Solve the 8 queens problem using recursion and backtracing.
5+
* Prints out all solutions.
6+
* <p/>
7+
* Limitations: works for N <= 25, but slows down considerably
8+
* for larger N.
9+
* <p/>
10+
* Remark: this program implicitly enumerates all N^N possible
11+
* placements (instead of N!), but the backtracing prunes off
12+
* most of them, so it's not necessarily worth the extra
13+
* complication of enumerating only permutations.
14+
* <p/>
15+
* <p/>
16+
* % java Queens 3
17+
* <p/>
18+
* % java Queens 4
19+
* * Q * *
20+
* * * * Q
21+
* Q * * *
22+
* * * Q *
23+
* <p/>
24+
* * * Q *
25+
* Q * * *
26+
* * * * Q
27+
* * Q * *
28+
* <p/>
29+
* % java Queens 8
30+
* Q * * * * * * *
31+
* * * * * Q * * *
32+
* * * * * * * * Q
33+
* * * * * * Q * *
34+
* * * Q * * * * *
35+
* * * * * * * Q *
36+
* * Q * * * * * *
37+
* * * * Q * * * *
38+
*/
39+
public class Queen {
40+
/**
41+
* ********************************************************************
42+
* Return true if queen placement q[n] does not conflict with
43+
* other queens q[0] through q[n-1]
44+
* *********************************************************************
45+
*/
46+
47+
public static boolean isConsistent(int[] q, int n) {
48+
for (int i = 0; i < n; i++) {
49+
if (q[i] == q[n]) return false; // same column
50+
if ((q[i] - q[n]) == (n - i)) return false; // same major diagonal
51+
if ((q[n] - q[i]) == (n - i)) return false; // same minor diagonal
52+
}
53+
return true;
54+
}
55+
56+
// since it is unique int array, there is no need to compare column/row
57+
public static boolean isConsistent(int[] q) {
58+
for (int i = 0; i < q.length; i++) {
59+
for (int j = i + 1; j < q.length; j++) {
60+
if (q[i] == q[j]) return false; // same column
61+
if ((q[i] - q[j]) == (j - i)) return false; // same major diagonal
62+
if ((q[j] - q[i]) == (j - i)) return false; // same minor diagonal
63+
}
64+
}
65+
return true;
66+
}
67+
68+
/**
69+
* ********************************************************************
70+
* Print out N-by-N placement of queens from permutation q in ASCII.
71+
* *********************************************************************
72+
*/
73+
public static void printQueens(int[] q) {
74+
int N = q.length;
75+
for (int i = 0; i < N; i++) {
76+
for (int j = 0; j < N; j++) {
77+
if (q[i] == j) System.out.print("Q ");
78+
else System.out.print("* ");
79+
}
80+
System.out.println();
81+
}
82+
System.out.println();
83+
}
84+
85+
86+
public static void permQueen(String prefix, String s) {
87+
int N = s.length();
88+
if (N == 0) {
89+
int[] tmp = new int[prefix.length()];
90+
for (int i = 0; i < prefix.length(); i++)
91+
tmp[i] = Integer.valueOf(prefix.substring(i, i + 1));
92+
if (isConsistent(tmp)) {
93+
System.out.println(prefix);
94+
printQueens(tmp);
95+
}
96+
return;
97+
}
98+
for (int i = 0; i < N; i++)
99+
permQueen(prefix + s.charAt(i), s.substring(0, i) + s.substring(i + 1));
100+
101+
}
102+
103+
public static void enumerate(int[] q, int n) {
104+
int N = q.length;
105+
if (n == N) {
106+
System.out.println(Arrays.toString(q));
107+
printQueens(q);
108+
}
109+
else {
110+
for (int i = 0; i < N; i++) {
111+
q[n] = i;
112+
if (isConsistent(q, n)) enumerate(q, n+1);
113+
}
114+
}
115+
}
116+
117+
public static void main(String[] args) {
118+
int N = 4;
119+
enumerate(new int[N], 0);
120+
121+
StringBuffer sb = new StringBuffer();
122+
for (int i = 0; i < N; i++)
123+
sb.append(String.valueOf(i));
124+
125+
permQueen("", sb.toString());
126+
}
127+
}

0 commit comments

Comments
 (0)