Tag Archives: LeetCode

数组中第k大的元素

此文为 LeetCode 215. Kth Largest Element in an Array 的题解。

题意

在一个未排序的数组中,寻找第k大的元素。

分析

这个题目其实很简单,但是踩了一些坑,所以记录一下:

首先是用PriorityQueue,然后poll k次即可(5 ms,37.5 MB)。但是属于API caller,略去不表。

其次就是堆排序,很久不写了,第一次把堆排序写成了选择排序,导致时间很长:101 ms,37.2 MB。

后来复习了下堆排序,写出来了(2 ms,36.6 MB):

// from https://www.robberphex.com/kth-largest-element-in-an-array/
Read the rest

LeetCode 25. Reverse Nodes in k-Group

本文为LeetCode 25. Reverse Nodes in k-Group的题解。

题意

给定一个链表,k个一组反转链表。

k 是一个正数,且小于链表长度。如果按照k个一组,最后剩下的不组k,则不反转剩下的元素。

例子:

对于链表: 1->2->3->4->5

k = 2, 应返回: 2->1->4->3->5

k = 3, 应返回: 3->2->1->4->5

注意:

  • 只允许O(1)的空间复杂度。
  • 不可以改变节点的值。

题解

这个题目麻烦的地方在… Read the rest

LeetCode:991. Broken Calculator

此文为LeetCode 991. Broken Calculator的题解。

题意

有一台坏掉的计算器,能够显示一个数字,我们可以对这个数字做两个操作:

  • 二: 将显示的数字乘以2, 或者;
  • 减一: 将显示的数字减1.

初始时,计算器显示数字 X.

返回要得到数字Y需要的最小操作次数。

题解

如果XY,则只能执行减一操作。否则,如果Y是奇数,则上一步操作一定是X减一;如果Y是偶数,则上一步操作只能是X乘二

只需要通过上述规则,由Y反推X即可。

代码

/**
 * https://www.robberphex.com/broken-calculator/
Read the rest

LeetCode:1106. Parsing A Boolean Expression

本文是LeetCode 1106. Parsing A Boolean Expression的题解。

题意

给定一个String类型的布尔表达式expression,返回一个求值的结果。

表达式可以是:

  • "t", 表示为 True;
  • "f", 表示为 False;
  • "!(expr)", 将内部的 expr 结果取反;
  • "&(expr1,expr2,...)", 将内部的expr1, expr2, ...求与;
  • "|(expr1,expr2,...)", 将内部的expr1, expr2, ...求或。

题解

直接递归解释表达式… Read the rest

LeetCode:103. Binary Tree Zigzag Level Order Traversal

本文为LeetCode:103. Binary Tree Zigzag Level Order Traversal的题解。

题意

一颗给定的二叉树,返回节点值的之子形的便利结果。即,从左到右,然后下一级别是从右到左,如此交替。

例如:

给定二叉树:[3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

程序将会返回之字形遍历顺序:

[
  [3],
  [20,9],
  [15,7]
]

题解

对于第一层遍历,从左到右,添加到一个stack中;对于第二层遍… Read the rest

LeetCode 1103:Distribute Candies to People

本文为LeetCode 1103:Distribute Candies to People的题解。

题意

我们用下面的方法给num_people个人分发一些糖果:

我们给第一个人1块糖,给第二个人2块糖,以此类推,直到我们给最后一个人n块糖。

然后,我们回到开始,给第一个人n + 1块糖,给第二个人n + 2块糖,以此类推,直到我们给最后一个人2 * n块糖。

这个过程不断重复(当重新走到队首的时候,我们每次比上次多给n个糖果),直到糖果分配结束。最后一个人将收到我们所有剩余的糖果。

返回一个数组(长度为num_people… Read the rest

LeetCode题解:Path In Zigzag Labelled Binary Tree

本文为LeetCode 1104. Path In Zigzag Labelled Binary Tree 的题解。

题目描述

一棵无穷的二叉树,每个节点都编号(label)了:对于奇数层(第1、3、5等层),从左向右编号。对于偶数层,从右向左编号。但是每层的编号还是最小2^(level-1),最大2^level-1

如图:

给你一个编号(label),输出从顶层到该节点经过的节点编号。

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output:
Read the rest

LeetCode 41. First Missing Positive

这个题目虽然是Hard,但是只要想到解法之后,就很简单了。

题目要求:找到最小的、没有出现在数组中的整数,数组未排序。

初看起来,这个至少得排个序才能搞定。但是题目说了,时间复杂度O(n),空间复杂度O(1)。

如果能把数字n填写到第n-1个,那不就能在O(n)时间内看出来缺失数字了吗?把数字n填写到第n-1个,完全就是遍历一遍所有的数字就可以了啊。

思路就这样出来了:

  1. 遍历所有数字,将数字n放到第n-1个位
  2. 遍历数组,第一个不满足nums[i]!=i+1的i+1即为缺失的数字

代码如下:

class Solution
Read the rest

Leetcode 990: 等式的满足性

题目来源:https://leetcode.com/problems/satisfiability-of-equality-equations/

题目描述:

给一字符串数组,每个元素是一个等式,表示两个变量之间的关系。每个等式长度为4,形如 “a==b” 或者 “a!=b”,a 和 b 两个小写字母表示变量名,a和b可能相同。

如果能给这些变量分配数字,并满足这些等式,返回 true。

解题过程:

开始想着,遇见新变量且没有约束就… Read the rest