[移动开发] 【Android春招每日一练】（三）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 移动开发 -> 【Android春招每日一练】（三） -> 正文阅读

[移动开发]【Android春招每日一练】（三）

文章目录

概览

剑指offer：旋转数组最小数字、矩阵中的路径（DFS）、机器人运动范围、剪绳子
Java基础：Java泛型、Java注解、Java IO、Java异常

剑指offer

1.9 旋转数组最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为1。

示例 ：
输入：[3,4,5,1,2]
输出：1

//旋转数组，二分法；
//先使用二分查找，注意升序时，将mid与右边界比较才能确定零界点位置；
class Solution {
    public int minArray(int[] numbers) {
        int i=0,j=numbers.length-1,mid;
        while(i < j){
            mid = (i + j) / 2;
            if(numbers[mid] < numbers[j]) j = mid; 			//零界点肯定在mid左边
            else if(numbers[mid] > numbers[j]) i = mid + 1; //零界点在mid右边
            //如果mid == j，那么numbers[i]~numbers[mid]或者numbers[mid]~numbers[j]数字相同，这时直接遍历查找
            else{											
                for(int t=i;t<j;t++){
                    if(numbers[t] > numbers[t+1]) return numbers[t+1];
                }
                return numbers[i];
            } 
        }
        return numbers[i];
    }
}

1.10 矩阵中的路径（DFS）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-19REaQ6s-1642322212021)(D:\Typora\img\word2.jpg)]

示例：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ursRTHef-1642322212022)(D:\Typora\img\1604944042-glmqJO-Picture0.png)]

//图的DFS+剪枝
//利用递归的思想，首先遍历图查找与字符串第一个字符匹配的位置，再依次朝4个方向搜索（其中越界、已访问过等的方向需要剪枝）；
class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for(int i = 0; i < board.length; i++) {// 遍历图
            for(int j = 0; j < board[0].length; j++) {
                if(dfs(board, words, i, j, 0)) return true;// 如果找到了，就返回true
            }
        }
        return false;
    }

    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // i:行，j:列， k是传入字符串当前索引
        //先剪枝，再匹配字符串第一个字符位置
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) 
            return false;
        if(k == word.length - 1) return true;   //字符串匹配成功
        board[i][j] = '\0';                     //标记访问过的字符，防止重复访问 
        //已经找到了第一个字符对应位置，索引字符串索引k+1，再朝4个方向DFS
        boolean res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
                      dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1); 
        board[i][j] = word[k];// 还原找过的元素，因为之后可能还会访问到（不同路径）
        return res;
    }
}

1.11 机器人运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例：
输入：m = 2, n = 3, k = 1
输出：3

提示：
1 <= n,m <= 100
0 <= k <= 20

//DFS
//仅需向右和向下搜索即可访问所有可达解（等腰三角形）
class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n]; //标识单元格已被访问
        return dfs(m,n,k,0,0,visited);
    }

    //i:行坐标,j:纵坐标
    int dfs(int m,int n,int k,int i,int j,boolean[][] visited){
        if(i >= m || j >= n || k < sum(i) + sum(j) || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(m,n,k,i+1,j,visited) + dfs(m,n,k,i,j+1,visited);//本身自己的1格加上朝右和朝下搜索格数；
    }

    //计算位数和
    int sum(int x){
        int t = x % 10;
        x /= 10;
        return t + x;
    }
}

1.12 剪绳子

给你一根长度为 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。

示例:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

