算法
1.冒泡排序
//1.冒泡排序
public static int[] bubbleSort(int[] arr){
int temp;
//用来控制比较的次数为数组长度-1次
for (int j = 0; j <arr.length-1; j++) {
//用来比较和替换
for (int i = 0; i <arr.length-1-j ; i++) {
if(arr[i]>arr[i+1]){
temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
}
}
}
return arr;
}
2.二分查找法
public static int binarySearch(int a,int[] arr){
int start=0;
int end=arr.length-1;
while(start<=end){
//防止int溢出，所以才不用(end+start)/2
int mid=start+(end-start)/2;
if(a==arr[mid]){
return mid;
}else if(a<arr[mid]){
end=mid-1;
}else{
start=mid+1;
}
}
return -1;
}
3.插入排序
public static int[] insertSort(int[] arr){
//从数组的第二个数开始插入
for (int i = 1; i <=arr.length-1 ; i++) {
int tmp=arr[i];
//第一个要插入的位置
int index=i-1;
while(index>=0&&tmp<arr[index]){
arr[index+1]=arr[index];
index--;
}
//如果比要判断的元素大那就确定这个位置
arr[index+1]=tmp;
}
return arr;
}
4.选择排序
public static void selectionSort(int[] arr){
//如果数组为空或者数组长度小于2,直接退出方法
if(arr==null||arr.length<2){
return;
}
for (int i = 0; i <arr.length ; i++) {
//先把i当做数组中最小数的下标.
int minIndex=i;
//从i+1开始跟arr[minIndex]对比,如果比它小,minIndex就重新赋值
for(int j=i+1;j<arr.length;j++){
if(arr[j]<arr[minIndex]){
minIndex=j;
}
}
if(minIndex!=i) {
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
5.数据里有{1,2,3,4,5,6,7,8,9}，请随机打乱顺序，生成一个新的数组（请以代码实现）
public static int[] srand(int arr[]){
int b[]=new int[arr.length];
for (int i = 0; i <arr.length ; i++) {
//随机出此次循环原数组中哪个下标的元素要放入新数组
int index = (int) (Math.random() * (arr.length - i));
b[i]=arr[index];
//把原数组中tmp下标的元素跟数组中"最后"一位元素交换。
int temp=arr[arr.length-1-i];
arr[arr.length-1-i]=arr[index];
arr[index]=temp;
}
return b;
}
6.一个问题的最优解是什么意思
一般情况下，解决一个问题的算法流程，在时间复杂度的指标上，一定要尽可能的低，先满足了时间复杂度最低这个指标之后，使用最少的空间的算法流程，叫这个问题的最优解。
一般说最优解是忽略掉常数项这个因素的，因为这个层次只决定了实现层次的优化和考虑，而和怎么解决这个问题的思想无关。
7.如何不用额外变量交换两个数
public static boolean swap(int arr[],int i,int j){
//这种交换必须满足一个条件,交换的两个数不能指向同一个内存地址.
//因为交换相当于两个容器里东西交换,如果只有1个容器谈何交换.
//所以对于数组而言,下标i和j不能相等.
if(i!=j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
return true;
}
return false;
}
8.一个数组中只有一个出现了奇数次的数，找出这个数
思路：异或运算满足交换律和结合律。根据N^N=0 0^N=N 出现偶数次的数最后异或后肯定为0，如果只有1个出现奇数次的数，那最后数组所有元素的异或运算就是这个奇数的值。
public static void printOddTimesNum(int[] arr){
int eor=0;
for (int i = 0; i <arr.length ; i++) {
eor^=arr[i];
}
System.out.println("eor="+eor);
}
9.提取整形数最右侧的1
n&(~n+1)
public static void main(String[] args) {
//随机来个偶数,因为奇数的个位数肯定是1
int a=((int)(Math.random()*500000))<<1;
//提取整数最右侧的1
int b=a&(~a+1);
System.out.println(a);
System.out.println(Integer.toBinaryString(a));
System.out.println(Integer.toBinaryString(b));
}
10.一个数组中出现奇数次的两个数，其它数都是偶数次。
public static void printOddTimesNum2(int[] arr){
int eor=0;
for (int i = 0; i <arr.length ; i++) {
//假设a,b是这两个奇数,那么所有数组元素的异或运算结果其实就是a^b
eor^=arr[i];
}
//由于两数不相等所以eor=a^b不可能等于1,不可能等于1意味着肯定某一位至少出现了1个1.
//那就提取出最右侧的那个1,既然这一位是1了,因为这个数是a^b来的,那么a和b的这一位肯定是1个1和1个0
int newEor=eor&(~eor+1);
int onlyOne=0;
//我们把数组分成2派,一派这位数是1的(肯定包含a或b)，一派这个位数是0的(肯定包含b或a)
for (int i = 0; i <arr.length ; i++) {
//按位与运算能把数组分成2派,值不等于0,说明这个位为1
if((newEor&arr[i])!=0){
onlyOne^=arr[i];
}
}
//最后得出的结果onlyOne就是a或者b,再跟eor进行异或就能得到另一个数.假设onlyOne是a
//eor^onlyOne=a^b^a=a^a^b=0^b=b
System.out.println("the one="+onlyOne+"\tother one="+(onlyOne^eor));
}
11.统计一个数的二进制里有多少个1
public static int bigCount(int i){
int count=0;
// 011011010000
// 000000010000 1
// 011011000000
while(i!=0){
int rightOne=i&(~i+1);
count++;
i^=rightOne;
}
return count;
}
12.红黑树的性质：
1.节点要么是红色要么是黑色
2.根节点必须是黑色
3.叶子节点都是NIL是黑色
4.红色节点的两个子节点都是黑色
5.任意一个节点到它的每个叶子节点的路径都包含相同的黑色节点。
根据性质5推导出如果一个子节点为黑色，那这个节点肯定有两个子节点。
13.手写双向链表
package com.zcc.Algorithm;
public class MyLinkedList<E> {
private Node<E> first;
private int length;
private Node<E> last;
private static final class Node<E>{
private Node<E> pre;
private E elemnt;
private Node<E> next;
public Node(Node<E> pre, E elemnt, Node<E> next) {
this.pre = pre;
this.elemnt = elemnt;
this.next = next;
}
public Node() {
}
}
public boolean add(E e){
Node<E> l=last;
Node<E> newNode=new Node<>(last,e,null);
last=newNode;
if(l!=null){
l.next=last;
}else{
first=newNode;
}
length++;
return true;
}
public E get(int index){
if(index<=length/2){
Node<E> f=first;
for (int i = 0; i <index ; i++) {
f=f.next;
}
return f.elemnt;
}else{
Node<E> l=last;
for (int i = length-1; i >index ; i--) {
l=l.pre;
}
return l.elemnt;
}
}
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append("{");
Node<E> f=first;
for (int i = 0; i <= length-1; i++) {
sb.append(f.elemnt+",");
f=f.next;
}
sb.deleteCharAt(sb.length()-1);
sb.append("}");
return sb.toString();
}
public static void main(String[] args) {
MyLinkedList<Object> list = new MyLinkedList<>();
list.add("小明");
list.add("小李");
list.add("小王");
list.add("小程");
list.add("小宋");
list.add("小黄");
list.add("小刘");
list.add("小高");
System.out.println(list.get(5));
System.out.println(list.toString());
}
}
14.手写一个ArrayList
package com.zcc.juc;
import java.util.*;
import java.util.function.Consumer;
public class MyArrayList<E> {
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
private static final Object[] EMPTY_ELEMENTDATA={};
private static final int DEFAULT_CAPACITY = 10;
private Object[] elementData;
private int size;
protected transient int modCount = 0;
//如果是无参创建
public MyArrayList(){
this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//如果有参创建
public MyArrayList(int initialCapacity){
if(initialCapacity>0){
elementData=new Object[initialCapacity];
}else if(initialCapacity==0){
elementData=EMPTY_ELEMENTDATA;
}else{
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}
public boolean add(E e){
ensureCapacityInternal(size+1);
elementData[size++]=e;
return true;
}
public E remove(int index){
//先判断要删除的索引是否过界
if(index>=size)
throw new IndexOutOfBoundsException();
modCount++;
E oldElement = get(index);
int numMoved=size-index-1;
System.arraycopy(elementData,index+1,elementData,index,numMoved);
elementData[--size]=null;
return oldElement;
}
public E get(int index){
//先判断要删除的索引是否过界
if(index>=size)
throw new IndexOutOfBoundsException();
return (E)elementData[index];
}
private void ensureCapacityInternal(int minCapacity) {
//先判断elementData是不是还是默认的数组
if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
minCapacity=DEFAULT_CAPACITY;
}
modCount++;
//如果要求最小容量减去数组长度>0就要扩容
if(minCapacity-elementData.length>0){
grow(minCapacity);
}
}
//扩容
private void grow(int minCapacity) {
//旧数组长度
int oldCapacity=elementData.length;
//新数组长度为原来的1.5倍
int newCapacity=oldCapacity+(oldCapacity>>1);
//如果是初始化数组长度的话 新数组长度就=要求最小长度
if(newCapacity-minCapacity<0){
newCapacity=minCapacity;
}
elementData= Arrays.copyOf(elementData,newCapacity);
}
private class Itr implements Iterator<E>{
int cursor;
int lastRet=-1;
int expectedModCount=modCount;
public Itr() {
}
@Override
public boolean hasNext() {
return cursor!=size;
}
@Override
public E next() {
checkForModification();
int i=cursor;
//如果游标大于等于数组长度就抛出异常
if(i>=size){
throw new NoSuchElementException();
}
Object[] elementData = MyArrayList.this.elementData;
//如果游标大于数组的长度
if(i>=elementData.length){
throw new ConcurrentModificationException();
}
cursor=i+1;
return (E)elementData[lastRet=i];
}
@Override
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForModification();
try {
MyArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
//
private void checkForModification() {
if(expectedModCount!=modCount){
throw new ConcurrentModificationException();
}
}
}
@Override
public String toString() {
Iterator<E> it=new Itr();
if (! it.hasNext())
return "[]";
StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
E e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (! it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
}
}