算法总结

作者: 进击的诺基亚 | 来源:发表于2019-04-09 22:34 被阅读0次

iOS算法总结-堆排序
iOS算法总结-冒泡排序
Apriori
基础查找算法分析
面试常问的排序算法
区块链难度调整算法总结
总结几种常用的安全算法
一文搞定十大经典排序算法（Java实现）
JVM垃圾回收算法
机器学习常用算法

基本排序算法
二叉树三种遍历方式
反转链表
反转链表的m到n个节点
股票买入卖出最大利润
全排列
去重的全排列
LRU
从一个数组中找出和为T的组合

基本排序算法

快速排序：
class Solution(object):
    def quickSort(self, arr, start, end):
        i = start
        j = end
        sp = arr[start]

        while i < j:
            while i < j and arr[j] >= sp:
                j -= 1
            if i < j:
                arr[i] = arr[j]
                i += 1
            while i < j and arr[i] <= sp:
                i += 1
            if i < j:
                arr[j] = arr[i]
                j -= 1

        arr[i] = sp
        if start < i-1:
            self.quickSort(arr, start, i - 1)
        if j+1 < end:
            self.quickSort(arr, j + 1, end)

二叉树遍历

前序遍历：
public void PreOrderTraversal(BitNode root) {
    if (root != null) {
        System.out.print(root.data);
        PreOrderTraversal(root.left);
        PreOrderTraversal(root.right);
    }
}

深度优先搜索：
public void DepthFirstSearch(BitNode root) {
    Stack<BitNode> nodeStack = new Stack<>();
    nodeStack.push(root);
    while (!nodeStack.empty()) {
        BitNode node = nodeStack.peek();
        System.out.print(root.data);
        nodeStack.pop();
        if (node.right != null) {
            nodeStack.push(node.right);
        }
        if (node.left != null) {
            nodeStack.push(node.left);
        }
    }
}

广度优先搜索：
public void BreadthFirstSearch(BitNode root) {
    Queue<BitNode> nodeQueue = new PriorityQueue<>();
    nodeQueue.add(root);
    while (!nodeQueue.isEmpty()) {
        BitNode node = nodeQueue.peek();
        System.out.print(root.data);
        nodeQueue.poll();
        if (node.left != null) {
            nodeQueue.add(node.left);
        }
        if (node.right != null) {
            nodeQueue.add(node.right);
        }
    }
}

打印出二叉树所有路径
class Solution {
    
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> result= new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        if (root!=null){
            paths(result, path, root, 0);
        }
        return result;
    }

    private void paths(List<List<Integer>> result, List<Integer> curPath,TreeNode root, int depth){
        curPath.add(depth, root.val);
        if (root.left == null && root.right == null){
            ArrayList<Integer> path=new ArrayList<>();
            for (int i=0; i<=depth; i++){
                path.add(curPath.get(i));
            }
            result.add(path);
            return;
        }

        if (root.left!=null){
            paths(result, curPath, root.left, depth+1);
        }
        if (root.right!=null){
            paths(result, curPath, root.right, depth+1);
        }

    }

}

层次遍历
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(root==null){
            return result;
        }
        Queue<TreeNode> queue=new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> list=new ArrayList<Integer>();
            for(int count=queue.size();count>0;count--){
                TreeNode tempNode=queue.poll();
                list.add(tempNode.val);
                if(tempNode.left!=null){
                    queue.add(tempNode.left);
                }
                if(tempNode.right!=null){
                    queue.add(tempNode.right);
                }
            }
            result.add(list);       
        }
        return result;
    }
}

反转链表

反转链表：
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev=null,curr=head,next=null;
        while(curr!=null){
            next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
        }
        return prev; 
    }
}

反转m到n个节点：
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode mPre=dummy,nNext=null,curr=null,next=null,prev=null;
        
        for(int i=0;i<m-1;i++){
            mPre=mPre.next;
        }
        curr=mPre.next;
        for(int i=0;i<=n-m;i++){
            next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
            nNext=next;
        }
        mPre.next.next=nNext;
        mPre.next=prev;      
        return dummy.next;
    }
}

股票买入卖出最大利润

全排列

