Count Primes leetcode

Description:

Count the number of prime numbers less than a non-negative number, n.

厄拉多塞筛法(Sieve of Eeatosthese):
从第一个质数开始 把所有他的倍数都去掉, 那么下一个没有被去掉的肯定是质数, 依次循环到sqrt(n)

public class Solution {
    public int countPrimes(int n) {
        if(n <= 2) {
            return 0;
        }
        boolean[] map = new boolean[n];
        for (int i = 2; i <= Math.sqrt(n); i++) {
            //如果n=100, 那么只需要递加到10就可以, 之后的11* 11 > 100, 而11*(2到10)都已经在2到10时候剪去过了
            if (map[i] == false) {
                for (int j = i + i; j < n; j += i) {
                    map[j] = true;
                }
            }
        }
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (map[i] == false) {
                count++;
            } 
        }
        return count;
    }
}

Excel Sheet Column Title leetcode

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

public class Solution {
    public String convertToTitle(int n) {
        StringBuilder res = new StringBuilder();
        while (n > 0) {
            n--;
            char tem = (char) (n % 26 + 'A');
            res.append(tem);
            n = n / 26;
        }
        return res.reverse().toString();
    }
}

Max Points on a Line leetcode

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
给一个2d的平面, 所给的数据结构point代表一个点, 让找一条点最多的直线. 
对于一个点来说斜率相同的就在一条直线上, 所以遍历所有点i, 对于每个点再遍历一次, 得到所有的斜率存入hashmap key是斜率 value是此斜率上的点数, 如果key已经存在的话就value + 1 不存在就给value赋值2(一条线有两个点) 这里要注意因为遍历可能会出现跟i点相同的点(x, y 值都相同),对于这样的点他存在在i为起始的所有直线上 所以我们维护一个same来记录这样的点的个数.
最后value中的最大值加上same的个数就是每个i点的最多直线数目 比较每个i点得到最后的最多直线
注意: 第二次遍历不用从0开始遍历 直接从i开始遍历就可以 (后面的点就不用太回头看已经扫描过得点)因为如果此点和前边的点组成的线是最多的点 那么前边已经遍历过了
因为会出现slop = 0 或者slop = 无穷大 但是因为slop是double型数 所有的0 不相等 所以单独拿出来讨论

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        int max = 1;
        for (int i = 0; i < points.length; i++) {
            HashMap<Double, Integer> hash = new HashMap<Double, Integer>();
            int localmax = 1;//最少一个点
            int same = 0;
            double slop = 0.0;
            for (int j = i + 1; j < points.length; j++) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) {
                    same++;
                    continue;
                } 
                if (points[j].y == points[i].y) {
                    slop = 0.0;
                } else if (points[j].x == points[i].x) {
                    slop = (double) Integer.MAX_VALUE;
                } else {
                    slop = (double) (points[j].y - points[i].y) / (double)(points[j].x - points[i].x);
                }
                if (hash.containsKey(slop)) {
                    hash.put(slop, hash.get(slop) + 1);
                } else {
                    hash.put(slop, 2);
                }
            }
            for (Integer value : hash.values()) {
                localmax = Math.max(localmax, value);
            }
            localmax += same;
            max = Math.max(localmax, max);
        }
        return max;
    }
}

Valid Number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

要满足的情况:

对于一个小数点:

1.前边不能出现过小数点或者exp 2.不能单独存在(.) 3.如果他是0位 后边必须是数字 4. 如果是最后一位前边也必须是数字

对于 e 或者E

1. 不能前边存在exp 2. 不能是最后一位或者第一位 3.前一位必须是数字或者'.' 4. 后一位必须是数字或者加减号

对于加减号:

1.不能是最后一位 2. 如果不是第一位的话能把么前边必须是e 或者E 3.下一位必须是数字或者'.'

