知识总结（一）
操作系统
- 线程和进程的区别
(1)地址空间:进程内的一个执行单元;进程至少有一个线程;它们共享进程的地址空间;而进程有自己独立的地址空间;
(2)资源拥有:进程是资源分配和拥有的单位,同一个进程内的线程共享进程的资源
(3)线程是处理器调度的基本单位,但进程不是.
(4)线程只需要很少的资源就可“轻装上阵”运行的优点，来弥补进程并发的“颗粒度”粗糙的缺点，提高系统资源（如：CPU,内存——又可分为数据区，堆栈区等等，和IO总线控制权……）利用率。 - 线程切换如何做，有啥性能影响
view.post(Runnable action)
activity.runOnUiThread(Runnable action)
Handler机制
性能影响：CPU调度，创建了新的线程，耗费资源 - 线程之间如何进行同步
所谓的线程之间保持同步，是指不同的线程在执行同一个对象的同步代码块时，因为要获得对象的同步锁而互相牵制
synchronized - 死锁如何造成的，如何避免
当一个线程等待由另一个线程持有的锁，而后者正在等待已被第一个线程持有的锁时，就会发生死锁。JVM不监测也不试图避免这种情况，因此保证不发生死锁就成了程序员的责任。
如何避免: 一个通用的经验法则是：当几个线程都要访问共享资源A、B、C时，保证每个线程都按照同样的顺序去访问他们。 - 进程间通信方式
第一种：Intent方式
Intent分为两种，一种是显式Intent,只适合在同一进程内的不同组件之间通信，例如 new Intent(this,Target.class).
另外一种是隐式Intent,在AndroidMainifest.xml中注册，一般可以用于跨进程通信，例如new Intent(String action).
下面就介绍隐式Intent跨进程通信的例子：
Project A 中的代码比较简单，主要就是在的button onClick事件中：
button.setOnClickListener(new OnClickListener()
{
@Override
public void onClick(View v)
{
Intent intent = new Intent();
intent.setAction("com.example.IPCByIntent");
intent.putExtra("data", "this is ipc by intent");
startActivity(intent);
}
});
其中intent.SetAction里面的值是Project B中定义的。
在Project B中的AndroidMainifest.xml，在MainActivity的第二个intent-filter中，添加在Project A中用到的action值
<activity
android:name="com.example.adildemo.MainActivity"
android:label="@string/app_name" >
<intent-filter>
<action android:name="android.intent.action.MAIN" />
<category android:name="android.intent.category.LAUNCHER" />
</intent-filter>
<intent-filter>
<action android:name="com.example.IPCByIntent"/>
<category android:name="android.intent.category.DEFAULT"/>
</intent-filter>
</activity>
在Project B的MainActivity.java的OnCreate方法中，添加如下代码
Intent intent = this.getIntent();
if(null != intent.getStringExtra("data")){
tv.setText(intent.getStringExtra("data"));
}
先运行Project B,在运行Project A,点击 Porject A 的button,则Project B上的textview 将会显示 this is ipc by intent.Intent 可以非常方便的通信，但是它是非实时的，无法进行实时的像函数调用那样的实时通信。
第二种方式：AIDL方式
AIDL方式应该是应用的比较多的一种方式，下面介绍一个简单的例子来实现用AIDL解决进程之间的数据传递。
有两个Project,AIDLDemo 和AIDLDemoClient,AIDLDemo里面有一个Service,我们当作是Server Project,另外一个AIDLDemoClient我们当作是Client.
首先看Server Project，首先新建一个File，myAidl.aidl,注意后缀名要是.aidl.其实就是一个接口文件，在该文件中：
1.我们不需要使用public,protected,private等修饰符.
2.对于基本类型，如int,String等我们不需要import.
3.如果在文件中引用别的aidl文件接口，需要import进来，即使在一个包下面也需要import.
package com.sha.aidl;
interface myAidl{
int add(int x,int y);
String get();
}
定义好myAidl.aidl文件以后，build project，系统会给我们自动生成一个myAidl.java文件，在gen下面
然后在AndroidMainifest.xml中注册静态Service如下：
<service android:name="com.example.adildemo.myService">
<intent-filter >
<action android:name="com.example.adildemo.myService"/>
</intent-filter>
</service>
定义Service文件这里面核心的步骤就是定义了一个 myAidl.Stub的 Binder,然后在onBinder函数里面，返回这个Binder.
package com.example.adildemo;
import android.app.Service;
import android.content.Intent;
import android.os.IBinder;
import android.os.RemoteException;
import com.sha.aidl.myAidl;
public class myService extends Service
{
@Override public IBinder onBind(Intent intent)
{
return myBinder;
}
private myAidl.Stub myBinder = new myAidl.Stub()
{
@Override public int add(int x, int y) throws RemoteException
{
return x + y;
}
@Override public String get() throws RemoteException
{
return "test";
}
};
}
至此，Server Project的工作就完成了。
下面看看Client Project的内容：
把ADILDemo里面的myAidl.aidl拷贝到ADILDemo_Client项目中，注意myAidl.aidl的包名一定要一致，如果不一致会出现错误。
在ADIDemo_Client的MainActivity.Java文件中：
首先在OnCreate函数里面，绑定Service,定义一个ServiceConnection变量，通过调用myAidl.stub.asInterface(IBinder)方法获取myAidl变量，然后调用myAidl变量的get方法
package com.example.adildemo;
import android.app.Activity;
import android.content.ComponentName;
import android.content.Context;
import android.content.Intent;
import android.content.ServiceConnection;
import android.os.Bundle;
import android.os.IBinder;
import android.os.RemoteException;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
import android.widget.TextView;
import android.widget.Toast;
import com.example.adildem.R;
import com.sha.aidl.myAidl;
public class MainActivity extends Activity
{
private Button button;
private myAidl aidl;
private TextView tv;
private ServiceConnection sc = new ServiceConnection()
{
@Override public void onServiceDisconnected(ComponentName name)
{
aidl = null;
}
@Override public void onServiceConnected(ComponentName name, IBinder service)
{
aidl = myAidl.Stub.asInterface(service);
}
};
@Override protected void onCreate(Bundle savedInstanceState)
{
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
button = (Button)findViewById(android.R.id.button1);
tv = (TextView)findViewById(android.R.id.text1);
Intent intent = new Intent("com.example.adildemo.myService");
bindService(intent, sc, Context.BIND_AUTO_CREATE);
/* Intent intent = this.getIntent();
if(null != intent.getStringExtra("data")){
tv.setText(intent.getStringExtra("data"));
}*/
button.setOnClickListener(new OnClickListener()
{
@Override public void onClick(View v)
{
String result = "";
try
{
result = aidl.get();
}
catch (RemoteException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
Toast.makeText(MainActivity.this, result+"", Toast.LENGTH_SHORT).show();
}
});
}
}
先运行AIDLDemo project,再运行AIDLDemoClient project,点击button,弹出toast,表示client调用server成功
第三种方式：Messenger方式
在AndroidMainifest.xml中注册静态Service如下：
<service android:name="com.example.aidldemomessager.myService">
<intent-filter>
<action android:name="com.example.aidldemomessager.myService"/>
</intent-filter>
</service>
Service文件：
package com.example.aidldemomessager;
import android.app.Service;
import android.content.Intent;
import android.os.Handler;
import android.os.IBinder;
import android.os.Message;
import android.os.Messenger;
import android.widget.Toast;
public class myService extends Service
{
private Handler serviceHandler = new Handler(){
@Override public void handleMessage(Message msg)
{
Toast.makeText(getApplicationContext(), "test", Toast.LENGTH_LONG).show();
}
};
private Messenger messager = new Messenger(serviceHandler);
@Override public IBinder onBind(Intent intent)
{
return messager.getBinder();
}
}
MainActivity文件
package com.example.aidldemomessager;
import android.app.Activity;
import android.content.ComponentName;
import android.content.Context;
import android.content.Intent;
import android.content.ServiceConnection;
import android.os.Bundle;
import android.os.IBinder;
import android.os.Message;
import android.os.Messenger;
import android.os.RemoteException;
import android.view.View;
import android.view.View.OnClickListener;
import android.widget.Button;
public class MainActivity extends Activity
{
private Button button;
@Override protected void onCreate(Bundle savedInstanceState)
{
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_main);
Intent intent = new Intent("com.example.aidldemomessager.myService");
bindService(intent, sc, Context.BIND_AUTO_CREATE);
button = (Button)findViewById(R.id.button);
button.setOnClickListener(new OnClickListener()
{
@Override public void onClick(View v)
{
Message msg = new Message();
msg.what = 1;
try
{
messenger.send(msg);
}
catch (RemoteException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
}
});
}
private Messenger messenger;
private ServiceConnection sc = new ServiceConnection()
{
@Override public void onServiceDisconnected(ComponentName name)
{
messenger = null;
}
@Override public void onServiceConnected(ComponentName name, IBinder service)
{
messenger = new Messenger(service);
}
};
}
网络篇
- TCP/UDP的区别
1.基于连接与无连接；TCP（Transmission Control Protocol，传输控制协议）是面向连接的协议，也就是说，在收发数据前，必须和对方建立可靠的连接。UDP是一个非连接的协议，传输数据之前源端和终端不建立连接，当它想传送时就简单地去抓取来自应用程序的数据，并尽可能快地把它扔到网络上。
2.对系统资源的要求（TCP较多，UDP少）；
3.UDP程序结构较简单；
4.流模式与数据报模式 ；
5.TCP保证数据正确性，UDP可能丢包，TCP保证数据顺序，UDP不保证。
-
TCP三次握手和四次挥手流程，为什么要进行第三次握手，为什么是四次挥手而不是三次挥手就完了
三次握手：
同步连接双方的序列号和确认号并交换 TCP窗口大小信息。
1 为了防止已失效的连接请求报文段突然又传送到了服务端，因而产生错误
2 解决“网络中存在延迟的重复分组”的问题
3 保证连接是双工的，可靠更多的是通过重传机制来保证的。
4 为了保证服务端能收接受到客户端的信息并能做出正确的应答而进行前两次握手，为了保证客户端能够接收到服务端的信息并能做出正确的应答而进行后两次握手。
四次挥手：
这是因为服务端的LISTEN状态下的SOCKET当收到SYN报文的连接请求后，它可以把ACK和SYN(ACK起应答作用，而SYN起同步作用)放在一个报文里来发送。但关闭连接时，当收到对方的FIN报文通知时，它仅仅表示对方没有数据发送给你了；但未必你所有的数据都全部发送给对方了，所以你可能未必会马上关闭SOCKET,也即你可能还需要发送一些数据给对方之后，再发送FIN报文给对方来表示你同意现在可以关闭连接了，所以它这里的ACK报文和FIN报文多数情况下都是分开发送的。 -
即时通讯中为什么大多使用UDP
首先,QQ并不是完全基于UDP实现。比如在使用QQ进行文件传输等活动的时候，就会使用TCP作为可靠传输的保证。使用UDP进行交互通信的好处在于，延迟较短，对数据丢失的处理比较简单。同时，TCP是一个全双工协议，需要建立连接，所以网络开销也会相对大。如果使用QQ语音和QQ视频的话，UDP的优势就更为突出了，首先延迟较小。最重要的一点是不可靠传输，这意味着如果数据丢失的话，不会有重传。因为用户一般来说可以接受图像稍微模糊一点，声音稍微不清晰一点，但是如果在几秒钟以后再出现之前丢失的画面和声音，这恐怕是很难接受的。 -
TCP做心跳检测网络情况
一、什么是心跳检测
判断对方（设备，进程或其它网元）是否正常动行，一般采用定时发送简单的通讯包，如果在指定时间段内未收到对方响应，则判断对方已经当掉。用于检测TCP的异常断开。
基本原因是服务器端不能有效的判断客户端是否在线也就是说，服务器无法区分客户端是长时间在空闲，还是已经掉线的情况。所谓的心跳包就是客户端定时发送简单的信息给服务器端告诉它我还在而已。
代码就是每隔几分钟发送一个固定信息给服务端，服务端收到后回复一个固定信息。如果服务端几分钟内没有收到客户端信息则视客户端断开。比如有些通信软件长时间不使用，要想知道它的状态是在线还是离线就需要心跳包，定时发包收包。
发包方可以是客户也可以是服务端，看哪边实现方便合理。一般是客户端。服务器也可以定时轮询发心跳下去。
二、心跳检测需要以下步骤：
1 客户端每隔一个时间间隔发送一个探测包给服务器
2 客户端发包时启动一个超时定时器
3 服务器端接收到检测包，应该回应一个包
4 如果客户机收到服务器的应答包，则说明服务器正常，删除超时定时器
5 如果客户端的超时定时器超时（n次），依然没有收到应答包，则说明服务器挂了 -
HTTP的几种请求方式以及适用情况
GET
GET请求会显示请求指定的资源。一般来说GET方法应该只用于数据的读取，而不应当用于会产生副作用的非幂等的操作中。
GET会方法请求指定的页面信息，并返回响应主体，GET被认为是不安全的方法，因为GET方法会被网络蜘蛛等任意的访问。
HEAD
HEAD方法与GET方法一样，都是向服务器发出指定资源的请求。但是，服务器在响应HEAD请求时不会回传资源的内容部分，即：响应主体。这样，我们可以不传输全部内容的情况下，就可以获取服务器的响应头信息。HEAD方法常被用于客户端查看服务器的性能。
POST
POST请求会 向指定资源提交数据，请求服务器进行处理，如：表单数据提交、文件上传等，请求数据会被包含在请求体中。POST方法是非幂等的方法，因为这个请求可能会创建新的资源或/和修改现有资源。
PUT
PUT请求会身向指定资源位置上传其最新内容，PUT方法是幂等的方法。通过该方法客户端可以将指定资源的最新数据传送给服务器取代指定的资源的内容。
DELETE
DELETE请求用于请求服务器删除所请求URI（统一资源标识符，Uniform Resource Identifier）所标识的资源。DELETE请求后指定资源会被删除，DELETE方法也是幂等的。
-
HTTPS建立连接的流程，证书有什么用，怎么解决中间人劫持攻击
Paste_Image.png
证书的作用：
1）认证用户和服务器，确保数据发送到正确的客户机和服务器；
2）加密数据以防止数据中途被窃取；
3）维护数据的完整性，确保数据在传输过程中不被改变。
解决中间人劫持攻击：双向验证；对SSL证书进行强校验（签名CA是否合法、证书是否是自签名、主机域名是否匹配、证书是否过期等） -
HTTP是怎么做的断点重传
对于断点续传，关键点是两个：
1.终端知道当前的文件和上一次加载的文件是不是内容发生了变化，如果有变化，需要重新从offset 0 的位置开始下载
2.终端记录好上次成功下载到的offset，告诉server端,server端支持从特定的offset 开始吐数据
数据结构和算法
- 排序算法：
package test;
import java.util.Random;
/**
*
* 排序算法类
*
*
* 排序算法的分类如下：
*
* 1.插入排序（直接插入排序、折半插入排序、希尔排序）；
*
* 2.交换排序（冒泡泡排序、快速排序）；
*
* 3.选择排序（直接选择排序、堆排序）；
*
* 4.归并排序；
*
* 5.基数排序。
*
*
*
* 关于排序方法的选择：
*
* (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
*
* 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
*
* (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；
*
* (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
*
*
*/
public class SortAlgorithm {
/**
* 初始化测试数组的方法
* @return 一个初始化好的数组
*/
public int[] createArray() {
Random random = new Random();
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
array[i] = random.nextInt(100) - random.nextInt(100);// 生成两个随机数相减，保证生成的数中有负数
}
System.out.println("==========原始序列==========");
printArray(array);
return array;
}
/**
* 打印数组中的元素到控制台
* @param source
*/
private void printArray(int[] data) {
for (int i : data) {
System.out.print(i + " ");
}
System.out.println();
}
/**
* 交换数组中指定的两元素的位置
* @param data
* @param x
* @param y
*/
private void swap(int[] data, int x, int y) {
int temp = data[x];
data[x] = data[y];
data[y] = temp;
}
/**
* 冒泡排序----交换排序的一种
* 方法:相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。
* 性能: 比较次数O(n^2),n^2/2；
* 交换次数O(n^2),n^2/4
*
* @param data 要排序的数组
* @param sortType 排序类型
* @return
*/
public void bubbleSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // 正排序，从小排到大
// 比较的轮数
for (int i = 1; i < data.length; i++) {
// 将相邻两个数进行比较，较大的数往后冒泡
for (int j = 0; j < data.length - i; j++) {
if (data[j] > data[j + 1]) {
// 交换相邻两个数
swap(data, j, j + 1);
}
}
}
} else if (sortType.equals("desc")) { // 倒排序，从大排到小
// 比较的轮数
for (int i = 1; i < data.length; i++) {
// 将相邻两个数进行比较，较大的数往后冒泡
for (int j = 0; j < data.length - i; j++) {
if (data[j] < data[j + 1]) {
// 交换相邻两个数
swap(data, j, j + 1);
}
}
}
} else {
System.out.println("您输入的排序类型错误！");
}
printArray(data);// 输出冒泡排序后的数组值
}
/**
*
* 直接选择排序法----选择排序的一种
*
* 方法:每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
*
* 性能:比较次数O(n^2),n^2/2
* 交换次数O(n),n
*
* 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。
*
* 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。
*
* @param data 要排序的数组
* @param sortType 排序类型
* @return
*/
public void selectSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // 正排序，从小排到大
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] > data[index]) {
index = j;
}
}
// 交换在位置data.length-i和index(最大值)两个数
swap(data, data.length - i, index);
}
} else if (sortType.equals("desc")) { // 倒排序，从大排到小
int index;
for (int i = 1; i < data.length; i++) {
index = 0;
for (int j = 1; j <= data.length - i; j++) {
if (data[j] < data[index]) {
index = j;
}
}
// 交换在位置data.length-i和index(最大值)两个数
swap(data, data.length - i, index);
}
} else {
System.out.println("您输入的排序类型错误！");
}
printArray(data);// 输出直接选择排序后的数组值
}
/**
*
* 插入排序
*
* 方法:将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。
*
* 性能:比较次数O(n^2),n^2/4
* 复制次数O(n),n^2/4
*
* 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。
*
* @param data 要排序的数组
*
* @param sortType 排序类型
*/
public void insertSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // 正排序，从小排到大
// 比较的轮数
for (int i = 1; i < data.length; i++) {
// 保证前i+1个数排好序
for (int j = 0; j < i; j++) {
if (data[j] > data[i]) {
// 交换在位置j和i两个数
swap(data, i, j);
}
}
}
} else if (sortType.equals("desc")) { // 倒排序，从大排到小
// 比较的轮数
for (int i = 1; i < data.length; i++) {
// 保证前i+1个数排好序
for (int j = 0; j < i; j++) {
if (data[j] < data[i]) {
// 交换在位置j和i两个数
swap(data, i, j);
}
}
}
} else {
System.out.println("您输入的排序类型错误！");
}
printArray(data);// 输出插入排序后的数组值
}
/**
* 反转数组的方法
*
* @param data 源数组
*/
public void reverse(int[] data) {
int length = data.length;
int temp = 0;// 临时变量
for (int i = 0; i < length / 2; i++) {
temp = data[i];
data[i] = data[length - 1 - i];
data[length - 1 - i] = temp;
}
printArray(data);// 输出到转后数组的值
}
/**
* 快速排序
*
* 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
*
* 步骤为：
*
* 1. 从数列中挑出一个元素，称为 "基准"（pivot），
*
* 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，
* 该基准是它的最后位置。这个称为分割（partition）操作。
*
* 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
*
* 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）
* 中，它至少会把一个元素摆到它最后的位置去。
*
* @param data 待排序的数组
* @param low
* @param high
*
* @see SortTest#qsort(int[], int, int)
*
* @see SortTest#qsort_desc(int[], int, int)
*/
public void quickSort(int[] data, String sortType) {
if (sortType.equals("asc")) { // 正排序，从小排到大
qsort_asc(data, 0, data.length - 1);
} else if (sortType.equals("desc")) { // 倒排序，从大排到小
qsort_desc(data, 0, data.length - 1);
} else {
System.out.println("您输入的排序类型错误！");
}
}
/**
* 快速排序的具体实现，排正序
*
* @param data
* @param low
* @param high
*/
private void qsort_asc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // 这个条件用来结束递归
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] > x) {
j--; // 从右向左找第一个小于x的数
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] < x) {
i++; // 从左向右找第一个大于x的数
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_asc(data, low, i - 1);
qsort_asc(data, i + 1, high);
}
}
/**
*
* 快速排序的具体实现，排倒序
*
* @param data
* @param low
* @param high
*/
private void qsort_desc(int data[], int low, int high) {
int i, j, x;
if (low < high) { // 这个条件用来结束递归
i = low;
j = high;
x = data[i];
while (i < j) {
while (i < j && data[j] < x) {
j--; // 从右向左找第一个小于x的数
}
if (i < j) {
data[i] = data[j];
i++;
}
while (i < j && data[i] > x) {
i++; // 从左向右找第一个大于x的数
}
if (i < j) {
data[j] = data[i];
j--;
}
}
data[i] = x;
qsort_desc(data, low, i - 1);
qsort_desc(data, i + 1, high);
}
}
/**
*
* 二分查找特定整数在整型数组中的位置(递归)
*
* 查找线性表必须是有序列表
*
* @paramdataset
* @paramdata
* @parambeginIndex
* @paramendIndex
* @returnindex
*/
public int binarySearch(int[] dataset, int data, int beginIndex, int endIndex) {
int midIndex = (beginIndex + endIndex) >>> 1; // 相当于mid = (low + high) / 2，但是效率会高些
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) {
return -1;
}
if (data < dataset[midIndex]) {
return binarySearch(dataset, data, beginIndex, midIndex - 1);
} else if (data > dataset[midIndex]) {
return binarySearch(dataset, data, midIndex + 1, endIndex);
} else {
return midIndex;
}
}
/**
*
* 二分查找特定整数在整型数组中的位置(非递归)
*
* 查找线性表必须是有序列表
*
* @paramdataset
* @paramdata
* @returnindex
*/
public int binarySearch(int[] dataset, int data) {
int beginIndex = 0;
int endIndex = dataset.length - 1;
int midIndex = -1;
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) {
return -1;
}
while (beginIndex <= endIndex) {
midIndex = (beginIndex + endIndex) >>> 1; // 相当于midIndex =(beginIndex + endIndex) / 2，但是效率会高些
if (data < dataset[midIndex]) {
endIndex = midIndex - 1;
} else if (data > dataset[midIndex]) {
beginIndex = midIndex + 1;
} else {
return midIndex;
}
}
return -1;
}
public static void main(String[] args) {
SortAlgorithm sortTest = new SortAlgorithm();
int[] array = sortTest.createArray();
System.out.println("==========冒泡排序后(正序)==========");
sortTest.bubbleSort(array, "asc");
System.out.println("==========冒泡排序后(倒序)==========");
sortTest.bubbleSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========倒转数组后==========");
sortTest.reverse(array);
array = sortTest.createArray();
System.out.println("==========选择排序后(正序)==========");
sortTest.selectSort(array, "asc");
System.out.println("==========选择排序后(倒序)==========");
sortTest.selectSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========插入排序后(正序)==========");
sortTest.insertSort(array, "asc");
System.out.println("==========插入排序后(倒序)==========");
sortTest.insertSort(array, "desc");
array = sortTest.createArray();
System.out.println("==========快速排序后(正序)==========");
sortTest.quickSort(array, "asc");
sortTest.printArray(array);
System.out.println("==========快速排序后(倒序)==========");
sortTest.quickSort(array, "desc");
sortTest.printArray(array);
System.out.println("==========数组二分查找==========");
System.out.println("您要找的数在第" + sortTest.binarySearch(array, 74) + "个位子。（下标从0计算）");
}
}
- 单向链表反转：
一、简介
经查阅，主要有两种方法实现链表反转，递归反转法和遍历反转法；
递归： 在反转当前结点之前先反转其后边的结点，即、从尾结点开始逆向反转各个节点的指针域指向；
遍历：从前往后反转各个结点的指针域的指向。
二、实现
定义一个结点类：
public class Node {
private int data; //数据域
private Node next; //指针域
public Node(int data) {
super();
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
递归反转：
public static Node reverse(Node head){
//如果是空链表或者尾结点
if (head==null||head.getNext()==null) {
return head;
}
//先反转后续结点
Node reversedHead=reverse(head.getNext());
//当前结点指针指向前一结点
head.getNext().setNext(head);
//令前一结点的指针域为null
head.setNext(null);
return reversedHead;
}
遍历反转：
public static Node reverse1(Node head){
if (head==null) {
return head;
}
//上一结点
Node pre=head;
//当前结点
Node cur=head.getNext();
//用于存储下一节点
Node tem;
//cur==null 即尾结点
while(cur!=null){
//下一节点存入临时结点
tem=cur.getNext();
//将当前结点指针指向上一节点
cur.setNext(pre);
//移动指针
pre=cur;
cur=tem;
}
head.setNext(null);
return pre;
}
- 怎么检测链表成环
方法一：首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。
例如这样的链表：A->B->C->D->B->C->D， 当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。
假设从链表头节点到入环点的距离是D，链表的环长是S。D+S是链表总节点数。那么算法的时间复杂度是0+1+2+3+….+(D+S-1) = (D+S-1)(D+S)/2 ， 可以简单地理解成 O(NN)。而此算法没有创建额外存储空间，空间复杂度可以简单地理解成为O(1)。
方法二：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。
这个方法在流程上和方法一类似，本质的区别是使用了HashSet作为额外的缓存。
假设从链表头节点到入环点的距离是D，链表的环长是S。而每一次HashSet查找元素的时间复杂度是O(1), 所以总体的时间复杂度是1*(D+S)=D+S，可以简单理解为O(N)。而算法的空间复杂度还是D+S-1，可以简单地理解成O(N)。
方法三：首先创建两个指针1和2（在Java里就是两个对象引用），同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
例如链表A->B->C->D->B->C->D，两个指针最初都指向节点A，进入第一轮循环，指针1移动到了节点B，指针2移动到了C。第二轮循环，指针1移动到了节点C，指针2移动到了节点B。第三轮循环，指针1移动到了节点D，指针2移动到了节点D，此时两指针指向同一节点，判断出链表有环。
此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。
package demo6;
import java.util.HashMap;
import demo6.LinkReverse2.Node;
/**
* 判断链表是否有环的方法
* @author mengfeiyang
*
*/
public class LinkLoop {
public static boolean hasLoop(Node n){
//定义两个指针tmp1,tmp2
Node tmp1 = n;
Node tmp2 = n.next;
while(tmp2!=null){
int d1 = tmp1.val;
int d2 = tmp2.val;
if(d1 == d2)return true;//当两个指针重逢时，说明存在环，否则不存在。
tmp1 = tmp1.next; //每次迭代时，指针1走一步，指针2走两步
tmp2 = tmp2.next.next;
if(tmp2 == null)return false;//不存在环时，退出
}
return true; //如果tmp2为null，说明元素只有一个，也可以说明是存在环
}
//方法2：将每次走过的节点保存到hash表中，如果节点在hash表中，则表示存在环
public static boolean hasLoop2(Node n){
Node temp1 = n;
HashMap<Node,Node> ns = new HashMap<Node,Node>();
while(n!=null){
if(ns.get(temp1)!=null)return true;
else ns.put(temp1, temp1);
temp1 = temp1.next;
if(temp1 == null)return false;
}
return true;
}
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
n5.next = n1; //构造一个带环的链表,去除此句表示不带环
System.out.println(hasLoop(n1));
System.out.println(hasLoop2(n1));
}
}
执行结果：
true
true
- 查找算法
二分查找算法
从n个元素中A0,A1....An-1中，找到要找到的元素x，最简单的方法是遍历n个元素，找到元素x则返回x的位置，这种算法的时间复杂度为O(n)。
如果这n个元素是有序的，我们不需要从头到尾遍历一遍就可以找到要查找的元素，可以使用二分法。二分查找的时间复杂度是O(lgn)
二分查找的前提是元素有序（一般是升序），基本思想是拿中间元素A[m]与要查找的元素x进行比较，如果相等，则已经找到，如果A[m]比x大，那么要找的元素一定在A[m]前边，如果A[m]比x小，那么要找的元素一定在A[m]后边。没进行一次查找，数组规模减半。反复将子数组规模减半，直到发现要查找的元素，或者当前子数组为空。
例如，在[1,2,3,4,5]中查找2
第一次找到的数字下标是(0+4)/2=2，找到的数字是3，3<2,要找的数字位置位于[0，2)之间
第二次找到的数字下标是(0+1)/2=0，找到的数字是1,1<2,要找的数字位于(0,1]之间
第三次找到的数字下标是(1+1)/2=1,找到数字2，返回找到的位置1.
如果这个时候找到的数字不是1，那么说明数组中没有要找的数字。
需要注意的点就是区间位置，既然A[m]不等于x，下一次肯定不是从m这个位置开始找的，而是以m+1作为下一个起始位置，或者m-1作为下一个开始位置
二分查找有两种实现方式，一种是递归实现，一种是非递归实现
直接上代码
package com.algorithm.tree;
import java.util.Arrays;
/**
* 二分查找
*
* @author chao
*
*/
public class BinarySearchTree {
/**
* 非递归二分查找
*
* @param num
* @param number
* @return
*/
public static int binarySearch(int num[], int number) {
if (num == null || num.length == 0) {
return -1;
}
int start, end, mid;
start = 0;
end = num.length - 1;
while (start <= end) {
mid = (start + end) / 2;
if (num[mid] == number)
return mid;
else if (num[mid] > number) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
/**
* 递归查找
*
* @param num
* @param number
* @return
*/
public static int RecursivebinarySearch(int num[], int start, int end, int key) {
int mid = (start + end) / 2;
if (num == null || num.length == 0 || key < num[start] || key > num[end]) {
return -1;
} else if (num[mid] > key) {
return RecursivebinarySearch(num, start, mid - 1, key);
} else if (num[mid] < key) {
return RecursivebinarySearch(num, mid + 1, end, key);
} else {
return mid;
}
}
public static void main(String[] args) {
int num[] = { 3, 5, 7, 9, 10 };
Arrays.sort(num);
System.out.println(binarySearch(num, 7));
System.out.println(binarySearch(num, 8));
System.out.println(RecursivebinarySearch(num, 0, num.length - 1, 7));
System.out.println(RecursivebinarySearch(num, 0, num.length - 1, 8));
}
}
- 贪心算法
一、定义 什么是贪心算法呢？所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似解。 贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每个子问题求解，得到每个子问题的局部最优解。
4.把每个子问题的局部最优解合成为原来问题的一个解。
实现该算法的过程：
从问题的某一初始状态出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素；
由所有解元素组合成问题的一个可行解；
二、例题分析
[活动安排问题] 活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。
设有n个活动的集合e={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si< fi。如果选择了活动i，则它在半开时间区间[si，fi]内占用资源。若区间[si，fi]与区间[sj，fj]不相交，则称活动i与活动j是相容的。也就是说，当si≥fi或sj≥fj时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
在下面所给出的解活动安排问题的贪心算法gpeedyselector中，各活动的起始时间和结束时间存储于数组s和f{中且按结束时间的非减序：．f1≤f2≤…≤fn排列。如果所给出的活动未按此序排列，我们可以用o(nlogn)的时间将它重排。
/**
* 活动时间安排
*/
@Test
public void testArrangeActivity() {
int[] start = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int[] end = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
List<Integer> results = arrangeActivity(start, end);
for (int i = 0; i < results.size(); i++) {
int index = results.get(i);
System.out.println("开始时间:" + start[index] + ",结束时间:" + end[index]);
}
}
/**
* 活动安排
*
* @param s 开始时间
* @param e 结束时间
* @return
*/
public List<Integer> arrangeActivity(int[] s, int[] e) {
int total = s.length;
int endFlag = e[0];
List<Integer> results = new ArrayList<>();
results.add(0);
for (int i = 0; i < total; i++) {
if (s[i] > endFlag) {
results.add(i);
endFlag = e[i];
}
}
return results;
}
[找零钱问题]假如老板要找给我99分钱，他有上面的面值分别为25，10，5，1的硬币数，为了找给我最少的硬币数，那么他是不是该这样找呢，先看看该找多少个25分的，诶99／25＝3，好像是3个，要是4个的话，我们还得再给老板一个1分的，我不干，那么老板只能给我3个25分的拉，由于还少给我24，所以还得给我2个10分的和4个1分。
@Test
public void testGiveMoney() {
//找零钱
int[] m = {25, 10, 5, 1};
int target = 99;
int[] results = giveMoney(m, target);
System.out.println(target + "的找钱方案:");
for (int i = 0; i < results.length; i++) {
System.out.println(results[i] + "枚" + m[i] + "面值");
}
}
public int[] giveMoney(int[] m, int target) {
int k = m.length;
int[] num = new int[k];
for (int i = 0; i < k; i++) {
num[i] = target / m[i];
target = target % m[i];
}
return num;
}
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
记得当时学算法的时候，就是这个例子，可以说很经典。
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量，即∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略?
贪心算法是很常见的算法之一，这是由于它简单易行，构造贪心策略简单。但是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于本例题中的3种贪心策略，都无法成立，即无法被证明，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。比如，求最小生成树的Prim算法和Kruskal算法都是漂亮的贪心算法。
［均分纸牌］有N堆纸牌，编号分别为1，2，…，n。每堆上有若干张,但纸牌总数必为n的倍数.可以在任一堆上取若干张纸牌,然后移动。移牌的规则为：在编号为1上取的纸牌，只能移到编号为2的堆上；在编号为n的堆上取的纸牌，只能移到编号为n-1的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如：n=4，4堆纸牌分别为：① 9 ② 8 ③ 17 ④ 6 移动三次可以达到目的：从③取4张牌放到④ 再从③区3张放到②然后从②去1张放到①。
输入输出样例：4
9 8 17 6
屏幕显示：3
算法分析：设a[i]为第I堆纸牌的张数（0<=I<=n），v为均分后每堆纸牌的张数，s为最小移动次数。
我们用贪心算法，按照从左到右的顺序移动纸牌。如第I堆的纸牌数不等于平均值，则移动一次（即s加1），分两种情况移动：
1．若a[i]>v，则将a[i]-v张从第I堆移动到第I+1堆；
2．若a[i]< v，则将v-a[i]张从第I+1堆移动到第I堆。为了设计的方便，我们把这两种情况统一看作是将a[i]-v从第I堆移动到第I+1堆，移动后有a[i]=v; a[I+1]=a[I+1]+a[i]-v.
在从第I+1堆取出纸牌补充第I堆的过程中可能回出现第I+1堆的纸牌小于零的情况。
如n=3，三堆指派数为1 2 27 ，这时v=10，为了使第一堆为10，要从第二堆移9张到第一堆，而第二堆只有2张可以移，这是不是意味着刚才使用贪心法是错误的呢？
我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张，第二堆剩下-7张，在从第三堆移动17张到第二堆，刚好三堆纸牌都是10，最后结果是对的，我们在移动过程中，只是改变了移动的顺序，而移动次数不便，因此此题使用贪心法可行的。
@Test
public void testMoveCard() {
//总共4堆
int heap = 4;
// int[] cards = {9, 8, 17, 6};
int[] cards = {10, 10, 20, 0};
int count = moveCards(cards, heap);
System.out.println("移动次数:" + count);
for (int i = 0; i < cards.length; i++) {
System.out.println("第" + (i + 1) + "堆牌数:" + cards[i]);
}
}
/**
* 均分纸牌
* @param cards
* @param heap
* @return
*/
public int moveCards(int[] cards, int heap) {
//总牌数
int sum = 0;
for (int i = 0; i < cards.length; i++) {
sum += cards[i];
}
//每堆平均牌数
int avg = sum / heap;
//移动次数
int count = 0;
for (int i = 0; i < cards.length; i++) {
if(cards[i] != avg) {
int moveCards = cards[i] - avg;
cards[i] -= moveCards;
cards[i + 1] += moveCards;
count++;
}
}
return count;
}
利用贪心算法解题，需要解决两个问题：
一是问题是否适合用贪心法求解。我们看一个找币的例子，如果一个货币系统有三种币值，面值分别为一角、五分和一分，求最小找币数时，可以用贪心法求解；如果将这三种币值改为一角一分、五分和一分，就不能使用贪心法求解。用贪心法解题很方便，但它的适用范围很小，判断一个问题是否适合用贪心法求解，目前还没有一个通用的方法，在信息学竞赛中，需要凭个人的经验来判断。
二是确定了可以用贪心算法之后，如何选择一个贪心标准，才能保证得到问题的最优解。在选择贪心标准时，我们要对所选的贪心标准进行验证才能使用，不要被表面上看似正确的贪心标准所迷惑，如下面的例子。
［最大整数］设有n个正整数，将它们连接成一排，组成一个最大的多位整数。
例如：n=3时，3个整数13，312，343，连成的最大整数为34331213。
又如：n=4时，4个整数7，13，4，246，连成的最大整数为7424613。
输入：n
N个数
输出：连成的多位数
算法分析：此题很容易想到使用贪心法，在考试时有很多同学把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种标准，我们很容易找到反例：12，121应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如12，123就是12312而非12123，这种情况就有很多种了。是不是此题不能用贪心法呢？
其实此题可以用贪心法来求解，只是刚才的标准不对，正确的标准是：先把整数转换成字符串，然后在比较a+b和b+a，如果a+b>=b+a，就把a排在b的前面，反之则把a排在b的后面。
@Test
public void testMaxNum() {
//有n个正整数，将它们连接成一排，组成一个最大的多位整数
//12112错误
//12121正解
// int[] nums = {12, 121};
int[] nums = {12, 123};
String result = maxNum(nums);
System.out.println("组成最大整数:" + result);
}
/**
* 根据给定的整数组成最大的多位数
* @param nums
*/
public String maxNum(int[] nums) {
String result = "";
for (int i = 0; i < nums.length; i++) {
String num1 = nums[i] + "";
for (int j = 1; j < nums.length; j++) {
String num2 = nums[j] + "";
if ((num1 + num2).compareTo(num2 + num1) < 0) {
int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
}
}
}
for (int i = 0; i < nums.length; i++) {
result += nums[i];
}
return result;
}
贪心算法所作的选择可以依赖于以往所作过的选择，但决不依赖于将来的选择，也不依赖于子问题的解，因此贪心算法与其他算法相比具有一定的速度优势。如果一个问题可以同时用几种方法解决，贪心算法应该是最好的选择之一。
