118. Pascal’s Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

本题要求生成前n行的Pascal’s Triangle，其实这东西就是中国的杨辉三角。下一行的第j个元素等于上一行的第j-1、j个元素之和。根据这个规律很容易写出代码，如下：

class Solution {
public:
    vector<vector<int> > generate(int numRows)
    {
        vector<vector<int> > ans;
        if (numRows == 0)
            return ans;
        ans.push_back({ 1 });
        for (int i = 2; i <= numRows; i++) {
            vector<int> cur = { 1 };
            for (int j = 1; j <= i – 2; j++) {
                cur.push_back(ans[i – 2][j – 1] + ans[i – 2][j]);
            }
            cur.push_back(1);
            ans.push_back(cur);
        }
        return ans;
    }
};

本代码提交AC，用时0MS。

238. Product of Array Except Self

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]

Constraint: It’s guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

很有意思的一个题。给定一个数组，要求数组中除了当前元素的其他所有元素的乘积。比如数组[1,2,3,4]，则3对应的值应该是1*2*4=8。
题目要求不能用除法，且要是常数时间空间复杂度。
如果能用除法就很简单了，先把数组完整的乘积算出来，然后依次除以每个元素。
网上看了题解，这题还是很巧妙的。我们可以扫描两遍数组，第一遍从左往右，计算不包括当前元素的之前所有元素的乘积；第二遍从右往左，计算不包括当前元素的之后所有元素的乘积；最后把两遍的结果乘起来就是要求的结果。比如样例
原始数组    1,  2, 3, 4
第一遍        1,  1, 2, 6
第二遍     24, 12, 4, 1
两遍乘积 24, 12, 8, 6
仔细想想很容易就知道其中的原理，对于第i个元素，最终结果应该是
$(x_0*x_1*…*x_{i-1})*(x_{i+1}*x_{i+2}*…*x_{n-1})$
第一遍相当于计算了前半部分，第二遍相当于计算了后半部分，最后两个部分乘起来就好了。
题目还有一个要求，就是常数空间复杂度，方法是：第二遍的时候，借助一个变量right_prod来存储从右到左的乘积，ans里面就是第二遍乘第二遍的结果，也就是最终结果。
完整代码如下：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        vector<int> ans(nums.size(), 1);
        for (int i = 1; i < nums.size(); i++) {
            ans[i] = ans[i – 1] * nums[i – 1];
        }
        int right_prod = 1;
        for (int i = nums.size() – 2; i >= 0; i–) {
            right_prod *= nums[i + 1];
            ans[i] *= right_prod;
        }
        return ans;
    }
};

本代码提交AC，用时52MS。

LeetCode Super Ugly Number Write a program to find the n^th super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4. Note: (1) 1 is a super ugly number for any given primes. (2) The given numbers in primes are in ascending order. (3) 0 < k ≤ 100, 0 < n ≤ 10⁶, 0 < primes[i] < 1000.

264. Ugly Number II 264. Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:  

1. 1 is typically treated as an ugly number.
2. n does not exceed 1690.

本题是LeetCode Ugly Number的升级版，题目还是不错的，要求出第n个丑数是什么。非常naive的方法就是从1开始不断调用LeetCode Ugly Number中判断丑数的函数，如果是丑数，cnt++，直到cnt==n时输出第n个丑数，但是hint里指出很多都不是丑数，所以这样很浪费时间。 hint里同时给出了怎样直接生成所有丑数序列的方法，不错。 主要思路是这样的，每个丑数都是更小的丑数乘以2,3或5得到的，所以我们可以维护一个丑数序列，要求更大的丑数时，用更小的丑数乘以2,3,5来得到，但是2,3,5对应的那个小丑数并不是一样的。举个例子，首先丑数序列中只有{1}这个元素，对于2,3,5，初始的时候i2=i3=i5=0，表明2,3,5对应丑数序列中的第0个元素1，此时用1分别乘以2,3,5得到的最小值是2，所以下一个丑数是1*2得到的，那么i2++去对应下一个小丑数，i3和i5对应的下标不变。不断这样产生丑数。 不太好描述，请看代码：

