Monthly Archives: May 2016

LeetCode Count and Say

38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"
Explanation: This is the base case.

Example 2:

Input: 4
Output: "1211"
Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and value = 2, the same way "1" is read as "11", so the answer is the concatenation of "12" and "11" which is "1211".

这题目英文描述真是醉了,看半天没理解意思,还是看网上翻译的。其实就是后一个字符串是前一个字符串的read,比如第三个字符串是21,它包含1个2和1个1,所以第四个字符串就是1211。 果然是easy模式,用递归几行代码搞定。

class Solution {
public:
    string countAndSay(int n)
    {
        if (n == 1)
            return "1";
        string pre = countAndSay(n – 1);
        string ans = "";
        int i = 0, j;
        while (i < pre.size()) {
            j = i + 1;
            while (j < pre.size() && pre[j] == pre[i])
                j++;
            ans += to_string(j – i) + pre.substr(i, 1);
            i = j;
        }
        return ans;
    }
};

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

LeetCode Valid Sudoku

36. Valid Sudoku

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.


A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

判断一个数独棋盘是否合法,即每行每列和每个小方格内不能有’1’~’9’的重复数字。只要求检查是否合法,不要求棋盘是否可解,所以程序很简单,直接按行、列和小方格检查即可。 完整代码如下:

class Solution {
public:
    bool isValidSudoku(vector<vector<char> >& board)
    {
        int m = board.size();
        if (m != 9)
            return false;
        for (int i = 0; i < m; i++) { // 行
            int n = board[i].size();
            if (n != 9)
                return false;
            vector<int> rows(n, 0);
            for (int j = 0; j < n; j++) {
                if (board[i][j] != ‘.’) {
                    rows[board[i][j] – ‘1’]++;
                    if (rows[board[i][j] – ‘1’] > 1)
                        return false;
                }
            }
        }
        for (int j = 0; j < m; j++) { //列
            vector<int> cols(m, 0);
            for (int i = 0; i < m; i++) {
                if (board[i][j] != ‘.’) {
                    cols[board[i][j] – ‘1’]++;
                    if (cols[board[i][j] – ‘1’] > 1)
                        return false;
                }
            }
        }
        for (int i = 0; i < m; i += 3) { // 小方格
            for (int j = 0; j < m; j += 3) {
                vector<int> cubes(m, 0);
                for (int k = 0; k < m; k++) {
                    if (board[i + k / 3][j + k % 3] != ‘.’) {
                        cubes[board[i + k / 3][j + k % 3] – ‘1’]++;
                        if (cubes[board[i + k / 3][j + k % 3] – ‘1’] > 1)
                            return false;
                    }
                }
            }
        }
        return true;
    }
};

本代码提交AC,用时12MS。
上述代码不够简洁,其实可以只用一个循环把行、列、小方块判断了,参考:https://discuss.leetcode.com/topic/8241/my-short-solution-by-c-o-n2
完整代码如下,i,j,k分别代表行号、列号、所在小方块的编号,用二维数组rows,cols,cubes标记是否重复。

class Solution {
public:
    bool isValidSudoku(vector<vector<char> >& board)
    {
        int m = 9;
        vector<vector<int> > rows(9, vector<int>(9, 0)), cols(9, vector<int>(9, 0)), cubes(9, vector<int>(9, 0));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] != ‘.’) {
                    int num = board[i][j] – ‘0’ – 1;
                    int k = i / 3 * 3 + j / 3;
                    if (rows[i][num] > 0 || cols[j][num] > 0 || cubes[k][num] > 0)
                        return false;
                    rows[i][num] = cols[j][num] = cubes[k][num] = 1;
                }
            }
        }
        return true;
    }
};

本代码提交AC,用时12MS。

二刷。也是一次循环搞定行、列、和小方块,代码如下。这里面的i,j在检查行时,i是行号,j是列号;在检查列时,i是列号,j是行号;在检查小方块时,i是9个小方块在整个board中的编号,j是小方块内部每个格子的编号,都是从左往右,从上往下开始编号。

class Solution {
public:
	bool IsRepeat(vector<int>& flag, char c) {
		if (c == '.')return false;
		int val = c - '0';
		if (flag[val] > 0)return true;
		++flag[val];
		return false;
	}
	bool isValidSudoku(vector<vector<char>>& board) {

		vector<int> row_flag(10, 0), col_flag(10, 0), box_flag(10, 0);
		for (int i = 0; i < 9; ++i) {
			fill(row_flag.begin(), row_flag.end(), 0);
			fill(col_flag.begin(), col_flag.end(), 0);
			
			for (int j = 0; j < 9; ++j) {

				int box_row_start = i / 3 * 3, box_col_start = i % 3 * 3;
				int	box_row_offset = j / 3, box_col_offset = j % 3;
				int box_row = box_row_start + box_row_offset, box_col = box_col_start + box_col_offset;

				if ((box_row == 0 && (box_col == 0 || box_col == 3 || box_col == 6)) ||
					(box_row == 3 && (box_col == 0 || box_col == 3 || box_col == 6)) ||
					(box_row == 6 && (box_col == 0 || box_col == 3 || box_col == 6)))fill(box_flag.begin(), box_flag.end(), 0); // 小方块左上角

				char rowc = board[i][j], colc = board[j][i], boxc = board[box_row][box_col];
				if (IsRepeat(row_flag, rowc) || IsRepeat(col_flag, colc) || IsRepeat(box_flag, boxc))return false;

			}
		}
		return true;
	}
};

本代码提交AC,用时12MS。

LeetCode Implement strStr()

28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C’s strstr() and Java’s indexOf().


串的模式匹配问题,首先献上暴力方法:

class Solution {
public:
    int strStr(string haystack, string needle)
    {
        int n1 = haystack.size(), n2 = needle.size();
        if (n2 > n1)
            return -1;
        for (int i = 0; i < n1 – n2 + 1; i++) {
            bool found = true;
            for (int j = 0; j < n2; j++) {
                if (needle[j] != haystack[i + j]) {
                    found = false;
                    break;
                }
            }
            if (found)
                return i;
        }
        return -1;
    }
};

本代码提交AC了,用时6MS。

然后使用神器KMP算法,如下:

class Solution {
public:
    void getNextVal(vector<int>& nextval, string t)
    {
        int n = t.size();
        nextval.resize(n);
        nextval[0] = -1;
        int j = 0, k = -1;
        while (j < n – 1) {
            if (k == -1 || t[j] == t[k]) {
                j++;
                k++;
                if (t[j] != t[k])
                    nextval[j] = k;
                else
                    nextval[j] = nextval[k];
            }
            else
                k = nextval[k];
        }
    }
    int strStr(string haystack, string needle)
    {
        if (needle == "")
            return 0;
        int n1 = haystack.size(), n2 = needle.size();
        if (n2 > n1)
            return -1;
        vector<int> nextval;
        getNextVal(nextval, needle);
        int i = 0, j = 0;
        while (i < n1 && j < n2) {
            if (j == -1 || haystack[i] == needle[j]) {
                i++;
                j++;
            }
            else
                j = nextval[j];
        }
        if (j >= n2)
            return i – n2;
        else
            return -1;
    }
};

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


下面还是仔细回顾一下KMP算法,免得以后忘了不好学。

假设主串为s,模式串为t,暴力的方法是依次检查以s[i]开头能否和t匹配成功,如果匹配不成功,则从s的下一个位置s[i+1]开始重新匹配。

但是如果遇到下图的情况:

图1,转自阮一峰的博客

很显然,从s的下一个位置’B’开始和t的开头重新匹配时,一定会失败,因为之前匹配的串是”ABCDAB”,要想再次成功匹配,可以把AB的前缀移到AB后缀的地方,也就是指向主串的i指针不变,j指针指向’C’重新开始下一轮匹配。

