周末愉快，刷题继续。
卡牌分组
题目：给定一副牌，每张牌上都写着一个整数。此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：每组都有 X 张牌。组内所有的牌上都写着相同的整数。仅当你可选的 X >= 2 时返回 true。
示例 1：
输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
示例 2：
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。
示例 3：
输入：[1]
输出：false
解释：没有满足要求的分组。
示例 4：
输入：[1,1]
输出：true
解释：可行的分组是 [1,1]
示例 5：
输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]
提示：
1 <= deck.length <= 10000
0 <= deck[i] < 10000
思路：这道题的思路也很简单，首先不能有落单的元素，其次每个元素要么是最小元素数。要么是最小元素个数（最小元素数大于等于2）然后我实现了。
这道题其实实现起来还是很麻烦的，真正做了才发现不仅仅是最小元素和最小元素倍数这么简单，而且比较是否有公因数。比如 15 27 81，不是倍数关系但是可以true，因为都是3的倍数。然后麻烦就麻烦在判断是否有公因数了。我是这么做的:找到第一个数的所有大于2因数存起来，然后挨个因数对比是不是给定数的因数，不是移除元素。是则继续判断。什么时候数组元素为0了，则说明这写数没有共同因数，返回false。一直不为0说明有共同因数，返回true。直接贴代码：
class Solution {
List<Integer> b;
public boolean hasGroupsSizeX(int[] deck) {
b = new ArrayList<Integer>();
int[] ar = new int[10000];
for(int i : deck){
ar[i]++;
}
int flag = -1;
for(int i : ar){
if(i>0){
if(i==1) return false;
if(flag==-1){
getB(i);
flag = 0;
}else{
if(isB(i)) return false;
}
}
}
return true;
}
//获取一个数的所有因数（2以上的）
public void getB(int i){
for(int n = 2;n<=i;n++){
if(i%n == 0){
b.add(n);
if(i/n>2) b.add(i/n);
}
}
}
//获取这个数和所有因数数组的共同因数。不是共同因数的则remove
public boolean isB(int i){
for(int n = b.size()-1;n>=0;n--){
if(i%b.get(n)!=0) b.remove(n);
}
return b.size()==0;
}
}
这个性能不太好，只超过了百分之七十多的人，我去看看排行第一的代码:
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
int[] t = new int[1000];
for (int i : deck) {
t[i]++;
}
int g = -1;
for (int i = 0; i < 1000; i++) {
if (t[i] > 0) {
if (g == -1) {
g = t[i];
} else {
g = gcd(g, t[i]);
}
}
}
return g >= 2;
}
public int gcd(int x, int y) {
if (x == 0) {
return y;
} else {
return gcd(y % x, x);
}
}
}
看着很简洁（相比较）。递归又是循环的，但是我没太看明白。主要是心态也不太好，所有这个留着以后参考吧。我就用我的”笨“方法了。
仅仅反转字母
题目：给定一个字符串 S，返回 “反转后的” 字符串，其中不是字母的字符都保留在原地，而所有字母的位置发生反转。
示例 1：
输入："ab-cd"
输出："dc-ba"
示例 2：
输入："a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"
示例 3：
输入："Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"
提示：
S.length <= 100
33 <= S[i].ASCIIcode <= 122
S 中不包含 \ or "
思路：类似的题做过很多，这个也没觉得多复杂。很幸运没有各种进阶条件（比如不需使用额外空间）这么说的话，我第一思路就是获取字符串所有字母的下标。然后根据下标顺序交换，然后就是答案了~~我去实现了。
emmmmm...题很简单，实现容易，性能不行。先贴第一版本代码：
class Solution {
public String reverseOnlyLetters(String S) {
char[] x = S.toCharArray();
int[] index = new int[x.length];
int idx = 0;
for(int i = 0;i<x.length;i++){
if(Character.isLetter(x[i])){
index[idx] = i;
idx++;
}
}
int l = 0;
int r = idx-1;
while(l<r){
char temp = x[index[l]];
x[index[l]] = x[index[r]];
x[index[r]] = temp;
l++;
r--;
}
return new String(x);
}
}
怎么说呢，这个题我觉得处理也就这样了，怎么优化也没啥思路，我再看一会。
看了性能第一的代码，思路大同小异！！但是人家自己实现的判断一个char是不是字母，然后就0ms第一了。我使用的现有api，然后就1ms第八十多了。。。我能说什么?我也很无奈啊~~~贴上代码下一题了：
class Solution {
public String reverseOnlyLetters(String S) {
int start=0,end=S.length()-1;
char[] chars = S.toCharArray();
while (start<end){
if(!isLetter(chars[start])){
start++;
continue;
}
if(!isLetter(chars[end])){
end--;
continue;
}
char temp=chars[start];
chars[start]=chars[end];
chars[end]=temp;
start++;
end--;
}
return new String(chars);
}
public boolean isLetter(char c){
return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
}
}
按奇偶排序数组2
题目：给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
提示：
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
思路：我很感谢又来一道送分题让我今天的目标可以更快的达到。这道题思路就是两个下标点。一个0开始，每次加2.一个1开始每次加2.奇数用1开始的那个，偶数用0开始的那个，一次遍历over。我去实现了
思路不错，主要是题目简单，一次过：
class Solution {
public int[] sortArrayByParityII(int[] A) {
int[] res = new int[A.length];
int i = 0;
int n = 1;
for(int num : A){
if(num%2==0){
res[i] = num;
i = i+2;
}else{
res[n] = num;
n = n+2;
}
}
return res;
}
}
又看了性能第一的，深深的感觉愧疚，没有给自己增加难度！！怎么题目不说不让额外空间就真不用了呢？？看看人家，没用额外空间性能还好。。。好的吧，继续说题目，人家没用额外空间，在原数组的基础上判断的：
class Solution {
public int[] sortArrayByParityII(int[] A) {
// 0. traversal
for (int e = 0, o = 1; e < A.length; e += 2) {
// 1. 如果偶数位置是奇数（&1等于0说明是偶数，位置正确继续往下）
if ((A[e] & 1) == 0)
continue;
// 2. 找奇数位置的偶数
while ((A[o] & 1) == 1)
o += 2;
int temp = A[e];
A[e] = A[o];
A[o] = temp;
}
return A;
}
}
讲真，我做用的都是现成的数字运算，而这种方法用到了二进制运算。偶数&1是0.奇数&1是1.偶数位判断，位置正确则继续往下判断，位置不正确和另一个位置不正确的互换。很精巧的方法。属于那种看了恍然大悟，不看压根没那么想。
下一题吧，这道题的最大收获就是如何二进制判断奇偶数。
长安键入
题目：你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。
示例 1：
输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。
示例 2：
输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。
示例 3：
输入：name = "leelee", typed = "lleeelee"
输出：true
示例 4：
输入：name = "laiden", typed = "laiden"
输出：true
解释：长按名字中的字符并不是必要的。
提示：
name.length <= 1000
typed.length <= 1000
name 和 typed 的字符都是小写字母。
思路：这道题反正我第一次看没看到有什么坑，应该是很简单的。主旨就是输入字符串有的字符数量名字不一定要有那么多，但是名字有的字符数量输入字符串一定要有。就是一个简单的char对比我觉得，我先去实现试试。
思路没问题，而且直接性能超过百分百，给自己点个赞，哈哈~~贴代码:
class Solution {
public boolean isLongPressedName(String name, String typed) {
char[] x = name.toCharArray();
char[] y = typed.toCharArray();
int ix = 0;
int iy = 0;
if(x[0]!=y[0]) return false;
while(ix<x.length && iy<y.length){
if(x[ix]==y[iy]){
ix++;
iy++;
}else if(y[iy]!=y[iy-1]) {
return false;
}else{
iy++;
}
}
return ix==x.length;
}
}
这个其实分两种：一种是去了长按相等的，一种是去了长按不等的。不等又有两种情况。一种是原名字中有的现在没了，一种是原名字中没有的现在多了。
我这个便利第一步：两个都有的直接略过往下判断。然后如果是长按的元素（要等于上一个元素）输入串继续往下遍历。但是如果遍历到不是长按的元素，但是还不是名字中应有的元素，不管是原名字中有的现在没了，一种是原名字中没有的现在多了。反正都是不对了，直接返回false。
最后遍历完了还有两种情况，是名字遍历完了都符合，还是输入字符串遍历完了但是名字没遍历完。所有要判断一下是不是名字遍历完了。
（ps：刚刚写到这顺便发现了题目有个bug。如果遍历完了名字，但是输入串还有额外的字符理论上讲应该也是错误的。但是我这里疏忽了居然过了。已经提交leetcode，不知道结果如何）
这道题就到这里吧，反正思路比较简单，而且代码也不复杂，最后一题。
独特的电子邮件地址
每封电子邮件都由一个本地名称和一个域名组成，以 @ 符号分隔.例如，在 alice@leetcode.com中， alice 是本地名称，而 leetcode.com 是域名。除了小写字母，这些电子邮件还可能包含 '.' 或 '+'。如果在电子邮件地址的本地名称部分中的某些字符之间添加句点（'.'），则发往那里的邮件将会转发到本地名称中没有点的同一地址。例如，"alice.z@leetcode.com” 和 “alicez@leetcode.com” 会转发到同一电子邮件地址。 （请注意，此规则不适用于域名。）如果在本地名称中添加加号（'+'），则会忽略第一个加号后面的所有内容。这允许过滤某些电子邮件，例如 m.y+name@email.com 将转发到 my@email.com。 （同样，此规则不适用于域名。）可以同时使用这两个规则。给定电子邮件列表 emails，我们会向列表中的每个地址发送一封电子邮件。实际收到邮件的不同地址有多少？
示例：
输入：["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"]
输出：2
解释：实际收到邮件的是 "testemail@leetcode.com" 和 "testemail@lee.tcode.com"。
提示：
1 <= emails[i].length <= 100
1 <= emails.length <= 100
每封 emails[i] 都包含有且仅有一个 '@' 字符。
思路：首先这种到底有多少种类的问题！第一反应是set，map这种唯一性的。而这道题没必要key-value。所以暂定返回的数组格式是set.size()。所以这道题目前思路就是遍历原数组。每一个邮件的最终地址add进set，最后返回set中的元素。我去实现了。
很好，一顿操作贼，五分钟搞定问题，然后性能只超过百分之三十三的人。。。笑死了。先贴上代码;
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> set = new HashSet<String>();
for(String s :emails){
String[] str = s.split("@");
String[] ss = str[0].split("\\+");
String r = ss[0].replace(".","")+"@"+str[1];
set.add(r);
}
return set.size();
}
}
其实我个人都知道为啥性能这么差，各种字符串分割替换操作，能好就怪了。但是架不住省事啊。都是现成api。哈哈。行了，不闹了，说说优化：其实转成char数组操作绝对不会差的。但是麻烦多了。哎，为了性能我去麻烦麻烦了。
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> set = new HashSet<String>();
for(String s :emails){
StringBuffer sb = new StringBuffer();
boolean flag = true;
boolean flag2 = false;
for(char c :s.toCharArray()){
if(c=='+') flag = false;
if(c=='@') {
flag = true;
flag2 = true;
}
if(c=='.' && flag2) sb.append('.');
if(flag && c!='.') sb.append(c);
}
set.add(sb.toString());
}
return set.size();
}
}
性能超过百分之八十五，虽然还没及格但是已经进步多了。我继续看看怎么优化。
很好，又换个思路，性能超过百分之九十七的人了，凭自己及格，贴上代码：
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> set = new HashSet<String>();
for(String s :emails){
StringBuffer sb = new StringBuffer();
int index = s.indexOf("@");
char[] c = s.toCharArray();
for(int i = 0;i<index;i++){
if(c[i]=='+') break;
if(c[i]!='.')sb.append(c[i]);
}
sb.append(s.substring(index));
set.add(sb.toString());
}
return set.size();
}
}
其实本来都用字符判断会有很多无用的判断，但是改进完即前面的判断做好了，又最后@后原样照抄做好了。
今天的笔记就做到这里。如果稍微帮到你了记得点个喜欢点个关注~~每天进步一点点！另外祝大家周末愉快，工作顺顺利利呦！
网友评论