leetcode算法题刷题笔记
合并两个有序数组
思路1：数组双指针（拉链法）
这道题很像前文 链表的双指针技巧汇总 中讲过的 21. 合并两个有序链表，这里让你合并两个有序数组。
对于单链表来说，我们直接用双指针从头开始合并即可，但对于数组来说会出问题。因为题目让我直接把结果存到 nums1 中，而 nums1 的开头有元素，如果我们无脑复制单链表的逻辑，会覆盖掉 nums1 的原始元素，导致错误。
但 nums1 后面是空的呀，所以这道题需要我们稍微变通一下：将双指针初始化在数组的尾部，然后从后向前进行合并，这样即便覆盖了 nums1 中的元素，这些元素也必然早就被用过了，不会影响答案的正确性。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 两个指针分别初始化在两个数组的最后一个元素（类似拉链两端的锯齿）
int i = m - 1, j = n - 1;
// 生成排序的结果（类似拉链的拉锁）
int p = nums1.length - 1;
// 从后向前生成结果数组，类似合并两个有序链表的逻辑
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[p] = nums1[i];
i--;
} else {
nums1[p] = nums2[j];
j--;
}
p--;
}
// 可能其中一个数组的指针走到尽头了，而另一个还没走完
// 因为我们本身就是在往 nums1 中放元素，所以只需考虑 nums2 是否剩元素即可
while (j >= 0) {
nums1[p] = nums2[j];
j--;
p--;
}
}
}
完整实现代码：
Solution s = new Solution();
PrintSolution p = new PrintSolution();
int[] nums1 = new int[]{1,2,3,0,0,0};
int[] nums2 = new int[]{2, 5, 6};
int m = 3;
int n = 3;
s.Merge(nums1, m, nums2, n);
p.PrintArray(nums1);
public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1;
int p = nums1.Length - 1;
while(i >= 0 && j >= 0){
if(nums1[i] > nums2[j]){
nums1[p] = nums1[i];
i--;
}
else
{
nums1[p] = nums2[j];
j--;
}
p--;
}
while(j >= 0){
nums1[p] = nums2[j];
j--;
p--;
}
}
}
public class PrintSolution
{
public void PrintArray(int[] arr)
{
foreach (var VARIABLE in arr)
{
System.Console.WriteLine(VARIABLE);
}
}
}
思路2：直接合并后排序
最直观的方法是先将数组nums2放进数组 nums1的尾部，然后直接对整个数组进行排序。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
}
}
C#完整代码：
Solution s = new Solution();
PrintSolution p = new PrintSolution();
int[] nums1 = new int[]{1,2,3,0,0,0};
int[] nums2 = new int[]{2, 5, 6};
int m = 3;
int n = 3;
s.Merge(nums1, m, nums2, n);
p.PrintArray(nums1);
public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
Array.Sort(nums1);
}
}
public class PrintSolution
{
public void PrintArray(int[] arr)
{
foreach (var VARIABLE in arr)
{
System.Console.WriteLine(VARIABLE);
}
}
}
思路3：双指针
思路2没有利用数组nums1与 nums2已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示：
- 此思路与思路1相似，但是思路1并未增加单独的数组用来接收，而是直接返回nums1，此思路返回新数组sorted用来接收
我们为两个数组分别设置一个指针 p1与 p2来作为队列的头部指针。代码实现如下：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0, p2 = 0;
int[] sorted = new int[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
}
同构字符串
思路1：数组法
public class Solution {
public bool IsIsomorphic(String s, String t) {
char[] chars = s.toCharArray();
char[] chart = t.toCharArray();
int[] preIndexOfs = new int[256];
int[] preIndexOft = new int[256];
for (int i = 0; i < chars.length; i++) {
if (preIndexOfs[chars[i]] != preIndexOft[chart[i]]) {
return false;
}
preIndexOfs[chars[i]] = i + 1;
preIndexOft[chart[i]] = i + 1;
}
return true;
}
}
C#完整代码：
Solution s = new Solution();
string a = "egg";
string b = "add";
bool c = s.IsIsomorphic(a, b);
System.Console.WriteLine(c);
public class Solution {
public bool IsIsomorphic(String s, String t) {
char[] chars = s.ToCharArray();
char[] chart = t.ToCharArray();
int[] preIndexOfs = new int[256];
int[] preIndexOft = new int[256];
for (int i = 0; i < chars.Length; i++) {
if (preIndexOfs[chars[i]] != preIndexOft[chart[i]]) {
return false;
}
preIndexOfs[chars[i]] = i + 1;
preIndexOft[chart[i]] = i + 1;
}
return true;
}
}
思路2：哈希表
此题是「290. 单词规律」的简化版，需要我们判断 ss 和 tt 每个位置上的字符是否都一一对应，即 ss 的任意一个字符被 tt 中唯一的字符对应，同时 tt 的任意一个字符被 ss 中唯一的字符对应。这也被称为「双射」的关系。
以示例 22 为例，tt 中的字符 aa 和 rr 虽然有唯一的映射 oo，但对于 ss 中的字符 oo 来说其存在两个映射 {a,r}{a,r}，故不满足条件。
因此，我们维护两张哈希表，第一张哈希表 s2t 以 ss 中字符为键，映射至 tt 的字符为值，第二张哈希表 t2s 以 tt 中字符为键，映射至 ss 的字符为值。从左至右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突（即当前下标 index 对应的字符 s[index] 已经存在映射且不为 t[index] 或当前下标 index 对应的字符t[index] 已经存在映射且不为 s[index]）时说明两个字符串无法构成同构，返回false。
如果遍历结束没有出现冲突，则表明两个字符串是同构的，返回 true 即可。
package org.example;
import java.util.*;
public class Main {
public static void main(String[] args) {
System.out.println("Hello world!");
String a = "egg";
String b = "add";
Solution s = new Solution();
boolean result = s.isIsomorphic(a, b);
System.out.println(result);
}
}
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s2t = new HashMap<Character, Character>();
Map<Character, Character> t2s = new HashMap<Character, Character>();
int len = s.length();
for (int i = 0; i < len; ++i) {
char x = s.charAt(i), y = t.charAt(i);
if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
return false;
}
s2t.put(x, y);
t2s.put(y, x);
}
return true;
}
}
两个数组的交集
方法一：哈希表
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums1) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
int[] intersection = new int[nums1.length];
int index = 0;
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
复杂度分析
时间复杂度：O(m+n)O(m+n)，其中 mm 和 nn 分别是两个数组的长度。需要遍历两个数组并对哈希表进行操作，哈希表操作的时间复杂度是 O(1)O(1)，因此总时间复杂度与两个数组的长度和呈线性关系。
空间复杂度：O(\min(m,n))O(min(m,n))，其中 mm 和 nn 分别是两个数组的长度。对较短的数组进行哈希表的操作，哈希表的大小不会超过较短的数组的长度。为返回值创建一个数组 intersection，其长度为较短的数组的长度。
方法二：排序 + 双指针
如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。
首先对两个数组进行排序，然后使用两个指针遍历两个数组。
初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[Math.min(length1, length2)];
int index1 = 0, index2 = 0, index = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
intersection[index] = nums1[index1];
index1++;
index2++;
index++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
结语 如果nums 2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中。那么就无法高效地对 nums2 进行排序，因此推荐使用方法一而不是方法二。在方法一中，nums 2只关系到查询操作，因此每次读取nums2中的一部分数据，并进行处理即可。