小奥的学习笔记

  • 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]题目解析(190612)

2019年6月12日 937点热度 0人点赞 0条评论

Surrounded Regions

题目描述

Given a 2D board containing'X'and'O', capture all regions surrounded by'X'.A region is captured by flipping all'O's into'X's in that surrounded region .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

解题思路

这道题的意思是,将边界及所有与边界相连的O予以保留,其它的O变为X。
所以我们可以采取的思路是,将边界及所有与边界相连的O先行转换成别的字母,例如S。然后遍历整个矩阵,将所有的O变为X,所有的S变为O,这样就完成了任务。

代码实现

void toS(vector<vector<char>> &board, int i, int j,int rows, int cols)
{
    if (i < 0 || j < 0 || i >= rows || j >= cols)
        return;
    if (board[i][j] == 'O')
    {
        board[i][j] = 'S';
        toS(board, i + 1, j, rows, cols);
        toS(board, i - 1, j, rows, cols);
        toS(board, i, j - 1, rows, cols);
        toS(board, i, j + 1, rows, cols);
    }

}

void solve(vector<vector<char>> &board) {
    int rows = board.size();//行数
    int cols = board[0].size();//列数
    if (rows <= 2 || cols <= 2)
        return;
    //第一行
    for (int i = 0; i < cols; i++)
    {
        if (board[0][i] == 'O')
            toS(board, 0, i,rows,cols);
    }
    //最后一行
    for (int i = 0; i < cols; i++)
    {
        if (board[rows - 1][i] == 'O')
            toS(board, rows - 1, i, rows, cols);
    }

    //第一列
    for (int i = 1; i < rows - 1; i++) {
        if (board[i][0] == 'O')
            toS(board, i, 0, rows, cols);
    }

    //最后一列
    for (int i = 1; i < rows - 1; i++)
    {
        if (board[i][cols - 1]=='O')
            toS(board, i, cols - 1, rows, cols);
    }
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            if (board[i][j] == 'O')
                board[i][j] = 'X';
            else if (board[i][j] == 'S')
                board[i][j] = 'O';
        }
    }
}

Valid-Parentheses

题目描述

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true

示例 2:

输入: "()[]{}"
输出: true

示例 3:

输入: "(]"
输出: false

示例 4:

输入: "([)]"
输出: false

示例 5:

输入: "{[]}"
输出: true

题目解析

这种匹配问题,我们有这种思想,可以用栈来解决这个问题。因为合法的匹配实际上是类似于{[()]}这样的匹配,你会发现先输入的符号相匹配的右半边是最后输入,也就是说符合栈先入后出的特性。当pop完了这个栈为空,那就说明匹配。所以我们可以设计这这样一个算法:遍历整个字符串的每一个字符,然后:
1. 如果字符是左侧符号(如{``(``[)那么我们就向堆栈里面push进去;
2. 当字符不是左侧符号的时候,首先要判断堆栈此时是否为空,若为空返回false,因为左侧符号还未匹配完;如果栈不为空,判断此时栈顶元素是否与当前元素相等,若不相等,也返回flase;若相等,pop出来,继续走下去。
3.当所有字符遍历完,这个时候判断栈是否为空,若为空说明都匹配,返回true,否则返回false。

代码实现

bool isValid(string s) {
    int slen = s.size();
    if (slen == 0)
        return true;
    if (slen < 2)
        return false;
    stack<char>cstack;
    for (int i = 0; i < slen; i++)
    {
        if (s[i] == '(')
            cstack.push(')');
        else if (s[i] == '[')
            cstack.push(']');
        else if (s[i] == '{')
            cstack.push('}');
        else if (cstack.empty() || cstack.top() != s[i])
            return false;
        else
            cstack.pop();
    }
    return cstack.empty();

}

remove-nth-node-from-end-of-list

题目描述

Given a linked list, remove the n th node from the end of list and return its head.

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid.Try to do this in one pass.

解题思路

要求只能走一次路径,所以启发我们使用快慢指针。由于给予n总是合法的,所以我们不需要判断n是否超过链表长度(如果需要判断的话,必然不可能只走一趟)。

假设我们的链表是1->2->3->4->5,且n=2。那么我们初始状态下,链表如下:

2f36a12b121ad85ccb86484bd9a65a55.png

第一步,首先建立一个头指针,命名为dummy,算是一个pivot,然后令head也指向这个dummy。
第二步,新建快指针pfast、慢指针pslow,然后分别指向dummy。
到目前为止,链表关系如下图所示:
1b055cefbd3a12b61c57db3d0042af2e.png

第三步,这一步很关键。就是后移pfast指针n个位置,在这里就是2个位置。结果如下:
d59202ae5c0b12f16022575fc3ecdcdc.png

第四步,在完成上述操作之后,开始同时移动pfast和pslow,直到pfast的next指针为空的时候停止移动。这个时候的结果如下:
3984e10e8db88297035d408486fbb356.png

第五步,我们新建一个链表指针指向pslow的next,命名为delp节点,这就是我们待删除的位置。然后令pslow的next指向5的地址(pslow->next=pslow->next->next)。
第六步,删除delp节点,也就是执行delete(delp)命令。
最后,返回dummy->next即可。结果如下:

28a1e03948c4a4d7a6b32e53bff91872.png

代码实现

ListNode *removeNthFromEnd(ListNode *head, int n) {
    if (head == NULL)
        return head;
    ListNode *dummy = new ListNode(-1);
    dummy->next = head;
    head = dummy;
    ListNode *pslow = head;
    ListNode *pfast = head;
    while (n--)
    {
        pfast = pfast->next;
    }
    while (pfast->next != NULL)
    {
        pslow = pslow->next;
        pfast = pfast->next;
    }
    ListNode *delp = pslow->next;
    pslow->next = pslow->next->next;
    delete delp;
    return dummy->next;

}
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年6月12日

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
2015.1—2015.3【寒假】的计划(证书考试)安排 Leetcode题目解析(191206):33&34&39&42 Leetcode题目解析(191021) 生活点滴0920:学校的一些图片 新做了两个图,发出来纪念一下 The differences of academic writing and other types of writing
标签聚合
算法 生活 鸟哥的linux私房菜 学习 高中 leetcode python学习 Java Python linux
最近评论
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号