LeetCode 简单题（1）
来源剑指offer (opens new window) 主要分析javaScript和Python解法
# No.1 斐波那契 I
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
# Solution
方法一、动态规划
class Solution:
def fib(self, n: int) -> int:
MOD = 10 ** 9 + 7
if n < 2:
return n
p, q, r = 0, 0, 1
for i in range(2, n + 1):
p = q
q = r
r = (p + q) % MOD
return r
var fib = function(n) {
const MOD = 1000000007;
if (n < 2) {
return n;
}
let p = 0, q = 0, r = 1;
for (let i = 2; i <= n; ++i) {
p = q;
q = r;
r = (p + q) % MOD;
}
return r;
}
# No.2 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
读不懂题目不是我的错
输入： ["CQueue","appendTail","deleteHead","deleteHead"]
这一行表示每一行代码的操作
[[],[3],[],[]]
这个表示每一行代码操作所需要的参数
举例： CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此操作不需要参数。
appendTail 表示执行一个appendTail()操作，对应要被操作的元素为3。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：
1 <= values <= 10000 最多会对appendTail、deleteHead 进行10000次调用
# Solution
双栈
var CQueue = function() {
this.stackA = [];
this.stackB = [];
};
CQueue.prototype.appendTail = function(value) {
this.stackA.push(value);
};
CQueue.prototype.deleteHead = function() {
if(this.stackB.length){
return this.stackB.pop();
}else{
while(this.stackA.length){
this.stackB.push(this.stackA.pop());
}
if(!this.stackB.length){
return -1;
}else{
return this.stackB.pop();
}
}
};
class CQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def appendTail(self, value: int) -> None:
# 1 -> 2
while self.stack1:
self.stack2.append(self.stack1.pop())
# add value
self.stack1.append(value)
# 1 <- 2
while self.stack2:
self.stack1.append(self.stack2.pop())
return self.stack1
def deleteHead(self) -> int:
if not self.stack1: return -1
return self.stack1.pop()
# No.3 数组中重复的数字
找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
# Solution
JS方法一：哈希表判定存在
var findRepeatNumber = function(nums) {
let map = new Map();
for(let i of nums){
if(map.has(i)) return i;
map.set(i, 1);
}
return null;
};
Python方法一：set不重复性质
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
temp_set = set()
repeat = -1
for i in range(len(nums)):
temp_set.add(nums[i])
if len(temp_set) < i + 1:
repeat = nums[i]
break
return repeat
方法二：相邻数字相等
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums)-1):
if nums[i]==nums[i+1]:
return nums[i]
# No.4 青蛙跳台阶
经典动态规划，将问题化小。
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：2 示例 2：
输入：n = 7 输出：21 示例 3：
输入：n = 0 输出：1
# Solution
class Solution:
def numWays(self, n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a % 1000000007
/**
* @param {number} n
* @return {number}
*/
var numWays = function(n) {
let sum = 0;
let x = 1;
let y = 1;
for(let i =0;i < n;i++){
sum = (x + y)%1000000007;
x = y;
y = sum
}
return x;
};
# No.5 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
实际上用二分法找已排序数组一样，局部地左小右大，注意考虑相同数字
var minArray = function(numbers) {
let low = 0;
let high = numbers.length - 1;
while (low < high) {
const pivot = low + Math.floor((high - low) / 2); // 取整
if (numbers[pivot] < numbers[high]) {
high = pivot;
} else if (numbers[pivot] > numbers[high]) {
low = pivot + 1;
} else {
high -= 1;
}
}
return numbers[low];
};
class Solution:
def minArray(self, numbers: List[int]) -> int:
low, high = 0, len(numbers) - 1
while low < high:
pivot = low + (high - low) // 2
if numbers[pivot] < numbers[high]:
high = pivot
elif numbers[pivot] > numbers[high]:
low = pivot + 1
else:
high -= 1
return numbers[low]
# No.6 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
# Solution
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
let p = head = { next: null }
// 循环依次对比
while (l1 || l2) {
// l1 存在
if ((l1 && !l2) || (l1 && l1.val < l2.val)) {
// 得到 p.next 指向 以及 更新 l1
p.next = l1
l1 = l1.next
} else {
// 得到 p.next 指向 以及 更新 l2
p.next = l2
l2 = l2.next
}
// 更新p
p = p.next
}
return head.next
};
# No.7 二叉树镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
这个输入都比较骗人，实际上给的是树的根节点
# Solution
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var mirrorTree = function(root) {
if (root === null) {
return null;
}
const left = mirrorTree(root.left);
const right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
};
# No.8 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
这个输入都比较骗人，实际上给的是树的根节点
# Solution
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
//判断树是否为空
if(root===null){
return true;
}else{
return res(root.left,root.right);
}
function res(L,R){
if(L===null&&R===null){
return true;
}else if(L===null||R===null||L.val!==R.val){
return false;
}else{
return res(L.left,R.right)&&res(L.right,R.left);
}
}
};