Monthly Archives: May 2016

LeetCode Count and Say

LeetCode Count and Say
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 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, generate the nth sequence.
Note: The sequence of integers will be represented as a string.


这题目英文描述真是醉了,看半天没理解意思,还是看网上翻译的。其实就是后一个字符串是前一个字符串的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

LeetCode Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.


判断一个数独棋盘是否合法,即每行每列和每个小方格内不能有'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。

LeetCode Implement strStr()

LeetCode Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.


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

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]开始重新匹配。
但是如果遇到下图的情况:

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

那么怎样才能知道此时应该j指针应该调整到指向'C'呢?KMP算法的关键就是计算next数组了,next数组的作用就是当s[i]和t[j]失配时,i指针不动,j指针调整为next[j]继续匹配。
通过上面两张图的例子,我们知道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,这个很好理解。

如果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的博客:
比如,如果用之前的next 数组方法求模式串“abab”的next 数组,可得其next 数组为-1 0 0 1(0 0 1 2整体右移一位,初值赋为-1),当它跟下图中的文本串去匹配的时候,发现b跟c失配,于是模式串右移j - next[j] = 3 - 1 =2位。

右移2位后,b又跟c失配。事实上,因为在上一步的匹配中,已经得知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]继续匹配。

LeetCode Divide Two Integers

LeetCode Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.


要求不使用乘、除、取模运算求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。

LeetCode Remove Element

LeetCode Remove Element
Given an array and a value, 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 in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.


要求我们把数组中等于某个数的元素全部“移除”,移除并不是真正的移除,可以把它们移到数组的末尾。
我的思路是,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,排名倒数也是在我的预料之中的。看过题解之后,不得不感慨自己还是太笨,过段时间再来刷一遍。