那么怎样才能知道此时应该j指针应该调整到指向’C’呢?KMP算法的关键就是计算next数组了,next数组的作用就是当s[i]和t[j]失配时,i指针不动,j指针调整为next[j]继续匹配。

图2 转自july的博客
图3 转自july的博客

通过上面两张图的例子,我们知道next[j]的含义就是在t[j]之前的串中,相同的前缀和后缀的最大长度。比如最开始的图匹配到ABCDABD时失配,此时j指向最后一个字母’D’,’D’之前的串ABCDAB中最长的相同的前缀后缀是’AB’,所以next[j]=2,下一次,我们令j=next[j]=2,这样就直接从t[j]=t[2]=’C’开始匹配了。

(t[0,…,j]的前缀要以t[0]开头,后缀要以t[j]结尾,但都不能完全等于t[0,…,j],即前缀不能以t[j]结尾,后缀不能以t[0]开头。)

$$next[j]=\begin{cases} \max\{k|0<k<j|t_0t_1…t_{k-1}==t_{j-k}t_{j-k+1}…t_{j-1}\}, & \mbox{if this set is nonempty}\\-1, & \mbox{if }j==0\\ 0, & \mbox{otherwise}\end{cases}$$

既然next[j]的含义就是在t[j]之前的串中,相同的前缀和后缀的最大长度。假设我们已经知道next[0,…,j]了,怎样求解next[j+1]呢?假设next[j]=k,说明t[0,…,j-1]最长的相同前缀后缀长度为k。如果t[j]==t[k],则t[0,…,j]的最长的相同前缀后缀长度就是k+1了,即next[j+1]=k+1,这个很好理解。

图4

如果t[j]!=t[k],则以t[j]结尾的长度为k的后缀就没戏了,因为t[0,…,k]!=t[j-k,…,j],但是后缀又必须以t[j]结尾,所以我们只能缩短长度,从next[k]处继续递归往前查找。即k=next[k]递归查找,注意,递归时j不变,只是k往前递归。

常规的next数组求解就是这样的,但是有一个地方还可以改进,下面引用july的博客:
比如图2和图3,如果用之前的next 数组方法求模式串“abab”的next 数组,可得其next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当它在图2的文本串去匹配的时候,发现b跟c失配,于是模式串右移j – next[j] = 3 – 1 =2位。

右移2位后,b又跟c失配(图3)。事实上,因为在上一步的匹配中,已经得知t[3] = b,与s[3] = c失配,而右移两位之后,让t[ next[3] ] = t[1] = b 再跟s[3]匹配时,必然失配。问题出在哪呢?

问题出在不该出现t[j] = t[ next[j] ]。为什么呢?理由是:当t[j] != s[i] 时,下次匹配必然是t[ next [j]] 跟s[i]匹配,如果t[j] = t[ next[j] ],必然导致后一步匹配失败(因为t[j]已经跟s[i]失配,然后你还用跟t[j]等同的值t[next[j]]去跟s[i]匹配,很显然,必然失配),所以不能允许t[j] = t[ next[j ]]。如果出现了t[j] = t[ next[j] ]咋办呢?如果出现了,则需要再次递归,即令next[j] = next[ next[j] ]。
所以,咱们得修改下求next 数组的代码。

//优化过后的next 数组求法
void GetNextval(char* p, int next[])
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen – 1) {
        //p[k]表示前缀,p[j]表示后缀
        if (k == -1 || p[j] == p[k]) {
            ++j;
            ++k;
            //较之前next数组求法,改动在下面4行
            if (p[j] != p[k])
                next[j] = k; //之前只有这一行
            else //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else {
            k = next[k];
        }
    }
}

得到next数组就好办了,一旦t[j]!=s[i]失配,i不动,j=next[j]继续匹配。

