一、LCP 1. 猜数字
小 A 和 小 B 在玩猜数字。小 B 每次从 1, 2, 3 中随机选择一个,小 A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏,请返回 小 A 猜对了几次?
输入的 guess 数组为 小 A 每次的猜测,answer 数组为 小 B 每次的选择。guess 和 answer 的长度都等于 3。
示例 1:
1 | 输入:guess = [1,2,3], answer = [1,2,3] |
示例 2:
1 | 输入:guess = [2,2,3], answer = [3,2,1] |
限制:
1 | guess的长度 = 3 |
答案
1 | func game(guess []int, answer []int) int { |
二、1281. 整数的各位积和之差
给你一个整数 n,请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
示例 1:
1 | 输入:n = 234 |
示例 2:
1 | 输入:n = 4421 |
提示:
1 | 1 <= n <= 10^5 |
答案
1 | func subtractProductAndSum(n int) int { |
三、1290. 二进制链表转整数
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1:
1 | 输入:head = [1,0,1] |
示例 2:
1 | 输入:head = [0] |
示例 3:
1 | 输入:head = [1] |
示例 4:
1 | 输入:head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] |
示例 5:
1 | 输入:head = [0,0] |
提示:
链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。
这道题巧妙的运运用到了 位运算符 |或 &与 运算 这个思想需要谨记
答案
1 | func getDecimalValue(head *ListNode) int { |
四、反转字符串
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[]
的形式给出。
不要给另外的数组分配额外的空间,你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1:
1 | 输入:["h","e","l","l","o"] |
示例 2:
1 | 输入:["H","a","n","n","a","h"] |
答案
递归方案
1 | func reverseString(s []byte) { |
for 循环
1 | func reverseString(s []byte) { |
五、771. 宝石与石头
给定字符串 J 代表石头中宝石的类型,和字符串 S 代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。
J 中的字母不重复,J 和 S 中的所有字符都是字母。字母区分大小写,因此”a”和”A”是不同类型的石头。
示例 1:
1 | 输入: J = "aA", S = "aAAbbbb" |
示例 2:
1 | 输入: J = "z", S = "ZZ" |
注意:
1 | S 和 J 最多含有50个字母。 |
答案:
golang 里面没有集合
不过 map 也是一种好的解决方案(待实现)
1 | func numJewelsInStones(J string, S string) int { |
六、链表交换
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
给定 1->2->3->4
, 你应该返回 2->1->4->3
.
答案:
1 | /** |
七、杨辉三角
给定一个非负整数 numRows,生成杨辉三角的前 numRows *行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
*示例:**
1 | 输入: 5 |
答案
1 | func generate(numRows int) [][]int { |
八、杨辉三角 II
给定一个非负索引 k_,其中 _k ≤ 33,返回杨辉三角的第 k *行。
在杨辉三角中,每个数是它左上方和右上方的数的和。
*示例:**
1 | 输入: 3 |
答案
1 | func getRow(rowIndex int) []int { |
进阶:
你可以优化你的算法到 O(k) 空间复杂度吗?
优化版本
1 | func getRow(rowIndex int) []int { |
九、反转一个单链表。
示例:
1 | 输入: 1->2->3->4->5->NULL |
进阶:你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
~~
答案
1 | func reverseList(head *ListNode) *ListNode { |
十、斐波那契
斐波那契数,通常用 F(n)
表示,形成的序列称为斐波那契数列。该数列由 0
和 1
开始,后面的每一项数字都是前面两项数字的和。也就是:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
给定 N
,计算 F(N)
。
1 | 示例 1: |
提示:
- 0 ≤
N
≤ 30
1 | var cache map[int]int = make(map[int]int,100) |
十一、爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
1 | 输入: 2 |
示例 2:
1 | 输入: 3 |
答案
1 | #动态规划 |
十二、第二高的薪水(MYSQL)
编写一个 SQL 查询,获取 Employee
表中第二高的薪水(Salary) 。
1 | +----+--------+ |
例如上述 Employee
表,SQL 查询应该返回 200
作为第二高的薪水。如果不存在第二高的薪水,那么查询应返回 null
。
1 | +---------------------+ |
答案
1 | select (select distinct Salary from Employee order by Salary desc limit 1 offset 1 )as SecondHighestSalary |
十三、打印从 1 到最大的 n 位数
输入数字 n
,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
1 | func printNumbers(n int) []int { |
十四、统计位数为偶数的数字
给你一个整数数组 nums,请你返回其中位数为 偶数 的数字的个数。
示例 1:
输入:nums = [12,345,2,6,7896]
输出:2
解释:
12 是 2 位数字(位数为偶数)
345 是 3 位数字(位数为奇数)
2 是 1 位数字(位数为奇数)
6 是 1 位数字 位数为奇数)
7896 是 4 位数字(位数为偶数)
因此只有 12 和 7896 是位数为偶数的数字
示例 2:
输入:nums = [555,901,482,1771]
输出:1
解释:
只有 1771 是位数为偶数的数字。
提示:
1 <= nums.length <= 500
1 <= nums[i] <= 10^5
1 | func findNumbers(nums []int) int { |
十五、统计有序矩阵中的负数
给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。
请你统计并返回 grid 中 负数 的数目。
示例 1:
输入:grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出:8
解释:矩阵中共有 8 个负数。
示例 2:
输入:grid = [[3,2],[1,0]]
输出:0
示例 3:
输入:grid = [[1,-1],[-1,-1]]
输出:3
示例 4:
输入:grid = [[-1]]
输出:1
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100
1 | func countNegatives(grid [][]int) int { |
十六、IP 地址无效化
给你一个有效的 IPv4 地址 address,返回这个 IP 地址的无效化版本。
所谓无效化 IP 地址,其实就是用 “[.]” 代替了每个 “.”。
示例 1:
输入:address = “1.1.1.1”
输出:”1[.]1[.]1[.]1”
示例 2:
输入:address = “255.100.50.0”
输出:”255[.]100[.]50[.]0”
提示:
给出的 address 是一个有效的 IPv4 地址
答案
1 | func defangIPaddr(address string) string { |
十七、替换空格
请实现一个函数,把字符串 s 中的每个空格替换成”%20”。
示例 1:
输入:s = “We are happy.”
输出:”We%20are%20happy.”
限制:
0 <= s 的长度 <= 10000
!有点投机取巧
1 | func replaceSpace(s string) string { |
十八、位 1 的个数
编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。
示例 1:
输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 ‘1’。
示例 2:
输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 ‘1’。
示例 3:
输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 ‘1’。
提示:
请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 3 中,输入表示有符号整数 -3。
进阶:
如果多次调用这个函数,你将如何优化你的算法?
low 答案
1 | func hammingWeight(num uint32) int { |
high 答案
1 | func hammingWeight(num uint32) int { |
十九、大的国家
这里有张 World 表
+—————–+————+————+————–+—————+
| name | continent | area | population | gdp |
+—————–+————+————+————–+—————+
| Afghanistan | Asia | 652230 | 25500100 | 20343000 |
| Albania | Europe | 28748 | 2831741 | 12960000 |
| Algeria | Africa | 2381741 | 37100000 | 188681000 |
| Andorra | Europe | 468 | 78115 | 3712000 |
| Angola | Africa | 1246700 | 20609294 | 100990000 |
+—————–+————+————+————–+—————+
如果一个国家的面积超过 300 万平方公里,或者人口超过 2500 万,那么这个国家就是大国家。
编写一个 SQL 查询,输出表中所有大国家的名称、人口和面积。
例如,根据上表,我们应该输出:
+————–+————-+————–+
| name | population | area |
+————–+————-+————–+
| Afghanistan | 25500100 | 652230 |
| Algeria | 37100000 | 2381741 |
+————–+————-+————–+
1 | select name,population,area from World Where area>3000000 OR population> 25000000; |
二十、解压缩编码列表
给你一个以行程长度编码压缩的整数列表 nums 。
考虑每对相邻的两个元素 [a, b] = [nums[2i], nums[2i+1]] (其中 i >= 0 ),每一对都表示解压后有 a 个值为 b 的元素。
请你返回解压后的列表。
示例:
输入:nums = [1,2,3,4]
输出:[2,4,4,4]
解释:第一对 [1,2] 代表着 2 的出现频次为 1,所以生成数组 [2]。
第二对 [3,4] 代表着 4 的出现频次为 3,所以生成数组 [4,4,4]。
最后将它们串联到一起 [2] + [4,4,4] = [2,4,4,4]。
提示:
2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100
1 | func decompressRLElist(nums []int) []int { |
二十一、判定字符是否唯一
实现一个算法,确定一个字符串 s 的所有字符是否全都不同。
示例 1:
输入: s = “leetcode”
输出: false
示例 2:
输入: s = “abc”
输出: true
限制:
0 <= len(s) <= 100
如果你不使用额外的数据结构,会很加分。
1 | func isUnique(astr string) bool { |
二十二、URL 化
URL 化。编写一种方法,将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符,并且知道字符串的“真实”长度。(注:用 Java 实现的话,请使用字符数组实现,以便直接在数组上操作。)
示例 1:
输入:”Mr John Smith “, 13
输出:”Mr%20John%20Smith”
示例 2:
输入:” “, 5
输出:”%20%20%20%20%20”
提示:
字符串长度在[0, 500000]范围内。
1 | func replaceSpaces(S string, length int) string { |