iis部署网站 win7,邯郸网站建设网络公司,公司网站怎么建设,广东哪里有网站建设目录 1.跳跃游戏1.题目链接2.算法思路详解3.代码实现 2.加油站1.题目链接2.算法原理详解3.代码实现 3.单调递增的数字1.题目链接2.算法原理详解3.代码实现 4.坏了的计算器1.代码实现2.算法原理详解3.代码实现 1.跳跃游戏
1.题目链接
跳跃游戏 2.算法思路详解
贪心#xff1… 目录 1.跳跃游戏1.题目链接2.算法思路详解3.代码实现 2.加油站1.题目链接2.算法原理详解3.代码实现 3.单调递增的数字1.题目链接2.算法原理详解3.代码实现 4.坏了的计算器1.代码实现2.算法原理详解3.代码实现 1.跳跃游戏
1.题目链接
跳跃游戏 2.算法思路详解
贪心类似层序遍历的过程 3.代码实现
bool canJump(vectorint nums)
{int left 0, right 0, maxPos 0, n nums.size();while(left right){if(maxPos n - 1){return true;}for(int i left; i right; i){maxPos max(maxPos, nums[i] i);}left right 1;right maxPos;}return false;
}2.加油站
1.题目链接
加油站 2.算法原理详解
思路一暴力解 — 枚举 — 会超时:P 依次枚举所有的起点从起点开始模拟一遍加油的流程即可 思路二优化暴力解法 — 找规律(贪心) 3.代码实现
// v1.0 暴力解
int canCompleteCircuit(vectorint gas, vectorint cost)
{int n gas.size();for(int i 0; i n; i) // 枚举起点{int rest 0;for(int step 0; step n; step) // 枚举向后走的步数{int index (i step) % n; // 求出走step步之后的下标rest rest gas[index] - cost[index];if(rest 0){break;}}if(rest 0){return i;}}return -1;
}
--------------------------------------------------------------------
// v2.0 贪心
int canCompleteCircuit(vectorint gas, vectorint cost)
{int n gas.size();for(int i 0; i n; i) // 枚举起点{int rest 0, step 0;for(; step n; step) // 枚举向后走的步数{int index (i step) % n; // 求出走step步之后的下标rest rest gas[index] - cost[index];if(rest 0){break;}}if(rest 0){return i;}i i step; // 优化}return -1;
}3.单调递增的数字
1.题目链接
单调递增的数字 2.算法原理详解
思路一暴力枚举 从大到小的顺序枚举[n, 0]区间内的数字判断数字是否是“单调递增的” 思路二贪心 如果高位单调递增就不去修改 因为高位如果修改了那么该数大小会小非常多影响较大 从左往右找到第一个递减的位置 从这个位置向前推推到相同区域的最左端使其减1后面的数全部修改成9 3.代码实现
int monotoneIncreasingDigits(int n)
{string str to_string(n); // 把数字转化为字符串以便逐位操作int i 0, m str.size();// 找到第一个递减的位置while(i 1 m str[i] str[i 1]){i;}// 特判if(i m - 1){return n;}// 回推while(i - 1 0 str[i] str[i - 1]){i--;}// 操作str[i]--;for(int j i 1; j m; j){str[j] 9;}return stoi(str);
}4.坏了的计算器
1.代码实现
坏了的计算器 2.算法原理详解 思路一正向推导可用DFS解决 思路二贪心 -- 正难则反 从目标出发执行/2或1操作 3.代码实现
int brokenCalc(int startValue, int target)
{int ret 0;while(target startValue){if(target % 2 0){target / 2;}else{target 1;}ret;}return ret startValue - target;
}
