国外做名片的网站,怎么形容网站做的很好,html做网站在手机上显示,一个网站需要服务器吗1 前言
题目来源于Leetcode。
重点#xff1a;理清逻辑#xff0c;忽略细节#xff0c;模仿高手#xff0c;五毒神掌
2 题目分析
题目很容易理解#xff0c;先分成两个部分
正数负数
先解决正数
最开始想到的是 intchar数组long唯一增加的就是#xff0c;先判断整…1 前言
题目来源于Leetcode。
重点理清逻辑忽略细节模仿高手五毒神掌
2 题目分析
题目很容易理解先分成两个部分
正数负数
先解决正数
最开始想到的是
intchar数组long唯一增加的就是先判断整数是多少位。
之后再判断溢出
然后解决负数 先使用一个bool变量保存符号如果是负数则取绝对值再按正数进行运算之后再加上符号再判断溢出。
整体思维非常容易想到分治思想下面是代码。
3 自己想
int reverse(int x) {// 不管正负数全变正数bool isNegativeNumber false;int xAbsoluteValue 0;if (x 0) {isNegativeNumber true;if (x ! INT_MIN)xAbsoluteValue -x;elsereturn 0;}else {isNegativeNumber false;xAbsoluteValue x;}// 判断整数多少位【动态的】int xTemporary xAbsoluteValue;int count 0;for (int i 0; i sizeof(int)*8; i) { // 【注意】字节数*8if (xTemporary 0) {break;}else {count;}xTemporary / 10;}// 反转long long xNew 0; // 不要用long它在32位下也是4字节xTemporary xAbsoluteValue;for (int i 0; i count; i) {xNew xNew * 10 xTemporary % 10;xTemporary / 10;}// 符号回归if (isNegativeNumber) {xNew -xNew;}// 判断溢出if (xNew INT_MIN || xNew INT_MAX) {return 0;}else{return xNew;}}运行结果还可以就是系统本身不稳定有时候是4ms这不重要重要的是这种做法太啰嗦了我先尝试按照这个思路优化一下。
去掉符号转换这部分没有也一样
注意使用long long而不是long32位下前者8字节后者和int一样4个字节
判断溢出使用一行代码搞定取缔if else使用三元运算符
// 判断整数多少位【动态的】int xTemporary x;int count 0;for (int i 0; i sizeof(int) * 8; i) { // 【注意】字节数*8if (xTemporary 0) {break;}else {count;}xTemporary / 10;}// 反转long long xNew 0; xTemporary x;for (int i 0; i count; i) {xNew xNew * 10 xTemporary % 10;xTemporary / 10;}return (xNew INT_MIN || xNew INT_MAX) ? 0 : xNew;好了这个程序已经优化了很多了还有没有空间继续优化呢
再优化就只能在获取整数位数下手将其直接变成反转的条件使用。
好吧……我做不下去了看大神解法好了。
谈一谈收获
对待算法题重点关注逻辑对于防御性编程等细节可以不用深究先把逻辑在纸面上搞清楚再写代码int、long等数据类型的大小根据系统位数以及编译器决定需要实际测试一下尽量使用sizeof等通用的东西计算位数部分有一点动态规划的意思很有趣。
毫无移位按照我这么写算法题可以凉凉了~~~~接下来我来学习一下大神的解法吧。
4 看大神做法直接模仿学会
4.1 大神一
long long res 0;
while (x) {res res * 10 x % 10;x / 10;
}
return (res INT_MIN || res INT_MAX) ? 0 : res;这个大神与我的思路类似只不过比我的又进一步优化我们学习一下。
这里最重要的一点不需要判断多少位也不需要暂存不用管循环次数循环结束的条件就是x 0。
这也不是本质这题的本质是数学问题。
是1234变成4321的问题是1234提取出每一个数字的问题
来看看我的算法中愚蠢的点。
// 判断整数多少位【动态的】int xTemporary x;int count 0;for (int i 0; i sizeof(int) * 8; i) { // 【注意】字节数*8if (xTemporary 0) {break;}else {count;}xTemporary / 10;}// 反转long long xNew 0; xTemporary x;for (int i 0; i count; i) {xNew xNew * 10 xTemporary % 10;xTemporary / 10;}关注一下两个循环的条件
循环32次确定位数根据位数再反转
事实上我想的是先确定好位数这样就不用每次都循环32次了但是我在确定位数的时候还是循环了32次……蠢到家……
虽然不是每次循环32次但是这种程序结构无疑是垃圾的尽管是双重保险但是没有必要阿我们警惕一下
值得警惕的结构
抛开题目本身我们看一看这个结构
for (int i 0; i sizeof(int) * 8; i) { // 【注意】字节数*8if (xTemporary 0) {break;}else {count;}xTemporary / 10;
}for循环中嵌套一个通过if判断的跳出循环的装置我们来改进一下
while(xTemporary){ xTemporary / 10;count;}嗯这俩功能完全一样但是显然后者更加简洁
现在我们是通过中介count来完成程序那么可以去掉中间商吗
当然可以 既然xTemporary / 10就可以作为终止条件我们直接用就好了没必要再管中间商忽略它
看一下我们刚才优化的本质将x / 10;和while(x) 二者配合作为循环终止条件因此我们进一步优化。
// 判断整数多少位【动态的】int xTemporary x;int count 0;while(xTemporary){ xTemporary / 10;count;}// 反转long long xNew 0; while(xTemporary) {xNew xNew * 10 xTemporary % 10;xTemporary / 10;}这样一来你很容易发现第一个循环完全没有用直接删掉。
int reverse(int x) {long long xNew 0; while(x) {xNew xNew * 10 x % 10;x / 10;}return (xNew INT_MIN || xNew INT_MAX) ? 0 : xNew;
}我们成功将自己的烂程序一步步优化成了大神的程序。
为了程序的通用性我们稍改一下
int reverse(int x) {long long xNew 0; while(x ! 0) {xNew xNew * 10 x % 10;x / 10;}return (xNew INT_MIN || xNew INT_MAX) ? 0 : xNew;
}因为只有C/C使用0和false是一样的但是Java就不允许只能使用布尔值。
4.2 大神二
int reverse(int x) {int d 0;while (x){if (d INT_MAX / 10 || d INT_MIN / 10)return 0;d d * 10 x % 10;x x / 10;}return d;
}我们分析大神的思路我先缓缓下跪了
在后面五毒神掌第二掌会分析。
5 收获
5.1 一个重要结构的优化
for循环内通过if跳出的时候可以优化。
for(int i 0;i sizeof(int)*8;i){if(x){break; }x / 10
}while(x){x / 10
}5.2 去掉“中间商”的方法
对于一些共性的东西不再单独列出中间结果直接得到最终答案。
5.3 算法的本质是数学问题
这个数学表达式其实是这么来的
先分治拆解为数字权重的形式本质是硬件思维再调换数字的权重
至于最终的表达式需要一点点优化过来。
我们需要知道对于int x;
求最低位的数字x % 10降维降低数量级x / 10利用int直接抹掉小数点
第一次的算法(使用伪代码)
while(遍历每一位的数字){number[i] x % 10;x / 10;
}这是很容易想到的那么我们保存了每一位数字怎么保存它的权重真的有必要保存权重吗 显然没有必要我们试一下就知道可以直接一边处理旧数字一边计算新数字。
newX 0;
while(遍历每一位的数字){number[i] x % 10;x / 10;newX newX*10 number[i];
}这已经是最小单元没法解释自己试一下吧。
然后你会发现number[i]是多余的并且遍历的条件就是x 0。
long long newX 0;
while(x ! 0){newX newX*10 x % 10;x / 10;
}至于为什么用long long这叫先假想结果因为结果会溢出所以只能用long long了。
5.4 一些衍生的题目
5.4.1 求整数位数
所有整数均可。
int reverse(int x) {int count 0;while (x){x / 10;count;}return count;
}5.4.2 求整数的每一位
void reverse(int x) {int count 0;int xTemporary x;while (xTemporary){xTemporary / 10;count;}int *everyNumber new int[count];for (int i 0; i count; i) {everyNumber[i] x % 10;x / 10;}for (int i 0; i count; i) {cout everyNumber[i] endl;}
}注意
char与int转换记得差一个0
int i 4;
char a i 0;
cout a endl;6 五毒神掌
五毒神掌是什么
关注代码逻辑和结构层面的细节
目标导向一天一个完全搞定300题
6.1 第一掌
先正确理解题目自己想5分钟想出来就写想不出来就直接看世界大神答案并且理解然后大致理解背下来理解代替记忆如果不理解就先记忆多用用就理解了边抄边背的方式写代码
自己的思路不能只有一种每种都要尝试。
重点关注逻辑画图手算分析
6.1.1 自己思考的过程
题目很简单就是整数反转需要注意
正负数问题反转后溢出问题用long long存储 之后用几个数字试一试研究一下数学公式先写正确再不断优化。
int reverse(int x) {long long xNew 0;while (x ! 0) {xNew xNew * 10 x % 10;x / 10;}return (xNew INT_MIN || xNew INT_MAX) ? 0 : xNew;
}6.1.2 大神的代码
public int reverse(int x)
{int result 0;while (x ! 0){int tail x % 10;int newResult result * 10 tail;if ((newResult - tail) / 10 ! result){ return 0; }result newResult;x x / 10;}return result;
}基于我的思路如果可能溢出就直接使用更大的容器取存储数据然后看看有没有超过小容器的值那么如果没有更大的容器又该怎么办
没有大容器那就用2个小容器比较新值和旧值。
对于重点公式x1新 x1旧 * 10 x % 10我们知道在数学公式中进行等价变形等式应该相等也就是等式(x1新 - x%10) / 10 x1旧成立。
但是对于计算机不同如果第一个公式计算过程有溢出就会丢失数据那么第二个公式就不成立。
这也就是我们判断的重点If overflow exists, the new result will not equal previous one.
如果溢出存在那么使用新值运算反过来得到的旧值就不是原来的那个旧值。
代码如下
int reverse(int x) {int xNew1 0; // 旧值int xNew2 0; // 新值while (x) {xNew2 xNew1 * 10 x % 10;if ((xNew2 - x % 10) / 10 ! xNew1)return 0;xNew1 xNew2;x / 10;}return xNew2;
}事实上在Leetcode编译器上面的写法是错误的
新的收获使用经典的测试用例
不得不说……任何的算法在使用大量测试用例测试之前都不一定完美例如上面的算法如果使用INT_MAX作为测试用例对于能够进行溢出检测的严格编译器来说会出现报错不过C编译器一般不检测……那么报错的原因是什么
我们看一下xNew2 xNew1 * 10 x % 10;试想一下我们刚才假定这个过程中编译器是允许溢出后直接截断但不会报错那么现在我们假定编译器不允许溢出的发生我们又该怎么办
【思维修炼】“治未病”思想在问题发生之前处理掉
对于xNew2 xNew1 * 10 x % 10;我们需要在溢出发生前就检测出来因此有以下程序
int reverse(int x) {int xNew 0;while(x ! 0){if(xNew INT_MAX/10 || xNew INT_MIN/10) return 0;xNew xNew * 10 x % 10;x / 10;}return xNew;}更严格来说是不是需要把x % 10也“治未病”呢显然不需要因为不存在一个数字乘10后没有溢出但是再1就溢出了。 思考为什么不是 因为对于极限数字214748364也就是INT_MAX / 10乘10之后再加上x % 10是不可能溢出的可以想象如果溢出那x % 10的结果需要 7那么在这个数反转之前就已经溢出了所以不可能。
经典测试案例 严格编译器 优秀算法
对于经典测试案例例如本题可以有
123
-123
INT_MAX
INT_MIN
1230000这些提交前的测试案例足够描述各种情况了。
6.1.3 小结
1个大容器与2个小容器算法与数学公式
6.2 第二掌
把大神的代码完全不看的情况下写出来。 搞定
自己的代码多种写法不断优化到极致。
6.3 第三掌
过了24 小时的时间以后再次重复做题
不同解法的熟练程度 —— 专项练习 新的收获
6.3.1 整数反转图解——安检排队模型 如果你从动态的角度去看一下是不是像一个U型排队区人员流动的样子
想一想你过安检排队的情形。 怎么样是不是瞬间记住了这个整数反转模型
int reverse(int x) {int xNew 0;while(x){if(xNew INT_MAX/10 || xNew INT_MIN/10) return 0; // 预测xNew xNew*10 x%10;x / 10;}return xNew;}通过预测提高性能
这是伟大计算机思想之一应用广泛例如指令操作的分支预测在本题中溢出的检测就使用了预测思想。
6.4 第四掌
过了一周之后: 反复回来练习相同的题目
6.5 第五掌
面试前一周恢复性的训练所有题目全都刷一遍