//动态规划（dp）
class Solution {
    public int cuttingRope(int n) {
        //dp[i]存储长度为i的绳子剪成m端后长度的最大乘积
        int dp[] = new int[n+1];
        dp[2] = 1;	//长度为2时已经知道最大乘积为1
        for(int i = 3;i <= n;i++){	//dp[2]已知，从dp[3]开始求
            //首先对绳子剪长度为j的一段
            for(int j = 2;j < i;j++){
                //比较:dp[i]:当前长度不剪
                //j*(i-j):只剪了j长度的一段
                //j*dp[i-j]:剪了j长度一段并且j可能继续剪
                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        //现在已经求出每个长度i对应的最大乘积，返回dp[n]
        return dp[n];
    }
}

//贪心算法
//数学推导证明，当n大于4时，尽可能多的剪出长度为3的段，求出的乘积最大；
class Solution {
    public int cuttingRope(int n) {
        if(n == 2)return 1;
        if(n == 3)return 2;
        if(n == 4)return 4;
        int res = 1;
        while(n > 4){
            res *= 3;
            n -= 3;
        }
        return res*n;
    }
}

Java基础

2.4 Java泛型

语法糖

语法糖（Syntactic Sugar），也称糖衣语法，是由英国计算机学家Peter.J.Landin发明的一个术语，指在计算机语言中添加的某种语法，这种语法对语言的功能并没有影响，但是更方便程序员使用。Java中最常用的语法糖主要有泛型、变长参数、条件编译、自动拆装箱、内部类等。虚拟机并不支持这些语法，它们在编译阶段就被还原回了简单的基础语法结构，这个过程成为解语法糖。

泛型的目的： Java 泛型就是把一种语法糖，通过泛型使得在编译阶段完成一些类型转换的工作，避免在运行时强制类型转换而出现 ClassCastException ，即类型转换异常。

泛型的好处：

类型安全。类型错误现在在编译期间就被捕获到了，而不是在运行时当作 java.lang.ClassCastException展示出来，将类型检查从运行时挪到编译时有助于开发者更容易找到错误，并提高程序的可靠性。
消除了代码中许多的强制类型转换，增强了代码的可读性。
为较大的优化带来了可能。

**泛型的实质：**允许在定义接口、类时声明类型形参，类型形参在整个接口、类体内可当成类型使用，几乎所有可使用普通类型的地方都可以使用这种类型形参。

2.5 Java注解

元数据概念

元数据是关于数据的数据。在编程语言上下文中，元数据是添加到程序元素如方法、字段、类和包上的额外信息。对数据进行说明描述的数据。

**元数据的作用 **

一般来说，元数据可以用于创建文档（根据程序元素上的注释创建文档），跟踪代码中的依赖性（可声明方法是重载，依赖父类的方法），执行编译时检查（可声明是否编译期检测），代码分析。

1）编写文档：通过代码里标识的元数据生成文档

2）代码分析：通过代码里标识的元数据对代码进行分析

3）编译检查：通过代码里标识的元数据让编译器能实现基本的编译检查

**Java平台元数据 **

注解Annotation就是java平台的元数据，是 J2SE5.0新增加的功能，该机制允许在 Java 代码中添加自定义注释，并允许通过反射（reflection），以编程方式访问元数据注释。通过提供为程序元素（类、方法等）附加额外数据的标准方法，元数据功能具有简化和改进许多应用程序开发领域的潜在能力，其中包括配置管理、框架实现和代码生成。 Annotation能被用来为程序元素（类、方法、成员变量等）设置元素据。

Annotaion不影响程序代码的执行，无论增加、删除Annotation，代码都始终如一地执行。如果希望让程序中的Annotation起一定的作用，只有通过解析工具或编译工具对Annotation中的信息进行解析和处理。

2.6 Java IO

编码

Java采用unicode编码，2个字节来表示一个字符，这点与C语言中不同，C语言中采用ASCII，在大多数系统中，一个字符通常占1个字节，但是在0~127整数之间的字符映射，unicode向下兼容ASCII。而Java采用unicode来表示字符，一个中文或英文字符的unicode编码都占2个字节。但如果采用其他编码方式，一个字符占用的字节数则各不相同。

File类

File类是java.io包下代表与平台无关的文件和目录，也就是说，如果希望在程序中操作文件和目录，都可以通过File类来完成。

IO流

输入流和输出流

根据数据流向不同分为：输入流和输出流。

输入流:只能从中读取数据，而不能向其写入数据。

输出流：只能向其写入数据，而不能从中读取数据。

字节流和字符流

字节流和字符流和用法几乎完全一样，区别在于字节流和字符流所操作的数据单元不同。

字符流的由来：因为数据编码的不同，而有了对字符进行高效操作的流对象。本质其实就是基于字节流读取时，去查了指定的码表。字节流和字符流的区别：

（1）读写单位不同：字节流以字节（8bit）为单位，字符流以字符为单位，根据码表映射字符，一次可能读多个字节。

（2）处理对象不同：字节流能处理所有类型的数据（如图片、avi等），而字符流只能处理字符类型的数据。

注：只要是处理纯文本数据，就优先考虑使用字符流。除此之外都使用字节流。

节点流和处理流

按照流的角色来分，可以分为节点流和处理流。

可以从/向一个特定的IO设备（如磁盘、网络）读/写数据的流，称为节点流，节点流也被成为低级流。

处理流是对一个已存在的流进行连接或封装，通过封装后的流来实现数据读/写功能，处理流也被称为高级流。

//节点流，直接传入的参数是IO设备 
FileInputStream fis = new FileInputStream("test.txt"); 
//处理流，直接传入的参数是流对象
BufferedInputStream bis = new BufferedInputStream(fis);

当使用处理流进行输入/输出时，程序并不会直接连接到实际的数据源，没有和实际的输入/输出节点连接。使用处理流的一个明显好处是，只要使用相同的处理流，程序就可以采用完全相同的输入/输出代码来访问不同的数据源，随着处理流所包装节点流的变化，程序实际所访问的数据源也相应地发生变化。

IO流的四大基类

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jZdQcyxq-1642322371261)(D:\Typora\img\image-20220116154629503.png)]

2.7 Java异常

Java异常是Java提供的一种识别及响应错误的一致性机制。

Java异常机制可以使程序中异常处理代码和正常业务代码分离，保证程序代码更加优雅，并提高程序健壮性。在有效使用异常的情况下，异常能清晰的回答what, where, why这3个问题：异常类型回答了“什么”被抛出，异常堆栈跟踪回答了“在哪“抛出，异常信息回答了“为什么“会抛出。

Java异常机制用到的几个关键字：try、catch、finally、throw、throws。

? try – 用于监听。将要被监听的代码(可能抛出异常的代码)放在try语句块之内，当try语句块内发生异常时，异常就被抛出。

? catch – 用于捕获异常。catch用来捕获try语句块中发生的异常。

? finally – finally语句块总是会被执行。它主要用于回收在try块里打开的物力资源 (如数据库连接、网络连接和磁盘文件)。只有finally块，执行完成之后，才会回来执行try或者catch块中的return或者throw语句，如果finally中使用了return或者throw等终止方法的语句，则就不会跳回执行，直接停止。

? throw – 用于抛出异常。

? throws – 用在方法签名中，用于声明该方法可能抛出的异常。