2019-05-24 330 views 评论

[leetcode]题目解析（190524）

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] &gt;= '1' &amp;&amp; board[i][j]&lt;='9')
    int temp = board[i][j]-'1';

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&lt;vector&lt;char&gt; &gt; &amp;board) {
        int totalRows = board.size();
        int totalCols = board[0].size();
        if(totalRows == 0 || totalCols == 0)
            return false;
        vector&lt;vector&lt;bool&gt; &gt; fRow(totalRows,vector&lt;bool&gt;(totalCols,false));//行标志矩阵
        vector&lt;vector&lt;bool&gt; &gt; fCol(totalRows,vector&lt;bool&gt;(totalCols,false));//列标志矩阵
        vector&lt;vector&lt;bool&gt; &gt; fMat(totalRows, vector&lt;bool&gt;(totalCols,false));//9宫格标志矩阵
        for(int i = 0;i &lt; totalRows; i++)
        {
            for(int j = 0; j &lt; totalCols; j++)
            {
                if(board[i][j] &gt;= '1' &amp;&amp; board[i][j]&lt;='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;
    }

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

}

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]);

}

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

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-&gt;left = build(preorder, pstart + 1, pstart + i - istart, inorder, istart, i - 1);
    root-&gt;right = build(preorder, pstart + i - istart + 1, pend, inorder, i + 1, iend);

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&lt;int&gt; &amp;preorder, vector&lt;int&gt; &amp;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&lt;int&gt;&amp;preorder, int pstart, int pend, vector&lt;int&gt;&amp;inorder, int istart, int iend)
{
    if (pstart &gt; pend || istart &gt; iend)
        return NULL;
    int mid = preorder[pstart];
    TreeNode* root = new TreeNode(mid);
    int i = istart;
    for (; i &lt;= iend; ++i)
    {
        if (inorder[i] == mid)
            break;
    }

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