算法面试题

LEETCODE EASY

1,给你一个由一些多米诺骨牌组成的列表 dominoes。

如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌,我们就认为这两张牌是等价的。

形式上,dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d,或是 a==d 且 b==c。

在 0 <= i < j < dominoes.length 的前提下,找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。

输入:dominoes = [[1,2],[2,1],[3,4],[5,6]]

输出:1

2,给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。

示例A:

输入: [3, 2, 1]

输出: 1

解释: 第三大的数是 1.

示例B:

输入: [2, 2, 3, 1]

输出: 1

解释: 注意,要求返回第三大的数,是指第三大且唯一出现的数。

存在两个值为2的数,它们都排第二。

3,给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

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

输出: [5,6,7,1,2,3,4]

解释:

向右旋转 1 步: [7,1,2,3,4,5,6]

向右旋转 2 步: [6,7,1,2,3,4,5]

向右旋转 3 步: [5,6,7,1,2,3,4]

4,回旋镖定义为一组三个点,这些点各不相同且不在一条直线上。给出平面上三个点组成的列表,判断这些点是否可以构成回旋镖。

示例 1:

输入:[[1,1],[2,3],[3,2]]

输出:true

示例 2:

输入:[[1,1],[2,2],[3,3]]

输出:false

5,编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例A:

输入: ["flower","flow","flight"]

输出: "fl"

示例B:

输入: ["dog","racecar","car"]

输出: ""

解释: 输入不存在公共前缀。

6,矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。

给出两个矩形,判断它们是否重叠并返回结果。

示例 1:

输入:rec1 = [0,0,2,2], rec2 = [1,1,3,3]

输出:true

示例 2:

输入:rec1 = [0,0,1,1], rec2 = [1,0,2,1]

输出:false

7,给定一个未经排序的整数数组,找到最长且连续的的递增序列。

示例 1:

输入: [1,3,5,4,7]

输出: 3

解释: 最长连续递增序列是 [1,3,5], 长度为3。

尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为5和7在原数组里被4隔开。

示例 2:

输入: [2,2,2,2,2]

输出: 1

解释: 最长连续递增序列是 [2], 长度为1。

8,给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例A:

输入: "A man, a plan, a canal: Panama"

输出: true

示例 B:

输入: "race a car"

输出: false

【LEETCODE MEDIUM】

1,给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

输入:

[

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

输出: [1,2,3,6,9,8,7,4,5]

2,给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

输入: 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

解释:

向右旋转 1 步: 5->1->2->3->4->NULL

向右旋转 2 步: 4->5->1->2->3->NULL

3,给出集合 [1,2,3,…,n],其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况,并一一标记,当 n = 3 时, 所有排列如下:

"123"

"132"

"213"

"231"

"312"

"321"

给定 n 和 k,返回第 k 个排列。

示例 1:

输入: n = 3, k = 3

输出: "213"

4,编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:

每行中的整数从左到右按升序排列。

每行的第一个整数大于前一行的最后一个整数。

示例 1:

输入:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 3

输出: true

5,给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例 2:

输入: 1->1->1->2->3

输出: 2->3

6,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。

写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

示例:

LRUCache cache = new LRUCache( 2 / 缓存容量 / );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 该操作会使得密钥 2 作废

cache.get(2); // 返回 -1 (未找到)

cache.put(4, 4); // 该操作会使得密钥 1 作废

cache.get(1); // 返回 -1 (未找到)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

8,给定一个二叉树,判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征:

节点的左子树只包含小于当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:

2

/ \

1 3

输出: true

示例 2:

输入:

5

/ \

1 4

 / \

3   6

输出: false

解释: 输入为: [5,1,4,null,null,3,6]。

 根节点的值为 5 ,但是其右子节点值为 4 。

9,给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。

示例 1:

输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]

输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

10,在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。

示例:

输入:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

输出: 4

11,给定一个大小为 n 的数组,找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

说明: 要求算法的时间复杂度为 O(n),空间复杂度为 O(1)。

示例 1:

输入: [3,2,3]

输出: [3]

示例 2:

输入: [1,1,1,3,3,2,2,2]

输出: [1,2]

12,给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2

输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

发表新评论