1.初等数论

• 算术基本定理：任何一个大于1的自然数N，如果N不为质数，都可以唯一分解成有限个质数的乘积：

  
  
  
  

  关于任意两个数x和y的最大公约数和最小公倍数：

  
  
  
  
  
  
  
  
  
  
  
  

  并且如果x整除y，则ji <= ki对于所有i都成立。

• 素数检查
  1）如果a是一个合数，则a必有一个小于等于根号a的真因子。
  2）如果a是一个合数，则a必有一个小于等于根号a的素因子
  3）埃拉托斯特尼筛法：
  首先划掉被2整除的；
  然后找到下一个整数，划掉所有可能被它整除的；
  继续，依次类推

public class SieveOfEratosthenes {
    
    public static void crossOff(boolean[] flags, int prime) {
        /* Cross off remaining multiples of prime. We can start with
         * (prime*prime), because if we have a k * prime, where k < prime,
         * this value would have already been crossed off in a prior
         * iteration. */        
        for (int i = prime * prime; i < flags.length; i += prime) {
            flags[i] = false;
        }
    }
    
    public static int getNextPrime(boolean[] flags, int prime) {
        int next = prime + 1;
        while (next < flags.length && !flags[next]) {
            next++;
        }
        return next;    
    }
    
    public static void init(boolean[] flags) {
        flags[0] = false;
        flags[1] = false;
        for (int i = 2; i < flags.length; i++) {
            flags[i] = true;
        }
    }
    
    public static int[] prune(boolean[] flags, int count) {
        int[] primes = new int[count];
        int index = 0;
        for (int i = 0; i < flags.length; i++) {
            if (flags[i]) {
                primes[index] = i;
                index++;
            }
        }
        return primes;
    }
    
    public static boolean[] sieveOfEratosthenes(int max) {
        boolean[] flags = new boolean[max + 1];
        int count = 0;
        
        init(flags);
        int prime = 2;
        
        while (prime <= Math.sqrt(max)) {
            count++;            
            crossOff(flags, prime);
            prime = getNextPrime(flags, prime);
            if (prime >= flags.length) {
                break;
            }
        }
        
        return flags; //prune(flags, count);
    }
    

2.概率

与 或 独立 互斥

3.题目

Q1.有个篮球框，下面两种玩法可任选一种。
玩法1：一次出手机会，投篮命中得分。
玩法2：三次出手机会，必须投中两次。
如果p是某次投篮命中的概率，则p的值为多少时，才会选择玩法1或玩法2？

Ans.思路：

• 玩法一赢的概率为p
• 玩法二赢的概率为三投三中 + 三投两中 = p^3 + 3(1-p)p^2
• p > p^3 + 3(1-p)p^2
  => (2p - 1) (p - 1) > 0
  => p < 0.5
  若p < 0.5 则应选择玩法1，p = 0 0.5 1时，两种都可以，否则选择玩法2.

Q2.三角形的三个顶点上各有一只蚂蚁。如果蚂蚁开始沿着三角形的边爬行，两只或三只蚂蚁撞在一起的概率有多大？假定每只蚂蚁会随机选一个方向，每个方向被选到的几率相等，而且三只蚂蚁的爬行速度相同。
类似问题：在n个顶点的多边形上有n只蚂蚁，求出这些蚂蚁发生碰撞的概率。

Ans.思路：

• 总的可能性：每个蚂蚁又可以有两种方向选择，所以总共有2^3 = 8种可能。不会发生碰撞的情况有两种：三只蚂蚁都选择同一个方向。因此发生碰撞的概率 = 1 - 1/4 = 3/4
• n只的情况 1 - 2(1/2)^n

Q3.给定直角坐标系上的两条线，确定这两条线会不会相交。

Ans.思路：

• 若两条线为同一条，则认为这两条线相交
• 若两条直线平行则必不相交
• 因此关键是判断是否为同一条或者是否平行

public class Line {
    static double epsilon = 0.000001;
    public double slope;
    public double yintercept;
    
    public Line(double s, double y) {
        slope = s;
        yintercept = y;
    }
    