class Solution {
public:
    int nthUglyNumber(int n)
    {
        if (n == 1)
            return 1;
        vector<int> ugly_num = { 1 };
        int i2 = 0, i3 = 0, i5 = 0;
        int next_ugly_num = 0;
        while (ugly_num.size() < n) {
            next_ugly_num = min(min(ugly_num[i2] * 2, ugly_num[i3] * 3), ugly_num[i5] * 5);
            if (next_ugly_num == ugly_num[i2] * 2)
                i2++;
            if (next_ugly_num == ugly_num[i3] * 3)
                i3++;
            if (next_ugly_num == ugly_num[i5] * 5)
                i5++;
            ugly_num.push_back(next_ugly_num);
        }
        return next_ugly_num;
    }
};

代码很简洁，但是要想到这个思路还是有难度的。本代码提交AC，用时16MS。

263. Ugly Number 263. Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example 1:

Input: 6
Output: true
Explanation: 6 = 2 × 3

Example 2:

Input: 8
Output: true
Explanation: 8 = 2 × 2 × 2

Example 3:

Input: 14
Output: false 
Explanation: 14 is not ugly since it includes another prime factor 7.

Note:

1. 1 is typically treated as an ugly number.
2. Input is within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. 263. Ugly Number

本题要判断一个数是否是丑数，丑数的定义是素因子只有2,3,5，简单想法就是不断的除这些数，如果最后结果是1，则说明素因子只有2,3,5，否则还有其他素因子。 完整代码如下：

class Solution {
public:
    bool isUgly(int num)
    {
        if (num < 1)
            return false;
        while (num % 5 == 0)
            num /= 5;
        while (num % 3 == 0)
            num /= 3;
        while (num % 2 == 0)
            num /= 2;
        return num == 1;
    }
};

本代码提交AC，用时3MS。

二刷：

class Solution {
public:
	bool isUgly(int num) {
		if (num <= 0)return false;
		while (num != 1) {
			if (num % 5 == 0)num /= 5;
			else if (num % 3 == 0)num /= 3;
			else if (num % 2 == 0)num /= 2;
			else return false;
		}
		return num == 1;
	}
};

本代码提交AC，用时0MS。

258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

Example:

Input: 38
Output: 2 
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?
258. Add Digits

题意就是把一个数的每一位相加，如果得到的和大于10，则对和的每一位继续相加，直到最后结果是小于10的。得到的这个数称为数根。 题目要求用O(1)的算法实现，要求好高啊，完全懵*，还是先实现一个常规的迭代算法吧：

class Solution2 {
public:
    int addDigits(int num)
    {
        int sum = num;
        while (sum > 9) {
            int cur_sum = 0;
            while (sum) {
                cur_sum += sum % 10;
                sum = sum / 10;
            }
            sum = cur_sum;
        }
        return sum;
    }
};

本代码提交AC，用时3MS。
后来网上搜索了一下，发现数根有规律，1~20的数根如下：
1    1
2    2
3    3
4    4
5    5
6    6
7    7
8    8
9    9
10    1
11    2
12    3
13    4
14    5
15    6
16    7
17    8
18    9
19    1
20    2
每9个一个循环，而且结果是对9取模，但如果是9的倍数的话，结果还是9，所以为了一行搞定，可以用(n-1)%9+1来包括所有的情况。
完整代码如下：

class Solution {
public:
    int addDigits(int num)
    {
        return (num – 1) % 9 + 1;
    }
};

本代码提交AC，用时3MS。

29. Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. For the purpose of this problem, assume that your function returns 2³¹ − 1 when the division result overflows.