二刷。上面的解读理解起来太费劲了,也记不住。在知乎上看到一个很好的解读:https://www.zhihu.com/question/21923021/answer/281346746

首先,KMP算法在主串和模式串的匹配阶段的原理很好理解,这个不用多讲。关键是如何求解模式串的next数组。

请看下图。核心思想是,要把求next数组的过程理解为模式串自己和自己匹配的过程,更具体来说,是模式串的后缀和前缀匹配的过程,因为next数组的含义就是后缀和前缀相等的最大长度。

如下图所示,首先令i和j错一个位置开始匹配,这就保证了j是从头开始匹配,匹配前缀;而i是从中间某个位置匹配,表示后缀。

下图就可以很直观的看出来j匹配的是前缀,i匹配的是后缀,只要i和j一直匹配,则j的长度就表示主串以i结尾时前缀和后缀相等的长度。所以,只要一直匹配,则next[i]=j。

如果匹配失败,则根据KMP的思路和next数组的定义,直接令j=next[j]进行跳转,i保持不动就行了,这就是KMP主串和模式串匹配的原理。

基于这个思想,其实求解next数组的过程和KMP匹配的过程很相似。完整代码如下:

class Solution {
public:
	vector<int> GetNext(string s) {
		int n = s.size();
		vector<int> next(n, 0);
		next[0] = -1;
		int i = 0, j = -1;
		while (i < n - 1) {
			if (j == -1 || s[i] == s[j]) {
				++i;
				++j;
				next[i] = j;
			}
			else {
				j = next[j];
			}
		}
		return next;
	}
	int strStr(string haystack, string needle) {
		if (needle == "")return 0;
		vector<int> next = GetNext(needle);
		int m = haystack.size(), n = needle.size();
		if (n > m)return -1;
		int i = 0, j = 0;
		while (i < m&&j < n) {
			if (j == -1 || haystack[i] == needle[j]) {
				++i;
				++j;
			}
			else {
				j = next[j];
			}
		}
		if (j == n)return i - n;
		else return -1;
	}
};

LeetCode Divide Two Integers

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: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 231 − 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。

LeetCode Remove Element

27. Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

要求我们把数组中等于某个数的元素全部“移除”,移除并不是真正的移除,可以把它们移到数组的末尾。

我的思路是,i指针从前往后扫,遇到一个等于val的(需要移除的)元素时,j从i+1开始找一个不等于val的,交换i,j指向的元素,i继续前进。
思路还是很简单,结果也正确,但是在计算新数组的长度时需要考虑较多cases,太麻烦,我就直接从末尾再往前找,直到找到一个不等于val的下标位置。ugly代码:

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        if (nums.size() == 0)
            return 0;
        if (nums.size() == 1)
            return (nums[0] != val) ? 1 : 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] != val) {
                        nums[i] = nums[j];
                        nums[j] = val;
                        break;
                    }
                }
            }
        }
        if (nums[0] == val)
            return 0;
        else {
            int i;
            for (i = nums.size() – 1; i >= 0; i–)
                if (nums[i] != val)
                    break;
            return i + 1;
        }
    }
};

本代码提交AC,用时4MS,排名倒数也是在我的预料之中的。看过题解之后,不得不感慨自己还是太笨,过段时间再来刷一遍。

二刷。这题其实很简单,也相当于快慢指针,快指针j一直走,如果nums[j]!=val,则把nums[j]赋值给nums[i],同时i也往前走;如果nums[j]==val,则i要停下来,相当于i这个位置指示了可以放合法元素的位置。完整代码如下:

class Solution {
public:
	int removeElement(vector<int>& nums, int val) {
		int n = nums.size(), i = -1;
		for (int j = 0; j < n; ++j) {
			if (nums[j] != val)nums[++i] = nums[j];
		}
		return i + 1;
	}
};

本代码很简洁,提交AC,用时4MS。