LeetCode算法面试题汇总-开始之前
LeetCode算法面试题汇总-开始之前
码农帮派
发布于 2021-01-12 11:32:20
发布于 2021-01-12 11:32:20
代码可运行
运行总次数：0
代码可运行
只出现一次的数字
[题目]
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
要求空间复杂度为O(1)。
[输入1]
[2,2,1][返回1]
1[输入2]
[4,1,2,1,2][返回2]
4[解法]
题目要求空间复杂度是O(1)，那就不能使用map，这里使用异或，我们知道一个数被同一个数异或两次之后，恢复为原来的数，题目中其他的数字都出现了两次，找那个唯一一次的数，可以让所有数字异或0，最后获得的就是只出现一次的那个数字。
[代码实现]
package main
import "fmt"
func main() {
input := []int {4,1,2,1,2}
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input []int) int {
temp := 0
for i := 0; i < len(input); i++ {
temp ^= input[i]
}
return temp
}多数元素
[题目]
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
[输入1]
[3,2,3][返回1]
3[输入2]
[2,2,1,1,1,2,2][返回2]
2[解法]
题目要求空间复杂度是O(1)，那就不能使用map，这里使用异或，我们知道一个数被同一个数异或两次之后，恢复为原来的数，题目中其他的数字都出现了两次，找那个唯一一次的数，可以让所有数字异或0，最后获得的就是只出现一次的那个数字。
[代码实现]
package main
import "fmt"
func main() {
input := []int {2,2,1,1,1,2,2}
result := computeResult(input)
fmt.Println("result:", result)
}
func computeResult(input []int) int {
filter := map[int]int {}
for i := 0; i < len(input); i++ {
if count, exists := filter[input[i]]; exists {
filter[input[i]] = count + 1
} else {
filter[input[i]] = 1
}
}
size := len(input) / 2
for key, value := range filter {
if value >= size {
return key
}
}
return -1
}搜索二维矩阵 II
[题目]
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
[输入1]
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],
target = 5[返回1]
true[输入2]
matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],
target = 20[返回2]
false[解法]
遍历整个二维矩阵，为了保证在同一方向上不回退，因为一回退就有可能进入一个死循环，我们保证两个遍历方向相反，一个从小到大，另一边从大到小遍历,即从左下方或者右上方开始遍历。
[代码实现]
package main
import "fmt"
func main() {
input := [][]int {
{1,4,7,11,15},
{2,5,8,12,19},
{3,6,9,16,22},
{10,13,14,17,24},
{18,21,23,26,30},
}
target := 5
result := computeResult(target, input)
fmt.Println("result:", result)
}
func computeResult(target int, input [][]int) bool {
colCount := len(input)
rowCount := len(input[0])
colIndex := 0
rowIndex := rowCount - 1
for colIndex < colCount && rowIndex >= 0 {
if input[colIndex][rowIndex] == target {
return true
}
if colIndex < colCount && input[colIndex][rowIndex] < target {
colIndex++
}
if rowIndex >= 0 && input[colIndex][rowIndex] > target {
rowIndex--
}
}
return false
}合并两个有序数组
[题目]
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明：
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
[输入]
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3[返回]
[1,2,2,3,5,6][解法]
无
[代码实现]
package main
import "fmt"
func main() {
num1 := []int {1,2,3,0,0,0}
m := 3
num2 := []int {2,5,6}
n := 3
result := computeResult(num1, m, num2, n)
fmt.Println("result:", result)
}
func computeResult(num1 []int, m int, num2 []int, n int) []int {
result := make([]int, len(num1))
num1Index := 0
num2Index := 0
pointer := 0
for num1Index < m || num2Index < n {
if pointer == len(num1) {
break
}
if num2Index >= n {
result[pointer] = num1[num1Index]
num1Index++
pointer++
continue
}
if num1Index >= m {
result[pointer] = num2[num2Index]
num2Index++
pointer++
continue
}
if num2[num2Index] < num1[num1Index] {
result[pointer] = num2[num2Index]
num2Index++
} else {
result[pointer] = num1[num1Index]
num1Index++
}
pointer++
}
return result
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-01-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
