博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
诡异的数学,数字问题 - leetcode
阅读量:4839 次
发布时间:2019-06-11

本文共 4299 字,大约阅读时间需要 14 分钟。

134.

那么这题包含两个问题:

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.

There are some remaining problems to solve to achieve a bug-free solution.

  1. Pay attention to the sign of the result;
  2. Handle cases that may cause overflow like numerator = -2147483648, denominator = -1 appropriately by using long long;
  3. 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的开始部分 加左括号。

233.

这道题让我们比给定数小的所有数中1出现的个数,之前有道类似的题,那道题是求转为二进数后1的个数,我开始以为这道题也是要用那题的方法,其实不是的,这题实际上相当于一道找规律的题。那么为了找出规律,我们就先来列举下所有含1的数字,并每10个统计下个数,如下所示:

1的个数          含1的数字                                                                        数字范围

1                   1                                                                                     [1, 9]

11                 10  11  12  13  14  15  16  17  18  19                              [10, 19]

1                   21                                                                                   [20, 29]

1                   31                                                                                   [30, 39]

1                   41                                                                                   [40, 49]

1                   51                                                                                   [50, 59]

1                   61                                                                                   [60, 69]

1                   71                                                                                   [70, 79]

1                   81                                                                                   [80, 89]

1                   91                                                                                   [90, 99]

11                 100  101  102  103  104  105  106  107  108  109          [100, 109]

21                 110  111  112  113  114  115  116  117  118  119             [110, 119]

11                 120  121  122  123  124  125  126  127  128  129          [120, 129]

...                  ...                                                                                  ...

 

通过上面的列举我们可以发现,100以内的数字,除了10-19之间有11个‘1’之外,其余都只有1个。如果我们不考虑[10, 19]区间上那多出来的10个‘1’的话,那么我们在对任意一个两位数,十位数上的数字(加1)就代表1出现的个数,这时候我们再把多出的10个加上即可。比如56就有(5+1)+10=16个。如何知道是否要加上多出的10个呢,我们就要看十位上的数字是否大于等于2,是的话就要加上多余的10个'1'。那么我们就可以用(x+8)/10来判断一个数是否大于等于2。对于三位数也是一样,除了[110, 119]之间多出的10个数之外,其余的每10个数的区间都只有11个‘1’,那么还是可以用相同的方法来判断并累加1的个数,参见代码如下:

 

解法一:

class Solution {public:    int countDigitOne(int n) {        int res = 0, a = 1, b = 1;        while (n > 0) {            res += (n + 8) / 10 * a + (n % 10 == 1) * b;            b += n % 10 * a;            a *= 10;            n /= 10;        }        return res;    }};

 

73.

题目中给足了提示,首先告诉我们要3个一组的进行处理,而且题目中限定了输入数字范围为0到231 - 1之间,最高只能到billion位,3个一组也只需处理四组即可,那么我们需要些一个处理三个一组数字的函数,我们需要把1到19的英文单词都列出来,放到一个数组里,还要把20,30,... 到90的英文单词列出来放到另一个数组里,然后我们需要用写技巧,比如一个三位数n,百位数表示为n/100,后两位数一起表示为n%100,十位数表示为n%100/10,个位数表示为n%10,然后我们看后两位数是否小于20,小于的话直接从数组中取出单词,如果大于等于20的话,则分别将十位和个位数字的单词从两个数组中取出来。然后再来处理百位上的数字,还要记得加上Hundred。主函数中调用四次这个帮助函数,然后中间要插入"Thousand", "Million", "Billion"到对应的位置,最后check一下末尾是否有空格,把空格都删掉,返回的时候检查下输入是否为0,是的话要返回'Zero'。参见代码如下:

 

class Solution {public:    string numberToWords(int num) {        string res = convertHundred(num % 1000);        vector
v = {"Thousand", "Million", "Billion"}; for (int i = 0; i < 3; ++i) { num /= 1000; res = num % 1000 ? convertHundred(num % 1000) + " " + v[i] + " " + res : res; } while (res.back() == ' ') res.pop_back(); return res.empty() ? "Zero" : res; } string convertHundred(int num) { vector
v1 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}; vector
v2 = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}; string res; int a = num / 100, b = num % 100, c = num % 10; res = b < 20 ? v1[b] : v2[b / 10] + (c ? " " + v1[c] : ""); if (a > 0) res = v1[a] + " Hundred" + (b ? " " + res : ""); return res; }};

279. 

//逻辑非“!”:逻辑取反, false变true,true变false,在C中,只要不是0就是真

//根据四平方和定理,任意一个正整数均可表示为4个整数的平方和,其实是可以表示为4个以内的平方数之和,那么就是说返回结果只有1,2,3或4其中的一个,首先我们将数字化简一下,由于一个数如果含有因子4,那么我们可以把4都去掉,并不影响结果,比如2和8,3和12等等,返回的结果都相同,读者可自行举更多的栗子。还有一个可以化简的地方就是,如果一个数除以8余7的话,那么肯定是由4个完全平方数组成,这里就不证明了,因为我也不会证明,读者可自行举例验证。那么做完两步后,一个很大的数有可能就会变得很小了,大大减少了运算时间,下面我们就来尝试的将其拆为两个平方数之和,如果拆成功了那么就会返回1或2,因为其中一个平方数可能为0. (注:由于输入的n是正整数,所以不存在两个平方数均为0的情况)。注意下面的!!a + !!b这个表达式,可能很多人不太理解这个的意思,其实很简单,感叹号!表示逻辑取反,那么一个正整数逻辑取反为0,再取反为1,所以用两个感叹号!!的作用就是看a和b是否为正整数,都为正整数的话返回2,只有一个是正整数的话返回1
int numSquares(int n) {
while(n % 4 == 0) n /= 4;
if(n % 8 == 7) return 4;
for(int a = 0; a * a <= n; ++a){
int b = sqrt(n - a * a);
if(a * a + b * b == n){
return !!a + !!b;
}
}
return 3;
}

2

转载于:https://www.cnblogs.com/93scarlett/p/6201854.html

你可能感兴趣的文章
终端命令对字符串进行sha1、md5、base64、urlencode/urldecode
查看>>
Rxjava+Retrofit2+Okhttp3多文件上传(服务器端代码+客户端代码)
查看>>
Spring系列之bean的使用
查看>>
Mac下lombok无法安装到eclipse mars
查看>>
Mac下为什么有的文件名后带一个* 星号?
查看>>
Hololens入门之语音识别(语音命令)
查看>>
python_day09 多进程 多线程 协程 paramiko模块
查看>>
学习WPF之 Binding
查看>>
Windows7系统下Oracle数据库安装的oracle net configuration assistant失败问题
查看>>
umeditor 踩坑
查看>>
luogu P1854 花店橱窗布置
查看>>
6-6 小球下落 uva679
查看>>
Victor and World 状压dp
查看>>
vim 常用设置
查看>>
NGUI所见即所得之UIAtlasMaker , UIAtlas (2)
查看>>
Dynamics AX 2012 R2 耗尽用户
查看>>
项目引入非配置的文件,打成war包后测试报错的可能原因
查看>>
ubuntu更改apache2根目录
查看>>
Hibernate配置属性
查看>>
hibernate.properties
查看>>