EASY题NEEDREVIEWD

一些算法模板

2017-04-01  本文已影响102人  DrunkPian0

递归的二分查找：

    int BinarySearchRecursion(int array[], int findData, int start, int end) {
        if (array == null || end <= 0)
            return -1;
        if (start > end)
            return -1;
        int mid = start + (end - start) / 2;
        if (array[mid] == findData)
            return mid;
        else if (findData < array[mid])
            return BinarySearchRecursion(array, findData, start, mid - 1);
        else
            return BinarySearchRecursion(array, findData, mid + 1, end);
    }

把终止条件写在最前面总是更清晰，不然就要这么写：

int BinSearch(int Array[],int low,int high,int key/*要找的值*/)
{
    if (low<=high)
    {
        int mid = (low+high)/2;
        if(key == Array[mid])
            return mid;
        else if(key<Array[mid])
            return BinSearch(Array,low,mid-1,key);
        else if(key>Array[mid])
            return BinSearch(Array,mid+1,high,key);
    }
    else
        return -1;
}

以下摘自:http://www.cnblogs.com/yueyebigdata/p/5126333.html
很乱，不知道怎么排版的。先简单放着。

3. UnionFind并查集模板

import java.util.HashMap;
import java.util.HashSet;


class UnionFind {
    HashMap<Integer, Integer> father = new HashMap();
    // 初始化
    UnionFind(HashSet<Integer> hashSet) {
        for (Integer now : hashSet) {
            father.put(now, now);
        }
    }
    // O(n)复杂度的find
//    public int find(int x) {
//        int parent = father.get(x);
//        while (parent != father.get(parent)) {
//            parent = father.get(parent);
//        }
//        return parent;
//    }
    // O(1)复杂度的find
    public int compressedFind(int x) {
        int parent = father.get(x);
        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }
        // 这里parent是他的最大祖先。那么，包括他以及中间的各种都直接设置为指道最大祖先。
        int temp = -1;
        int xFa = x;
        while (xFa != father.get(xFa)) {
            temp = father.get(xFa); // 因为要把xFa的祖先设置为最大祖先了，所以，得先把踏上一级father记录下来。
            father.put(xFa, parent);
            xFa = temp;
        }
        return parent;
    }
    // x，y有一条边。所以，如果他们的祖先不一样，那么就把他们随便谁和谁连起来
    public void union(int x, int y) {
        int xFa = compressedFind(x);
        int yFa = compressedFind(y);
        if (xFa != yFa) {
            father.put(xFa, yFa);
        }
    }
}

2. 二分

非递归的，while-loop

public static int binarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }

递归的，recursion

public class Solution {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        System.out.println(binarySearch(a, 0, a.length-1, 6));
    }
    public static int binarySearch(int[] nums, int start, int end, int target) {
        if (nums == null || nums.length == 0 || start > end) {
            return -1;
        }
        int mid = start + (end - start) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        return binarySearch(nums, start, end, target);
    }
}

1. 非递归的二叉树遍历：

前序遍历：一句话概括就是：先放进去root，然后放进去顶元素的right，然后放进去left。

    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (null == root) {
            return result;
        }
        stack.push(root);
        while (!stack.empty()) {
            TreeNode cur = stack.pop();
            result.add(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }

中序遍历：一句话总结概括：在进入while循环之前什么都不错，先把cur=root。进去之后，首先再用一个wihle一直往左走知道尽头，也一路的存入stack，然后把顶元素存入result，并且这时候把cur变成顶元素的右儿子。

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (null == root) {
            return result;
        }
        TreeNode cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            result.add(cur.val);
            cur = cur.right;
        }
        return result;
    }

后序遍历：一句话总结，首先用一个cur，和一个pre。进入之前把root存进去。然后，只要是上一个处理的是null，或者是pre.left,pre.right等于现在的cur，就先把left存进去，如果left空，存进去right。然后，如果上一次处理的是当前结点的left，那么说明该处理右边了，所以把right存进去，如果以上两个情况都不是，那么就要存结果了，并且pop。记住就是最后的时候pre = cur。

    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        // write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (null == root) {
            return result;
        }
        stack.push(root);
        TreeNode pre = null;
        TreeNode cur = root;
        while (!stack.empty()) {
            cur = stack.peek();
            if (pre == null || pre.left == cur || pre.right == cur) {
                if (cur.left != null) {
                    stack.push(cur.left);
                } else if (cur.right != null) {
                    stack.push(cur.right);
                }
            } else if (cur.left == pre) {
                if (cur.right != null) {
                    stack.push(cur.right);
                }
            } else {
                result.add(cur.val);
                stack.pop();
            }
            pre = cur;
        }
        return result;
    }

0. 下面一大堆大杂烩。

6移位操作

“>> 右移,高位补符号位” 这里右移一位表示除2
“>>> 无符号右移,高位补0”； 与>>类似
“<< 左移” 左移一位表示乘2，二位就表示4，就是2的n次方

6树的各种操作

import java.util.ArrayDeque;
import java.util.Queue;

