您的位置: 首页  >  IT文章  >  ARTS习惯（7）

ARTS习惯（7）

分类: IT文章 • 2025-02-08 15:44:55

目录

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 ]

    ​
    ​
    ​

[ a^n = egin{cases} a^frac{n}{2}a^frac{n}{2} & n为偶数 \ a^frac{n-1}{2}a^frac{n-1}{2}a &n为奇数 end{cases} ]

公式1

根据以上的分析，给出参考代码

 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
      1. cd MyProject/classes
      2. jar -cvmf manifest.txt packFoof.jar javaranch

  • Running (executing) the JAR

    • 执行jar
      1. cd MyProject/classes
      2. java -jar packFoof.jar

  • Put your classes in packages

    • 为什么要创建包？

      • 数一下有多少个List

        ARTS习惯（7）

      • 保证class文件的唯一性，不要同名

        举例：叫孙少安的人很多，那怎么区分呢？最简单的就是根据户口，也就是你是xx省xx市xx县xx镇xx村的孙少安，我是另外一个村的孙少安也就可以区分了

    • 怎么避免包名冲突，保证包的唯一性

      • 域名反写

      sun官方给的命名规范建议是：反写的域名，借助域名唯一的特点来保证包不同名。例如：com.alibaba、org.apache

  • META-INF目录

    • MANIFEST.MF文件

      指定jar包的main（）方法的位置

  • jar管理工具

    • Maven

Tip

学习至少一个技术技巧

总结的高频快捷键速查清单，全部经过测试，不灌水

Share

分享一篇有观点和思考的技术文章

ES官方的教程，轻巧结构清晰，Elasticsearch: 权威指南

米罗说

  • 人生不在于做多少事，在于把关键的事做到极致。

移动端更方便随时阅读，下面是作者的微信公号，觉得作者的文章对你有帮助，可以关注支持一下。

ARTS习惯（7）

相关推荐