计划2-LintCode




(2) 尾部的零(Easy)

因为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];
    }
};

(5) – 第K大(中等)

方法:

利用快速排序的分块算法(Partition)+二分查找的思想解决即可.

public class Topic_5 {
    public static void main(String[] args){
        int[] nums=new int[]{9,3,2,4,8};
        System.out.println(kthLargestElement(3,nums));
    }

    //用首元素做pivot
    private static int partition(int l,int r,int[] nums){
        int pivot=nums[l];
        int temp=nums[l],low=l,high=r;
        while(low<high){
            while(low<high && nums[high]<=temp){
                high--;
            }
            nums[low]=nums[high];
            while(low<high && nums[low]>=temp){
                low++;
            }
            nums[high]=nums[low];
        }
        nums[low]=temp;
        return low;
    }

    public static int kthLargestElement(int n, int[] nums) {
        // write your code here
        int l=0,r=nums.length - 1;
        while(l<r){
            int k=partition(l,r,nums);
            if(k==n-1) break;
            if(k<n-1) l=k+1;
            else if(k>n-1) r=k-1;
        }
        return nums[n-1];
    }
}

(6) – 合并有序数组(简单)

方法:

常规合并

public class Solution {
    /**
     * @param A: sorted integer array A
     * @param B: sorted integer array B
     * @return: A new sorted integer array
     */

    private int[] solve(int A[],int B[]){
        int[] res=new int[A.length+B.length];
        int tagA=0,tagB=0,tot=0;
        while(tagA<A.length && tagB<B.length){
            if(A[tagA]<B[tagB])res[tot++]=A[tagA++];
            else res[tot++]=B[tagB++];
        }
        while(tagA<A.length){
            res[tot++]=A[tagA++];
        }
        while(tagB<B.length){
            res[tot++]=B[tagB++];
        }
        return res;
    }

    public int[] mergeSortedArray(int[] A, int[] B) {
        // write your code here
        return solve(A,B);
    }
}

(7) – 序列化二叉树与反序列化

注意bfs序列化后最简单的反序列化是for循环.
dfs序列化后最简单的反序列是递归.
当然也可以用两序遍历

import sun.reflect.generics.tree.Tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class TOPIC_6 {
    public static class TreeNode {
        public int val;
        public TreeNode left, right;
        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    public static void main(String[] args){
        TreeNode nt=Solution.deserialize("1,2,3,#,#,#,#,");
        System.out.println(Solution.serialize(nt));
    }

    public static class Solution {
        /**
         * This method will be invoked first, you should design your own algorithm
         * to serialize a binary tree which denote by a root node to a string which
         * can be easily deserialized by your own "deserialize" method later.
         */

        public static void dfs(TreeNode root,StringBuilder data){
            if(root==null){
                data.append("#,");
            }else{
                data.append(String.valueOf(root.val)+",");
                dfs(root.left,data);
                dfs(root.right,data);
            }
        }

        public static String serialize(TreeNode root) {
            // write your code here
            StringBuilder data=new StringBuilder();
            dfs(root,data);
            return data.toString();
        }

        // Decodes your encoded data to tree.
        public static TreeNode deserialize(String data) {
            LinkedList<String> que = new LinkedList<String>();
            que.addAll(Arrays.asList(data.split(",")));
            return deserial(que);
        }

        private static TreeNode deserial(LinkedList<String> que){
            String str = que.pollFirst();
            if(str.equals("#")){
                return null;
            }
            TreeNode root = new TreeNode(Integer.valueOf(str));
            if(que.size()!=0) {
                root.left = deserial(que);
                root.right = deserial(que);
            }
            return root;
        }
    }
}

(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);
    }
}

(9) – 嘶嘶

public class Solution {
    /**
     * @param n: An integer
     * @return: A list of strings.
     */
    public List<String> fizzBuzz(int n) {
        // write your code here
        List<String> ans=new LinkedList<String>();
        for(int i=1;i<=n;++i){
            if(i%3==0 && i%5==0) ans.add("fizz buzz");
            else if(i%3==0) ans.add("fizz");
            else if(i%5==0) ans.add("buzz");
            else ans.add(String.valueOf(i));
        }
        return ans;
    }
}

(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];
    }
}