0%


题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y,计算它们之间的汉明距离。

示例:

输入: x = 1, y = 4
输出: 2
解释:

1
2
3
1   (0 0 0 1)
4 (0 1 0 0)
↑ ↑
阅读全文 »


前言

最近一直在刷 Leetcode ,其中涉及了很多二叉树相关的题,二叉树是一种很重要的数据结构,很多其他的数据结构都是以二叉树为基础,二叉树的遍历涉及很多种,包括前序遍历、中序遍历、后序遍历、层次遍历。开始一直分不清这些遍历是如何工作的,随着后面题刷的越来越多,也渐渐熟悉了二叉树的遍历方式,在这里做一个总结分享给大家。

四种遍历的主要方式为:

  • 前序遍历:根节点 -> 左子树 -> 右子树
  • 中序遍历:左子树 -> 根节点 -> 右子树
  • 后序遍历:左子树 -> 右子树 -> 根节点
  • 层次遍历:从上到下按照层遍历

接下来使用以下的二叉树做样例:

1
2
3
4
5
6
7
8
9
10
11
12
13

1
/ \
2 3
/ \ \
4 5 6
/ \
7 8

前序遍历:1 2 4 5 7 8 3 6
中序遍历:4 2 7 5 8 1 3 6
后序遍历:4 7 8 5 2 6 3 1
层次遍历:1 2 3 4 5 6 7 8
阅读全文 »


题目描述

给定一个表示分数的非负整数数组。 玩家 1 从数组任意一端拿取一个分数,随后玩家 2 继续从剩余数组任意一端拿取分数,然后玩家 1 拿,…… 。每次一个玩家只能拿取一个分数,分数被拿取之后不再可取。直到没有剩余分数可取时游戏结束。最终获得分数总和最多的玩家获胜。给定一个表示分数的数组,预测玩家1是否会成为赢家。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1:

输入:[1, 5, 2]
输出:False
解释:一开始,玩家1可以从1和2中进行选择。
如果他选择 2(或者 1 ),那么玩家 2 可以从 1(或者 2 )和 5 中进行选择。如果玩家 2 选择了 5 ,那么玩家 1 则只剩下 1(或者 2 )可选。
所以,玩家 1 的最终分数为 1 + 2 = 3,而玩家 2 为 5 。
因此,玩家 1 永远不会成为赢家,返回 False 。

示例 2:

输入:[1, 5, 233, 7]
输出:True
解释:玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个,玩家 1 都可以选择 233 。最终,玩家 1(234 分)比玩家 2(12 分)获得更多的分数,所以返回 True,表示玩家 1 可以成为赢家。

提示:

  • 1 <= 给定的数组长度 <= 20.
  • 数组里所有分数都为非负数且不会大于 10000000 。
  • 如果最终两个玩家的分数相等,那么玩家 1 仍为赢家。
阅读全文 »


题目描述

有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,…,N - 1,并且房间里可能有一些钥匙能使你进入下一个房间。在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0, 1,…,N - 1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初,除 0 号房间外的其余所有房间都被锁住。你可以自由地在房间之间来回走动。如果能进入每个房间返回 true,否则返回 false。

示例 1:

输入: [[1], [2], [3], []]
输出: true
解释:
我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。

示例 2:

输入:[[1, 3], [3, 0, 1], [2], [0]]
输出:false
解释:我们不能进入 2 号房间。

提示:

  • 1 <= rooms.length <= 1000
  • 0 <= rooms[i].length <= 1000
  • 所有房间中的钥匙数量总计不超过 3000。
阅读全文 »


题目描述

给定一个机票的字符串二维数组 [from, to],子数组中的两个成员分别表示飞机出发和降落的机场地点,对该行程进行重新规划排序。所有这些机票都属于一个从 JFK(肯尼迪国际机场)出发的先生,所以该行程必须从 JFK 开始。

提示:

  • 如果存在多种有效的行程,请你按字符自然排序返回最小的行程组合。例如,行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小,排序更靠前。
  • 所有的机场都用三个大写字母表示(机场代码)。
  • 假定所有机票至少存在一种合理的行程。
  • 所有的机票必须都用一次且只能用一次。

示例 1:

输入:[[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]]
输出:[“JFK”, “MUC”, “LHR”, “SFO”, “SJC”]

示例 2:

输入:[[“JFK”, “SFO”],[“JFK”, “ATL”],[“SFO”, “ATL”],[“ATL”, “JFK”],[“ATL”, “SFO”]]
输出:[“JFK”, “ATL”, “JFK”, “SFO”, “ATL”, “SFO”]
解释:另一种有效的行程是 [“JFK”, “SFO”, “ATL”, “JFK”, “ATL”, “SFO”]。但是它自然排序更大更靠后。

阅读全文 »


题目描述

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

示例 1:

输入: [5, 7]
输出: 4

示例 2:

输入: [0, 1]
输出: 0

阅读全文 »


题目描述

给你一棵二叉搜索树,请你返回一棵平衡后的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是平衡的。如果有多种构造方法,请你返回任意一种。

示例:

输入:root = [1, null, 2, null, 3, null, 4, null, null]
输出:[2, 1, 3, null, null, null, 4]
解释:这不是唯一的正确答案,[3, 1, 4, null, 2, null, null] 也是一个可行的构造方案。

提示:

  • 树节点的数目在 1 到 10^4 之间。
  • 树节点的值互不相同,且在 1 到 10^5 之间。
阅读全文 »


题目描述

给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

示例 1:

1
2
3
4
5
6
7
给定二叉树 [3, 9, 20, null, null, 15, 7]
3
/ \
9 20
/ \
15 7
返回 true 。

示例 2:

1
2
3
4
5
6
7
8
9
给定二叉树 [1, 2, 2, 3, 3, null, null, 4, 4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
阅读全文 »