Home

gentlesnow

31 Mar 2019

【Algorithm】 000 算法基础

Basics Data Structure

String

s1 = str()
s2 = "shaunwei"
s2len = len(s2)
s2[-3:] # wei
s2[5:8] # wei
s3 = s2[:5] # shaun
s3 += 'wei' # shaunwei
# List in python is same as ArrayList in Java
s2list = list(s3)
s2[4] # 'n'
s2.index('w') # return 5, if not found, throw ValueError
s2.find('w') # return 5, if not found, return -1

在Python里面，没有StringBuffer 或者 StringBuilder。 但是在Python 里面处理String本身就比较 cheap。

String s1 = new String();
String s2 = "billyan";
int s2Len = s2.length();
s2.substring(4, 6); // return "ryan"
StringBuilder s3 = new StringBuilder(s2.substring(4, 8));
s3.append("bill");
String s2New = s3.toString(); // return 'ryanbill'
// convert String to char array
char[] s2Char = s2.roCharArray();
// char at index 4
char ch = s2.charAt(4); // return 'r'
// find index ar first
int index = s2.indexOf('r'); // return 4, if not found, return -1

StringBuffer 与 StringBuilder, 前者保证线程安全，后者不是，但单线程下效率高一些，一般使用 StringBuilder.

Linked List

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val;
        this.next = null;
    }
}

反转链表

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

    # in python next is a reversed word
    def reverse(self, head):
        prev = None
        while head:
            temp = head.next
            head.next = prev
            prev = head
            head = temp
        return prev

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

// iterative method
public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

// recursive method
public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode next = head.next;
    ListNode newHead = reverse(next);
    next.next = head;
    head.next = null;
    return newHead;
}

双向链表

class DListNode(object):
    def __init__(self, val):
        self.val = val
        self.prev = self.next = null

    def reverse(self, head):
        curt = None
        while head:
            curt = head
            head = curt.next
            curt.next = curt.prev
            curt.prev = head
        return curt

class DListNode {
    int val;
    DListNode prev, next;
    DListNode(int val) {
        this.val = val;
        this.prev = this.next = null;
    }
}

public DListNode reverse(DListNode head) {
    DListNode curr = null;
    while (head != null) {
        curr = head;
        head = curr.next;
        curr.next = curr.prev;
        curr.prev = head;
    }
    return curr;
}

class NodeCircle:
    def __init__(self, val):
        self.val = val
        self.next = None

    def has_circle(self, head):
        slow = head
        fast = head
        while (slow and fast):
            fast = fast.next
            slow = slow.next
            if fast:
                fast = fast.next
            if fast == slow:
                break
            if fast and slow and (fast == slow):
                return True
            else:
                return False

Binary Tree

Huffman Tree

Queue

Heap

Stack

Set

Map

Graph

Basics Sorting

Bubble Sort

public class Sort {
    public static void main(String[] args) {
        int[] unsortedArray = new int[]{6, 5, 3, 1, 8, 7, 2, 4};
        bubbleSort(unsortedArray);
        System.out.println("After sort: ");
        for (int item : unsortedArray) {
            System.out.print(item + " ");
        }
    }
    public static void bubbleSort(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            for (int num : nums) {
                System.out.print(num + " ");
            }
            for (int j = 1; j < len - i; j++) {
                if (nums[j - 1] > nums[j])
                    int temp = nums[j - 1];
                    nums[j - 1] = nums[j];
                    nums[j] = temp;
            }
        }
    }
}

Selection Sort

