Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution 2 Approaches: Two Pointers and Recursion of Problem 344. Reverse String .

Here shows 2 Approaches to slove this problem, Recursion and Two Pointers.

Two Pointers

Most of us may think about two pointers solution.

We need \(\dfrac {N}{2}\) times swap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void reverseString(char[] s) {
    if (s == null || s.length <= 1) {
        return;
    }
    
    int left = 0;
    int right = s.length - 1;
    while (left < right) {
        char ch = s[left];
        s[left] = s[right];
        s[right] = ch;
        left++;
        right--;
    }
}

or use For Loop:

1
2
3
4
5
6
7
8
9
10
11
12
13
// Two Pointers Opt O(n) O(1)
public static void reverseString_tp_opt(char[] s) {
    if (s == null || s.length <= 1) {
        return;
    }

    int n = s.length;
    for (int left = 0, right = n - 1; left < right; ++left, --right) {
        char tmp = s[left];
        s[left] = s[right];
        s[right] = tmp;
    }
}

Analysis

  • Time Complexity: \(O(n)\)
  • Space Complexity: \(O(1)\)
阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

By Long Luo

这篇文章是 Leetcode 1385. 两个数组间的距离值 的 力扣社区题解 。

方法一：模拟

对于 \(arr1\) 数组中的每一个元素 \(x\)，枚举数组 \(arr2\) 中的每一个元素 \(y\)，检查是否对于每一个 \(y\) 都有 \(|x - y| > d\)，如果是，就将答案增加 \(1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// BF time: O(m * n) space: O(1)
public static int findTheDistanceValue_bf(int[] arr1, int[] arr2, int d) {
	int ans = 0;
	for (int x : arr1) {
		boolean flag = true;
		for (int y : arr2) {
			if (Math.abs(x - y) <= d) {
				flag = false;
			}
		}

		ans += flag ? 1 : 0;
	}

	return ans;
}

复杂度分析

  • 时间复杂度：\(O(mn)\)，其中 \(arr1\) 中元素个数为 \(m\)，\(arr2\) 中元素个数为 \(n\)。
  • 空间复杂度：\(O(1)\)。

方法二： 二分搜索

在方法一中，要知道是否每一个 \(y\) 是不是满足 \(|x - y| > d\)，我们枚举了所有 \(y\)。

实际上因为 \(d >= 0\)，假如arr2存在某个 \(y\) 满足 \(x - d \le y \le x + d\)，那么arr1中的数 \(x\) 就不满足要求。

先对arr2进行排序，之后枚举arr1每个元素 \(x\)，利用二分搜索来判断 \(x\) 是否满足要求。

阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 5.7k 阅读时长 ≈ 5 分钟

By Long Luo

This article is the solution 6 Approaches: Brute Force, Row Search, Column Search, One Binary Search, 2D Coordinate Axis of Problem 74. Search a 2D Matrix.

Here are 6 approaches to solve this problem: Brute Force, Binary Search(Row), Binary Search(Column), One Binary Search and \(2D\) Coordinate Axis.

BF(2 Loops)

It’s easy to use \(2\) Loops to traverse the entire matrix to find the target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// BF
public static boolean searchMatrix_bf(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }

    return false;
}

Notice that the first integer of each row is greater than the last integer of the previous row.

