2019-11-27  89 views 评论

Leetcode题目解析(191127):1&19&70&78&79&84

 标签:

Leetcode 1:两数之和

题目描述

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

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

示例

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

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

题目解析

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

代码实现

复杂度

复杂度分析

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

题目描述

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

示例

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

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

代码实现

复杂度

时间复杂度O(n)

复杂度分析

Leetcode 70:爬楼梯

题目描述

题目解析

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

代码实现

复杂度

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

Leetcode 78:子集

题目描述

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

示例

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

代码实现

实现消耗

复杂度分析

Leetcode 79:单词搜索

题目描述

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

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

示例

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

解题思路

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

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

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

题解

题解

题解

题解

题解

代码实现

复杂度

复杂度分析

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: