小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

[leetcode]题目解析(190524)

2019年5月24日 1173点热度 0人点赞 0条评论

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]为例来思考这个题目的思想。观察如图所示。

7ca37b3c6aa82f235c77db4e0ebd8239.png

代码实现

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;
}
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode 算法
最后更新:2019年5月24日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
语音信号处理学习笔记(1):语音的基本知识 Java语言程序设计【学堂在线】编程作业(第一章) 递归读目录获取普通文件个数 使用HTK中的HResults计算WER 2013年山东高考本科上线资料统计(个人制作) Python语言程序设计(第6周)知识点整理
标签聚合
算法 学习 高中 linux Python Java 鸟哥的linux私房菜 python学习 leetcode 生活
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号