全排列：
class Solution { 
     public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums==null || nums.length==0) {
            return res;
        }
        range(nums,0,nums.length,res);
        return res;
    }
    
    public void range(int[] nums, int start, int length, List<List<Integer>> res){
        if (start == length-1){
            res.add(toArrayList(nums));
            return;
        }
        for (int i=start;i<nums.length;i++){
            int temp=nums[start];
            nums[start]=nums[i];
            nums[i]=temp;
            
            range(nums,start+1,length,res);
            
            nums[i]=nums[start];
            nums[start]=temp;
        }
    }
    
    public List<Integer> toArrayList(int[] nums){
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++){
            list.add(nums[i]);
        }
        return list;
    }
}

去重的全排列：
class Solution {
     public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nums==null || nums.length==0) {
            return res;
        }
         Arrays.sort(nums);
        range(nums,0,nums.length,res);
        return res;
    }
        
    public void range(int[] nums, int start, int length, List<List<Integer>> res){
        if (start == length-1){
            res.add(toArrayList(nums));
            return;
        }
        for (int i=start;i<nums.length;i++){
            boolean isSwap=true;
            for(int j=start;j<i;j++){
                if(nums[j]==nums[i]){
                    isSwap=false;
                }
            }
            
            if(!isSwap){
                continue;
            }
            int temp=nums[start];
            nums[start]=nums[i];
            nums[i]=temp;
            
            range(nums,start+1,length,res);
            
            nums[i]=nums[start];
            nums[start]=temp;
        }
    }
    
    public List<Integer> toArrayList(int[] nums){
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<nums.length;i++){
            list.add(nums[i]);
        }
        return list;
    }
}

全组合
public static void combination(char[] chars) {
    if (chars == null) return;
    int length = chars.length;
    int count = 1 << length;
    for (int i = 1; i < count; i++) {
        for (int j = 0; j < length; j++) {
            if ((i & (1 << j)) > 0) {
                System.out.print(chars[j]);
            }
        }
        System.out.println();
    }
}

LRU

public class LRUCache {

    private Map<Integer, Integer> map;

    public LRUCache(int capacity) {
        map = new LinkedHashMap<Integer, Integer>(capacity, 1.0f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return this.size() > capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        map.put(key, value);
    }

}

多线程

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class Main {
    private final Lock lock = new ReentrantLock();// 通过JDK5中的Lock锁来保证线程的访问的互斥
    private int state = 0;//通过state的值来确定是否打印

    class ThreadA extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < 10; ) {
                try {
                    lock.lock();
                    while (state % 3 == 0) {// 多线程并发，不能用if，必须用循环测试等待条件，避免虚假唤醒
                        System.out.print("A");
                        state++;
                        i++;
                    }
                } finally {
                    lock.unlock();// unlock()操作必须放在finally块中
                }
            }
        }
    }

    public static void main(String[] args) {
        Main m = new Main();
        m.new ThreadA().start();
    }
}

iOS算法总结-堆排序
iOS算法总结-堆排序 iOS算法总结-堆排序
iOS算法总结-冒泡排序
iOS算法总结-冒泡排序 iOS算法总结-冒泡排序
Apriori
Apriori算法原理总结-刘建平FP Tree算法原理总结-刘建平PrefixSpan算法原理总结-刘建平用Sp...
基础查找算法分析
在之前学习了一些排序算法，得出了基础排序算法的总结。之后学习了一些查找算法，今天来对于基础的一些查找算法进行总结。...
面试常问的排序算法
排序算法总结排序是算法问题中的经典问题。为什么要总结排序算法呢？你懂的 : (假设所有的排序都是要求最终结果为：...
区块链难度调整算法总结
区块链难度调整算法总结
总结几种常用的安全算法
总结几种常用的安全算法
一文搞定十大经典排序算法（Java实现）
本文总结十大经典排序算法及变形，并提供Java实现。参考文章：十大经典排序算法总结（Java语言实现）快速排序算法...
JVM垃圾回收算法
Java基础：JVM垃圾回收算法 [toc] 参考：Java基础：JVM垃圾回收算法图解JVM垃圾回收算法总结：...
机器学习常用算法
机器学习常用算法总结如下：决策树随机森林算法逻辑回归SVM朴素贝叶斯K最近邻算法K均值算法Adaboost 算法神...