// 1784. Check if Binary String Has at Most One Segment of Ones
class Solution {
public boolean checkOnesSegment(String s) {
return !s.contains("01");
}
}
学习笔记： 由于开头没有前导零，那么开头必须是1，或者只有0。 要有第二段1111的，必须有中间夹的0和后面跟着的1，也就是说要包含01。 所以这道题就是检查是否包含01子串就行。
// 0777. Swap Adjacent in LR String
class Solution {
public boolean canTransform(String start, String end) {
char[] s = start.toCharArray();
char[] e = end.toCharArray();
int len = s.length;
int xs = 0;
for (int i = 0; i < len; ++i) {
if (s[i] == 'X') ++xs;
if (e[i] == 'X') --xs;
}
if (xs != 0) return false;
for (int i = 0, j = 0; i < len; ++i) {
if (s[i] == 'L') {
while (j < len && e[j] != 'L') ++j;
if (j > i) return false;
++j;
}
if (s[i] == 'R') {
while (j < len && e[j] != 'R') ++j;
if (j < i) return false;
++j;
}
}
return true;
}
}
学习笔记： 这道题特别难，L可以往左边走，R可以往右边走，但互相不可以跨越。 那就是说X的总数一样，L总数一样，R总数一样。 然后从左到右的L和R顺序都一样，并且这样还不够！我就被坑在这里面了。 因为LX是变不到XL的，L没办法往右。 所以要用双指针跑，如果L的话，i要小于等于j，如果是R的话，i要大于等于j。
// 1694. Reformat Phone Number
class Solution {
public String reformatNumber(String number) {
StringBuilder sb = new StringBuilder();
StringBuilder ans = new StringBuilder();
for (int i = 0; i < number.length(); ++i) {
if (number.charAt(i) >= '0' && number.charAt(i) <= '9') {
sb.append(number.charAt(i));
}
}
int i = 0;
while (i < sb.length() - 4) {
ans.append(sb.charAt(i));
++i;
ans.append(sb.charAt(i));
++i;
ans.append(sb.charAt(i));
++i;
ans.append('-');
}
if (i == sb.length() - 4) {
ans.append(sb.charAt(i));
++i;
ans.append(sb.charAt(i));
++i;
ans.append('-').append(sb.charAt(i));
++i;
ans.append(sb.charAt(i));
} else {
while (i < sb.length()) {
ans.append(sb.charAt(i));
++i;
}
}
return ans.toString();
}
}
学习笔记： 这道题就是将数字提取出来，然后3个一组。 剩下不到4个或刚好4个再进行处理。
// 面试题 01.08. Zero Matrix LCCI
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean column0Has0 = false;
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == 0) {
column0Has0 = true;
}
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (column0Has0) {
for (int i = 0; i < m; ++i) {
matrix[i][0] = 0;
}
}
}
}
学习笔记： 今天虽然是一道比较简单的题目，动态清零 先统计行列是否有0，再操作，但是要做到只使用一个变量属实不容易，所以这也是一道很好的面试题目。
// 面试题 01.09. String Rotation LCCI
class Solution {
public boolean isFlipedString(String s1, String s2) {
return s1.length() == s2.length() && (s1 + s1).contains(s2);
}
}
学习笔记： 这是一道简单题，但是特别巧妙，拼接了两份后再寻找，这样寻找起来就很快了。
// 面试题 17.09. Get Kth Magic Number LCCI
class Solution {
public int getKthMagicNumber(int k) {
int[] magicNumbers = new int[k + 1];
magicNumbers[1] = 1;
int pointer3 = 1;
int pointer5 = 1;
int pointer7 = 1;
for (int i = 2; i <= k; ++i) {
int min = Math.min(Math.min(magicNumbers[pointer3] * 3, magicNumbers[pointer5] * 5), magicNumbers[pointer7] * 7);
if (min == magicNumbers[pointer3] * 3) ++pointer3;
if (min == magicNumbers[pointer5] * 5) ++pointer5;
if (min == magicNumbers[pointer7] * 7) ++pointer7;
magicNumbers[i] = min;
}
return magicNumbers[k];
}
}
学习笔记： 这是一道简单的题目，之前有教过学生。 就是比较三个数里面最小的，添加到数组里面。 找到第k个数字。
// 面试题 01.02. Check Permutation LCCI
class Solution {
public boolean CheckPermutation(String s1, String s2) {
if (s1.length() != s2.length()) return false;
int len = s1.length();
int[] count = new int[123];
for (int i = 0; i < len; ++i) {
++count[s1.charAt(i)];
--count[s2.charAt(i)];
}
for (int i = 97; i < 123; ++i) {
if (count[i] != 0) return false;
}
return true;
}
}
学习笔记： 连续困难题之后，今天终于轮到了一道简单题。 这是一道计数的问题，很简单就完成了。0ms击败100%。
// 面试题 17.19. Missing Two LCCI
class Solution {
public int[] missingTwo(int[] nums) {
int xorsum = 0;
int n = nums.length + 2;
for (int num : nums) {
xorsum ^= num;
}
for (int i = 1; i <= n; i++) {
xorsum ^= i;
}
int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & -xorsum);
int type1 = 0, type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
for (int i = 1; i <= n; i++) {
if ((i & lsb) != 0) {
type1 ^= i;
} else {
type2 ^= i;
}
}
return new int[]{type1, type2};
}
}学习笔记： 今天这题也太难了吧，又是困难题。 找出1到n之间两个缺少的数，并且时间复杂度是n，空间复杂度是1。 看了官方的解法，啃了特别久终于懂了。 用到了大量位运算。 首先异或，异或会抵消。 所有xorsum先加全部数字，再加一遍1到n。相当于出现的数字搞了两次都抵消了。 剩下的xorsum就变成了a和b的异或了。 那么知道了有啥用呢？ a和b的异或，就说明a和b哪些位不同，本来a和b就肯定不同，所以肯定有1存在。 但可能有很多1，也有可能只有一个1。但我们要找出一位不同的来，也就是随便找一个1。 怎么找呢，就用x & -x来做，一个数和自己相反数按位与，结果就是只有一个1，那便是最右边最末尾的那个1。 找到了某一位是不同的之后，就把所有数字分成两类，一类是这一位是0的，一类是这一位是1的。 遍历一遍所有数字，再遍历一遍1到n，这样异或一遍之后。剩下的一组是a，另一组是b，答案就出来了。 这道题属实是太牛逼了，简直是面试神体，应该不提出苛刻的要求，让面试者来做，然后做完后层层递进提问。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// 0788. Rotated Digits
class Solution {
int[] check = {0, 0, 1, -1, -1, 1, 1, -1, 0, 1};
int[][][] memo = new int[5][2][2];
List<Integer> digits = new ArrayList<Integer>();
public int rotatedDigits(int n) {
while (n != 0) {
digits.add(n % 10);
n /= 10;
}
Collections.reverse(digits);
for (int i = 0; i < 5; ++i) {
for (int j = 0; j < 2; ++j) {
for (int k = 0; k < 2; ++k) {
memo[i][j][k] = -1;
}
}
}
return dfs(0, 1, 0);
}
public int dfs(int pos, int bound, int diff) {
if (pos == digits.size()) return diff;
if (memo[pos][bound][diff] != -1) return memo[pos][bound][diff];
int ret = 0;
if (bound == 0) {
for (int i = 0; i <= 9; ++i) {
if (check[i] != -1) {
if (diff == 1 || check[i] == 1) {
ret += dfs(pos + 1, 0, 1);
} else {
ret += dfs(pos + 1, 0, 0);
}
}
}
} else {
for (int i = 0; i <= digits.get(pos); ++i) {
if (check[i] != -1) {
if (digits.get(pos) == i) {
if (diff == 1 || check[i] == 1) {
ret += dfs(pos + 1, 1, 1);
} else {
ret += dfs(pos + 1, 1, 0);
}
} else {
if (diff == 1 || check[i] == 1) {
ret += dfs(pos + 1, 0, 1);
} else {
ret += dfs(pos + 1, 0, 0);
}
}
}
}
}
memo[pos][bound][diff] = ret;
return ret;
}
}
学习笔记： 这是一道困难题，用的是记忆化搜索。 memo是记忆结果的。 pos是目前进行到了第几位， bound是是否贴近边缘的意思比如123，那现在前两位是12那就贴近边缘了，如果是11就没贴， diff是是否出现了不一样的比如2569就会导致diff变成1。 分支也很多，写动态规划也是三维的，记忆化搜索的话也不好搞，看来答案后也思考了很久很久。 但是网上有看到状态转移总结成一条各种运算夹杂在一起的方程式，太猛了吧，不过代码可读性太低了。
// 1652. Defuse the Bomb
class Solution {
public int[] decrypt(int[] code, int k) {
int len = code.length;
int[] ans = new int[len];
if (k == 0) return ans;
if (k > 0) {
for (int i = 0; i < len; ++i) {
for (int j = 1; j <= k; ++j) {
ans[i] += code[(i + j) % len];
}
}
} else {
k *= -1;
for (int i = 0; i < len; ++i) {
for (int j = 1; j <= k; ++j) {
ans[i] += code[(i - j + len) % len];
}
}
}
return ans;
}
}
学习笔记： 这是一道简单的字符串题，慵懒的周末加班日，我在办公室用愚蠢的方法写了这道题。 实际上这道题应该使用哈希表和滑动窗口，但是我懒得再写了，就这样吧。