Smallest Good Base

对于数n，“11”一定可以由base（n－1）组成，寻找最小的base，实际上就是找最长的“1111111”。

寻找一个x满足n=x^0+x^1+...+x^(k-1), 利用错位相消，实际上需要找到n*(x-1)=x^k-1的x，每次固定K值，二分搜索x。

import java.math.*;
public class Solution {
    public String smallestGoodBase(String n) {
        BigInteger N = new BigInteger(n);
        long base = Long.MAX_VALUE;
        for(int k=2;k<66;k++){
            long left = 2; long right = Long.MAX_VALUE-5;
            while(left<=right){
                long mid = left+(right-left)/2;
                BigInteger a = N.multiply(BigInteger.valueOf(mid).subtract(BigInteger.ONE));
                BigInteger b = BigInteger.valueOf(mid).pow(k).subtract(BigInteger.ONE);
                int cmp = a.compareTo(b);
                if(cmp==0){
                    base = Math.min(base, mid);
                    break;
                }
                else if(cmp<0){
                    right = mid-1;
                }
                else
                    left=mid+1;
            }
        }
        return ""+base;
    }
}

Super Pow

这道题乍一看有点蒙，肯定用到了某种数学性质。

a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k = (a^123456 % k)^10 % k * (a^7 % k) % k

通过这种数学关系转化，我们可以每次将数组b的最后一位隔离出来，对最后一位单独处理，对前面部分单独处理， 前面部分处理结果^10％k后再乘后一位结果再%k. 不知道这性质妥妥跪了。

public class Solution {
    public int superPow(int a, int[] b) {
        return superPow(a, b, b.length, 1337);
    }
    public int superPow(int a, int[] b, int len, int k){
        if(len==1)
            return pow(a, b[0], k);
        else
            return (pow(superPow(a, b, len-1, k),10,k) *pow(a, b[len-1], k))%k;
    }

    public int pow(int a, int b, int k){
        a %=k;
        int pow =1;
        for(int i=0;i<b;i++){
            pow = (a*pow)%k;
        }
        return pow;
    }
}

Base 7

考察基本功，作为CS科班，第一反应居然忘记怎么转换了。。。

转化类时注意几个特殊case，0，maxValue，minValue。负数要先变正数，否则-8返回-1-1

public class Solution {
    public String convertToBase7(int num) {
        if(num==0) return "0";
        StringBuilder sb = new StringBuilder(); boolean neg = false;
        if(num<0) {neg = true;num=-num;}
        while(num!=0){
            int mod = num%7;
            sb.insert(0, mod);
            num=num/7;
        }
        if(neg) sb.insert(0, '-');
        return sb.toString();
    }
}

Complex Number Multiplication

(a+bi)(c+di) = (ac - bd) + (ad+bc)i.

public String complexNumberMultiply(String a, String b) {
    int[] coefs1 = Stream.of(a.split("\\+|i")).mapToInt(Integer::parseInt).toArray(), 
          coefs2 = Stream.of(b.split("\\+|i")).mapToInt(Integer::parseInt).toArray();
    return (coefs1[0]*coefs2[0] - coefs1[1]*coefs2[1]) + "+" + (coefs1[0]*coefs2[1] + coefs1[1]*coefs2[0]) + "i";
}

Valid Square

最简单方式，对坐标按x排序，再按y排序。check 组合。

public class Solution {
    public double dist(int[] p1, int[] p2) {
        return (p2[1] - p1[1]) * (p2[1] - p1[1]) + (p2[0] - p1[0]) * (p2[0] - p1[0]);
    }
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        int[][] p={p1,p2,p3,p4};
        Arrays.sort(p, (l1, l2) -> l2[0] == l1[0] ? l1[1] - l2[1] : l1[0] - l2[0]);
        return dist(p[0], p[1]) != 0 && dist(p[0], p[1]) == dist(p[1], p[3]) && dist(p[1], p[3]) == dist(p[3], p[2]) && dist(p[3], p[2]) == dist(p[2], p[0])   && dist(p[0],p[3])==dist(p[1],p[2]);
    }
}