29 October 2019
LeetCode(52) -- 1037, 1042, 1046, 1047, 1051
by Jerry Zhang
P1037. Valid Boomerang (Easy)
不在一条直线上的三个不同的点。
我的思路
首先三个点不能有任何两个点重合。其次三点的斜率不能一样。
我的代码
class Solution {
public boolean isBoomerang(int[][] points) {
if ((points[0][0] == points[1][0] && points[0][1] == points[1][1]) ||
(points[0][0] == points[2][0] && points[0][1] == points[2][1]) ||
(points[1][0] == points[2][0] && points[1][1] == points[2][1])) {
return false;
}
if ((points[1][1] - points[0][1]) / (double) (points[1][0] - points[0][0]) ==
(points[2][1] - points[0][1]) / (double) (points[2][0] - points[0][0])) {
return false;
}
return true;
}
}
100%
最优解
class Solution {
public boolean isBoomerang(int[][] points) {
int[] p0 = points[0];
int[] p1 = points[1];
int[] p2 = points[2];
int d1 = p0[0]*(p1[1]-p2[1]);
int d2 = p1[0]*(p2[1]-p0[1]);
if(d1+d2+p2[0]*(p0[1]-p1[1])==0)
return false;
else
return true;
// x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)=0.
}
}
三角形面积公式，其实就是鞋带法求面积，只不过稍稍改了一下公式。只要三个点面积为0，说明他们在一条直线上。
P1042. Flower Planting With No Adjacent (Easy)
有N个花园，每个种植一种花，从四种花里面选一种。路径表示两个花园之间存在一个双向路径。
我的思路
有点像四色原理画地图，相邻的两个国家不能用同一种颜色。首先把每个国家对应的相邻国家存到hashmap里。涂色时，看它所有的相邻国家的颜色，不能选已经有的颜色，剩下的颜色随便选一个。
我的代码
class Solution {
public int[] gardenNoAdj(int N, int[][] paths) {
HashMap<Integer, List<Integer>> map = new HashMap<>();
for (int[] path : paths) {
List<Integer> list1 = map.getOrDefault(path[0], new LinkedList<>());
list1.add(path[1]);
map.put(path[0], list1);
List<Integer> list2 = map.getOrDefault(path[1], new LinkedList<>());
list2.add(path[0]);
map.put(path[1], list2);
}
int[] ans = new int[N];
ans[0] = 1;
for (int i = 1; i < N; i++) {
List<Integer> list = map.get(i + 1);
if (list == null) {
ans[i] = 1;
} else {
boolean[] selected = new boolean[4];
for (Integer garden : list) {
if (ans[garden - 1] != 0) {
selected[ans[garden - 1] - 1] = true;
}
}
for (int j = 0; j < selected.length; j++) {
if (!selected[j]) {
ans[i] = j + 1;
break;
}
}
}
}
return ans;
}
}
68%
最优解
class Solution {
public int[] gardenNoAdj(int N, int[][] paths) {
// Each garden has at most 3 gardens connected to it
// connectionsToEarlyGardens[i][0] = j1 => first early neighbour of i is j1 (j1 < i)
// connectionsToEarlyGardens[i][1] = j2 => first early neighbour of i is j2 (j2 < i)
// connectionsToEarlyGardens[i][2] = j3 => first early neighbour of i is j3 (j3 < i)
int[][] connectionsToEarlyGardens = new int[N+1][3]; // 1-index-based
// numberOfEarlyNeighbour[i] = k (0 <= k <= 3) => i has k number of early neighbours
int[] numberOfEarlyNeighbour = new int[N+1]; // 1-index-based
for (int[] path : paths) {
int min, max;
if (path[0] < path[1]) {
min = path[0];
max = path[1];
} else {
min = path[1];
max = path[0];
}
connectionsToEarlyGardens[max][numberOfEarlyNeighbour[max]++] = min;
}
// no backtrack is needed
int[] ans = new int[N];
for (int pos = 1; pos <= N; pos++) {
int typeUsage = 0;
for (int i = 0; i < numberOfEarlyNeighbour[pos]; i++) {
int neighbourID = connectionsToEarlyGardens[pos][i];
typeUsage = typeUsage | (1 << ans[neighbourID-1]);
}
for (int type = 1; type <= 4; type++) {
if (((1 << type) & typeUsage) == 0) {
ans[pos-1] = type;
break;
}
}
}
return ans;
}
}
P1046. Last Stone Weight (Easy)
有一组石头，数组中每个数代表一块石头的重量。每次都找到最重的两块石头互相碰撞，如果质量相同，则都毁掉，如果质量不同，则生成一个小石头，质量是它们俩的差。直到碰撞到剩下一个石头为止。
我的思路
常规做法就是先排序，然后按题目要求，每次生成的新石头，再插入的数组中的正确位置。
我的代码
class Solution {
public int lastStoneWeight(int[] stones) {
Arrays.sort(stones);
LinkedList<Integer> list = new LinkedList<>();
for (int stone : stones) {
list.add(stone);
}
while (list.size() != 1) {
Integer heaviest = list.removeLast();
Integer heaviest2 = list.removeLast();
int diff = heaviest - heaviest2, i;
for (i = 0; i < list.size(); i++) {
if (list.get(i) >= diff) {
list.add(i, diff);
break;
}
}
if (i == list.size()) {
list.addLast(diff);
}
}
return list.get(0);
}
}
96%
最优解
class Solution {
public int lastStoneWeight(int[] stones) {
if(stones == null || stones.length == 0) return 0;
int n = stones.length;
while(n > 1) {
Arrays.sort(stones);
stones[n - 2] = stones[n - 1] - stones[n - 2];
n--;
}
return stones[0];
}
}
每次排一次序？n^2 * log(n) ?
P1047. Remove All Adjacent Duplicates In String (Easy)
一个字符串，移除所有相邻并相同的字母。就像消消乐之类的游戏。
我的思路
发现两个一样的字母后，就把它们都变成一个特殊标记（比如0），往前往后继续看，如果还相同，就一直标记。直到消除干净为止。后面如果再遇到相同的消掉后，要记得往前看非0的字符。
我的代码
class Solution {
public String removeDuplicates(String S) {
char[] chars = S.toCharArray();
int s = 0, e = 0;
for (int i = 1; i < chars.length; i++) {
if (chars[i] == chars[i-1]) {
chars[i] = 0;
chars[i-1] = 0;
s = i - 2;
e = i + 1;
while (s >= 0 && chars[s] == 0) {
s--;
}
while (s >= 0 && e < chars.length) {
if (chars[s] == chars[e]) {
chars[s] = 0;
chars[e] = 0;
s--;
e++;
} else {
break;
}
}
i = e;
}
}
StringBuilder sb = new StringBuilder();
for (char c : chars) {
if (c != 0) {
sb.append(c);
}
}
return sb.toString();
}
}
94%
最优解
class Solution {
public String removeDuplicates(String S) {
char[] arr = S.toCharArray();
int pivot = 0;
for (int i = 1; i < arr.length; i++) {
if (pivot > -1 && arr[i] == arr[pivot]) {
pivot--;
} else {
pivot++;
arr[pivot] = arr[i];
}
}
return new String(arr, 0, pivot + 1);
}
}
这个方法太聪明了。。。如果不一样，就把它放到下一个可以用的空位上去。 仅靠前后移动坐标，就实现了删除重复的目的。
P1051. Height Checker (Easy)
一些学生需要按身高从低到高排序，找出没站在正确位置的学生的最小人数。
我的思路
先排序，再跟原数组比较，不一样的就加1。
我的代码
class Solution {
public int heightChecker(int[] heights) {
int[] clone = heights.clone();
Arrays.sort(clone);
int count = 0;
for (int i = 0; i < heights.length; i++) {
if (heights[i] != clone[i]) {
count++;
}
}
return count;
}
}
87%
最优解
class Solution {
public int heightChecker(int[] heights) {
int[] heightToFreq = new int[101];
for (int height : heights) {
heightToFreq[height]++;
}
int result = 0;
int curHeight = 0;
for (int i = 0; i < heights.length; i++) {
while (heightToFreq[curHeight] == 0) {
curHeight++;
}
if (curHeight != heights[i]) {
result++;
}
heightToFreq[curHeight]--;
}
return result;
}
}
就是通过hashtable排序，然后跟原数组进行比较。
P1071. Greatest Common Divisor of Strings (Easy)
字符串S,T，如果T重复1次或多次后能构成S，则“T能整除S”。找出str1和str2的“最大公约数”
我的思路
把较短的一个不断重复，直到两个字符串长度一样。此时，另外一个字符串重复的次数，就是该字符串里面substring重复的次数。
我的代码
class Solution {
public String gcdOfStrings(String str1, String str2) {
if (str1.length() == str2.length()) {
if (str1.equals(str2)) {
return str1;
} else {
return "";
}
}
int count1 = 1, count2 = 1;
StringBuilder sb1 = new StringBuilder(str1);
StringBuilder sb2 = new StringBuilder(str2);
while (sb1.length() != sb2.length()) {
if (sb1.length() < sb2.length()) {
sb1.append(str1);
count1++;
} else {
sb2.append(str2);
count2++;
}
}
if (!sb1.toString().equals(sb2.toString())) {
return "";
}
return str1.substring(0, str2.length() / count1);
}
}
53%
最优解
class Solution {
public String gcdOfStrings(String str1, String str2) {
if((str1 + str2).equals(str2 + str1)) {
return str1.substring(0, gcd(str1.length(), str2.length()));
}
return "";
}
private int gcd(int a, int b) {
if(a % b == 0) return b;
return gcd(b, a % b);
}
}
直接算出来两个长度的最大公约数，不需要去操作字符串。另外，两个字符串互相拼接，得到的字符串相同才行。
P1078. Occurrences After Bigram (Easy)
Given words first and second, consider occurrences in some text of the form “first second third”, where second comes immediately after first, and third comes immediately after second.
For each such occurrence, add “third” to the answer, and return the answer.
Input: text = "alice is a good girl she is a good student", first = "a", second = "good"
Output: ["girl","student"]
我的思路
按顺序找即可。
我的代码
public class E_1078_OccurrencesAfterBigram {
public String[] findOcurrences(String text, String first, String second) {
ArrayList<String> ans = new ArrayList<>();
String[] words = text.split(" ");
for (int i = 0; i < words.length - 2; i++) {
if (words[i].equals(first) && words[i+1].equals(second)) {
ans.add(words[i+2]);
}
}
return ans.toArray(new String[0]);
}
}
96%
最优解
class Solution {
public String[] findOcurrences(String text, String first, String second) {
String combine = first +" "+ second;
int idx = 0;
List<String> res = new ArrayList<>();
while (idx < text.length()) {
int pos = text.indexOf(combine, idx);
if (pos==-1) break;
idx = pos + 1;
if (pos!=0 && text.charAt(pos-1) != ' ') continue;
pos += combine.length() + 1;
StringBuilder sb = new StringBuilder();
for (; pos<text.length()&& text.charAt(pos)!=' '; pos++) {
sb.append(text.charAt(pos));
}
if (sb.length() > 0) res.add(sb.toString());
}
return res.toArray(new String[res.size()]);
}
}
P1089. Duplicate Zeros (Easy)
一个数组里有一些0。每发现一个0，就复制一个0，剩下的数向右平移。超过数组范围的直接丢弃。所有更改必须在原数组内部进行。
我的思路
先跑一圈，用两个指针，从而找到最后一个数字应该在哪里。然后从右往左依次放置这些数，遇到0就复制。
我的代码
class Solution {
public void duplicateZeros(int[] arr) {
int i = 0, j = 0;
for (; i < arr.length && j < arr.length; i++, j++) {
if (arr[i] == 0) {
j++;
}
}
i--;
j--;
if (j == arr.length) {
arr[j - 1] = 0;
i--;
j = j - 2;
}
while (i >= 0) {
arr[j] = arr[i];
if (arr[i] == 0) {
j--;
arr[j] = 0;
}
i--;
j--;
}
}
}
96%，代码写得越来越难看，我自己都不想看了。。。哎
最优解
class Solution {
public void duplicateZeros(int[] a) {
if (a == null) {
return;
}
int[] b = new int[a.length];
int i = 0;
int j = 0;
while (j < a.length) {
if (a[i] == 0) {
j++;
} else {
b[j] = a[i];
}
i++;
j++;
}
System.arraycopy(b, 0, a, 0, a.length);
}
}
答案
class Solution {
public void duplicateZeros(int[] arr) {
int possibleDups = 0;
int length_ = arr.length - 1;
// Find the number of zeros to be duplicated
// Stopping when left points beyond the last element in the original array
// which would be part of the modified array
for (int left = 0; left <= length_ - possibleDups; left++) {
// Count the zeros
if (arr[left] == 0) {
// Edge case: This zero can't be duplicated. We have no more space,
// as left is pointing to the last element which could be included
if (left == length_ - possibleDups) {
// For this zero we just copy it without duplication.
arr[length_] = 0;
length_ -= 1;
break;
}
possibleDups++;
}
}
// Start backwards from the last element which would be part of new array.
int last = length_ - possibleDups;
// Copy zero twice, and non zero once.
for (int i = last; i >= 0; i--) {
if (arr[i] == 0) {
arr[i + possibleDups] = 0;
possibleDups--;
arr[i + possibleDups] = 0;
} else {
arr[i + possibleDups] = arr[i];
}
}
}
}