Baylee的技术博客
0%

发表于 分类于

题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例

1
2
3
4
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
1
2
3
4
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
1
2
3
4
5
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示

  • nums1.length == m + n
  • ``nums2.length == n`
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109
阅读全文 »

发表于 分类于

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和 empty）。

实现 MyStack类：

void push(int x) 将元素 x 压入栈顶。
int pop()移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true；否则，返回 false。

注意：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和 empty）。

实现 MyStack类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true；否则，返回 false。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list（列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：

1
2
3
4
5
6
7
8
9
10
11
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

  • 1 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

阅读全文 »

发表于 分类于

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek和 empty
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

阅读全文 »

发表于 分类于

题目描述

给定一个数组prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例

1
2
3
4
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104
阅读全文 »

发表于 分类于

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例

1
2
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
1
2
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 104
  • -104 <= nums[i] <= 104

题解

利用快排的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
  var numbers = nums
  let targetIndex = numbers.count - k
  var left = 0
  var right = numbers.count - 1
  while true {
    let index = patitation(&numbers, left, right)
    if index == targetIndex {
      return nums[index]
    } else if index < targetIndex {
      left = index + 1
    } else {
      right = index - 1
    }
  }
}

func patitation(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
  guard left < right else { return left }
  var begin = left
  var end = right
  let povit = nums[begin]
  while begin < end {
    while begin < end && nums[end] >= povit {
      end -= 1
    }
    if begin < end {
      nums[begin] = nums[end]
      begin += 1
    }
    while begin < end && nums[begin] < povit {
      begin += 1
    }
    if begin < end {
      nums[end] = nums[begin]
      end -= 1
    }
  }
  nums[begin] = povit
  return begin
}

发表于 分类于

题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
1
2
输入：nums = [1]
输出：1
1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
阅读全文 »

发表于 分类于

题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例

给定二叉树：

1
root = [3,5,1,6,2,0,8,null,null,7,4]
1
2
3
输入：p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
1
2
3
输入：p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

提示：

  • 树中节点数目在范围 [2, 105]内。
  • -109 <= Node.val <= 109
  • 所有Node.val互不相同 。
  • p != q
  • p和q均存在于给定的二叉树中。
阅读全文 »

发表于 分类于

题目描述

示例1

1
2
输入：root = [1,2,2,3,4,4,3]
输出：true

示例1

1
2
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

  • 树中节点数目在范围 [1, 1000] 内
  • -100 <= Node.val <= 100
阅读全文 »

发表于 分类于

题目描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

给定二叉树如上图，返回3， 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

阅读全文 »

发表于 分类于

题目描述

给定一个二叉树的root，确定它是否是一个完全二叉树。

在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h节点之间的最后一级h。

示例1

1
2
3
输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

示例2

1
2
3
输入：root = [1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点没有尽可能靠向左侧。
阅读全文 »