17 October 2019
LeetCode(40) -- 893, 896, 897, 905, 914
by Jerry Zhang
P893. Groups of Special-Equivalent Strings (Easy)
两个字符串“特殊相等”是指可以互换两个索引同奇或同偶的两个字符任意次。找出一共可以形成多少个这样的特殊相等的组。
我的思路
数一个单词在奇数位上的各个字母和偶数位上的各个字母。
没想对，看答案了。
答案
class Solution {
public int numSpecialEquivGroups(String[] A) {
Set<String> seen = new HashSet();
for (String S: A) {
int[] count = new int[52];
for (int i = 0; i < S.length(); ++i)
count[S.charAt(i) - 'a' + 26 * (i % 2)]++;
seen.add(Arrays.toString(count));
}
return seen.size();
}
}
其实建一个长为52的数组计数，我也想到了，但是后来想做一个hash value用来比较每个单词的统计情况。答案直接把这个长为52的数组tostring了，然后放到一个HashSet里。
重点是，如果想记录每个字母出现次数这样一个统计数据，可以直接用toString。虽然这样形成的字符串很长，但是可以把它交给Java的hash去想办法。
最优解
class Solution {
public int numSpecialEquivGroups(String[] A) {
int grouds = 0;
Set<Word> set = new HashSet<>();
for(String s:A) {
set.add(new Word(s));
}
return set.size();
}
class Word {
int[] odd;
int[] even;
public Word(String s) {
odd=new int[26];
even=new int[26];
for(int i=0;i<s.length();i++) {
if(i%2!=0)
odd[s.charAt(i)-'a']++;
else
even[s.charAt(i)-'a']++;
}
}
public int hashCode() {
return Arrays.hashCode(odd) + Arrays.hashCode(even);
}
public boolean equals(Object o) {
Word w = (Word) o;
for(int i=0;i<w.odd.length;i++) {
if(w.odd[i]!=this.odd[i]) return false;
if(w.even[i]!=this.even[i]) return false;
}
return true;
}
}
}
这个非常值得学习！新做了一个Word类，同时重写equals和hashcode方法，这样再用HashSet时就能自动调动这两个方法，实现hash
Arrays.hashCode()方法可以非常方便的给一个算出一个array的hashcode。那这个新实现的类，因为有两个数组，就把它们简单相加，或者用IDE默认的重写hash方法，一个hash乘以31再加上另一个hash。
P896. Monotonic Array (Easy)
判断一个数组是否是单调的（递增或递减）可重复。
我的思路
直接遍历判断就好了。跟上一题相比简单到极点了。
我的代码
class Solution {
public boolean isMonotonic(int[] A) {
boolean increasing = true;
boolean decreasing = true;
for (int i = 1; i < A.length; i++) {
if (A[i] > A[i - 1]) {
decreasing = false;
}
if (A[i] < A[i - 1]) {
increasing = false;
}
}
return increasing || decreasing;
}
}
75%
最优解
class Solution {
public boolean isMonotonic(int[] A) {
if(A.length==1 || A.length==0)
return true;
//is increasing
boolean isIncreasing=true;
for(int i=0;i<A.length-1;i++){
if(A[i+1]<A[i]){
isIncreasing=false;
break;
}
}
boolean isDeacreasing= true;
for(int i=0;i<A.length-1;i++){
if(A[i+1]>A[i]){
isDeacreasing=false;
break;
}
}
return isIncreasing || isDeacreasing;
}
}
跟我代码几乎完全一样。
P897. Increasing Order Search Tree (Easy)
中序遍历一棵树，然后把它的最左边的节点作为根节点，变成一个只有右节点的线性树。
我的思路
中序遍历然后存成一个新树即可。
我的代码
public class E_897_IncreasingOrderSearchTree {
TreeNode ans;
TreeNode current;
public TreeNode increasingBST(TreeNode root) {
inOrder(root);
return ans;
}
private void inOrder(TreeNode node) {
if (node == null) {
return;
}
inOrder(node.left);
if (ans == null) {
ans = new TreeNode(node.val);
current = ans;
} else {
current.right = new TreeNode(node.val);
current = current.right;
}
inOrder(node.right);
}
}
100%
最优解
class Solution {
TreeNode cur;
public TreeNode increasingBST(TreeNode root) {
TreeNode ans = new TreeNode(0);
cur = ans;
inorder(root);
return ans.right;
}
public void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
node.left = null;
cur.right = node;
cur = node;
inorder(node.right);
}
}
不需要新建节点，用原来的节点即可。
P905. Sort Array By Parity (Easy)
一个非负整数数组，返回一个数组使它所有偶数都是前面，所有奇数都放后面。顺序无所谓。
我的思路
先挑一遍偶数，再挑一遍奇数。
我的代码
class Solution {
public int[] sortArrayByParity(int[] A) {
int[] ans = new int[A.length];
int j = 0;
for (int i = 0; i < A.length; i++) {
if (A[i] % 2 == 0) {
ans[j] = A[i];
j++;
}
}
for (int i = 0; i < A.length; i++) {
if (A[i] % 2 != 0) {
ans[j] = A[i];
j++;
}
}
return ans;
}
}
100%
最优解
class Solution {
private void swap(int[] a, int x, int y) {
int tmp = a[x];
a[x] = a[y];
a[y] = tmp;
}
public int[] sortArrayByParity(int[] A) {
int N = A.length;
int[] ans = Arrays.copyOf(A, N);
int i=0;
int j=N-1;
while (i < j) {
while(ans[i]%2==0&&i<j) i+=1;
while(ans[j]%2!=0&&i<j) j-=1;
if((i<j)&&(ans[i]%2!=0)&&(ans[j]%2==0)) {
swap(ans, i, j);
i += 1;
j -= 1;
}
// System.out.printf("i=%d,j=%d\n",i,j);
}
// System.out.println(Arrays.toString(ans));
// System.out.println();
return ans;
}
}
P914. X of a Kind in a Deck of Cards (Easy)
有一组卡牌，每张牌上都有一个整数。问是否能分组，使每组都有X张牌且数字相等？(X >= 2)
我的思路
上周竞赛题weekly158也有一道分组的题，也是不知道每组里有几个数，但是每组的数字要相同。
我的代码
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
int[] count = new int[10000];
for (int i = 0; i < deck.length; i++) {
count[deck[i]]++;
}
int min = Integer.MAX_VALUE;
for (int i : count) {
if (i > 0) {
min = Math.min(min, i);
}
}
if (min < 2) {
return false;
}
for (int i : count) {
if (i > min && findGCD(i, min) < 2) {
return false;
}
}
return true;
}
private int findGCD(int number1, int number2) {
if(number2 == 0){
return number1;
}
return findGCD(number2, number1 % number2);
}
}
98%
最优解
class Solution {
public boolean hasGroupsSizeX(int[] arr) {
int[] res = new int[10001];
for(int i: arr){
res[i]++;
}
int min = 0;
for(int j=0;j<10001;j++){
if(res[j]!=0){
if(res[j]<2) return false;
if(min==0) {
min = res[j];
}else{
min = gcd(min,res[j]);
if(min<2)return false;
}
}
}
return true;
}
private int gcd(int x, int y) {
return x == 0 ? y : gcd(y % x, x);
}
}
答案：
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
int[] count = new int[10000];
for (int c: deck)
count[c]++;
int g = -1;
for (int i = 0; i < 10000; ++i)
if (count[i] > 0) {
if (g == -1)
g = count[i];
else
g = gcd(g, count[i]);
}
return g >= 2;
}
public int gcd(int x, int y) {
return x == 0 ? y : gcd(y%x, x);
}
}