    public void print() {
        System.out.print("y = " + slope + "x + " + yintercept);
    }
    
    public boolean intersect(Line line2) {
        return Math.abs(slope - line2.slope) > epsilon ||
               Math.abs(yintercept - line2.yintercept) < epsilon;
    }
};

Q4.编写方法，实现整数的乘法、减法和除法运算。只允许使用加号。

Ans.思路：

• 减法换为加法，加的另一个数为相反数，相反数可以通过累加-1最后与原数相加为0得到
• 乘法为多次累加同一个数
• 除法转换为累加次数，累加到目标值
• 关键是不要假设都是整数，某个数比某个数大

public class Question {
    /* Flip a positive sign to negative, or a negative sign to pos */
    public static int negate(int a) {
        int neg = 0;
        int d = a < 0 ? 1 : -1;
        while (a != 0) {
            neg += d;
            a += d;
        }
        return neg;
    }

    /* Subtract two numbers by negating b and adding them */
    public static int minus(int a, int b) {
        return a + negate(b);
    }

    /* Return absolute value */
    public static int abs(int a) {
        if (a < 0) {
            return negate(a);
        }
        else return a;
    }

    /* Multiply a by b by adding a to itself b times */
    public static int multiply(int a, int b) {
        if (a < b) {
            return multiply(b, a); // algo is faster if b < a
        }
        int sum = 0;
        for (int i = abs(b); i > 0; i--) {
            sum += a;
        }
        if (b < 0) {
            sum = negate(sum);
        }
        return sum;
    }

    /* Divide a by b by literally counting how many times b can go into
     * a. That is, count how many times you can add b to itself until you reach a. */
    public static int divide(int a, int b) throws java.lang.ArithmeticException {
        if (b == 0) {
            throw new java.lang.ArithmeticException("ERROR: Divide by zero.");
        }
        int absa = abs(a);
        int absb = abs(b);
        
        int product = 0;
        int x = 0;
        while (product + absb <= absa) { /* don't go past a */
            product += absb;
            x++;
        }
        
        if ((a < 0 && b < 0) || (a > 0 && b > 0)) {
            return x;
        } else {
            return negate(x);
        }
    }

Q5.在二维平面上，有两个正方形，请找出一条直线，能够将这两个正方形对半分。假定正方形的上下两条边与x轴平行。

Ans.思路：

• 这条线必须连接两个正方形中心点。必须注意特殊情况，比如中心点重合。

Q6.在二维平面上，有一些点，请找出经过点数最多的那条线。

Ans.思路：

• 只需遍历所有线段(n - 1)n/2，并用散列表统计出每条直线出现的次数。
• 斜率可能是初值无限大，需要单独记录
• 浮点数不能精确表示的问题，检查浮点数差值是否在某个极小值范围内。首先对斜率进行floor，即变成epsilon的整数倍。然后搜索时，搜索三个位置：floor, floor-epsilon, floor+epsilon

public class GraphPoint {
    public double x;
    public double y;
    public GraphPoint(double x1, double y1) {
        x = x1;
        y = y1;
    }
    
    public String toString() {
        return "(" + x + ", " + y + ")";
    }
}

public class Line {
    public static double epsilon = .0001;
    public double slope;
    public double intercept;
    
    private boolean infinite_slope = false;
    
    public Line(GraphPoint p, GraphPoint q) {
        if (Math.abs(p.x - q.x) > epsilon) { // if x�s are different
            slope = (p.y - q.y) / (p.x - q.x); // compute slope
            intercept = p.y - slope * p.x; // y intercept from y=mx+b
        } else {
            infinite_slope = true;
            intercept = p.x; // x-intercept, since slope is infinite
        }
    }
    
    public boolean isEquivalent(double a, double b) {
        return (Math.abs(a - b) < epsilon);
    }
    
    public void Print() {
        System.out.println("y = " + slope + "x + " + intercept);
    }
        
    public static double floorToNearestEpsilon(double d) {
        int r = (int) (d / epsilon);
        return ((double) r) * epsilon;
    }
    
