18 October 2019
LeetCode(41) -- 917, 922, 925, 929, 933
by Jerry Zhang
P917. Reverse Only Letters (Easy)
一个字符串，所有非字母位置保持不变，字母的顺序前后反转。
我的思路
比较简单，争取bugfree
我的代码
class Solution {
public String reverseOnlyLetters(String S) {
char[] chars = S.toCharArray();
int l = 0, r = chars.length - 1;
while (l < r) {
if (!Character.isAlphabetic(chars[l])){
l++;
continue;
}
if (!Character.isAlphabetic(chars[r])){
r--;
continue;
}
char temp = chars[l];
chars[l] = chars[r];
chars[r] = temp;
l++;
r--;
}
return new String(chars);
}
}
100%
最优解
class Solution {
public String reverseOnlyLetters(String S) {
char[] arr = S.toCharArray();
int i = 0, j = arr.length - 1;
while(i < j) {
while(i < j && !Character.isLetter(arr[i])) i++;
while(i < j && !Character.isLetter(arr[j])) j--;
if(i >= j) break;
char tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
j--;
i++;
}
return String.valueOf(arr);
}
}
差不多
P922. Sort Array By Parity II (Easy)
非负整数的数组，一半是奇数，一半是偶数。重新排列这个数组，使得在奇数索引上一定是奇数，偶数索引上一定是偶数。
我的思路
挨个看，不符合的，就往后看，直到找到下一个错误，就互换。实际是错误有两种可能，一种是本该放奇数的位置放了偶数，另一种是本该放偶数的位置放了奇数。用两个变量分别暂存一下这两种错误，后面遇到同样的错误，就跟前面那个错的互换。
有个bug，偶数位上的错误应该用奇数位上的错误解决。
我的代码
class Solution {
public int[] sortArrayByParityII(int[] A) {
LinkedList<Integer> oddErrorIndexBuffer = new LinkedList<>();
LinkedList<Integer> evenErrorIndexBuffer = new LinkedList<>();
for (int i = 0; i < A.length; i++) {
if (A[i] % 2 != i % 2) {
if (i % 2 == 0) {
if (oddErrorIndexBuffer.size() == 0) {
evenErrorIndexBuffer.push(i);
} else {
Integer oddError = oddErrorIndexBuffer.pop();
int temp = A[oddError];
A[oddError] = A[i];
A[i] = temp;
}
} else {
if (evenErrorIndexBuffer.size() == 0) {
oddErrorIndexBuffer.push(i);
} else {
Integer evenError = evenErrorIndexBuffer.pop();
int temp = A[evenError];
A[evenError] = A[i];
A[i] = temp;
}
}
}
}
return A;
}
}
22%
最优解
class Solution {
public int[] sortArrayByParityII(int[] A) {
int i = 0, j = 1;
while(i < A.length) {
if((A[i] & 1) == 1) {
while((A[j] & 1) == 1)
j += 2;
int temp = A[i];
A[i] = A[j];
A[j] = temp;
}
i += 2;
}
return A;
}
}
我那个代码太麻烦了。这个最优解值得学习。用i,j分别表示偶数坐标和奇数坐标。如果i表示的偶数坐标上遇到了一个奇数，就去j表示的奇数坐标找，直到找到一个偶数为止。找到后互换。这样两个坐标还能保持在正确的位置。
P925. Long Pressed Name (Easy)
一个人正在拼写自己的名字，有时候键盘会重复输入某个字母。问是不是有可能是这种重复输入的问题。
Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.
我的思路
用两个指针跟踪两个单词。具体的代码我写得比较难看，瞎试了好几次才通过。
我的代码
public class E_925_LongPressedName {
public boolean isLongPressedName(String name, String typed) {
int i = 0;
for (int j = 0; i < name.length() && j < typed.length(); i++, j++) {
if (name.charAt(i) != typed.charAt(j)) {
if (j == 0) return false;
while (j < typed.length() && typed.charAt(j) == typed.charAt(j - 1)){
j++;
}
if (j == typed.length()) return false;
if (name.charAt(i) != typed.charAt(j)) return false;
}
}
return i == name.length();
}
}
52%
最优解
class Solution {
public boolean isLongPressedName(String name, String typed) {
int j = 0;
for(char c: name.toCharArray()){
if(j >= typed.length())
return false;
if(c != typed.charAt(j)) {
if(j == 0 || typed.charAt(j - 1) != typed.charAt(j)) {
return false;
} else {
while(j < typed.length() && typed.charAt(j) == typed.charAt(j - 1)){
j++;
}
if(j == typed.length() || typed.charAt(j) != c)
return false;
}
}
j++;
}
return true;
}
}
这么看起来其实我代码的问题也没那么大。。。确实需要各种乱七八糟的判断。。。 不过最优解看起来还是舒服一些。
P929. Unique Email Addresses (Easy)
email地址，如果包含“.”，就忽略掉，如果包含“+”，后面的全忽略掉。问这个数组中一共有多少个实质上不同的email.
我的思路
hashset, 然后根据字符串拼接成新email。
我的代码
public class E_929_UniqueEmailAddresses {
public int numUniqueEmails(String[] emails) {
HashSet<String> set = new HashSet<>();
for (String email : emails) {
int at = email.indexOf('@');
StringBuilder sb = new StringBuilder();
for (int i = 0; i < at; i++) {
if (email.charAt(i) == '.') {
continue;
}
if (email.charAt(i) == '+') {
break;
}
sb.append(email.charAt(i));
}
sb.append(email.substring(at));
set.add(sb.toString());
}
return set.size();
}
}
90%
最优解
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> unique = new HashSet();
for (String email: emails){
unique.add(standardize(email));
}
return unique.size();
}
private String standardize(String s){
char[] array = s.toCharArray();
int i = 0, j = 0;
boolean domain = false, ignore = false;
while (j < array.length){
switch(array[j]){
case '.':
if (domain) array[i++] = array[j];
break;
case '+':
ignore = true;
break;
case '@':
ignore = false;
domain = true;
array[i++] = array[j];
break;
default:
if (!ignore) array[i++] = array[j];
}
j++;
}
return new String(array, 0, i);
}
}
P933. Number of Recent Calls (Easy)
这个题我看了半天没看懂，网上搜也都没人说明白了，只好直接看答案了。
看了答案其实这题非常简单。我在这里稍微解释一下吧。 ping(int t)这个方法是指，回溯3秒，看一共发了多少次ping请求。这3000毫秒是双闭区间，也就是说，[t-3000, t], 当前时间点要算进去，恰好3000毫秒前的也要算进去。
以上仅是翻译了一下题目，这么看恐怕谁都不明白说的是啥。下面我再详细解释一下。我们现在需要设计一个类，ping是唯一一个方法。ping(int t)这个方法的t，是指当前的时间点，比如你调用ping(5000),意思就是在5000这个时间点，发了一个ping请求。那么如果调用ping(5001)，就是在5001这个时间点又发了一次ping请求。就把这些ping的时间点，看作数轴上的点，5000的位置和5001的位置分别有一个点。那么ping(5001)应该返回什么呢？应该从5001这个点，往前数3000毫秒，也就是2001这个点，在[2001,5001]这个闭区间内，有多少个点呢？结果当然是2，原因是我们刚刚在5000的时间点ping过一次，在5001这个时间点又ping了一次。
关于题目给的example更是莫名其妙。
Input: inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]
Output: [null,1,2,3,3]
我看了半天才明白。这两个inputs数组，你要放在一起，一一对应来看。首先是RecentCounter和[]。这是说新建了一个RecentCounter对象，然后什么也没干。第二个是”ping”和[1]，这是说调用了一次ping方法，传入的参数为1。依次类推，后面几个ping就是调用了几次ping方法。每次调用应该返回的结果，就是output对应的位置上那个值。千万不要把这些真的理解为数组。
我实在是不明白出题这人给example时想的是啥。。。纯误导。
答案：
class RecentCounter {
Queue<Integer> q;
public RecentCounter() {
q = new LinkedList();
}
public int ping(int t) {
q.add(t);
while (q.peek() < t - 3000)
q.poll();
return q.size();
}
}