要求不使用乘、除、取模运算求a除以b。马上想到用a不断减b，直到a<b为止，但是这种方法超时，因为当a很大，b很小时，要减很多次。有没有办法一次减很多个b呢，即一次性减b的t倍。但题目要求不能使用乘法，但是b每左移一位相当于b的2倍，所以可以用移位代替乘法。 我们知道任意一个自然数可以表示成以2的幂为底的一组基的线性组合，即 $$num=a_0*2^0+a_1*2^1+a_2*2^2+…+a_n*2^n$$ 如果我们能找到一个使得$2^n*b\leq a$的最大的$n$，则a可以一次性减掉$2^n$个b，速度就快很多了。 基于这个思想，我们每次找最大的n，然后$a-2^n*b$，不断循环，直到a<b。完整代码如下：

class Solution {
public:
    int divide(int dividend, int divisor)
    {
        if (divisor == 0)
            return INT_MAX;
        if (divisor == -1 && dividend == INT_MIN)
            return INT_MAX;
        unsigned int divd = dividend, divr = divisor;
        if (dividend < 0)
            divd = -divd; // 先都转换为正数，方便处理
        if (divisor < 0)
            divr = -divr;
        int ans = 0;
        while (divd >= divr) {
            unsigned long long tmp = divr; // 注意类型，防止溢出
            int p = 0;
            while (divd >= tmp) {
                tmp <<= 1;
                p++;
            }
            ans += 1 << (p – 1);
            divd -= divr << (p – 1);
        }
        int sign = dividend ^ divisor; // 首位为符号位，如果符号相同，异或之后为正数
        return sign >= 0 ? ans : -ans;
    }
};

本代码提交AC，用时8MS。
P.S.一直以来对数论的题都没底，这次在将负数转换为正数时也花了不少时间。

// (a)_2 = 1111 1111 1111 1111 1111 1111 1100 0010; (a)_10 = -62;
int a = -62;
// (b)_2 = 1111 1111 1111 1111 1111 1111 1100 0010; (b)_10 = 4294967234;
unsigned int b = a;
// (b)_2 = 0000 0000 0000 0000 0000 0000 0011 1110; (b)_10 = 62;
b = -b;

请看上面这个例子，当我们想把一个int转换为unsigned int时，如果是正数，直接强制类型转换没有问题，但是如果是负数，则会出问题。

我们知道一个数在内存中是以补码的形式保存的，把a强制类型转换为b，a,b在内存中的表示是一样的，只是此时b按unsigned int的格式来解析了，解析出来的结果自然不会是+62。
我们还知道负数的补码是对应正数补码取反加1，我们在将负数转换为正数的时候，同样的也是补码取反加1，所以还需要添加一句b = -b。

二刷。题目中说运行环境是32位系统，所以不能用long的类型，于是修改成如下代码。

class Solution {
public:
	int divide(int dividend, int divisor) {

		if (dividend == INT_MIN && divisor == -1)return INT_MAX;
		if (dividend == INT_MIN && divisor == 1)return INT_MIN;

		unsigned int a = dividend, b = divisor;
		if (dividend < 0)
			a = (~a+1);
		if (divisor < 0)
			b = (~b+1);

		int ans = 0;
		while (a >= b) {
			int p = 0;
			int tmp = b;
			while (a > tmp && tmp < INT_MAX / 2) {
				tmp <<= 1;
				++p;
			}
			if (p > 0) {
				ans += (1 << (p - 1));
				a -= (tmp >> 1);
			}
			else if (p == 0) {
				if (a >= tmp) {
					++ans;
					a -= tmp;
				}
			}
		}

		int sign = dividend ^ divisor;
		if (sign >= 0)return ans;
		else return -ans;
	}
};

最主要的改变是在while循环时，为了防止tmp左移过程中超过INT_MAX，可以在左移前判断它是否大于INT_MAX的一半，因为左移就是*2操作，如果左移之前已经大于INT_MAX的一半，则左移后肯定超过范围。

另外如果while时没有发生左移，则使用简单的减法操作。

最后由于不能用long，所以把所有数都转换为unsigned int，因为unsigned int能表示的正数范围比int大，即使是INT_MIN也能转换为正数的unsigned int存储。

本代码提交AC，用时4MS。