LintCode

目录

1 Algorithms

1.1 1.

1.1.1 Description

Write a function that add two numbers A and B.

There is no need to read data from standard input stream. Both parameters are given in function aplusb, you job is to calculate the sum and return it.

  • Clarification
    • Are a and b both 32-bit integers? Yes.
    • Can I use bit operation? Sure you can.
  • Example
    • Given a=1 and b=2 return 3.
  • Challenge
    • Of course you can just return a + b to get accepted. But Can you challenge not do it like that?(You should not use + or any arithmetic operators.)

1.1.2 Answer1

如果直接使用+实现，本题没有意义，考虑使用位算法（异或、与、或、非）。

考虑二进制加法的四种情况：

  • 0+0=0
  • 0+1=1
  • 1+0=1
  • 1+1=0

其结果与按位异或相同，但需要单独考虑进位情况：对应位都为1时，向高位进1。考虑 按位取与，结果保留全部为1的位，左移一位后与之前加法结果相加，迭代进行直到进位 部分为0。递归版本实现如下： 

#include <stdio.h>

int do_sum(int a, int b)
{
        int sum, carry;

        if (b == 0)
                return a;

        sum = a^b;
        carry = (a&b)<<1;

        return do_sum(sum, carry);
}

int main(int argc, char *argv[argc])
{
        int sum = do_sum(13579, 24689), i, j, k;

        printf("sum=%d\n", sum);

        for (i = 0; i < 10000; ++i) {
                for (j = 0; j < 10000; ++j) {
                        if (i +j != do_sum(i, j)) {
                                fprintf(stderr, "BUG: i(%d)+j(%d)=sum(%d, %d)",
                                        i, j, i + j, do_sum(i, j));
                        }
                }
        }

        return 0;
}

从递归版本优化为迭代版本： 

#include <stdio.h>

int do_sum2(int a, int b)
{
        int old;

        do {
                /* reuse variable @a for sum and @b for carry */
                old = a;
                a = a^b;
                b = (old&b)<<1;
        } while (b);

        return a;
}

int main(int argc, char *argv[argc])
{
        int sum = do_sum2(13579, 24689), i, j;

        printf("sum=%d\n", sum);

        for (i = 0; i < 10000; ++i) {
                for (j = 0; j < 10000; ++j) {
                        if (i +j != do_sum2(i, j)) {
                                fprintf(stderr, "BUG: i(%d)+j(%d)=sum(%d, %d)",
                                        i, j, i + j, do_sum2(i, j));
                        }
                }
        }

        return 0;
}

1.2 2. Trailing Zeros

1.2.1 Description

Write an algorithm which computes the number of trailing zeros in n factorial.

  • Example

11! = 39916800, so the out should be 2

  • Challenge
  • O(log N) time

1.2.2 Answer1

计算n阶乘作为被模数，初始化10为模数求余，如果为0则10倍模数，直到结果不为0。 

#include <stdio.h>

long long trailingzeros(long long n)
{
        long long m = 10, c = 0, f = n;

        if (0 == n)
                return 0;

        for (c = 1; c < n; ++c)
                f = f*c;

        c = 0;

        while (0 == (f%m)) {
                ++c;
                m *= 10;
        }

        return c;
}

int main(int argc, char *argv[argc])
{
        long long r = trailingzeros(11);

        if (r != 2) {
                fprintf(stderr, "Expect 11! = 2, r=%lld\n", r);
                return 1;
        }

        fprintf(stdout, "11! trailingzeros = %lld\n", r);
        return 0;
}

1.2.3 Answer2

时间复杂度为O(N)，挑战为O(log N)，优化点在于n!。这是已知的数学公式，参见 Legendre's formula定理，StackExchange有更详细的解释，从数学公式可知，n!中 尾部0的个数等于 $∑1^∞\frac{n}{5^i}$。实现如下： 

#include <stdio.h>