public class Sort {
    public static void main(String[] args) {
        int unsortedArray[] = new int[]{8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
        selectionSort(unsortedArray);
        System.out.println("After sort: ");
        for (int item : unsortedArray) {
            System.out.print(item + " ");
        }
    }

    public static void selectionSort(int[] array) {
        int len = array.length;
        for (int i = 0; i < len; i++) {
            for (int item : array) {
                System.out.print(item + " ");
            }
            System.out.println();
            int min_index = i;
            for (int j = i + 1; j < len; j++) {
                if (array[j] < array[min_index]) {
                    min_index = j;
                }
            }
            int temp = array[i];
            array[i] = array[min_index];
            array[min_index] = temp;
        }
    }
}

Insertion Sort

Merge Sort

Quick Sort

Heap Sort

Bucket Sort

Counting Sort

Radix Sort

Basics Algorithm

Divide and Conquer

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = new int[]{1,2,2,3,4,6,6,6,13,18};
        System.out.println(lowerBound(nums, 6)); // 5
        System.out.println(upperBound(nums, 6)); // 7
        System.out.println(lowerBound(nums, 7)); // 8
        System.out.println(upperBound(nums, 7)); // 7
    }

    /*
    * nums[index] >= target, min(index)
    */
    public static int lowerBound(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int lb = -1, ub = nums.length;
        while (lb + 1 < ub) {
            int mid = lb + (ub + lb) / 2;
            if (nums[mid] > target) ub = mid;
            else lb = mid;
        }
        return lb + 1;
    }

    /*
    * nums[index] <= target, max(index)
    */
    public static int upperBound(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int lb = -1, ub = nums.length;
        while (lb + 1 < ub) {
            int mid = lb + (ub + lb) / 2;
            if (nums[mid] > target) ub = mid;
            else lb = mid;
        }
        return ub;
    }
}

有 N 条绳子，它们的长度分别为 Li. 如果从它们中切割出K条长度相同的绳子的话，这K条绳子每条最长能有多长？答案保留到小数点后两位。

import java.io.*;
import java.util.*;

public lass Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        double[] nums = new double[n];
        for (int i = 0; i < n ; i++) {
            nums[i] = in.nextDouble();
        }
        System.out.printf("%.2f\n", Math.floor(solve(nums, k) * 100) / 100);
    }

    public static double solve(int[] nums, int K) {
        double lb = 0.00, ub = 10e5 + 0.01;
        for (int i = 0; i < 100; i++) {
            double mid = lb + (ub - lb) / 2;
            if (C(nums, mid, K)) lb = mid;
            else ub = mid;
        }
        return lb;
    }

    public static boolean C(int[] nums, int mid, int K) {
        int count = 0;
        for (num : nums) {
            count += Math.floor(num / mid);
        }
        return count >= K;
    }
}

九章算法

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

Math

Modulus - 求模运算

Fast Power - 快速幂运算

import java.util.*;

public class MyClass {
    public static long fastModPow(long x, long n, long mod) {
        long res = 1 % mod;
        while (n > 0) {
            if ((n & 1) != 0) {
                res = res * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }

    public static void main(String[] args) {
        if (args.length != 2 && args.length != 3) return;

        long x = Long.parseLong(args[0]);
        long n = Long.parseLong(args[1]);
        long mod = Long.MAX_VALUE;
        if (args.length == 3) {
            mod = Long.parseLong(args[2]);
        }
        System.out.println(fastModPow(x, n, mod));
    }
}

最大公约数(GCD, Greatest Common Divisor)

public class Solution{
    public static long gcd(long a, long b) {
        return (b == 0) ? a : gcd(b, a % b);
    }
}

扩展欧几里得算法

public class Solution{
    public static int gcd(int a, int b) {
        return (b == 0) ? a : gcd(b, a % b);
    }

    public static int[] gcdExt(int a, int b) {
        if (b == 0) {
            return new int[] {a, 1, 0};
        } else {
            int[] vals = gcdExt(b, a % b);
            int d = vals[0];
            int x = vals[2];
            int y = vals[1];
            y -= (a / b) * x;
            return new int[] {d, x, y};
        }
    }

    public static void main(String[] args) {
        int a = 4, b = 11;
        int[] result = gcdExt(a, b);
        System.out.printf("d = %d, x = %d, y = %d.\n", result[0], result[1], result[2]);
    }
}

Prime

import java.util.*;

public class Prime{
    //test if n is prime
    public static boolean isPrime(int n){
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return n != 1;
    }

    // enumerate all the divisor for n
    public static List<Integer> getDivisor(int n) {
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                result.add(i);
                if (i != n / i) {
                    result.add(n / i);
                }
            }
        }
        Collections.sort(result);
        return result;
    }