    public boolean isEquivalent(Object o) {  
        Line l = (Line) o;
        if (isEquivalent(l.slope, slope) && isEquivalent(l.intercept, intercept) && (infinite_slope == l.infinite_slope)) {
            return true;
        }
        return false;
    }      
}

public class Question { 
    
    /* Count lines within an array of lines which are "equivalent" (slope and y-intercept are within an epsilon value) to a given line */
    public static int countEquivalentLines(ArrayList<Line> lines, Line line) {
        if (lines == null) {
            return 0;
        }
        
        int count = 0;
        for (Line parallelLine : lines) {
            if (parallelLine.isEquivalent(line)) {
                count++;
            }
        }
        return count;       
    }
    
    /* Check hashmap for lines that are equivalent. Note that we need to check one epsilon above and below the actual slope
     * since we're defining two lines as equivalent if they're within an epsilon of each other.
     */
    public static int countEquivalentLines(HashMap<Double, ArrayList<Line>> linesBySlope, Line line) {
        double key = Line.floorToNearestEpsilon(line.slope);
        int count = countEquivalentLines(linesBySlope.get(key), line);
        count += countEquivalentLines(linesBySlope.get(key - Line.epsilon), line);
        count += countEquivalentLines(linesBySlope.get(key + Line.epsilon), line);
        return count;
    }   
    
    /* insert line into hashmap */
    public static void insertLine(HashMap<Double, ArrayList<Line>> linesBySlope, Line line) {
        ArrayList<Line> lines = null;
        double key = Line.floorToNearestEpsilon(line.slope);
        if (!linesBySlope.containsKey(key)) {
            lines = new ArrayList<Line>();
            linesBySlope.put(key, lines);
        } else {
            lines = linesBySlope.get(key);
        }
        lines.add(line);
    }
    
    
    public static Line findBestLine(GraphPoint[] points) {
        Line bestLine = null;
        int bestCount = 0;
        HashMap<Double, ArrayList<Line>> linesBySlope = new HashMap<Double, ArrayList<Line>>();
        
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                Line line = new Line(points[i], points[j]);
                insertLine(linesBySlope, line);
                
                /* count lines that are equivalent to current line */
                int count = countEquivalentLines(linesBySlope, line);
                
                /* if better than current line, replace it */
                if (count > bestCount) {
                    bestLine = line;
                    bestCount = count;
                }
            }
        } 
        
        return bestLine;
    }   
    
    public static GraphPoint[] createPoints() {
        int n_points = 100;
        System.out.println("Points on Graph\n***************");
        GraphPoint[] points = new GraphPoint[n_points - 1];
        for (int i = 0; i < n_points / 2; i++) {
            GraphPoint p = new GraphPoint(i, 2.3 * ((double)i) + 20.0);
            points[i] = p;
            System.out.println(p.toString());
        }
        for (int i = 0; i < n_points / 2 - 1; i++) {
            GraphPoint p = new GraphPoint(i, 3.0 * ((double)i) + 1.0);
            points[n_points / 2 + i] = p;
            System.out.println(p.toString());
        }
        System.out.println("****************\n");
        return points;
    }

Q7.有些数的素因子只有3、5、7，请设计一个算法，找出其中第k个数。

Ans.思路：

• 一种直观的思路，从3开始，然后将列表中的数字与3/5/7相乘，找出下一个数。3（1 + 2 + ... + k - 1） = O(k^2)
• 同样的本质，换个思路：每次要将Ai加入列表时，就用某个临时表存放3Ai、5Ai和7Ai三个值。要产生Ai+1时，会搜索这个临时表

• 优化：按1常数因子将列表分组存放，那就只需检查3 、5和7倍数的第一个。求出最小的y后，将3y插入Q3、 5y插入Q5、 7y插入Q7，不过只有这些元素在其他列表中不存在时，才会将它们插入列表。
  例如从Q7中取出当前最小的7*suffix，此时肯定已经取出了3*suffix和5*suffix，处理3*suffix时，已经将7*3*suffix加入了Q7，处理5*suffix时，已经将7*5*suffix加入了Q7。所以此时只会将7 * 7 *suffix加入Q7。

  
  
  
  
  
  

