LeetCode(9) -- 441, 443, 447

P441. Arranging Coins (Easy)

n个硬币，想组成一个楼梯的形状。

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

我的思路

根据等差数列求和公式，s = (1+n)n / 2, 推导出n = (-1 + sqrt(1+8s)) / 2。再求出它的floor，应该就是解了。

我的代码

class Solution {
    public int arrangeCoins(int n) {
        long s = n;
        return (int) Math.floor((Math.sqrt(s * 8 + 1) - 1) / 2);
    }
}

一开始越界了，改成long就通过了。超过60%

最优解

class Solution {
    public int arrangeCoins(int n) {
        return (int)((-1 + Math.sqrt(1 + 8 * ((long) n))) / 2);
    }
}

看起来跟我几乎完全一样，只不过直接在行内把n给转化成long型了。

P443. String Compression (Easy)

压缩字符串。

Input:
["a","a","b","b","c","c","c"]

Output:
Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]

Explanation:
"aa" is replaced by "a2". "bb" is replaced by "b2". "ccc" is replaced by "c3".

Input:
["a"]

Output:
Return 1, and the first 1 characters of the input array should be: ["a"]

Explanation:
Nothing is replaced.

Input:
["a","b","b","b","b","b","b","b","b","b","b","b","b"]

Output:
Return 4, and the first 4 characters of the input array should be: ["a","b","1","2"].

Explanation:
Since the character "a" does not repeat, it is not compressed. "bbbbbbbbbbbb" is replaced by "b12".
Notice each digit has it's own entry in the array.

我的思路

如果相同的字符都在一起，像例子中那样，那就很简单了。保留两个指针，只要长度大于1就替换。

我的代码

public class E_443_StringCompression {
    public int compress(char[] chars) {
        if (chars.length == 0){
            return 0;
        }
        char current = chars[0];
        int counter = 1;
        int j = 1;
        for (int i = 1; i < chars.length; i++) {
            if (chars[i] == current) {
                counter++;
            } else if (counter > 1) {
                String s = String.valueOf(counter);
                int length = s.length();
                for (int k = 0; k < length; k++, j++) {
                    chars[j] = s.charAt(k);
                }
                current = chars[j++] = chars[i];
                counter = 1;
            } else {
                current = chars[j++] = chars[i];
            }
        }
        if (counter > 1) {
            String s = String.valueOf(counter);
            int length = s.length();
            for (int i = 0; i < length; i++, j++) {
                chars[j] = s.charAt(i);
            }
        }
        return j;
    }
}

96%

最优解

class Solution {
    public int compress(char[] chars) {
        int anchor = 0, write = 0;
        for (int read = 0; read < chars.length; read++) {
            if (read + 1 == chars.length || chars[read + 1] != chars[read]) {
                chars[write++] = chars[anchor];
                if (read > anchor) {
                    for (char c: ("" + (read - anchor + 1)).toCharArray()) {
                        chars[write++] = c;
                    }
                }
                anchor = read + 1;
            }
        }
        return write;
    }
}

如果读到了末尾，或者下一个不一样了，就把anchor那个字符写入，同时把anchor更新为下一个新字符。这期间，如果read > anchor， 则说明有连续的字符出现，就要算一下出现了几次，并把该数字转化成字符，写入。

这个代码写得相当优雅。而我的代码debug了一个小时才终于通过。

P447. Number of Boomerangs (Easy)

平面上有n个不同的点。找出所有的”boomerang”。就是一个三元组(i,j,k) i 和 j 的距离等于i 和 k 的距离。

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

讨论区

public int numberOfBoomerangs(int[][] points) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int i = 0; i < points.length; i++) {
            // clearing map for new search
            map.clear();
            for (int j = 0; j < points.length; j++) {
                // skipping the same point
                if (i == j) {
                    continue;
                }
                // calculating distance. We will compare distance^2 and get rid of Math.sqrt
                int distance = (points[j][0] - points[i][0])*(points[j][0] - points[i][0])
                    + (points[j][1] - points[i][1])*(points[j][1] - points[i][1]);
                // finding number of previously met points with the same distance to i point
                int size = map.getOrDefault(distance, 0);
                // adding that number * 2 to result, since j point can be either second or third point in the bumerang
                count += size++ * 2;
                // adding increased by 1 size back to map
                map.put(distance, size);
            }
        }
        return count;
    }

最优解

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if(points == null) return 0;
        int boomerangs = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

        for(int i=0; i<points.length; i++){
            for(int j=0; j<points.length; j++){
                if(j == i) continue;
                int dist = getDistance(points[i], points[j]);
                int count = map.getOrDefault(dist, 0);
                boomerangs += 2*count;
                map.put(dist, count+1);
            }
            map.clear();
        }

        return boomerangs;
    }

    private int getDistance(int[] point1, int[] point2){
        int x = point1[0] - point2[0], y = point1[1] - point2[1];
        return (x * x + y * y);
    }
}

注意：给的数组是二维数组，大数组里包含的小数组长度全是2，因为它们代表一个点。

用一个双层循环遍历所有点的两两组合。自己跟自己不算，所以if(j == i) continue.

其实总体思路还是用每一个点去跟其他的所有点进行比较，把距离存到HashMap里。

如果一个点到两个点的距离相等，那就可以找到两个Boomerangs; 如果到三个点距离相等，就会有四个； 如果到四个点距离相等，就会有6个。。。

所以他用了getOrDefault。第一次算出一个距离时，先拿到默认值0，再put成1；找到第二个点也是这个距离时，就可以出两个Boomerangs, 并put成2; 再下一次就找出同样距离时，就可以出4个，并put成3。。。