leetcode 30-Day LeetCoding Challenge Week3

概述

第三周, 题目来自LeetCode30天挑战。题目难度不大，引入了Tree、binary_search、dp概念，尚不涉及各概念的组合运用。

题目地址

思路分析

Product of Array Except Self

给定一个数组, 计算除了当前元素外的其他元素乘积

思路1. 朴素的想法, 对数组元素求和, 依次除以数组的当前元素。注意该方法不可以有0元素。（题目中禁止该方法）
该方法时间复杂度为O(N)

思路2. 考虑第i个元素, 其目标值为 nums[0...i-1] * nums[i+1...n-1], 其中最左侧元素与最右侧元素分别为nums[i+1...n-1]以及nums[0...n-2]。因此，我们可以发现，每一个元素，是由左、右两部分组成，并且相互独立，因此可以通过两次O(N)的遍历，分别计算。e.g, 一个例子left_product=1, left_product = left_product * nums[i-1];
该方式时间复杂度为O(N) + O(N)

总结.

1) 该题，可以视为2次的迭代题目
2）图示化处理过程，会更清晰化自己的思路

Valid Parenthesis String

给定一个字符序列, 判定其是否合法，规则如下：

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Input: "()"
Output: True

Input: "(*))"
Output: True

思路1. 在不考虑*的情况下, 单纯可以用栈来处理此问题（即遇到(压入栈，遇到)弹出，栈为空或无法弹出则判定为非法。那么考虑的引入带来了消除多余/缺少的( or )的能力。那么我们可以考虑，当我们正向遍历输入的字符串时, 拆分(与`, 并且仅记录数组下标, 数组下标的用意为确认与(`的序，即进行代替)的操作时，当且仅当*在(之后，方可进行。
该方法时间复杂度O(N)

总结.

1) 注意序这个概念

Number of Islands

给定二维数组, 1为陆地, 0为海洋，所有相互链接的1（上下左右）视为岛屿。问给定的二纬数组中，有多少岛屿？

思路1. 朴素的做法, 以所有为1的点且没有被访问过作为起点，进行DFS遍历，每有一个这样的起点，意味着有一个岛屿。
该算法复杂度为O(2^N), 实际场景下, 因为有减枝, 复杂度会有所降低。

总结.

1) 很朴素的DFS解法，以及全局标识位的使用。

Minimum Path Sum

给定m x n的矩阵，矩阵中的每一个点代表价值，限定操作向右/向下，寻找最小价值的路径

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路1. 此题会用到DP，本质上来说, 对于任意一个点，是通过前面的N次选择到达。那么其状态转移方程为dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j], 即为此点的组小值, 最后的结果为dp[i][j]。注意dp[i][j]的含义为，抵达matrix[i][j]时的路径最小值
该方法时间复杂度O(N^2)

思路2. 从起点开始进行BFS搜索, 需要进行global_min的比较, 同样获得正确解
该方法时间复杂度O(2^N)

总结.

1) 本质上为一搜索问题, 其优化点为, 优化中间状态, 避免重复计算.
2) 需要注意的是, DP自身也是同样的思路, dp中的状态转移，(i, i+1)或(i-1, i)均是自顶or自底的一种状态保留

Search in Rotated Sorted Array

给定一个数组, 数组已升序排列, 不过因反转被切分成两部分, 给定target_num，在数组中检索出对应的下标

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

思路1. 首先, 一但我们发现有序这个信息, 我们就可以做一些LogN的操作。题目中的key-point在于，我们如果能找将数组分成两个有序序列的分界点。当nums[left] > nums[right], 意味着存在mid, left < mid < right, 使得nums[left...mid], nums[mid+1...right]为单调序列。这一步可以通过二分进行。最后在两个有序的序列中进行binary_search即可。
该方法时间复杂度O(logN) + O(logN) + O(logN)

总结.

1) 核心考察对二分法的理解.