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

【Android春招每日一练】(四) 剑指4题+Java基础,第1张

【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基础知识的复习巩固。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5707630.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存