long long trailingzeros2(long long n)
{
        long long i, c = 0;

        for (i = 5; n >= i; i *= 5) {
                c += n/i;
        }

        return c;
}

int main(int argc, char *argv[argc])
{
        long long r = trailingzeros2(11);

        if (r != 2) {
                fprintf(stderr, "Expect 11! = 2, r=%lld\n", r);
                return 1;
        }

        fprintf(stdout, "11! trailingzeros = %lld\n", r);

        return 0;
}

也可参考GeeksForGeeks实现。

1.3 3. Digit Counts

1.3.1 Description

if n = 12, k = 1 in

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

we have FIVE 1's (1, 10, 11, 12)

1.3.2 Answer1

最简单的方式是暴力搜索： 

#include <stdio.h>

int countk(int n, int k)
{
        int i, v, c = 0;

        for (i = 0; i <= n; ++i) {
                v = i;
                do {
                        if (v%10 == k)
                                ++c;
                        v /= 10;
                } while (v);
        }

        return c;
}

int main(int argc, char *argv[argc])
{
        int c = countk(12, 1);

        if (c != 5) {
                fprintf(stderr, "countk(12, 1) expects 5, calc is %d\n", c);
                return 1;
        }

        c = countk(224, 2);
        fprintf(stdout, "countk(224, 2) is %d\n", c);

        c = countk(9, 0);
        fprintf(stdout, "countk(9, 0) is %d\n", c);

        c = countk(99, 0);
        fprintf(stdout, "countk(99, 0) is %d\n", c);

        c = countk(999, 0);
        fprintf(stdout, "countk(999, 0) is %d\n", c);

        c = countk(9999, 0);
        fprintf(stdout, "countk(9999, 0) is %d\n", c);

        c = countk(99999, 0);
        fprintf(stdout, "countk(99999, 0) is %d\n", c);

        c = countk(999999, 0);
        fprintf(stdout, "countk(999999, 0) is %d\n", c);

        c = countk(9999999, 0);
        fprintf(stdout, "countk(9999999, 0) is %d\n", c);

        return 0;
}

countk(224, 2) is 73 countk(9, 0) is 1 countk(99, 0) is 10 countk(999, 0) is 190 countk(9999, 0) is 2890 countk(99999, 0) is 38890 countk(999999, 0) is 488890 countk(9999999, 0) is 5888890 countk(224, 2) is 73 countk(9, 0) is 1 countk(99, 0) is 10 countk(999, 0) is 190 countk(9999, 0) is 2890 countk(99999, 0) is 38890 countk(999999, 0) is 488890 countk(224, 2) is 73 countk(9, 0) is 1 countk(99, 0) is 10 countk(999, 0) is 190 countk(9999, 0) is 2890 countk(99999, 0) is 38890

1.3.3 Answer2

这中间有很多数字是无效的、不必要去扫描的。无论k(0≤ k≤ 9)为何值，考虑[0,10) 范围，只有一个k；考虑[10,100)个位上一定有9个k，而十位上有10个k；考虑[100,1000) 范围，分解为9个[10,100)，并单独考量最高位。 

#include <stdio.h>

int countk(int n, int k)
{
        int i, v, c = 0;

        for (i = 0; i <= n; ++i) {
                v = i;
                do {
                        if (v%10 == k)
                                ++c;
                        v /= 10;
                } while (v);
        }

        return c;
}

int countk2(int n, int k)
{
        int xd, xbase, dbase = 1, div = 10, c = 0, k0penalty = 0;

        /*
         * Algorithms Description:
         */

        /* units digit (lowest digit) */
        if (n%10 >= k)
                c += 1;

        while(div <= n) {
                /* xd is the x's digits. e.g.: units, tens, hundreds, ... */
                xd = n%(div*10);
                xd /= div;
                xbase = div/10*dbase;

                c += xd*xbase;
                if (xd > k)
                        c += div;
                else if (xd == k)
                        c += (n%div) + 1;

                k0penalty += div; /* just used if @k == 0 */
                div *= 10;
                ++dbase;
        }

        if (k == 0)
                c -= k0penalty;

        return c;
}