public class Solution{

public static void main(String[] args){
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = null;
root.left.right =null;
root.right.left = null;
root.right.right =null;
levelOrder(root);
}
//树的遍历
//先序遍历
public static void preOrder(TreeNode root){
if(root == null) return;
System.out.println(root.val);
preOrder(root.left);
preOrder(root.right);
}
//层次遍历
public static void levelOrder(TreeNode root){

Queue<TreeNode> q = new ArrayDeque<TreeNode>();
q.add(root);
while( !q.isEmpty()){
TreeNode tmp = q.poll();
System.out.println(tmp.val);

if(tmp.left != null ) q.add(tmp.left);
if(tmp.right != null ) q.add(tmp.right);
}

}

//树的高度
public static int treeHeight(TreeNode root){
int high = 0;
if(root == null) return 0;
high = 1 + Math.max(treeHeight(root.left), treeHeight(root.right));

return high;
}
//二叉排序树
public static boolean isBST(TreeNode root, int left, int right){
if(root == null) return true;
return (left < root.val && root.val < right && isBST(root.left,left ,root.val) && isBST(root.right,root.val,right));

}
public static boolean isBST(TreeNode root){
return isBST(root,Integer.MIN_VALUE, Integer.MAX_VALUE);
}



}
class TreeNode{
TreeNode left;
TreeNode right;
int val;
TreeNode(int x){
val = x;
}
}

5快速排序

public static void qSort(int[] a, int low, int high){
if(low >= high) return;
int first = low, last = high, key = a[first];
while(first < last){
while(first < last && a[last] >= key) --last;
a[first] = a[last];
while(first < last && a[first] <= key) ++first;
a[last] = a[first];
}
a[first] = key;
qSort(a, low, first - 1);
qSort(a, last + 1, high);
}

4归并排序（背下来）。

public static void mergeSort(int[] a, int[] temp, int left, int right){
if(left >= right) return;
int mid = (left + right) / 2;

mergeSort(a, temp, left, mid);
mergeSort(a, temp, mid+1, right);

int p_final = left, p_left = left, p_right = mid + 1;
while(p_left <= mid || p_right <= right){

if(p_left <= mid && (p_right >right || a[p_left] <= a[p_right])){
temp[p_final++] = a[p_left++];
}
else{
temp[p_final++] = a[p_right++];
}
}
for ( int i = left; i <= right; i++){
a[i] = temp[i];
}

}

3. 二分函数（背下来）。

public static int binSearch(int[] a, int key){
int left = 0;
int right = a.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(key < a[mid]){
right = mid -1;
}
else if (key > a[mid]){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}

1. java的swap函数。交换

public  static  void  swap ( int [] data,  int  a,  int  b) {

int  t = data [a];      

        data [a] = data [b];      

        data [b] = t;      

}

2. 数组翻转函数（reverse）

2.向右移动数组k位（rotate array）；

public class Solution {
public void rotate(int[] nums, int k) {
if(nums.length <= 1){
return;
}
//step each time to move
int step = k % nums.length;
reverse(nums,0,nums.length - 1);//放到最后就是向左移
reverse(nums,step,nums.length - 1);
reverse(nums,0,step - 1);
}

//reverse int array from n to m
public void reverse(int[] nums, int n, int m){
while(n < m){
nums[n] ^= nums[m];
nums[m] ^= nums[n];
nums[n] ^= nums[m];
n++;
m--;
}
}
}

3. 字符串转成字符数组

s.toCharArray();

方法1：直接在构造String时转换。
char[] data = {'a', 'b', 'c'};
String str = new String(data);

方法2：调用String类的方法转换。
String.valueOf(char[] ch)

4.字符串翻转（String reverse）

new String

整数数组转化成字符串

Arrays.toString(a)

补充：我曾写过的快速排序和冒泡排序
quicksort
43125第一次循环后是23145, 4是pivot，4左边的都比它小，右边的都比它大。注意一定是j先往左走，不然结果不对。

public class Qksort{
    public static void sort(int array[] , int low , int high ){
        int i = low , j = high , index = array[i];
        if(low >= high )return ;
        while (i<j)
        {
            while(i<j && array[j]>= index)
                j-- ;
            if(i< j )
                array[i++] = array[j];
            while(i<j && array[i]<= index)
                i++ ;
            if(i<j )
                array[j--] = array[i];
        }
        array[i]= index ;
        sort(array, low , i - 1);
        sort(array, i + 1 , high );
    }
    public static void main(String args[]){
        int a[] = {4,3,1,2,5};
        sort(a, 0 , a.length - 1);
        for(int i = 0 ; i < a.length ; i++)
            System.out.println(a[i]);
    }

}

bubblesort

public class BBsort{
    private static void BBsort(int array[])
    {
        int temp ;
        int len = array.length;
        for(int i = 0 ; i < len-1 ; i++)
        {
            for(int j = 0 ; j < len - i - 1 ; j ++ )
            {
                if(array[j]>array[j+1])
                {
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp ;
                    
                }
            
            }
        }
    
    
    }
    
    public static void main(String args[])
    {
        int a[] = {4,3,1,5,6,1,2,4,8};
        BBsort(a);
        for(int i = 1 ; i < a.length ; i ++ )
            System.out.println(a[i]);
    
    }

}

另：
https://github.com/Yuelinghui/personNote/blob/master/10大基础实用算法.md

上一篇下一篇

猜你喜欢

热点阅读