Leet Code 01 - 基础题合集
0. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
解答如下:
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if m == n {
return head
}
T := &ListNode{0, head}
ph := T
pe := T.Next
for i := 1; i < m; i++ {
ph = ph.Next
pe = pe.Next
}
pt := pe.Next
for i := 0; i < (n - m); i++ {
pe.Next = pt.Next
pt.Next = ph.Next
ph.Next = pt
pt = pe.Next
}
return T.Next
}
1. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
func swapPairs(head *ListNode) *ListNode {
T := &ListNode{0, head}
ph := T
for ph.Next != nil {
pt := ph.Next.Next
if pt != nil {
ph.Next.Next = pt.Next
pt.Next = ph.Next
ph.Next = pt
ph = ph.Next.Next
} else {
break
}
}
return T.Next
}
不加额外节点的版本
func swapPairs(head *ListNode) *ListNode {
if head == nil {
return head
}
ph := head
pt := head.Next
if pt != nil {
ph.Next = pt.Next
pt.Next = ph
head = pt
}
for ph.Next != nil {
pt := ph.Next.Next
if pt != nil {
ph.Next.Next = pt.Next
pt.Next = ph.Next
ph.Next = pt
ph = ph.Next.Next
} else {
break
}
}
return head
}
2. 第k个排列
给出集合[1,2,3,…,n]，其所有元素共有n!种排列。
按大小顺序列出所有排列情况，并一一标记，当n = 3时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定n和k，返回第k个排列。
说明：
- 给定 n 的范围是 [1, 9]。
- 给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
解答如下:
对于一个n位数字 它从最高位到最低位每组能包含
(n-1)!、(n-2)!、(n-3)!, …, 1!, 0! 种情况
因此对于k我们只需要求出它分布在各位的第几组就行了
// 计算阶乘
func factorial(n int) int {
for i := n - 1; i > 1; i-- {
n *= i
}
if n == 0 {
return 1
}
return n
}
// 获取下一个数字
func getInxNum() func(int) int {
nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9}
return func(inx int) int {
c := 0
for i := 0; i < len(nums); i++ {
if nums[i] != 0 {
if c == inx {
n := nums[i]
nums[i] = 0
return n
}
c++
}
}
return 0
}
}
func getPermutation(n int, k int) string {
getNext := getInxNum()
ret := 0
k--
for i := n; i > 0; i-- {
FAC := factorial(i - 1)
div := k / FAC
mod := k % FAC
ret = ret*10 + getNext(div)
k = mod
}
return fmt.Sprintf("%v", ret)
}
3. 寻找两个正序数组的中位数
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解法简单，根据两个数组的长度是奇数还是偶数确定是需要两个数还是一个数来算中位数
用(TotalLen-1)/2来求出中位数的起始索引位置
找出索引位置后两个数字，就可以直接求出中位数
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
maxN := (len(nums1) + len(nums2) - 1) / 2
i := 0
j := 0
a := 0
b := 0
for c := 0; ; c++ {
if i >= len(nums1) && j < len(nums2) {
b = nums2[j]
j++
} else if j >= len(nums2) && i < len(nums1) {
b = nums1[i]
i++
} else if i < len(nums1) && j < len(nums2) {
if nums1[i] < nums2[j] {
b = nums1[i]
i++
} else {
b = nums2[j]
j++
}
}
if c == maxN+1 {
break
}
a = b
}
if (len(nums1)+len(nums2))%2 == 0 {
return float64(a + b) / 2.0
}
return float64(a)
}