    public static void printQueue(Queue<Integer> q, int x) {
        System.out.print(x + ": ");
        for (Integer a : q) {
            System.out.print(a / x + ", ");
        }
        System.out.println("");
    }
    
    public static int getKthMagicNumber(int k) {
        if (k < 0) {
            return 0;
        }
        int val = 0;
        Queue<Integer> queue3 = new LinkedList<Integer>();
        Queue<Integer> queue5 = new LinkedList<Integer>();
        Queue<Integer> queue7 = new LinkedList<Integer>();
        queue3.add(1);
        for (int i = 0; i <= k; i++) { // Include 0th iteration through kth iteration
            int v3 = queue3.size() > 0 ? queue3.peek() : Integer.MAX_VALUE; 
            int v5 = queue5.size() > 0 ? queue5.peek() : Integer.MAX_VALUE;
            int v7 = queue7.size() > 0 ? queue7.peek() : Integer.MAX_VALUE;
            val = Math.min(v3, Math.min(v5, v7));
            if (val == v3) {
                queue3.remove();
                queue3.add(3 * val);
                queue5.add(5 * val);
            } else if (val == v5) {
                queue5.remove();
                queue5.add(5 * val);
            } else if (val == v7) {
                queue7.remove();
            }
            queue7.add(7 * val);
        }
        return val;
    }

Q8.编写一个方法，洗一副牌。要求做到完美洗牌，换言之，这副牌52！种排列组合出现的概率相同。假设给定一个完美的随机数发生器。

Ans.思路：

• 假设前n-1个元素已经随机打乱了，那么用它来打乱n个元素可行吗？
  可以，只要第n个元素与数组中元素随机交换。
• 证明：前n-1取某一种排列的概率1/(n-1)!，第n个元素从n个位置中随机取一个位置的概率为1/n，两者相乘就是该排列的概率，就是1/n!。

• 那怎样确保所有这种排列都是不同的？前面(n-1)!排列是不同，再在后面接一个n也是不同的；
  现在可能相同的是，n同前面的某个数置换过后，将某个相同的数置换到第n的位置上。将n-1中某个数替换为n，放到n位置上，跟n-1个数的随机排列无本质区别，所以还是不同！

  
  

    /* Random number between lower and higher, inclusive */
    public static int rand(int lower, int higher) { 
        return lower + (int)(Math.random() * (higher - lower + 1));
    }   
    
    public static int[] shuffleArrayRecursively(int[] cards, int i) {
        if (i == 0) {
            return cards;
        }
        
        /* shuffle elements 0 through index - 1 */
        shuffleArrayRecursively(cards, i - 1);
        int k = rand(0, i);     
        
        /* Swap element k and index */
        int temp = cards[k];
        cards[k] = cards[i];
        cards[i] = temp;
        
        /* Return shuffled array */
        return cards;
    }
    
    public static void shuffleArrayInteratively(int[] cards) { 
        for (int i = 0; i < cards.length; i++) { 
            int k = rand(0, i);
            int temp = cards[k];
            cards[k] = cards[i];
            cards[i] = temp;
        } 
    }

Q9.编写一个算法，从大小为n的整数数组中随机选出m个整数。要求每个元素被选中的概率相同。

Ans.思路：

• 先取前m个数，然后i从m到n，每次取随机数(0, i)——k，如若k小于m，则将前面第k位置换为original[i]。
• 证明：跟第8题本质上是一样的。可以依据前面的算法，随机排列，然后返回前m个数。只不过前面m个数的随机排列不需要，另外，超过m的交换也不需要。

    /* pick M elements from original array.*/
    public static int[] pickMIteratively(int[] original, int m) {
        int[] subset = new int[m];
        
        /* Fill in subset array with first part of original array */
        for (int i = 0; i < m ; i++) {
            subset[i] = original[i];
        }
        
        /* Go through rest of original array. */
        for (int i = m; i < original.length; i++) {
            int k = rand(0, i);
            if (k < m) {
                subset[k] = original[i];
            }
        }
        
        return subset;
    }