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类型，因此首先要进行一个类型转换才能判断：
| 1 2 3 | if(board[i][j] >= '1' && board[i][j]<='9') int temp = board[i][j]-'1'; |
若检测到该行出现这个数字，则设置该行这个位置为true，当又遍历到这个数字的时候，若检查发现这个位置已经设置为true了，则返回false。当然在实现代码的时候，要把判断放在前面，把设置标志位放在后面。
该方法的时间复杂度为O(n2)，空间复杂度为O(n2)。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | 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]为例来思考这个题目的思想。观察如图所示。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | 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].
题目解析
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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.
思路
关于根据前序和中序如何得到二叉树的结构的计算方式，我就不重复了，之前的程序里面也有，这里就只说说代码里几个参数的思路。
**一定要做边界条件的判断！***
| 1 2 3 | 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。
代码实现
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | 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; } |
