计划2-LintCode




2 尾部的零

因为2的数量远大于5,统计5的数量即可

public class Solution {
    /*
     * @param n: An integer
     * @return: An integer, denote the number of trailing zeros in n!
     */

    public long trailingZeros(long n) {
        // write your code here, try to do it without arithmetic operators.
        long cnt=0,k=n;

        while(k>0){
            cnt+=k/5;
            k/=5;
        }
        return cnt;
    }
}

3 统计数字

伪数位DP

public class Solution {
    /*
     * @param : An integer
     * @param : An integer
     * @return: An integer denote the count of digit k in 1..n
     */

    public int digitCounts(int k, int n) {
        // write your code here
        int cnt=0,mt=1,tmp=0;
        int a=n;
        if(k==0)tmp=1;
        while(a>0){
            int digit=a%10;
            a/=10;
            if(digit>k)cnt+=(a+1-tmp)*mt;
            else if(digit==k) cnt+=(a-tmp)*mt+n%mt+1;
            else cnt+=a*mt;
            mt*=10;
        }
        cnt+=tmp;
        return cnt;
    }
};

4 丑数二

筛法只能过94%

因为他后面的数据超过10亿!....

public class Solution {
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
        int[] ans=new int[767];
        boolean[] is=new boolean[10000000];  
        int tot=0;

        void init(int n){
            for(int i=0;i<10000000;++i) is[i]=false;
            is[1]=true;
            ans[tot++]=1;
            for(int i=1;i<10000000;++i){
                if(is[i]){
                    for(int j=i*2;j<10000000;j*=2){
                        if(!is[j]){
                            is[j]=true;
                            ans[tot++]=j;
                        }
                    }
                    for(int j=i*3;j<10000000;j*=3){
                        if(!is[j]){
                            is[j]=true;
                            ans[tot++]=j;
                        }
                    }
                    for(int j=i*5;j<10000000;j*=5){
                        if(!is[j]){
                            is[j]=true;
                            ans[tot++]=j;
                        }
                    }
                }
            }
        }

    public int nthUglyNumber(int n) {
        // write your code here
            init(n);
            //ans=IntStream.of(ans).boxed().sorted().mapToInt(Integer::intValue).toArray();
            Arrays.sort(ans);
            return ans[n-1];
    }
}

用HashSet+Dfs AC

因为他给数据了,所以在已知数据是INT_MAX的前提下就好做多了

public class Solution {
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    HashSet<Integer> tSet=new HashSet<>();
    int[] ans=new int[1665];
    int tot=0;
    void dfs(long num){
        if(num>(long)1898437500)return;
        if(tSet.size()>=1665) return;
        if(tSet.contains((int)num)) return;
        else{
            tSet.add((int)num);
            if(tot==1665)return;
            ans[tot++]=(int)num;
            dfs(num*2);
            dfs(num*3);
            dfs(num*5);
        }
    }

    public int nthUglyNumber(int n) {
        // write your code here
        dfs(1);
        Arrays.sort(ans);
        return ans[n-1];
    }
}

找规律的解法

可以发现只需要三个指针指向P1P2P3,同步前移,第n个就是这三个中最小的一个

class Solution {
public:
    /**
     * @param n: An integer
     * @return: the nth prime number as description.
     */
    #define min(a,b) ((a)<(b)?(a):(b))
    #define min3(a,b,c) (min(min(a,b),min(a,c)))
    int nthUglyNumber(int n) {
        int i = 1;
        int p2 = 0;
        int p3 = 0;
        int p5 = 0;
        int uglyNum[6048] = {0};
        uglyNum[0] = 1;
        while ( i < n ) {
            uglyNum[i] = min3(uglyNum[p2] * 2, uglyNum[p3] * 3, uglyNum[p5] * 5);
            if (uglyNum[i] == uglyNum[p2] * 2) {
                p2++;
            }
            if (uglyNum[i] == uglyNum[p3] * 3) {
                p3++;
            }
            if (uglyNum[i] == uglyNum[p5] * 5) {
                p5++;
            }
            i++;
        }
        return uglyNum[n-1];
    }
};

8 旋转字符串

剑指Offer上的一道题

先整体旋转,然后把offset前后各旋转一次即可

public class Solution {
    /**
     * @param str: An array of char
     * @param offset: An integer
     * @return: nothing
     */

    void Reverse(char[] str,int start,int end){
        while(start<end){
            if(end-1<=start)break;
            str[start]^=str[end-1];
            str[end-1]^=str[start];
            str[start]^=str[end-1];
            start++;end--;
        }
    } 

    public void rotateString(char[] str, int offset) {
        // write your code here
        int len=str.length;
        if(len<=0)return;
        int fnos=offset%len;
        Reverse(str,0,len);
        Reverse(str,0,fnos);
        Reverse(str,fnos,len);
    }
}

114 不同的路径

很明显是杨辉三角,求C(n,m)
当然,也可以用动态规划,dp[i][j]=dp[i-1][j]+dp[i][j-1]

public class Solution {
    /**
     * @param m: positive integer (1 <= m <= 100)
     * @param n: positive integer (1 <= n <= 100)
     * @return: An integer
     */
    public int[][] res=new int[204][204];
    public void init(){
        res[0][0]=1;
        for(int i=1;i<=200;++i){
            res[i][0]=1;
            for(int j=1;j<=i;++j){
                res[i][j]=res[i-1][j-1]+res[i-1][j];
            }
        }
    }

    public int uniquePaths(int m, int n) {
        // write your code here
        init();
        return res[m+n-2][m-1];
    }
}

发表评论