小奥的学习笔记

  • 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题目解析(191127):1&19&70&78&79&84

2019年11月27日 961点热度 0人点赞 0条评论

Leetcode 1:两数之和

题目描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目解析

直接看代码即可,非常清晰

代码实现

vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>res(2,-1);
        map<int,int> tmp;
        for(int i=0;i<nums.size();i++)
        {
            if(tmp.count(target-nums[i]))
            {
                res[0]=tmp[target - nums[i]];
                res[1]=i;
                break;
            }
            tmp[nums[i]]=i;
        }
        return res;
    }

复杂度

复杂度分析

Leetcode 19:删除链表的倒数第N个节点

题目描述

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

代码实现

ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == NULL )
        return head;
    ListNode *dummy=new ListNode(-1);
    dummy->next = head;
    ListNode *pre = dummy;
    ListNode *end = dummy;
    //Move end to n+1 
    for (int i = 0; i < n + 1; i++)
    {
        end = end->next;
    }
    while (end != NULL)
    {
        pre = pre->next;
        end = end->next;
    }
    ListNode *dpoint = pre->next;//待删除的点
    pre->next = dpoint->next;
    delete(dpoint);
    return dummy->next;
    }

复杂度

时间复杂度O(n)

复杂度分析

Leetcode 70:爬楼梯

题目描述

题目解析

我们很容易就发现,由于我们可以走一步也可以走两步,那实际对于第n个台阶来说,其依赖于走第n-1阶有多少种方法(此时只需要再走1步即可)和走第n-2阶有多少种方法(此时只需要再走2步即可),也就是说f(n)=f(n-1)+f(n-2),为一个斐波那契数列。递归形式很简单,所以这里写了一个迭代形式。

代码实现

int climbStairs(int n) {
    if (n == 0 || n == 1)
        return 1;
    if (n == 2)
        return 2;
    int first = 1, second = 2;
    for (int i = 3; i <= n; i++)
    {
        int third = first + second;
        first = second;
        second = third;
    }
    return second;
}

复杂度

时间复杂度:O(n),空间复杂度O(1)。
复杂度分析

Leetcode 78:子集

题目描述

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集。

示例

输入: nums = [1,2,3]
输出:
[
[3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

代码实现

vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> temp;
        vector<vector<int>> r;
        dfs(r, temp, nums, 0);
        return r;
    }
    void dfs(vector<vector<int>>& r, vector<int>& temp, const vector<int>& nums, int begin)
    {
        r.push_back(temp);
        for (int i = begin; i < nums.size(); i++)
        {
            temp.push_back(nums[i]);
            dfs(r, temp, nums, i + 1);
            temp.pop_back();
        }
    }

实现消耗

复杂度分析

Leetcode 79:单词搜索

题目描述

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

解题思路

看这个题,我们自己脑子里先有一个思路:首先遍历这个矩阵,寻找到第一个对应的字母,然后再对其上下左右方向进行搜索,寻找下一个字母。
我们还需要注意可能存在这样一种情况,比如说在矩阵中有两个A,其中第一个A的上下左右不符合我们的要求,而第二个A则符合。此时当我们遍历到第一个A的时候,符合要求,开始对它的上下左右搜索,结果搜索不到,此时不应该单纯返回false然后判断找不到,而是应该继续遍历这个矩阵,寻找第二个A。

所以这个题可以使用回溯法解决,涉及到了深度优先遍历和状态重置。

我们结合ABCCED这个组合来顺一遍代码。

题解

题解

题解

题解

题解

代码实现

vector<vector<int>>dir{ {-1,0},{1,0},{0,-1},{0,1} };
    bool edfs(int x, int y, int ind, vector<vector<char>>& board, string& word, vector<vector<bool>>& visited)
{
    //word长度为1的情况
    if (ind == word.size() - 1)
        return word[ind] == board[x][y];
    //其它情况
    if (word[ind] == board[x][y])
    {
        visited[x][y] = true;//找到了,在visited中相应坐标标记
        //然后开始在上下左右寻找下一个字母
        for (int i = 0; i < 4; i++)
        {
            int new_x = x + dir[i][0];
            int new_y = y + dir[i][1];
            if (new_x >= 0 && new_x < board.size() && new_y >= 0 && new_y < board[0].size() && !visited[new_x][new_y])
            {
                if (edfs(new_x, new_y, ind + 1, board, word, visited))
                    return true;
            }
        }
        visited[x][y] = false;
    }
    //字符找不到
    return false;
}
bool exist(vector<vector<char>>& board, string word) {
    int row = board.size();
    int col = board[0].size();
    vector<vector<bool>> visited(row, vector<bool>(col));
    //从矩阵的第一个元素开始寻找与word第一个字母相对应的字母,若找不到,则j+1,j加到最后,就i+1,这样一行一行查找。
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            if (edfs(i, j, 0, board, word, visited))
                return true;
        }
    }
    //找不到就返回false
    return false;
}

复杂度

复杂度分析

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

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:TV版 我所使用的一些Wordpress东东 Leetcode题目解析(191121):105&114 2009 S.V Beijing Travel 23~25:杂谈 2011年12月voa常速英语mp3打包下载 C++:实现“鱼额宝”
标签聚合
Java 生活 鸟哥的linux私房菜 python学习 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号