`算法`标签下的文章

未分类

淘汰算法LRU

T 发表于 2019-03-16 标签：算法

基于双链表实现LRU
原理：将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

public class LRUCache {  
	
	//缓存大小
    private int cacheSize;
    //缓存容器
    private Hashtable<K, CacheNode<K, V>> nodes;
    //当前缓存对象数量
    private int currentSize;
    //(实现双链表)链表头
    private CacheNode first;
    //(实现双链表)链表尾
    private CacheNode last;

    public LRUCache(int i) {
        currentSize = 0;
        cacheSize = i;
        nodes = new Hashtable(i);//缓存容器
    }

    /**
     * 链表节点
     *
     */
    private static class CacheNode<K,V> {
        CacheNode prev;
        CacheNode next;
        K key;
        V value;
        CacheNode() {
        }
    }

    public V get(K key){
        CacheNode<K, V> node = nodes.get(key);
        if(node!=null){
            moveToHead(node);
            return node.value;
        }else{

            return null;
        }
    }

    public void put(K key, V value){
        CacheNode<K, V> node = nodes.get(key);
        if(node == null){
            if(currentSize >= cacheSize){
                if(last != null){
                    nodes.remove(last.key);
                }
                removeLast();
            }else{
                currentSize++;
            }
            node = new CacheNode<>();
        }
        node.value=value;
        node.key=key;
        moveToHead(node);
        nodes.put(key, node);
    }

    private void removeLast(){
        if(last!=null){
            if(last.prev != null){
                last.prev.next = null;
            }else{
                first = null;
            }
            last = last.prev;
        }
    }

    private void moveToHead(CacheNode node){
        if(node == first){
            return;
        }

        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (last == node) {
            last = node.prev;
        }
        if (first != null) {
            node.next = first;
            first.prev = node;
        }
        first = node;
        node.prev = null;
        if (last == null) {
            last = first;
        }
    }
}

阅读剩下更多

未分类

链表相关算法

T 发表于 2019-03-15 标签：算法

1.删除链表指定节点

public class LinkedNode{
	public LinkedNode removeElement(LinkedNode head, int val){
		
		//先从头结点开始删
		while(head != null && head.val == val){
			head = head.next;
		}
		
		if(head==null){
			return head;
		}
		
		LinkedNode pre = head;
		while(pre.next!=null){
			if(pre.next.val==val){
				pre.next = pre.next.next;
			}else{
				pre = pre.next;
			}
		}
		return head;
	}
}

2.有序链表插入元素

public class LinkedNode{
	public void insertElement(LinkedNode node){
		LinkedNode pre = null;
		LinkedNode current = first;
		while(current!=null&&node.value<current.value){
			pre = current;
			current = current.next;
		}
		
		if(pre==null){
			first = node;
		}else{
			pre.next = node;
		}
		node.next = current;
	}
}

3.判断链表是否有环

public static <T> boolean isLoopList(ListNode<T> head){
	ListNode<T> slowPointer, fastPointer;

	slowPointer = fastPointer = head;
	while(fastPointer != null && fastPointer.next != null){
		slowPointer=slowPointer.next;
		fastPointer=fastPointer.next.next;
		if(slowPointer == fastPointer){
			return true;
		}
	} 
	return false;
}

阅读剩下更多

未分类

二叉树的一些操作

T 发表于 2015-06-18 标签：算法

反转二叉树

前一段时间国外某大牛面试Google被刷掉，原因是没有能够徒手写出来反转二叉树的代码，在网上看到了一个人的分析代码，特此记下来。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        return root;
    }
}

阅读剩下更多

未分类

经典排序算法

T 发表于 2012-03-16 标签：算法

本次介绍几种经典排序算法以及Java实现代码
1.冒泡排序
冒泡排序是属于相邻两两比较进行排序的一种，由于其实现是经过1到n-1轮排序，
通过比较相邻的两个数，大的向下继续与相邻的进行比较，直到找到正确的顺序位置。

public void bubbleSort(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {//比较轮次，经过n-1次比较
			for (int j = 0; j < a.length - 1 - i; j++) {//每次比较相邻的两个数，大的向后移动
				if (a[j] > a[j + 1]) {
					int temp = a[j + 1];
					a[j + 1] = a[j];
					a[j] = temp;
				}
			}
		}
	}

阅读剩下更多

未分类

二分查找Java实现

T 发表于 2012-03-11 标签：算法

这个栗子是用Java实现的二分查找

public class BinarySearch {

	public static int binarySearch(int array[], int number, int value) {
		int left = 0;
		int right = number - 1;
		while (left <= right) {
			int middle = left + ((right - left) >> 1);
			if (array[middle] > value) {
				right = middle - 1;
			} else if (array[middle] < value) {
				left = middle + 1;
			} else {
				return middle;
			}
		}
		return -1;
	}
}

阅读剩下更多

未分类

求最大子序列和的问题

T 发表于 2011-08-13 标签：算法

问题：给定（可能有负数）整数A1，A2，…，An，求∑Ak的最大值。（所有整数均为负数，则最大子序列和为0）。

1.穷举法
这种算法就是穷举所有的可能。for循环中的循环变量反映了Java中数组从0开始而不是从1开始这样一个事实。还有，本算法并不计算实际的子序列；实际的计算还要添加一些额外的代码。这个算法的运行时间为O(N3)

public static int maxSubSum1(int[] a) {
		int maxSum = 0;
		for(int i = 0; i < a.length; i++)
			for(int j = i; j < a.length; j++){
			int thisSum = 0;
			for(int k = i; k <= j; k++)
				thisSum += a[k];

			if(thisSum > maxSum)
				maxSum = thisSum;
		}
		return maxSum;
	}

阅读剩下更多