Algorithm
每周至少做一个Leetcode算法题
第1道
【题目来源】
T9：斐波那契数列，何海涛《剑指Offer》
【题目】
写一个函数，输入参数n，输出斐波那契数列的第n项
【例子】
# 斐波那契数列从第0开始
0 1 1 2 3 5 8 13
【解答】
-
解法1：递归解法，容易理解，但效率太差，不予详细分析
-
解法2：动态规划法（推荐）
斐波那契的递推关系，也是DP的状态转移方程
-
解法3：乘方法,f(n)=M^n
[M = left[ egin{matrix} 1 & 1\1 & 0end{matrix} ight] ]/** * 解法2：动态规划，从底往上计算，避免重复计算 * 例子：f(0)+f(1)-> f(2) * f(1)+f(2)-> f(3) * ... PreTwo+Preone-> cur * * @param n * @return */ public int FibonacciByOrder(int n) { if (n < 2) { return n; } int PrevOne = 1; int PrevTwo = 0; int cur = 0; for (int i = 2; i <= n; i++) { cur = PrevOne + PrevTwo; PrevTwo = PrevOne; PrevOne = cur; } return cur; }
【思考】
- 改编题1：一只青蛙一次可以跳上1 级台阶，也可以跳上2 级。求该青蛙跳上一个n级的台阶总共有多少种跳法
- 改编题2：在青蛙跳台阶的问题中，如果把条件改成：一只青蛙一次可以跳上 1级台阶，也可以跳上 2 级……它也可以跳上 n 级，此时该青蛙跳上一个 n级的台阶总共有多少种跳法？我们用数学归纳法可以证明f（n）=2^n-1。
第2道
【题目来源】
T11：数值的整数次方，何海涛《剑指Offer》
【题目】
实现函数 double Power（double base, int exponent），求 base 的exponent次方。不得使用库函数，同时不需要考虑大数问题。
【例子】
// power(2,2)
4
// power(2,-2)
0.25
【解答】
-
解法1：循环法记录底数相乘的次数，很显然根据次方exp（幂）的定义：就是exp个base连续相乘。
这是所有人下意识都能想到的解法，不能体现算法训练的价值，这里不细分析，提醒注意：（1）底数为0的负整数次方，如0^-2，（2）指数exp除了正整数外为负数和零的情形
-
解法2：二分法。二分法的本质是每次排除一半，那么是否可以根据公式1利用二分法写出O(logN)的解法呢，答案是当然可以。我们可以利用递归将指数n-> n/2-> n/4->...1逐步二分掉，直到满足基准条件
[a^0 = 1,a^1=a ]
根据以上的分析，给出参考代码
public double myPow(double base, long exp) {
// 排除除0的异常
if (base ==0 && exp < 0) {
return 0;
}
if (exp == 0) {
return 1;
}
if (exp == 1) {
return base;
}
// 处理负指数幂
if (exp < 0) {
exp = -exp;
base = 1 /base;
}
double result = myPow(base, exp>>1);
result *= result;
if ( exp%2 == 1 ) {
result *= base;
}
return result;
}
值得注意的是
int exp = [−2^31, 2^31 − 1],左边界取反会出现越界的错误，因此定义exp为long
【思考】
Review
阅读并点评至少1篇英文技术文章
【原文】：CH17.Release Your Code From Kathy Sierra's Head first Java author
【译文】：
【点评】：
部署：指的是将程序员写的Java源代码经过处理加工成jar文件的过程，可以供其他人运行和充当轮子。
处理过程可以分为：编译、打包
JAR is Java ARchive（Java归档）,这是一种基于pkzip的文件格式，对于终端使用者来说，操作的是1个.jar文件，而不是成百上千的.class文件。
-
Deploying your application
- 本地：可执行的JAR文件
- 混合
- 远程
-
Separate source code and class files
- sources目录：存放源代码
- classes目录：存放字节码文件
-
Put your Java in a JAR
- 如何生成.jar
cd MyProject/classesjar -cvmf manifest.txt packFoof.jar javaranch
- 如何生成.jar
-
Running (executing) the JAR
- 执行jar
cd MyProject/classesjava -jar packFoof.jar
- 执行jar
-
Put your classes in packages
-
为什么要创建包？
-
数一下有多少个List
-
保证class文件的唯一性，不要同名
举例：叫孙少安的人很多，那怎么区分呢？最简单的就是根据户口，也就是你是xx省xx市xx县xx镇xx村的孙少安，我是另外一个村的孙少安也就可以区分了
-
-
怎么避免包名冲突，保证包的唯一性
- 域名反写
sun官方给的命名规范建议是：反写的域名，借助域名唯一的特点来保证包不同名。例如：com.alibaba、org.apache
-
-
META-INF目录
-
MANIFEST.MF文件
指定jar包的main（）方法的位置
-
-
jar管理工具
- Maven
Tip
学习至少一个技术技巧
Share
分享一篇有观点和思考的技术文章
ES官方的教程，轻巧结构清晰，Elasticsearch: 权威指南
米罗说
- 人生不在于做多少事，在于把关键的事做到极致。
移动端更方便随时阅读，下面是作者的微信公号，觉得作者的文章对你有帮助，可以关注支持一下。
