小收获

<code>数组是存放在连续内存空间上的相同类型数据的集合

测试一下go

func main() {

fmt.Printf("Size of int: %d bytes\n", unsafe.Sizeof(int(0)))

fmt.Printf("Size of int8: %d bytes\n", unsafe.Sizeof(int8(0)))

fmt.Printf("Size of int16: %d bytes\n", unsafe.Sizeof(int16(0)))

fmt.Printf("Size of int32: %d bytes\n", unsafe.Sizeof(int32(0)))

fmt.Printf("Size of int64: %d bytes\n", unsafe.Sizeof(int64(0)))

fmt.Printf("Size of uint: %d bytes\n", unsafe.Sizeof(uint(0)))

fmt.Printf("Size of uint8: %d bytes\n", unsafe.Sizeof(uint8(0)))

fmt.Printf("Size of uint16: %d bytes\n", unsafe.Sizeof(uint16(0)))

fmt.Printf("Size of uint32: %d bytes\n", unsafe.Sizeof(uint32(0)))

fmt.Printf("Size of uint64: %d bytes\n", unsafe.Sizeof(uint64(0)))

fmt.Println("========================================================")

var testlist = []int{1, 2, 3, 4, 5}

for idx, _ := range testlist { // for range 的变量是同一个内存地址

fmt.Printf("内存地址：%p\n", &testlist[idx])

}

}

//Size of int: 8 bytes

//Size of int8: 1 bytes

//Size of int16: 2 bytes

//Size of int32: 4 bytes

//Size of int64: 8 bytes

//Size of uint: 8 bytes

//Size of uint8: 1 bytes

//Size of uint16: 2 bytes

//Size of uint32: 4 bytes

//Size of uint64: 8 bytes

//========================================================

//内存地址：0xc0000120d0

//内存地址：0xc0000120d8

//内存地址：0xc0000120e0

//内存地址：0xc0000120e8

//内存地址：0xc0000120f0

// 多维数组同样连续

func main() {

var testlist = [][]int{{1, 2}, {3, 4}}

for y, li := range testlist {

for x, _ := range li {

fmt.Printf("[%d][%d]%p\n", x, y, &testlist[y][x])

}

}

}

// [0][0]0xc0000120c0

// [1][0]0xc0000120c8

// [0][1]0xc0000120d0

// [1][1]0xc0000120d8

704 二分查找

• 思路

  二分，即为每次将列表的长度缩短一半，所以需要保存中间索引，并不断更新直至找到结果

func search(nums []int, target int) int {

left, right := 0, len(nums) - 1

for left <= right { // 边界条件，可以思考极端情况，比如2个值【0，1】, 此时如果不取等于，那么最多只能查找一次 ！！！！ 看了视频才知道，通过区间是否合法判断更简单，淦，我这个是左闭右闭，所以应该加上等于条件

mid := (left + right) / 2

if nums[mid] == target{

return mid

}

if nums[mid] < target {

left = mid + 1

}

if nums[mid] > target {

right = mid - 1

}

}

return -1

}

// 此实现方式 时间复杂度：log2n（每次长度缩减一半） 空间：1 （只启用了有限的变量保存）

// 递归思路，大事化小，将长列表逐渐二分缩短直至为长度为1的列表，此时可以直接判断是否等于target

// 个人想法，做简单递归前可以尝试循环解决，然后再转为递归可能更好书写

func search(nums []int, target int) int {

return recursion(nums, 0, len(nums)-1, target)

}

func recursion(nums []int, low, high, target int)(result int ){

if low > high { // 参考简单二分的循环条件相反递归的一种极端结束条件

return -1

}

mid := (low + high) / 2

if nums[mid] == target {

return mid // 递归终止条件

}

// 通过保存变量方式可以更直观理解，当让也可以通过直接return 递归函数更简洁

if nums[mid] < target{

result = recursion(nums, mid+1, high, target) // 仅仅相当于将low = mid+ 1的循环体放入递归中处理

}else {

result = recursion(nums, low, mid-1, target) // 同理

}

return result

}

时间 logn 空间logn

27 删除列表元素

// 题目真难读懂，简单说就是列表移除某个值元素，然后重新排列，保证剩余元素再列表前几位就行，顺序不论

func removeElement(nums []int, val int) int {

// 思路： 最简单遍历

for i := 0; i < len(nums); {

if nums[i] == val {

nums = append(nums[:i], nums[i+1:]...) // 本质上删除nums[i]

} else {

i++

}

}

return len(nums)

}

时间 遍历n*append移动n次 = n^2 空间 每次append都可能分配新数组所以 n

func removeElement(nums []int, val int) int {

// 思路：快慢指针，快指针如果不等于val就赋值给慢指针，如果等于那么就++

slow := 0

for fast := 0; fast < len(nums); fast++ {

if nums[fast] != val {

nums[slow] = nums[fast]

slow++

}

}

return slow

}