int main(int argc, char *argv[argc])
{
        int i, j, k, c, c2 = countk2(12, 1);
        int ta[] = {0, 5, 10, 48, 94, 100, 102, 108, 110, 111, 115};
        int ka[] = {2, 0};

        if (c2 != 5) {
                fprintf(stderr, "countk(12, 1) expects 5, calc is %d\n", c2);
                return 1;
        }

        for (i = 0; i < 100000; ++i) {
                for (k = 0; k <= 9; ++k) {
                        c = countk2(i, k);
                        c2 = countk2(i, k);
                        if (c != c2) {
                                fprintf(stderr,
                                        "error: n(%d) k(%d) c(%d) c2(%d)\n",
                                        i, k, c, c2);
                                return 1;
                        }
                }
        }

        c = countk2(224, 2);
        fprintf(stdout, "countk(224, 2) is %d\n", c);

        return 0;
}

countk(224, 2) is 73 countk(224, 2) is 73

1.4 4. Ugly Number II

1.4.1 Description

  • Ugly number is a number that only have factors 2, 3 and 5.
  • Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12…
  • Note that 1 is typically treated as an ugly number.
  • Example: If n=9, return 10.
  • Challenge: O(n log n) or O(n) time.

1.4.2 Answer

#include <stdio.h>
#include <malloc.h>

unsigned long dist = 0;

void distance(int *pf2, int *pf3, int *pf5)
{
        int *pmin, *pmax;
        unsigned long v;

        pmin = pmax = pf2;

        if (pf2 < pf3)
                pmax = pf3;
        else
                pmin = pf3;

        if (pmin > pf5)
                pmin = pf5;
        if (pmax < pf5)
                pmax = pf5;

        v = (pmax - pmin)/4;
        if (v > dist)
                dist = v;
}

int nthUglyNumber(int n)
{
        int i, f, f2, f3, f5, ret;
        int *pf2, *pf3, *pf5;
#define SARR_N  (1024*1024/4)
        int *arr, sarr[SARR_N]; // use stack if < 1MB

        if (n < 1)
                return 0;

        if (n < SARR_N)
                arr = sarr;
        else {
                arr = malloc(sizeof(*arr)*n);
                if (!arr)
                        return 0;
        }

        arr[0] = 1;
        f2 = 2;
        f3 = 3;
        f5 = 5;
        pf2 = pf3 = pf5 = arr;

        for (i = 1; i < n; ++i) {
                f = f2;
                if (f3 < f)
                        f = f3;
                if (f5 < f)
                        f = f5;

                arr[i] = f;
                if (f == f2) {
                        f2 = 2*(*++pf2);
                }
                if (f == f3) {
                        f3 = 3*(*++pf3);
                }
                if (f == f5) {
                        f5 = 5*(*++pf5);
                }

                distance(pf2, pf3, pf5);
        }

        ret = arr[i-1];
        if (arr != sarr)
                free(arr);

        return ret;
}

int main(int argc, char **argv)
{
        int n, v;
        for (n = 0; n < 80000; ++n) {
                v = nthUglyNumber(n);
                //printf("UglyNumber(%d)=%d\n", n, v);
        }

        printf("dist = %lu\n", dist);

        return 0;
}

1.5 86. Binary Search Tree Iterator

1.5.1 Description

Design an iterator over a binary search tree with the following rules:

Elements are visited in ascending order (i.e. an in-order traversal) next() and hasNext() queries run in O(1) time in average.

Have you met this question in a real interview?

  • Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 / \
1 11
 \ \
  6 12

  • Challenge
    • Extra memory usage O(h), h is the height of the tree.
    • Super Star: Extra memory usage O(1)

1.5.2 Answer1: usage O(h) by stack

2012-2020 Copyright© YANYG
Powered by Emacs Orgmode