数组字符串
合并两个有序数组
思路
类似于归并排序，对两个有序数组进行合并即可，但是空间复杂度是O(n+m);
代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] ans = new int[n + m];
int i = 0, j = 0;
int cnt = 0;
while (i < m && j < n) {
if (nums1[i] < nums2[j]) {
ans[cnt++] = nums1[i++];
} else {
ans[cnt++] = nums2[j++];
}
}
while(i < m) ans[cnt++] = nums1[i++];
while(j < n) ans[cnt++] = nums2[j++];
for (int k = 0; k < cnt; ++k) {
nums1[k] = ans[k];
}
}
}
优化：有一点小优化吧，可以从后往前合并装入nums1的后面，这样不会影响nums1的元素，同样也节省了n+m的空间（本题的数据量小，所以看不出）。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int cnt = n + m - 1;
while(i >= 0 && j >= 0) {
if (nums1[i] < nums2[j]) {
nums1[cnt--] = nums2[j--];
} else {
nums1[cnt--] = nums1[i--];
}
}
while(i >= 0) nums1[cnt--] = nums1[i--];
while(j >= 0) nums1[cnt--] = nums2[j--];
}
}
双指针
验证回文串
思路
用头指针和尾指针，每次比较的时候必须满足两个指针指向的是数字或字符，其他的符号都跳过。
代码
class Solution {
public boolean isPalindrome(String s) {
s = s.toLowerCase();
int len = s.length();
int i = 0, j = len - 1;
char[] ch = s.toCharArray();
while(i < j) {
while(i < len && !check(ch[i])) ++i;
while(j >= 0 && !check(ch[j])) --j;//前面两句是过滤非字符或数字
if (i > j) {
break;
}
if (ch[i] >= 'a') {
ch[i] -= 32;
}
if (ch[j] >= 'a') {
ch[j] -= 32;
}// 如果是字符，则统一转为小写
if (ch[i] != ch[j]) {
return false;
}
++i;
--j;
}
return true;
}
private boolean check(char ch) {
if (ch <= 'z' && ch >= 'a') {
return true;
}
if (ch <= 'Z' && ch >= 'z') {
return true;
}
if (ch <= '9' && ch >= '0') {
return true;
}
return false;
}
}
滑动窗口
长度最小的子数组
思路
由滑动窗口思想：设两个指针，尾指针一直走，当满足某个条件时，头指针也跟着走。
条件：当子数组和大于target时，不断缩小窗口，找到最小的窗口。
代码
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int ans = nums.length;
int ind = 0;
int sum = 0;
for (int i = 0; i < nums.length; ++i) {
sum += nums[i];
while (sum >= target) {
sum -= nums[ind];
ans = Math.min(ans, i - ind + 1);
ind++;
}
}
if (ind == 0) { // sum>=target没有执行，不存在子数组
return 0;
}
return ans;
}
}
矩阵
有效的数独
思路
创建三个set数组，分别是对存“行”，“列”，“区域”的数字，如果对应的set中有值，那么就不是有效的。否则就添加
这里最主要的是怎样判断是否为同一个区域。
可以先对9x9的表格通过i/3,j/3划分为9个3x3区域然后每个区域的值都是
(0, 0), (0, 1), (0, 2)
(1, 0), (1, 1)…
再通过将二维数组变为一维数组的计算公式i * row + j。就是9个区域。
代码
class Solution {
public boolean isValidSudoku(char[][] board) {
Set<Character>[] rows = new HashSet[9];
Set<Character>[] cols = new HashSet[9];
Set<Character>[] area = new HashSet[9];
for (int i = 0; i < 9; ++i) {
rows[i] = new HashSet<>();
cols[i] = new HashSet<>();
area[i] = new HashSet<>();
}
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (board[i][j] > '9' || board[i][j] < '0') continue;
if (rows[i].contains(board[i][j])) {
return false;
} else {
rows[i].add(board[i][j]);
}
if (cols[j].contains(board[i][j])) {
return false;
} else {
cols[j].add(board[i][j]);
}
int t= i / 3 * 3 + j / 3;
//System.out.println(i + " " + j + " " + t);
if (area[t].contains(board[i][j])) {
return false;
} else {
area[t].add(board[i][j]);
}
}
}
return true;
}
}
哈希表
赎金信
思路
比较r和m的26个字符个数，如果r的某个字符个数大于m的某个字符个数，则r不能由m的字符组成。
代码
class Solution {
public boolean canConstruct(String r, String m) {
int[] rCnt = new int[26];
int[] mCnt = new int[26];
for (int i = 0; i < r.length(); ++i) {
rCnt[r.charAt(i) - 'a']++;
}
for (int i = 0; i < m.length(); ++i) {
mCnt[m.charAt(i) - 'a']++;
}
for (int i = 0; i < 26; ++i) {
if (rCnt[i] > mCnt[i]) {
return false;
}
}
return true;
}
}
