建网站需要编程吗,同城购物网站建设,网站视频如何保存,开个网站建设公司需要什么软件题目1#xff1a;
指路#xff1a;
. - 力扣#xff08;LeetCode#xff09;238 除自身以外数组的乘积
思路与分析#xff1a;
除去自身元素求其他元素的乘积#xff0c;或许第一反应会是数组元素积乘再除以遍历到的元素#xff0c;定义一个结果数组再对应放结果值
指路
. - 力扣LeetCode238 除自身以外数组的乘积
思路与分析
除去自身元素求其他元素的乘积或许第一反应会是数组元素积乘再除以遍历到的元素定义一个结果数组再对应放结果值但是这里会有元素值“0”会有“division by zero”的错误提示而且题目描述里也明确给定了“without ...division...”。那么不妨换一种思路将遍历到的元素作为界限划分出左范围和右范围。定义两个数组分别盛放左右范围的累乘元素最后定义一个结果数组使下标与左右范围内的结果对应即可。
代码
class Solution {
public:vectorint productExceptSelf(vectorint nums) {int n nums.size();vectorint L(n, 0); // 左范围vectorint 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]; // 右范围累乘}vectorint ans(n, 0); // 定义结果集for (int i 0; i n; i) {ans[i] L[i] * R[i]; // 左右范围元素累乘}return ans;}
};
题目2
指路
. - 力扣LeetCode134 加油站
思路与分析
本题我们尝试用贪心的方法求解。首先排除结果一定的情况(一定到不了和一定到得了)。首先我们采取顺序遍历的方式很显然当油箱的总量小于花费的总量时一定到不了目的地反之当油箱内的油量大于等于将要消耗的油量则可以完成任务。接下来看不一定的情况。我们不知道会在哪一个节点上就决定了不会到达终点那么我们采取倒序遍历的方式当剩余的油量始终为正时证明从该节点出发是正确的选择。
代码
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint 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;}
};