    // the number of prime factor, small to big
    public static Map<Integer, Integer> getPrimeFactor(int n) {
        Map<Integer, Integer> result = new HashMap<Integer, Integer>();
        for (int i = 0; i * i <= n; i++) {
            while (n % i == 0) {
                if (result.containsKey(i)) {
                    result.put(i, result.get(i) + 1);
                } else {
                    result.put(i, 1);
                }
                n = n / i;
            }
        }
        if (n != 1) {
            result.put(n, 1);
        }
        return result;
    }

    // sieve all the prime factor less equal than n
    public static List<Integer> sieve(int n) {
        List<Integer> prime = new ArrayList<Integer>();
        // flag id i is prime
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                prime.add(i);
                for (int j = 2 * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        return prime;
    }

    // sieve between [a, b)
    public static List<Integer> sieveSegment(int a, int b) {
        List<Integer> prime = new ArrayList<Integer>();
        boolean[] isPrime = new boolean[b];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i < b; i++) {
            if (isPrime[i]) {
                for (int j = i * 2; j < b; j += i) {
                    isPrime[j] = false;
                }
                if (i >= a) {
                    prime.add(i);
                }
            }
        }
        return prime;
    }

    public static void main(String[] args) {
        if (args.length == 1) {
            int n = Integer.parseInt(args[0]);
            if (isPrime(n)) {
                System.out.println("Integer " + n + " is prime.");
            } else {
                System.out.println("Integer " + n + " is not prime.");
            }
            System.out.println();

            List<Integer> divisor = getDivisor(n);
            System.out.print("Divisor of integer " + n + ":");
            for (int d : divisor) System.out.print(" " + d);
            System.out.println();
            System.out.println();

            Map<Integer, Integer> primeFactor = getPrimeFactor(n);
            System.out.println("Prime factor of integer " + n + ":");
            for (Map.Entry<Integer, Integer> entry : primeFactor.entrySet()) {
                System.out.println("prime: " + entry.getKey() + ", times: " + entry.getValue());
            }

            System.out.print("Sieve prime of integer " + n + ":");
            List<Integer> sievePrime = sieve(n);
            for (int i : sievePrime) System.out.print(" " + i);
            System.out.println();
        } else if (args.length == 2) {
            int a = Integer.parseInt(args[0]);
            int b = Integer.parseInt(args[1]);
            List<Integer> primeSegment = sieveSegment(a, b);
            System.out.println("Prime of integer " + a + " to " + b + ":");
            for (int i : primeSegment) System.out.print(" " + i);
            System.out.println();
        }
    }
}

Knapsack - 背包问题

Knapsack with repetition - 物品重复可用的背包问题

import java.util.*;

public class Backpack {
    // 01 backpack with small dataset(O(nW), W is small)
    public static int backpack(int W, int[] w, int[] v, boolean[] itemTake) {
        int N = w.length;
        int[][] dp = new int[N + 1][W + 1];
        boolean[][] matrix = new boolean[N + 1][W + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= W; j++) {
                if (w[i] > j) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
                    matrix[i][j] = (dp[i][j - w[i]] + v[i] > dp[i][j]);
                }
            }
        }

        //determine which items to take
        for (int i = N - 1, j = W; i >= 0; i--) {
            if (matrix[i][j]) {
                itemTake[i] = true;
                j -= w[i];
            } else {
                itemTake[i] = false;
            }
        }

        return dp[N][W];
    }

    // 01 backpack with big datasets(O(n\sigma{v}), W is very big)
    public static int backpack2(int W, int[] w, int[] v) {
        int N = w.length;
        // sum of value array
        int v = 0;
        for (int i : v) {
            V += i;
        }
        // initialize
        int[][] dp = new int[N + 1][V + 1];
        for (int[] i : dp) {
            // should avoid overflow for dp[i][j - v[i]] + w[i]
            Arrays.fill(i, Integer.MAX_VALUE >> 1);
        }
        dp[0][0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; <= V; j++) {
                if (v[i] > j) {
                    dp[i + 1][j] = dp[i][j];
                } else {
                    dp[i + 1][j] = Math.min(dp[i][j], dp[i][j - v[i]] + w[i]);
                }
            }
        }

        // search for the largest i dp[N][i] <= W
        for (int i = V; i >= 0; i--) {
            if (dp[N][i] <= W) {
                return i;
            }
        }

        return 0;
    }

    // repeated backpack
    public static int backpack3(int W, int[] w, int[] v) {

    }
}

