【Android春招每日一练】（四） 剑指4题+Java基础

【Android春招每日一练】（四） 剑指4题+Java基础

文章目录

概览剑指offer

1.13 剪绳子Ⅱ1.14 二进制中1的个数1.15 数值的整数次方1.16 打印1到最大的n位数（考虑大数） Java基础

2.8 Java抽象类和接口的区别2.9 浅拷贝和深拷贝2.10 Java序列化2.11 Java finally与return执行顺序2.12 Java传值还是传址 总结

概览

剑指offer：剪绳子Ⅱ、二进制中1的个数、数值的整数次方、打印1到最大的n位数（考虑大数）
Java基础：Java抽象类和接口的区别、浅拷贝和深拷贝、Java序列化、Java finally与return执行顺序、Java传值还是传址

剑指offer 1.13 剪绳子Ⅱ

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m - 1] 。请问 k[0]k[1]…*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

2 <= n <= 1000`

//只能使用贪心算法
//因为n较大，所以直接使用贪心算法，大数求余法：循环求余法；
class Solution {
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        if(n == 4) return 4;
        long res = 1;	//必须定义为long，否则会溢出；
        while(n > 4){
            res = res * 3 % 1000000007;
            n -= 3;
        }
        return (int)(res * n % 1000000007);
    }
}

1.14 二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量).）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例：
输入：n = 11 (控制台输入 00000000000000000000000000001011)
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

//第一种，逐位判断
//将n与1相与，每次向右移一位；
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){	//条件判断为 == 0；
            res += n & 1;
            n = n >>> 1;//(Java无符号移位>>>)
        }
        return res;
    }
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Iu3w0cMm-1642411071471)(D:Typoraimg9bc8ab7ba242888d5291770d35ef749ae76ee2f1a51d31d729324755fc4b1b1c-Picture10.png)]

//第二种，n&(n-1)
//n&(n - 1)其预算结果恰为把n的二进制位中的最低位的1变为0之后的结果。
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while(n != 0){
            res++;
            n &= n - 1;
        }
        return res;
    }
}

1.15 数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

//二分思想快速求幂法
//将x^n分为x^n/2 * x^n/2 循环相乘，判断奇数时再乘一个x；
//关键点：x =* x;而非res *= x;
class Solution {
    public double myPow(double x, int n) {
        if(n == 0) return 1.0;	//n为0时直接返回1.0
        double res = 1.0;
        long t = n;				//防止溢出
        if(t < 0){				//n<0时转换为正数计算
            t = -t;
            x = 1 / x;
        }
        while(t > 0){		
            if((t & 1) == 1){	//<=> t%2,奇数时，需要再乘一个x
                res *= x;
            }
            x *= x;				//<=>x^2
            t >>= 1;			//<=>t向下整除2
        }
        return res;
    }
}

1.16 打印1到最大的n位数（考虑大数）

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

//1.为了避免数字开头出现0，先把首位first固定，first取值范围为1~9
//2.用digit表示要生成的数字的位数，本题要从1位数一直生成到n位数，对每种数字的位数都生成一下首位，所以有个双重for循环
//3.生成首位之后进入递归生成剩下的digit - 1位数，从0~9中取值
//4.递归的中止条件为已经生成了digit位的数字，即index == digit，将此时的数num转为int加到结果res中
class Solution {
    int[] res;
    int count = 0;

    public int[] printNumbers(int n) {
        res = new int[(int)Math.pow(10, n) - 1];
        for(int digit = 1; digit < n + 1; digit++){
            for(char first = '1'; first <= '9'; first++){
                char[] num = new char[digit];
                num[0] = first;
                dfs(1, num, digit);
            }
        }
        return res;
    }

    private void dfs(int index, char[] num, int digit){
        if(index == digit){
            res[count++] = Integer.parseInt(String.valueOf(num));
            return;
        }
        for(char i = '0'; i <= '9'; i++){
            num[index] = i;
            dfs(index + 1, num, digit);
        }
    }
}

Java基础 2.8 Java抽象类和接口的区别

接口和抽象类的概念不一样。接口是对动作的抽象，抽象类是对根源的抽象。从设 计理念上，接口反映的是 “like-a” 关系，抽象类反映的是 “is-a” 关系。 抽象类表示的是，这个对象是什么。接口表示的是，这个对象能做什么。比如，男人，女人，这两个类，他们的抽象类是人。说明，他们都是人。 人可以吃东西，狗也可以吃东西，你可以把“吃东西”定义成一个接口，然后让这些类去实现它. 所以，在高级语言上，一个类只能继承一个类（抽象类）(正如人不可能 同时是生物和非生物)，但是可以实现多个接口(吃饭接口、走路接口)。

抽象类和接口都不能直接实例化，如果要实例化，抽象类变量必须指向实现所有抽象方法的子类对象，接口变量必须指向实现所有接口方法的类对象。

抽象类要被子类继承，接口要被类实现。

接口里定义的变量只能是公共的静态的常量，抽象类中的变量是普通变量。

抽象类里可以没有抽象方法。

接口可以被类多实现（被其他接口多继承），抽象类只能被单继承。

接口中没有 this 指针，没有构造函数，不能拥有实例字段（实例变量）或实例方法。

抽象类不能在Java 8 的 lambda 表达式中使用。

2.9 浅拷贝和深拷贝

浅拷贝

浅拷贝是按位拷贝对象，它会创建一个新对象，这个对象有着原始对象属性值的一份精确拷贝。如果属性是基本类型，拷贝的就是基本类型的值；如果属性是内存地 址（引用类型），拷贝的就是内存地址 ，因此如果其中一个对象改变了这个地址，就会影响到另一个对象。

在上图中，SourceObject有一个int类型的属性 “field1"和一个引用类型属 性"refObj”（引用ContainedObject类型的对象）。当对SourceObject做浅拷贝时， 创建了CopiedObject，它有一个包含"field1"拷贝值的属性"field2"以及仍指向refObj 本身的引用。由于"field1"是基本类型，所以只是将它的值拷贝给"field2"，但是由 于"refObj"是一个引用类型, 所以CopiedObject指向"refObj"相同的地址。因此对SourceObject中的"refObj"所做的任何改变都会影响到CopiedObject。

深拷贝

深拷贝会拷贝所有的属性,并拷贝属性指向的动态分配的内存。当对象和它所引用的对象一起拷贝时即发生深拷贝。深拷贝相比于浅拷贝速度较慢并且花销较大。

在上图中，SourceObject有一个int类型的属性 “field1"和一个引用类型属性"refObj1”（引用ContainedObject类型的对象）。当对SourceObject做深拷贝 时，创建了CopiedObject，它有一个包含"field1"拷贝值的属性"field2"以及包含"refObj1"拷贝值的引用类型属性"refObj2" 。因此对SourceObject中的"refObj"所做的任何改变都不会影响到CopiedObject 。

延迟拷贝

延迟拷贝是浅拷贝和深拷贝的一个组合，实际上很少会使用。 当最开始拷贝一个对象时，会使用速度较快的浅拷贝，还会使用一个计数器来记录有多少对象共享这个 数据。当程序想要修改原始的对象时，它会决定数据是否被共享（通过检查计数器）并根据需要进行深拷贝。

如何选择

如果对象的属性全是基本类型的，那么可以使用浅拷贝，但是如果对象有引用属性，那就要基于具体的需求来选择浅拷贝还是深拷贝。我的意思是如果对象引用任 何时候都不会被改变，那么没必要使用深拷贝，只需要使用浅拷贝就行了。如果对 象引用经常改变，那么就要使用深拷贝。没有一成不变的规则，一切都取决于具体需求。

2.10 Java序列化

把对象转换为字节序列的过程称为对象的序列化。

把字节序列恢复为对象的过程称为对象的反序列化。

对象的序列化主要有两种用途：
　　1） 把对象的字节序列永久地保存到硬盘上，通常存放在一个文件中；
　　2） 在网络上传送对象的字节序列。

ObjectOutputStream代表对象输出流，它的writeObject(Object obj)方法可对参数指定的obj对象进行序列化，把得到的字节序列写到一个目标输出流中。
ObjectInputStream代表对象输入流，它的readObject()方法从一个源输入流中读取字节序列，再把它们反序列化为一个对象，并将其返回。
只有实现了Serializable和Externalizable接口的类的对象才能被序列化。Externalizable接口继承自 Serializable接口，实Externalizable接口的类完全由自身来控制序列化的行为，而仅实现Serializable接口的类可以 采用默认的序列化方式 。
对象序列化包括如下步骤：
1） 创建一个对象输出流，它可以包装一个其他类型的目标输出流，如文件输出流；
2） 通过对象输出流的writeObject()方法写对象。

对象反序列化的步骤如下：
1） 创建一个对象输入流，它可以包装一个其他类型的源输入流，如文件输入流；
2） 通过对象输入流的readObject()方法读取对象。

serialVersionUID

虚拟机是否允许反序列化，不仅取决于类路径和功能代码是否一致，一个非常重要的一点是两个类的序列化 ID 是否一致。如果两个类的功能代码完全一致，但是序列化 ID 不同，那么他们无法相互序列化和反序列化。

显式地定义serialVersionUID有两种用途：
1、 在某些场合，希望类的不同版本对序列化兼容，因此需要确保类的不同版本具有相同的serialVersionUID；
2、 在某些场合，不希望类的不同版本对序列化兼容，因此需要确保类的不同版本具有不同的serialVersionUID。

静态变量序列化

序列化保存的是对象的状态，静态变量属于类的状态，因此 序列化并不保存静态变量。

transient

在实际开发过程中，我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，打个比方，如果一个用户有一些敏感信息（如密 码，yhk号等），为了安全起见，不希望在网络 *** 作（主要涉及到序列化 *** 作，本地序列化缓存也适用）中被传输，这些信息对应的变量就可以加上transient关键字。换句话说，这个字段的生命周期仅存于调用者的内存中而不会写到磁盘里持久 化。

反序列化时transient 变量的值被设为初始值，如 int 型的是 0，对象型的是 null。

2.11 Java finally与return执行顺序

Java中异常捕获机制try…catch…finally块中的finally语句是不是一定会被执行？不是，至少有两 种情况下finally语句是不会被执行的：

（1）try语句没有被执行到，如在try语句之前就返回了，这样finally语句就不会执行，这也说明了finally语句被执行的必要而非充分条件是：相应的try语句一定被执行到。

（2）在try块中有 System.exit(0); 这样的语句， System.exit(0); 是终止Java虚拟机JVM的，连JVM都停止了，所有都结束了，当然finally语句也不会被执 行到。

1. finally语句在return语句执行之后return返回之前执行的。

2. finally块中的return语句会覆盖try块中的return返回。

3. 如果finally语句中没有return语句覆盖返回值，那么原来的返回值可能因为finally里的修改而改变也可能不变。（取决于变量是基本数据类型还是引用数据类型）

4. try块里的return语句在异常的情况下不会被执行，这样具体返回哪个看情况。（取决于catch改变返回值还是finally改变，还是同时）

5. 当发生异常后，catch中的return执行情况与未发生异常时try中return的执行情况完全一样。

总结：finally块的语句在try或catch中的return语句执行之后返回之前执行且finally里的修改语句可能影响也可能不影响try或catch中 return已经确定的返回值，若finally里也有return语句则覆盖try或catch中的return语句直接返回。

2.12 Java传值还是传址

public class Example {
    String str = new String("good");
    char[] ch = { 'a', 'b', 'c' };
    
    public static void main(String args[]) {
        Example ex = new Example();
        ex.change(ex.str, ex.ch);
        System.out.print(ex.str + " and ");
        System.out.print(ex.ch);
    }

    public void change(String str, char ch[]) {
        str = "test ok";
        ch[0] = 'g';
    }
}
输出：good and gbc

在java里没有引用传递，只有值传递这个值指的是实参的地址的拷贝，得到这个拷贝地址后，你可以通过它修改这个地址的内容（引用不变），因为此时这个内容的地址和原地址是同一地址，但是你不能改变这个地址本身使其重新引用其它的对象，也就是值传递，

不管是引用数据类型还是基本类型，在函数中都不能改变其实际地址但能改变其中的内容。

总结

1.算法中学到了更多的关于数值计算问题的解法，大数计算会有一点难；
2.继续Java基础知识的复习巩固。