public class Solution {
    public boolean isNumber(String s) {
        if (s == null) {
            return false;
        }
        s = s.trim();
        if (s.length() == 0) {
            return false;
        }
        boolean dot = false;
        boolean exp = false;
        for (int i = 0; i < s.length(); i++) {
            switch(s.charAt(i)) {
                case '.':
                    if ( dot|| exp|| ((i==0||!(s.charAt(i-1)>='0'&&s.charAt(i-1)<='9')) 
                    && (i==s.length()-1||!(s.charAt(i+1)>='0'&&s.charAt(i+1)<='9')))){
                        return false;
                    }
                    dot = true;
                    break;
                case 'e':
                case 'E':
                    if (i == 0 || i == s. length() - 1|| exp|| !((s.charAt(i - 1) >= '0' && s.charAt(i - 1) <= '9')|| s.charAt(i - 1) == '.')|| !((s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') || s.charAt(i + 1) == '+' || s.charAt(i + 1) == '-' )) {
                        return false;
                    }
                    exp = true;
                    break;
                case '+':
                case '-':
                    if ((i > 0 && s.charAt(i - 1) != 'e' && s.charAt(i - 1) != 'E') || i == s.length() - 1 || !((s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') || s.charAt(i + 1) == '.')) {
                        return false;
                    }
                    break;
                case '0':
                case '1':
                case '2':
                case '3':
                case '4':
                case '5':
                case '6':
                case '7':
                case '8':
                case '9':
                    break;
                default://对于其他情况 如字母空格
                return false;
            }
        }
        return true;
    }
}

Sqrt(x) leetcode

Implement int sqrt(int x).
注意这道题是返回int 的平方根 所以:

sqrt(3) = 1

sqrt(4) = 2

sqrt(5) = 2

sqrt(10) = 3

用二分法来判定 逐步找到平方根, 但是要注意的是只要符合 mid^2 <= x < (mid + 1)^2 那么mid就是x的平方根.

另外要注意的是mid^2可能溢出 所以用x/mid >= mid的形式来表示

时间复杂度是O(log(x)) 空间是O(1)

public class Solution {
    public int mySqrt(int x) {
        if (x < 0) {
            return -1;
        } else if (x == 0) {
            return 0;
        }
        int left = 1;
        int right = x;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (x / mid >= mid  && x / (mid + 1) < mid + 1 ) {
                return mid;
            } else if (x / mid < mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return 0;
    }
}

Add Binary leetcode

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

从低位开始相加, 每得出一位的结果添加到result里 最后得到的result是低位在前边 所以要reverse一下.

只遍历了一次 时间复杂度是O(max(m,n)) 空间复杂度也是O(max(m,n))

public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.length() == 0) {
            return b;
        }
        if (b == null || b.length() == 0) {
            return a;
        }
        int next = 0;
        int digit;
        StringBuilder res = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        while (i >= 0 && j>=0) {
            digit = a.charAt(i) - '0' + b.charAt(j) - '0' + next;
            next = digit / 2;
            digit = digit % 2;
            res.append(digit);
            i--;
            j--;
        }
        while (i >= 0) {
            digit = a.charAt(i) - '0' + next;
            next = digit / 2;
            digit = digit % 2;
            res.append(digit);
            i--;
        }
        while (j >= 0) {
            digit = b.charAt(j) - '0' + next;
            next = digit / 2;
            digit = digit % 2;
            res.append(digit);
            j--;
        }
        if (next > 0) {
            res.append(next);
        }
        return res.reverse().toString();
    }
}

Plus One leetcode

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

从数组最后一位开始检查, 让i位加上进位 如果= 10 那么继续进一位.  如果不等于10那么就不往前进位了 直接跳出.

如果到i = 0时候还进位没有跳出 说明这时候遇到的数组内全是9 所以需要建立一个新数组 长度为当前长度+1 (99-->100 , 999-->1000) 并且让数组的第0位为1 其它位为0

扫描一遍 复杂度O(n) 如果不new新数组 空间O(1) 新数组就变成了O(n)

public class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) {
            return digits;
        }
        int next = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i] += next;
            if (digits[i] == 10) {
                digits[i] = 0;
            } else {
                return digits;
            }
        }
        int [] res = new int[digits.length + 1];
        res[0] = 1;//只有全是9时候才需要new一个新数组 新数组存储1000...
        return res;
    }
}

Multiply Strings leetcode

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note: The numbers can be arbitrarily large and are non-negative.

就是把字符所描述的数字相乘 直接乘法就数值太大可能溢出

