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’.’.

题目解析

数独具有以下规则：

• 每一行所有元素不能重复（1~9）；
• 每一列所有元素不能重复（1~9）；
• 由第3i~3(i)+2行和第3i~3(i)+2列组成的九宫格内元素不能重复（其中0<=i<n/3-1，元素仍为1~9）。

想到重复问题，自然而然我们想到了设置Flag的方法，由此我们可以设置3个n×n大小的矩阵来作为标志位：

• 第一个矩阵命名为fRow，作为判断每一行的数字是否重复的矩阵，因为元素只能为1~9，所以正好每行9个格子合适。
• 第二个矩阵命名为fCol，作为判断每一行列的数字是否重复的矩阵，因为元素只能为1~9，所以正好每行9个格子合适。
• 第三个矩阵命名为fMat，作为判断每个九宫格的数字是否重复的矩阵。

本题的特殊之处在于允许有空格的格子，且空格的地方以字符.表示，且所存储的数字都是char类型，因此首先要进行一个类型转换才能判断：

if(board[i][j] >= '1' && board[i][j]<='9')
    int temp = board[i][j]-'1';

若检测到该行出现这个数字，则设置该行这个位置为true，当又遍历到这个数字的时候，若检查发现这个位置已经设置为true了，则返回false。当然在实现代码的时候，要把判断放在前面，把设置标志位放在后面。

该方法的时间复杂度为O(n2)，空间复杂度为O(n2)。

代码实现

bool isValidSudoku(vector<vector<char> > &board) {
        int totalRows = board.size();
        int totalCols = board[0].size();
        if(totalRows == 0 || totalCols == 0)
            return false;
        vector<vector<bool> > fRow(totalRows,vector<bool>(totalCols,false));//行标志矩阵
        vector<vector<bool> > fCol(totalRows,vector<bool>(totalCols,false));//列标志矩阵
        vector<vector<bool> > fMat(totalRows, vector<bool>(totalCols,false));//9宫格标志矩阵
        for(int i = 0;i < totalRows; i++)
        {
            for(int j = 0; j < totalCols; j++)
            {
                if(board[i][j] >= '1' && board[i][j]<='9')
                {
                    int temp = board[i][j]-'1';
                    if(fRow[i][temp] || fCol[temp][j] || fMat[3*(i/3)+j/3][temp])
                        return false;
                    fRow[i][temp] = true;
                    fCol[temp][j] = true;
                    fMat[3*(i/3)+j/3][temp] = true;
                }
            }
        }
        return true;
    }

largest rectangle in histogram

题目描述

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example,Given height =[2,1,5,6,2,3],return10.

题目解析

我们以[2,1,5,6,2,3]为例来思考这个题目的思想。观察如图所示。

代码实现

int largestRectangleArea(vector<int> &height) {
	int maxarea = 0;
	stack<int>stk;
	for (int i = 0; i < height.size(); i++)
	{
		//如果堆栈是空的或者堆栈里面的最大数小于当前数组的元素，则当前数组元素入栈
		if (stk.empty() || stk.top() <= height[i])
			stk.push(height[i]);
		else {
			//如果堆栈非空且栈顶元素大于当前元素的话
			int count = 0;
			while (!stk.empty() && stk.top() > height[i])
			{
				count++;
				maxarea = max(maxarea, stk.top()*count);
				stk.pop();
			}
			while (count--)
				stk.push(height[i]);
			stk.push(height[i]);
		}

	}
	int count = 1;
	while (!stk.empty())
	{
		maxarea = max(maxarea, stk.top()*count);
		stk.pop();
		count++;
	}
	return maxarea;

}

pascals-triangle-ii

题目描述

Given an index k, return the k th row of the Pascal’s triangle.For example, given k = 3,
Return[1,3,3,1].

题目解析

代码实现

vector<int> getRow(int rowIndex) {
	vector<vector<int> > tempresult(rowIndex+1);//传回的二维数组
	vector<int> result;
	for (int i = 0; i <= rowIndex; ++i)
	{
		tempresult[i].push_back(1);
		for (int j = 1; j < i; j++)
			tempresult[i].push_back(tempresult[i - 1][j - 1] + tempresult[i - 1][j]);
		if (i > 0)
			tempresult[i].push_back(1);
	}
	return tempresult[rowIndex];
}

Construct binary tree from preorder and inorder traversal

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.

思路

关于根据前序和中序如何得到二叉树的结构的计算方式，我就不重复了，之前的程序里面也有，这里就只说说代码里几个参数的思路。
一定要做边界条件的判断！*

root->left = build(preorder, pstart + 1, pstart + i - istart, inorder, istart, i - 1);
root->right = build(preorder, pstart + i - istart + 1, pend, inorder, i + 1, iend);

对于左子树处理来说，中序遍历所要处理的位置就是根节点左侧的所有数字，所以自然起始位置就是istart，结束位置就是i-1；对于前序遍历来说表示就麻烦一些，起始位置还好，是pstart+1,结束位置是pstart+(i-istart)，其中i-istart是左子树的元素数。
对于右子树处理来说，中序遍历所要处理的位置就是根节点右侧的所有数字，所以自然起始位置就是i+1，结束位置就是iend；对于前序遍历来说，就是从左侧子树最后一个元素后面那个数字到最后一个，所以起始位置是pstart + i - istart + 1，结束位置是pend。

代码实现

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
	int presize = preorder.size();
	int insize = inorder.size();
	if (presize == 0 || insize == 0)
	{
		return NULL;
	}
	else if (presize != insize)
		return NULL;
	return build(preorder, 0, presize - 1, inorder, 0, insize - 1);
}

TreeNode* build(vector<int>&preorder, int pstart, int pend, vector<int>&inorder, int istart, int iend)
{
	if (pstart > pend || istart > iend)
		return NULL;
	int mid = preorder[pstart];
	TreeNode* root = new TreeNode(mid);
	int i = istart;
	for (; i <= iend; ++i)
	{
		if (inorder[i] == mid)
			break;
	}

	root->left = build(preorder, pstart + 1, pstart + i - istart, inorder, istart, i - 1);
	root->right = build(preorder, pstart + i - istart + 1, pend, inorder, i + 1, iend);
	return root;
}