算法数据结构
1、输入两个递增排序的链表，合并这两个链表并使新链表中的节点依然是递增顺序的。
ListNode* MergeList(ListNode* ListHeadNodeOne, ListNode* ListHeadNodeTwo){
if (NULL == ListHeadNodeOne)
{
return ListHeadNodeTwo;
}
else if (NULL == ListHeadNodeTwo)
{
return ListHeadNodeOne;
}
ListNode* ListResultNode = NULL;
if (ListHeadNodeOne->NodeValue < ListHeadNodeTwo->NodeValue)
{
ListResultNode = ListHeadNodeOne;
ListResultNode->NextNode = MergeList(ListHeadNodeOne->NextNode, ListHeadNodeTwo);
}
else
{
ListResultNode = ListHeadNodeTwo;
ListResultNode->NextNode = MergeList(ListHeadNodeOne, ListHeadNodeTwo->NextNode);
}
return ListResultNode;
}
2、快速排序
private static int partition(int[] arr, int low, int high) {
//指定左指针i和右指针j
int i = low;
int j= high;
//将第一个数作为基准值。挖坑
int x = arr[low];
//使用循环实现分区操作
while(i<j){//5 8
//1.从右向左移动j，找到第一个小于基准值的值 arr[j]
while(arr[j]>=x && i<j){
j--;
}
//2.将右侧找到小于基准数的值加入到左边的（坑）位置， 左指针想中间移动一个位置i++
if(i<j){
arr[i] = arr[j];
i++;
}
//3.从左向右移动i，找到第一个大于等于基准值的值 arr[i]
while(arr[i]<x && i<j){
i++;
}
//4.将左侧找到的打印等于基准值的值加入到右边的坑中，右指针向中间移动一个位置 j--
if(i<j){
arr[j] = arr[i];
j--;
}
}
//使用基准值填坑，这就是基准值的最终位置
arr[i] = x;//arr[j] = y;
//返回基准值的位置索引
return i; //return j;
}
private static void quickSort(int[] arr, int low, int high) {//???递归何时结束
if(low < high){
//分区操作，将一个数组分成两个分区，返回分区界限索引
int index = partition(arr,low,high);
//对左分区进行快排
quickSort(arr,low,index-1);
//对右分区进行快排
quickSort(arr,index+1,high);
}
}
3、2叉树的下一节点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
struct TreeLinkNode {
int val;
struct TreeLinkNode *left;
struct TreeLinkNode *right;
struct TreeLinkNode *next;
TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
}
};
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if(pNode==NULL)return NULL;
if(pNode->right)//如果有右子树，那么沿右子树往下最左边的节点即为下一个节点
{
TreeLinkNode *p=pNode->right;
while(p->left)p=p->left;
return p;
}else{//如果没有右子树，看父节点
TreeLinkNode *father=pNode->next;
if(father==NULL)return NULL;//如果没有父节点，返回NULL
else{
if(father->left==pNode)return father;//如果该节点为父节点的左孩子，则中序遍历下一个节点即为父节点
else{
TreeLinkNode *grandFather=father->next;
while(grandFather)//如果该节点为父节点的右孩子，则往上不断查找曾祖父节点，直到有一个节点是其父节点的左孩子
{
if(grandFather->left==father)return grandFather;
father=grandFather;
grandFather=father->next;
}
return NULL;//如果找不到，返回NULL
}
}
}
}
4、请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配]
bool match(char* str, char* pattern)
{
if (str == NULL || pattern == NULL)
return false;
return matchCore(str,pattern);
}
bool matchCore(char* str, char* pattern)
{
if (*str == '\0'&&*pattern == '\0') return true; //迭代终止条件
if (*str != '\0'&&*pattern == '\0') return false;//迭代终止条件
if (*(pattern + 1) == '*')
{
if (*str == *pattern||(*pattern=='.'&&*str!='\0'))
return matchCore(str + 1, pattern) || matchCore(str, pattern + 2);
else
return matchCore(str, pattern + 2);
}
if (*str == *pattern || (*pattern=='.'&&*str!='\0'))
return matchCore(str+1,pattern+1);
return false;
}
Android 基础
5、多线程并发
sleep 和 wait 区别
(1)这两个方法来自不同的类，sleep是来自Thread，wait是来自Object；
(2)sleep方法没有释放锁，而wait方法释放了锁。
(3)wait,notify,notifyAll只能在同步控制方法或者同步控制块里面使用，而sleep可以在任何地方使用。
6、ArrayList和LinkedList的区别，以及应用场景
ArrayList是基于数组实现的，ArrayList线程不安全。
LinkedList是基于双链表实现的：
使用场景：
（1）如果应用程序对各个索引位置的元素进行大量的存取或删除操作，ArrayList对象要远优于LinkedList对象；
( 2 ) 如果应用程序主要是对列表进行循环，并且循环时候进行插入或者删除操作，LinkedList对象要远优于ArrayList对象；
7、Http https区别，https的加密原理，非对称加密
https协议需要到ca申请证书，一般免费证书较少，因而需要一定费用。
http是超文本传输协议，信息是明文传输，https则是具有安全性的ssl加密传输协议。
http和https使用的是完全不同的连接方式，用的端口也不一样，前者是80，后者是443。
http的连接很简单，是无状态的；HTTPS协议是由SSL+HTTP协议构建的可进行加密传输、身份认证的网络协议，比http协议安全。
https实现原理：
（1）客户使用https的URL访问Web服务器，要求与Web服务器建立SSL连接。
（2）Web服务器收到客户端请求后，会将网站的证书信息（证书中包含公钥）传送一份给客户端。
（3）客户端的浏览器与Web服务器开始协商SSL连接的安全等级，也就是信息加密的等级。
（4）客户端的浏览器根据双方同意的安全等级，建立会话密钥，然后利用网站的公钥将会话密钥加密，并传送给网站。
（5）Web服务器利用自己的私钥解密出会话密钥。
（6）Web服务器利用会话密钥加密与客户端之间的通信。
8、自定义View流程，onMeasure 中的 MeasureSpec 是如何计算的?
onMeasure->onLayout->onDraw
1.UNSPECIFIED ：父试图不对子试图有任何的约束，它可以达到这几所需要的尺寸大小，例如：ListView，ScrollView等，一般在我们在自定义控件中不会用到这个测量模式的。
2.EXACTLY：父视图指定了确切的大小，无论子视图指定多大的尺寸，子视图必须在父视图指定的大小范围内，对应的属性为match_parent或者具体的值，父控件可以通过MeasureSpec.getSize(measureSpec)直接得到子控件的尺寸。
3.AT_MOST：父控件为子控件指定一个最大尺寸，子视图必须确保自己的孩子视图可以适应在该尺寸范围内，对应的属性为wrap_content，这种模式下父控件无法测量子view的大小，只能由子控件自己根据需求去计算自己的尺寸，这种模式就是我们自定义视图需要实现测量逻辑的情况。这就是大部分要重写onMeasure处理的过程，在wrap_content模式下，自定义view要显示多大，还是说显示父容器显示的大小，这个由你控制）
总结: OnMeasure（int widthMeasureSpec, int heightMeasureSpec）该方法就是我们自定义控件中测量逻辑的方法，该方法中的参数是父view传递给子view测量width与height大小的要求。在我们自定义视图中，要做的就是根据widthMeasureSpec与heightMeasureSpec进行对view宽高的一个测量，不同的测量模式，测量的逻辑是不同的。
9、三方开源库，原理分析，retrofit, leakCanacy,EventBus等。
10、Jetpack使用过哪些组件？具体用过哪些场景。
11、Kotlin掌握情况。
