LeetCode面试题Day6|LeetCode238 除自身以外数组的乘积、LeetCode134 加油站

题目1：

指路：

. - 力扣（LeetCode）238 除自身以外数组的乘积

思路与分析：

除去自身元素求其他元素的乘积，或许第一反应会是数组元素积乘再除以遍历到的元素，定义一个结果数组再对应放结果值，但是这里会有元素值“0”，会有“division by zero”的错误提示，而且题目描述里也明确给定了“without ...division...”。那么不妨换一种思路，将遍历到的元素作为界限划分出左范围和右范围。定义两个数组分别盛放左右范围的累乘元素，最后定义一个结果数组使下标与左右范围内的结果对应即可。

代码：

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> L(n, 0);  // 左范围vector<int> R(n, 0);  // 右范围L[0] = 1; R[n - 1] = 1;  // 初始化for (int i = 1; i < n; i++) {L[i] = nums[i - 1] * L[i - 1];  // 左范围累乘}for (int i = n - 2; i >= 0; i--) {R[i] = nums[i + 1] * R[i + 1];  // 右范围累乘}vector<int> ans(n, 0);  // 定义结果集for (int i = 0; i < n; i++) {ans[i] = L[i] * R[i];  // 左右范围元素累乘}return ans;}
};

题目2：

指路：

. - 力扣（LeetCode）134 加油站

思路与分析：

本题我们尝试用贪心的方法求解。首先，排除结果一定的情况(一定到不了和一定到得了)。首先我们采取顺序遍历的方式，很显然当油箱的总量小于花费的总量时一定到不了目的地，反之，当油箱内的油量大于等于将要消耗的油量则可以完成任务。接下来看不一定的情况。我们不知道会在哪一个节点上就决定了不会到达终点，那么我们采取倒序遍历的方式，当剩余的油量始终为正时证明从该节点出发是正确的选择。

代码：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum = 0;int min = INT_MAX;  // 从起点出发油箱里的最小值int n = gas.size();for (int i = 0; i < n; i++) {int rest = gas[i] - cost[i];curSum += rest;if (curSum < min) {min = curSum;}}// gas总和<cost总和，一定跑不完全程if (curSum < 0) return -1;// 正向顺序遍历，油量差为正，足以跑完全程if (min >= 0) return 0;// 倒序遍历求使油量为正的节点for (int i = n - 1; i >= 0; i--) {int rest = gas[i] - cost[i];min += rest;if (min >= 0) {return i;}}return -1;}
};