Probability

Shuffle and Sampling - 随机抽样和洗牌

import java.util.*;
import java.util.Random;

class Shuffle{
    public static void shuffleCard(int[] cards) {
        if (cards == null || cards.length == 0) {
            return ;
        }
        Random rand = new Random();
        for (int i = 0; i < cards.length; i++) {
            int k = rand.nexrInt(i + 1);
            int temp = cards[i];
            cards[i] = cards[k];
            cards[k] = temp;
        }
    }
}

Random sampling - 随机抽样

import java.util.*;
import java.util.Random;

class Shuffle{
    public static int[] randomSample(int[] nums, int m) {
        if (nums == null ||nums.length == 0 || m <= 0) {
            return new int[]{};
        }

        int[] sample = new int[m];
        for (int i = 0; i < m; i++) {
            sample[i] = nums[i];
        }

        Random rand = new Random();
        for (int i = m; i < nums.length; i++) {
            int k = rand.nextInt(i + 1);
            if (k < m) {
                sample[k] = nums[i];
            }
        }

        return sample;
    }
}

Implementation and Test case

import java.util.*;
import java.util.Random;

public class Probability {
    public static void main(String[] args) {
        int[] cards = new int[10];
        for (int i = 0; i < 10; i++) {
            cards[i] = i;
        }
        // 100000 times test
        final int times = 100000;
        final int m = 5;
        int[][] count = new int[cards.length][cards.length];
        int[][] count2 = new int[cards.length][m];
        for (int i = 0; i < times; i++) {
            shuffleCard(cards);
            shuffleTest(cards, count);
            int[] sample = randomSample(cards, m);
            shuffleTest(sample, count2);
        }
        System.out.println("Shuffle cards");
        shufflePrint(count);
        System.out.println();
        System.out.println("Random sample");
        shufflePrint(count2);
    }

    /*
     * shuffle cards
     */
    public static void shuffleCard(int[] cards) {
        if (cards == null || cards.length == 0) return;

        Random rand = new Random();
        for (int i = 0; i < cards.length; i++) {
            int k = rand.nextInt(i + 1);
            int temp = cards[i];
            cards[i] = cards[k];
            cards[k] = temp;
        }
    }

    /*
     * random sample
     */
    public static int[] randomSample(int[] nums, int m) {
        if (nums == null || nums.length == 0 || m <= 0) return new int[]{};

        m = Math.min(m, nums.length);
        int[] sample = new int[m];
        for (int i = 0; i < m; i++) {
            sample[i] = nums[i];
        }

        Random random = new Random();
        for (int i = m; i < nums.length; i++) {
            int k = random.nextInt(i + 1);
            if (k < m) {
                sample[k] = nums[i];
            }
        }

        return sample;
    }

    /*
     * nums[i] = j, num j appear in index i ==> count[j][i]
     */
    public static void shuffleTest(int[] nums, int[][] count) {
        if (nums == null || nums.length == 0) return;

        for (int i = 0; i < nums.length; i++) {
            count[nums[i]][i]++;
        }
    }

    /*
     * print shuffle test
     */
    public static void shufflePrint(int[][] count) {
        if (count == null || count.length == 0) return;

        // print index
        System.out.print("   ");
        for (int i = 0; i < count[0].length; i++) {
            System.out.printf("%-7d", i);
        }
        System.out.println();
        // print num appear in index i in total
        for (int i = 0; i < count.length; i++) {
            System.out.print(i + ": ");
            for (int j = 0; j < count[i].length; j++) {
                System.out.printf("%-7d", count[i][j]);
            }
            System.out.println();
        }
    }
}

Bitmap

Til next time,
gentlesnow at 20:31

scribble
‹ ›