Skip to content

Commit 618421e

Browse files
fishercoder1534fishercoder1534
committed
add 593
1 parent f9eeb3d commit 618421e

File tree

3 files changed

+142
-0
lines changed

3 files changed

+142
-0
lines changed

‎README.md

+1
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@ Your ideas/fixes/algorithms are more than welcome!
2121
| # | Title | Solutions | Time | Space | Difficulty | Tag | Notes
2222
|-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
2323
|594|[Longest Harmonious Subsequence](https://leetcode.com/problems/longest-harmonious-subsequence/)|[Solution](../master/src/main/java/com/stevesun/solutions/_594.java) | O(n) |O(n) | Easy | Array, HashMap
24+
|593|[Valid Square](https://leetcode.com/problems/valid-square/)|[Solution](../master/src/main/java/com/stevesun/solutions/_593.java) | O(1) |O(1) | Medium | Math
2425
|583|[Delete Operation for Two Strings](https://leetcode.com/problems/delete-operation-for-two-strings/)|[Solution](../master/src/main/java/com/stevesun/solutions/_583.java) | O(m*n) |O(m*n) could be optimized to O(n) | Medium | DP
2526
|582|[Kill Process](https://leetcode.com/problems/kill-process/)|[Solution](../master/src/main/java/com/stevesun/solutions/_582.java) | O(n) |O(h) | Medium | Stack
2627
|581|[Shortest Unsorted Continuous Subarray](https://leetcode.com/problems/shortest-unsorted-continuous-subarray/)|[Solution](../master/src/main/java/com/stevesun/solutions/_581.java) | O(n) |O(1) | Easy | Array, Sort

‎src/main/java/com/stevesun/solutions/_593.java

+89
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
package com.stevesun.solutions;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
/**
8+
* 593. Valid Square
9+
*
10+
* Given the coordinates of four points in 2D space, return whether the four points could construct a square.
11+
12+
The coordinate (x,y) of a point is represented by an integer array with two integers.
13+
14+
Example:
15+
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
16+
Output: True
17+
Note:
18+
All the input integers are in the range [-10000, 10000].
19+
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
20+
Input points have no order.
21+
22+
*/
23+
public class _593 {
24+
/**Note: I don't need to use backtracking to find all permutations, this is an overkill.
25+
* This is the most easy one: https://leetcode.com/articles/kill-process-2/#approach-3-checking-every-case-accepted*/
26+
27+
28+
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
29+
List<int[]> input = new ArrayList<>(Arrays.asList(p1, p2, p3, p4));
30+
List<List<int[]>> allPermuations = getAllPermutations(input);
31+
for (List<int[]> eachPermutation : allPermuations) {
32+
if (isValid(eachPermutation)) return true;
33+
}
34+
return false;
35+
}
36+
37+
private List<List<int[]>> getAllPermutations(List<int[]> input) {
38+
List<List<int[]>> result = new ArrayList();
39+
List<int[]> init = new ArrayList<>();
40+
result.add(init);
41+
return backTracking(result, input, 0);
42+
}
43+
44+
private List<List<int[]>> backTracking(List<List<int[]>> result, List<int[]> input, int pos) {
45+
if (pos == input.size()) {
46+
return result;
47+
}
48+
List<List<int[]>> newResult = new ArrayList<>();
49+
for (List<int[]> eachList : result) {
50+
for (int i = 0; i <= eachList.size(); i++) {
51+
List<int[]> newList = new ArrayList<>(eachList);
52+
newList.add(i, input.get(pos));
53+
newResult.add(newList);
54+
}
55+
}
56+
result = newResult;
57+
return backTracking(result, input, pos+1);
58+
}
59+
60+
private boolean isValid(List<int[]> points) {
61+
int[] p1 = points.get(0);
62+
int[] p2 = points.get(1);
63+
int[] p3 = points.get(2);
64+
int[] p4 = points.get(3);
65+
double distance = (Math.pow(p1[0]-p2[0], 2) + Math.pow(p1[1] - p2[1], 2));
66+
return distance == (Math.pow(p2[0]-p3[0], 2) + Math.pow(p2[1] - p3[1], 2))
67+
&& distance == (Math.pow(p3[0]-p4[0], 2) + Math.pow(p3[1] - p4[1], 2))
68+
&& distance == (Math.pow(p4[0]-p1[0], 2) + Math.pow(p4[1] - p1[1], 2))
69+
&& isRightAngle(p1, p2, p3)
70+
&& noDuplicate(p1, p2, p3, p4);
71+
}
72+
73+
public boolean noDuplicate(int[] p1, int[] p2, int[] p3, int[] p4) {
74+
return !Arrays.equals(p1, p2)
75+
&& !Arrays.equals(p1, p3)
76+
&& !Arrays.equals(p1, p4)
77+
&& !Arrays.equals(p2, p3)
78+
&& !Arrays.equals(p2, p4)
79+
&& !Arrays.equals(p3, p4);
80+
}
81+
82+
public boolean isRightAngle(int[] p1, int[] p2, int[] p3) {
83+
double angle1 = Math.atan2(p2[1] - p1[1], p2[0] - p1[0]);
84+
double angle2 = Math.atan2(p3[1] - p1[1], p3[0] - p1[0]);
85+
double degree = Math.toDegrees(angle1-angle2);
86+
return degree%45 == 0;
87+
}
88+
89+
}

‎src/test/java/com/stevesun/_593Test.java

+52
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.solutions._48;
4+
import com.stevesun.solutions._593;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static org.junit.Assert.assertEquals;
9+
10+
/**
11+
* Created by stevesun on 5/22/17.
12+
*/
13+
public class _593Test {
14+
private static _593 test;
15+
private static int[] p1;
16+
private static int[] p2;
17+
private static int[] p3;
18+
private static int[] p4;
19+
20+
@BeforeClass
21+
public static void setup(){
22+
test = new _593();
23+
}
24+
25+
@Test
26+
public void test1(){
27+
p1 = new int[]{0,0};
28+
p2 = new int[]{1,1};
29+
p3 = new int[]{1,0};
30+
p4 = new int[]{0,1};
31+
assertEquals(true, test.validSquare(p1, p2, p3, p4));
32+
}
33+
34+
@Test
35+
public void test2(){
36+
p1 = new int[]{1,1};
37+
p2 = new int[]{5,3};
38+
p3 = new int[]{3,5};
39+
p4 = new int[]{7,7};
40+
assertEquals(false, test.validSquare(p1, p2, p3, p4));
41+
}
42+
43+
@Test
44+
public void test3(){
45+
p1 = new int[]{0,0};
46+
p2 = new int[]{0,0};
47+
p3 = new int[]{0,0};
48+
p4 = new int[]{0,0};
49+
System.out.println(test.noDuplicate(p1, p2, p3, p4));
50+
assertEquals(false, test.validSquare(p1, p2, p3, p4));
51+
}
52+
}

0 commit comments

Comments
 (0)