建立一个m + n长度的数组 int[] tem99*99 也只是4位数 所以长度是两个长度的和

对于一个乘法 123* 45 结果的第0位是 num1的第0位与num2第0位 3* 5 % 10的结果 第1位是num1第一位和num2 的0位 2*5 + num1第0位和num2第一位4*3 的加和 再加上3*5 /10

对于num1 num2 遍历 每次i位和j位乘积都存储到 数组的第[i + j]上 

对于tem[i] tem[i] % 10 要贡献给结果的第i位 tem[i]/10 要贡献给i+ 1

最后可能tem的最高位有0 (10 * 10 只有3 位数 99 * 99 是四位数) 所以要把0 去除

时间O(m * n) 空间 O(m + n)

public class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        int[] list = new int[num1.length() + num2.length()];
        StringBuilder sb1 = new StringBuilder(num1).reverse();
        StringBuilder sb2 = new StringBuilder(num2).reverse();
        for (int i = 0; i < sb1.length(); i++) {
            for (int j = 0; j < sb2.length(); j++) {
                int m = sb1.charAt(i) - '0';
                int n = sb2.charAt(j) - '0';
                list[i + j] += m * n;
            }
        }
        int next = 0;
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < list.length; i++) {
            int tem = list[i] + next;
            next = tem / 10;
            res.insert(0, tem % 10);
        }
        while (res.length() > 1 && res.charAt(0) == '0') {//除去前边的0(由于建立tem的长度可能大于最后长度)

            res.deleteCharAt(0);
        }
        return res.toString();
    }
}

Reverse Integer leetcode

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

"越是简单的题目越要注意细节，一般来说整数的处理问题要注意的有两点，一点是符号，另一点是整数越界问题。"

这道题比较简单 但是简单题就是考细节. 注意Integer.MIN_VALUE的绝对值是比Integer.MAX_VALUE大1的，所以经常要单独处理.

public class Solution {
    public int reverse(int x) {
        if (x == Integer.MIN_VALUE) {
            return 0;
        }
        int num = Math.abs(x);
        int res = 0;
        while (num != 0) {
            if (res > (Integer.MAX_VALUE - num % 10) / 10) {
                return 0;
            }//防止res溢出
            res = res * 10 + num % 10;
            num /= 10;
        }
        if (x > 0) {
            return res;
        } else {
            return -res;
        }
    }
}

Permutation Sequence leetcode

The set [1,2,3,…,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

题解：from http://www.cnblogs.com/springfor/p/3896201.html

发现数学规律。

首先先捋捋这道题要干啥，给了我们n还有k，在数列 1，2，3，... , n构建的全排列中，返回第k个排列。

题目告诉我们：对于n个数可以有n!种排列；那么n-1个数就有(n-1)!种排列。

那么对于n位数来说，如果除去最高位不看，后面的n-1位就有 (n-1)!种排列。

所以，还是对于n位数来说，每一个不同的最高位数，后面可以拼接(n-1)!种排列。

所以你就可以看成是按照每组(n-1)!个这样分组。 

利用 k/(n-1)! 可以取得最高位在数列中的index。这样第k个排列的最高位就能从数列中的index位取得，此时还要把这个数从数列中删除。

然后，新的k就可以有k%(n-1)!获得。循环n次即可。

 同时，为了可以跟数组坐标对其，令k先--。

时间上总共需要n个回合，而每次删除元素如果是用数组需要O(n),所以总共是O(n^2)

public class Solution {
    public String getPermutation(int n, int k) {
        k = k-1;//为了使k的值对应num数组的坐标
        ArrayList<Integer> num = new ArrayList<Integer>();
        for (int i = 1 ; i <= n; i++) {
            num.add(i);
        }
        int factor = 1;
        for (int i = 2; i < n; i++) {
            factor *= i;
        }
        StringBuilder tem = new StringBuilder();
        for (int time = n-1; time >= 0; time--) {
            int index = k / factor;
            tem.append(num.get(index));
            num.remove(num.get(index));//因为只能出现一次 所以用过就抹去
            k = k % factor;
            if (time != 0) {
                factor = factor / time;
            }
        }
        return tem.toString();
    }
}