诡异的数学,数字问题 - leetcode
2024-08-29 11:45:24
134. Gas Station
那么这题包含两个问题:
1. 能否在环上绕一圈?
2. 如果能,这个起点在哪里?
第一个问题,很简单,我对diff数组做个加和就好了,leftGas = ∑diff[i], 如果最后leftGas是正值,那么肯定存在这么一个起始点。如果是负值,那说明,油的损耗大于油的供给,不可能有解。得到第一个问题的答案只需要O(n)。
对于第二个问题,起点在哪里?
假设,我们从环上取一个区间[i, j], j>i, 然后对于这个区间的diff加和,定义
sum[i,j] = ∑diff[k] where i<=k<j
如果sum[i,j]小于0,那么这个起点肯定不会在[i,j]这个区间里,跟第一个问题的原理一样。举个例子,假设i是[0,n]的解,那么我们知道 任意sum[k,i-1] (0<=k<i-1) 肯定是小于0的,否则解就应该是k。同理,sum[i,n]一定是大于0的,否则,解就不应该是i,而是i和n之间的某个点。所以第二题的答案,其实就是在0到n之间,找到第一个连续子序列(这个子序列的结尾必然是n)大于0的。
至此,两个问题都可以在一个循环中解决。
166. Fraction to Recurring Decimal
There are some remaining problems to solve to achieve a bug-free solution.
- Pay attention to the sign of the result;
- Handle cases that may cause overflow like
numerator = -2147483648, denominator = -1
appropriately by usinglong long
; - Handle all the cases of (1) no fractional part; (2) fractional part does not recur; and (3) fractional part recurs respectively.
整数,小数,循环小数。用map<long, long> map[remain] = result.size()来记录recurring的开始部分 加左括号。
最新文章
- Nginx配置(全)
- 面向对象Part4
- sysbench压力测试工具简介和使用(二)
- js 中escape,encodeURI,encodeURIComponent的区别
- pb数据窗口设置操作
- Flo&#39;s Restaurant[HDU1103]
- ChinaUnix上的帮助手册还不错!
- 根据不同的浏览器对不同元素进行css调整
- 新手指南:详解Linux Top 命令
- javascript中window.event事件用法详解
- MySQL - 启停服务
- ASP.NET5配置
- Lua 学习笔记(二)
- GDOI 2016 &; APIO 2016 游记
- 权限认证 cookie VS token
- Oracle Database 10g安装
- 解决ubuntu下,QQ重启后出现个人文件夹已被占用的问题
- back
- ubuntu14.04-64位机配置android开发环境,ADT,sdk,eclipsea
- Matlab信号处理工具箱函数