We can optimize the code before.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// BF Opt
public static boolean searchMatrix_bf_opt(int[][] matrix, int target) {
    int row = matrix.length;
    int col = matrix[0].length;

    if (matrix[0][0] > target || matrix[row - 1][col - 1] < target) {
        return false;
    }

    for (int i = 0; i < row; i++) {
        if (target >= matrix[i][0] && target <= matrix[i][col - 1]) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(m \times n)\)
  • Space Complexity: \(O(1)\)

We can scanning the rows of the matrix, If the \(\textit{target}\) is larger than the last element of this row, the target must not be in this row, but only in the lower row of the matrix.

If we find the row which the target may appears, search this row.

阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 5.5k 阅读时长 ≈ 5 分钟

By Long Luo

这篇文章是 287. 寻找重复数 的题解。

目前这道题，经过自己摸索和参考 官方题解: 寻找重复数 ，目前发现了9种方法。

这些方法可以分为以下几类：

  • 需要额外空间，需要修改原始数组 \(O(\log n)\) space
    • 排序 - \(O(n \log n)\) time
  • 需要额外空间，不修改原始数组 \(O(n)\) space
    • 计数法 - \(O(n)\) time
    • Set - \(O(n)\) time
  • 不需要额外空间，需要修改原始数组 \(O(1)\) space
    • 标记法 - \(O(n)\) time
    • 索引排序 - \(O(n)\) time
  • 不需要额外空间，不修改原始数组 \(O(1)\) space
    • 暴力 - \(O(n^2)\) time
    • 二分搜索 - \(O(n \log n)\) time
    • 位运算 - O(n n) time
    • 双指针 - \(O(n)\) time

因为题目要求：

  1. 必须不修改数组 \(\textit{nums}\)；
  2. 只用常量级 \(O(1)\) 的额外空间。

因此我们先从需要修改数组的方案开始，下面我们就来一一分析：

需要额外空间，需要修改原始数组

方法一：排序

先对数组进行排序，然后遍历数组，如果出现重复数字既是答案。

1
2
3
4
5
6
7
8
9
10
11
12
// Sort
public static int findDuplicate_sort(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    for (int i = 1; i < len; i++) {
        if (nums[i] == nums[i - 1]) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

  • 时间复杂度：\(O(n \log n + n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度，\(O(\log n)\) 排序复杂度，总时间复杂度为 \(O(n \log n + n)\)。
  • 空间复杂度：\(O(\log n)\)，排序需要使用 \(O(\log n)\) 空间。

需要额外空间，不修改原始数组

方法二：计数法

因为数组元素值的范围是 \([1, n]\) 之间，那么可以使用一个数组来记录数字出现次数，次数大于 \(1\) 即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
// Count
public static int findDuplicate_count(int[] nums) {
    int len = nums.length;
    int[] cnt = new int[len + 1];
    for (int i = 0; i < len; i++) {
        cnt[nums[i]]++;
        if (cnt[nums[i]] > 1) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

  • 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
  • 空间复杂度：\(O(n)\)，需要新建一个长度为 \(n\) 的数组。

方法三：HashSet

同方法二，这里使用HashSet来记录数组元素。

1
2
3
4
5
6
7
8
9
10
11
12
// Set
public static int findDuplicate_set(int[] nums) {
    Set<Integer> set = new HashSet<>();
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (!set.add(nums[i])) {
            return nums[i];
        }
    }

    return len;
}

复杂度分析

  • 时间复杂度：\(O(n)\)，其中 \(n\) 为 \(\textit{nums}\) 数组的长度。
  • 空间复杂度：\(O(n)\)。
阅读全文 »

发表于 更新于 分类于 阅读次数： Waline： 阅读次数： 本文字数： 2.7k 阅读时长 ≈ 2 分钟

By Long Luo

This article is the solution of Problem 81. Search in Rotated Sorted Array II .

Brute Force

The Brute Force solution is so easy.

Problem 33. Search in Rotated Sorted Array.

1
2
3
4
5
6
7
8
9
10
public static int search_bf(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target) {
            return i;
        }
    }

    return -1;
}

Problem 81. Search in Rotated Sorted Array II:

1
2
3
4
5
6
7
8
9
10
public static boolean search_bf(int[] nums, int target) {
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        if (nums[i] == target) {
            return true;
        }
    }

    return false;
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(1)\).

Binary Search

Step-by-step Binary Search Algorithm:

We basically ignore half of the elements just after one comparison.

  1. Compare target with the middle element;
  2. If target matches with the middle element, we return the mid index;
  3. Else If target is greater than the mid element, then target can only lie in the right half subarray after the mid element. So we recursive for the right half;
  4. Else (target is smaller) recursive for the left half.

The Key of Binary Search is Narrow the Search Interval, aka reducing the scale of the problem.

Every round exclusive the interval where the target element must not exist, so the scale of the problem is gradually reduced.

Problem 33. Search in Rotated Sorted Array.

阅读全文 »
0%