1.链表的翻转
思路：
原地算法： 不借助外在的存储空间，首先使用头插法，在链表的头部插入节点，每一轮循环插入一个节
class Node(
int data;
Node next;
)
public void test(Node head){
Node temp = null; Node nextnode = null;
while(head != null){
nextnode = head.next;
head.next = temp;
temp = head;
head = nextnode;
}
} 借助外部结构： 使用栈来实现链表的翻转
public void test(Node head){
Stack stack = new Stack();
while(head != null){
stack.push(head.data);
head = head.next;
}
while(!stack.isEmpty()){
System.out.println(stack.pop());
}
} 2.判断链表是否有环,以及环的入口
思路：
使用Floyed算法来判断链表时候有环，即使用两个指针，以不同的速度前进，如果链表没有环，则两个指针不会相遇，如果有，则会在某一个时刻相遇
public Boolean test(Node head){
Node head1 = head ; Node head2 = head;
while(head != null){
head1 = head.next;
head2 = head.next.next;
if(head1 == head2)
return true;
}
return false;
} 思路：
对于环的入口，首先我们设置两各指针，一个快（兔子）一个慢（乌龟），假设当兔子和乌龟在环里相遇，则这个时候，兔子已经在环内跑了n圈，每圈的长度为L,假设乌龟在进行环之前跑了k的路，进入环之后，跑了x之后与兔子相遇，所以等式： 2（k + x) = k + nL + x => k + x = nL.
故： 乌龟从起点跑到循环入口的距离为： nL - x
又：此时将兔子的速度和乌龟一样，则兔子在圈内跑n-1圈之后，又会回到和乌龟相遇的点，只要在跑L-x的路，就可以回到下一轮循环的起点.
即：（n-1)L + (L-x) = nL - x
int FindLoop(Node head){
Node slow = head;
Node fast = head;
int loopExists = 0,count =0;
while(slow && fast && fast.next){
slow = slow.next;
fast = fast.next.next;
if(slow == fast ){
loopExists = 1;
break;
}
}
if(loopExists){
fast = fast.next;
while(slow != fast){
fast = fast.next;
couter++;
}
return counter;
}
return 0; //不存在环
} 3.栈来模拟队列
思路：
队列的特性是FIFO,栈的特性是FILO,因此使用栈来模拟队列，则使用两个栈来运行，栈1，栈2，当进行入队操作时，则往栈1中push元素，当进行出队的时候，将栈1中的元素出栈并压栈到栈2中，然后进行出栈操作，在完后的出队是，需要注意的是，先要判断栈2中时候有元素，若有有，则从栈2出栈，没有的话，则将栈1的元素出栈然后压栈到栈2，在进行出栈.
public void line(){
Stack stack1,stack2;
//入队
public void enqueue(int data){
stack1.push(data);
}
public void dequeue(){
if(!stack2.isEmpty()){
stack2.pop();
}else{
if(!stack1.isEmpty()){
while(!stack1.isEmpyt()){
stack2.push(stack.pop());
}
stack2.pop();
}else{
return null;
}
}
}
} 4.使用队列模拟栈
思路:
栈的特性是FILO,队列的特性是FIFO,使用；两个队列q1,q2， 当进行压栈操作时，对q1执行入队操作，当进行出栈操作时，首先将q1中前n-1个元素出队并入队到q2中，然后将q1中的元素出队，注意必须保证一个队列是空的，当进行压栈的时候，对有数据的队列进行入队。
public void test(){
Queue queue1 ,queue2;
static count = 0;
public void push(int data){
queue1.queue(data);
count ++;
}
public void pop(){
if(count == 0 ){
;
}else if(count == 1){
queue1.deque();
count--;
}else{
while(count > 1){
queue2.queue(queue1.deque());
count--；
}
queue1.deuque();
switch(queue1,queue2);
}
}
} 5.树的前序,中序遍历
思路：（非递归）
使用栈的数据结构来进行树的输出
class Node {
int value;
Node left;
Node right;
}
前序
public void print(Node root){
Stack<Node> stack = new Stack<Node>();
while(1){
while(root!= null){
System.out.println(root.value);
stack.push(root);
root = root.left;
}
if(stack.isEmpty() == null)
break;
root = stack.pop();
root = root.rigth;
}
}
中序
public void print2(Node root){
Stack<Node> stack = new Stack<Node>();
while(1){
while(root != null){
stack.push(root);
root = root.left;
}
if(stack.isEmpty == null)
break;
root = stack.pop();
System.out.println(root.value);
root = root.right;
}
} 6.分层遍历
思路：
使用队列存储节点
public void print3(Node root){
Queue<Node> Que = new Queue<Node>();
Que.queue(root);
Node temp = null;
while(!Que.isEmpyt()){
temp = Que.Deque();
System.out.println(temp.value);
if(temp.left != null)
Que.queue(temp.left);
if(temp.right != null)
Que.queue(temp.right);
}
} 7.从遍历顺序遍历二叉树
思路：
使用队列和栈
public void print4(Node root){
Stack<Node> Sta = new Stack<Node> ();
Queue<Node> Que = new Queue<Node> ();
Que.queue(root);
Node temp = null;
while(!Que.isEmpyt()){
temp = Que.Deque();
Stack.push(temp);
if(temp.right != null)
Que.queue(temp.right);
if(temp.left != null)
Que.queue(temp.left);
}
while(!Sta.isEmpty())
System.out.println(Sta.pop());
}
8.曲折遍历二叉树
思路：
使用两个栈解决问题
public void ZigZag(Node root){
Node temp;
int leftToRight = 1;
if(root == null) return;
Stack CurrentLevel = new Stack();
Stack NextLevel = new Stack();
CurrentLevel.push(root);
while(!CurrentLevel.isEmpty()){
temp = CurrentLevel.pop();
if(temp != null){
System.out.println(temp.value);
if(leftToRight == 1 ){
if(temp.left != null)
NextLevel.push(temp.left);
if(temp.right != null)
NextLevel.push(temp.right);
}else{
if(temp.right != null)
NextLevel.push(temp.right);
if(tmep.left != null)
NextLevel.push(temp.left);
}
}
if(CurrentLevel.isEmpty()){
leftToRight = 1- leftToRight;
swap(CurrentLevel,NextLevel);
}
}
}
9.线索二叉树的后继节点和前驱节点
思路：
为了节省每个Node节点的空间，引出线索二叉树，即每个Node有一个前驱节点，又有一个后继节点，根据不同的遍历方式，其前驱节点和后继节点也不同，
class Node{
int Value;
int tagleft;
int tagrihgt;
Node left;
Node right;
}
当tagleft,tagright为0时，表示没有前驱或后继节点，则left,right则分别指向其指定遍历顺序的前驱和后继节点.
10.二叉搜索树的节点的插入
思路：
如果没有指定插入的位置，则将新的节点插入到空闲位置，
如果有指定插入的位置，则进行比较，然后插入到合适的位置.
//没有任何插入约束
public void insert(Node root, Node value){
Node node = new Node(vlaue);
node.left = node.rihgt = null;
Queue Que = new Queue();
Que.queue(root);
Node temp = null;
if(!Que.isEmpty()){
tmep = Que.Deuqe();
if(temp.left == null){
temp.left = node;
break;
}else{
Que.queue(temp.left);
}
if(temp.right == null){
temp.right = node;
break;
}else{
Que.queue(temp.right);
}
}
}
//将元素插入到二叉查找树中
public void insert(Node root,Node value){
Node node = new Node(value);
Queue Que = new Queue();
Que.queue(root);
Node temp = null;
while(!Que.isEmpty()){
temp = Queue.Deque();
if(temp.value > node.value){
if(temp.left == null){
temp.left = node;
}else{
Que.queue(temp.left);
}
}else{
if(temp.right == null){
temp.right = node;
}else{
Que.queue(temp.right);
}
}else{
System.out.println(“已存在”);
break;
}
}
}
11.二叉搜索树删除节点
思路：
对于二叉树的节点，分3中情况：
当被删除的节点是叶子节点，则将其父节点的左右指针变为NULL;
当被删除的节点有一个子节点，则找出删除节点的父节点,把子节点直接设置成父节点的子节点；
当被删除的节点有两个子节点，则在左子树中找到数值最大的那个节点，并用它的键来替换删除节点的键.然后对失去的节点运行满足条件的规则.
12.平衡二叉树的平衡问题
思路：
平衡二叉树是一种为了防止单节点二叉树的查找问题，即二叉树中每层只有一个节点，这样在查找的的复杂度比较高，因为引出平衡二叉树，节点的左子树和右子树的高度之差小于等于1.
只需要把首个失去平衡的节点修复好之后，AVL树性质都会自动回复，我们把需要恢复平衡的节点记为X，因为有以下几种情况：
-
当向X的左侧节点的左子树插入元素，LL旋转
public void rotatell(Node x){
Node w = x.left;
x.left = w.right;
w.right = x;
x.height = max(height(x.left),height(x.right)) + 1;
w.height = max(height(w.left),height(w.right)) + 1;
}
2. 当向X的右侧节点的右子树插入元素，RR旋转
public void rotaterr(Node x){
Node w = x.right;
x.right = w.left;
w.left = x;
x.height = max(height(x.left),height(x.right)) + 1;
w.height = max(height(w.left),height(w.right)) + 1;
}
-
当向X的左侧子节点的右子树插入元素，即LR旋转,需要旋转两次
public void rotate(Node z ){
z.left = rotaterr(z.left);
rotatell(z.left);
}
-
当向X的右侧子节点的左子树插入元素，即RL旋转，需要旋转两次
public void rotate(Node z){
z.right = rotatell(z.right);
rotate(z.right);
}
13.堆化
思路：
堆：即节点要么大于子节点(大根堆),要么小于子节点(小根堆),可用于排序
堆的存储可以使用数组进行存储：
class head{
int count;
int capacity;
int heap_type;
int [] array;
}
堆化：向下渗透
void down(head h,int i){
int l,r,max,temp;
l = leftChild(h,i);
r = rightChild(h,i);
if(l != -1 && h.array[l] > h.array[i]){
max = l;
}else{
max = i;
}
if(r != -1 && h.array[r] > h.array[max]){
max = r;
}
if(max != i){
temp = h.array[i];
h.array[i] = h.array[max];
h.array[max] = temp;
down(h.max);
}
}
插入元素： 向上渗透
将新元素放入到堆的末尾，
自下而上的执行堆化，直至到达根节点为止.
public int insert(head h,int data){
if(h.count == h.capacity)
resizeHead(h)；
int i= h.count++;
while( i> 1 && data > h.array[(i-1)/2]){
h.array[i] = h.array[(i-1)/2];
i = (i-1)/2;
}
h.array[i] = data;
}
删除元素：
只需要删除掉根元素，这是标准（最大）二叉堆所需支持的唯一一种删除操作，删除根元素后，把数组里的最后一个元素复制到0号位置,也就是复制到根所在的位置.
public int delete(head h){
int data;
if(h.count == 0) return -1;
data = h.array[0];
h.array[0] = h.array[h.count-1];
h.count--;
down(h,0);
return data;
}
14.排序
14.1冒泡排序
public void sort(int[] array,int n){
for(int i = 0 ;i<n ;i++){
for(int j = 1; j < n ; j++){
int temp;
if(array[i] < array[j]){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
14.2选择排序
public void sort(int [] array,int n){
int min,temp;
for(int i = 0 ; i< n -1 ; i++){
min = i;
for(int j = i+1; j< n ;j++){
if(array[j] < array[min])
min = j;
}
temp = array[min];
array[min] = array[i];
array[i] = temp;
}
}
14.3插入排序
public void sort(int [] array,int n){
for(int i = 1 ;i< n ;i++){
int temp = array[i];
int j = i;
while(array[i-1] > temp && j >= 1){
array[i] = array[i+1];
j--;
}
array[j] = temp;
}
}
14.4希尔排序(递减增量排序)
public void sort(int [] arrray, int n){
for(int h = 1; h < n /3 ; h = 3*h+1);
for(; h > 0 ; h = h/3){
for(int i = h; i < n-1;i +=1){
v = array[i];
j = i;
while(j >= h && array[j-h] > v){
array[j] = array[j-h];
j-=h;
}
array[j] = v;
}
}
}
14.5快速排序
public void sort(int[] array,int low,int length){
int pivot;
if(hight > low){
pivot = Partition(array,low,hight);
sort（array,low,pivot-1);
sort(arrry,pivot+1,hight);
}
}
public int Partition(int[] array,int low, int high){
int left,right,pivot_item = array[low];
left = low;
right = high;
while(left < right){
while(array[left] <= pivot_item)
left++;
while(array[right] >= privot_item)
right--;
if(left < right)
swap(array,left,right);
}
array[low] = array[right];
array[right] = pivot_item;
return right;
}
14.6堆排序
public void sort(int[] array,int n){
Head head = new Head();
int old_size ,i ,temp;
buildHead(head,array,n);
old_size = head.count;
for(int i = n-1 ; i>0 ; i++){
temp = head.array[0];
head.array[0] = head.array[head.count-1];
(head.array[head.count-1]) = temp;
head.count--;
down(head,0);
}
head.count = old_size;
}
14.7计数排序
public void sort(int[] X,int n ,int[] Y,int K){
int [] Z = new int [K],i,j;
for(int i = 0;i< K,i++)
Z[i] = 0;
for(int j = 0;j<n;j++)
Z[X[j]] = Z[X[j]] + 1;
for(int i = 1; i< K; i++)
Z[i] = Z[i] + Z[i-1];
for(int j = n-1;j>=0;j--){
Y[Z[X[j]]-1] = X[j];
Z[X[j]] = Z[X[j]]-1;
}
}
京公网安备 11010502036488号