代码随想录算法练习营第一天| 704. 二分查找、27. 移除元素 ...

小收获

数组是存放在连续内存空间上的相同类型数据的聚集
测试一下go

1. func main() {
2.         fmt.Printf("Size of int: %d bytes\n", unsafe.Sizeof(int(0)))
3.         fmt.Printf("Size of int8: %d bytes\n", unsafe.Sizeof(int8(0)))
4.         fmt.Printf("Size of int16: %d bytes\n", unsafe.Sizeof(int16(0)))
5.         fmt.Printf("Size of int32: %d bytes\n", unsafe.Sizeof(int32(0)))
6.         fmt.Printf("Size of int64: %d bytes\n", unsafe.Sizeof(int64(0)))
8.         fmt.Printf("Size of uint: %d bytes\n", unsafe.Sizeof(uint(0)))
9.         fmt.Printf("Size of uint8: %d bytes\n", unsafe.Sizeof(uint8(0)))
10.         fmt.Printf("Size of uint16: %d bytes\n", unsafe.Sizeof(uint16(0)))
11.         fmt.Printf("Size of uint32: %d bytes\n", unsafe.Sizeof(uint32(0)))
12.         fmt.Printf("Size of uint64: %d bytes\n", unsafe.Sizeof(uint64(0)))
14.         fmt.Println("========================================================")
15.         var testlist = []int{1, 2, 3, 4, 5}
16.         for idx, _ := range testlist {  // for range 的变量是同一个内存地址
17.                 fmt.Printf("内存地址：%p\n", &testlist[idx])
18.         }
19. }
22. //Size of int: 8 bytes
23. //Size of int8: 1 bytes
24. //Size of int16: 2 bytes
25. //Size of int32: 4 bytes
26. //Size of int64: 8 bytes
27. //Size of uint: 8 bytes
28. //Size of uint8: 1 bytes
29. //Size of uint16: 2 bytes
30. //Size of uint32: 4 bytes
31. //Size of uint64: 8 bytes
32. //========================================================
33. //内存地址：0xc0000120d0
34. //内存地址：0xc0000120d8
35. //内存地址：0xc0000120e0
36. //内存地址：0xc0000120e8
37. //内存地址：0xc0000120f0
41. // 多维数组同样连续
42. func main() {
43.         var testlist = [][]int{{1, 2}, {3, 4}}
44.         for y, li := range testlist {
45.                 for x, _ := range li {
46.                         fmt.Printf("[%d][%d]%p\n", x, y, &testlist[y][x])
47.                 }
48.         }
49. }
50. // [0][0]0xc0000120c0
51. // [1][0]0xc0000120c8
52. // [0][1]0xc0000120d0
53. // [1][1]0xc0000120d8

复制代码

704 二分查找

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

1. func search(nums []int, target int) int {
2.         left, right := 0, len(nums) - 1
4.         for left <= right {  // 边界条件，可以思考极端情况，比如2个值【0，1】, 此时如果不取等于，那么最多只能查找一次  ！！！！ 看了视频才知道，通过区间是否合法判断更简单，淦，我这个是左闭右闭，所以应该加上等于条件
5.                 mid := (left + right) / 2
6.                 if nums[mid] == target{
7.                         return mid
8.                 }
9.                 if nums[mid] < target {
10.                         left = mid + 1
11.                 }
12.                 if nums[mid] > target {
13.                         right = mid - 1
14.                 }
15.         }
16.         return -1
17. }
19. // 此实现方式   时间复杂度：log2n（每次长度缩减一半）  空间：1 （只启用了有限的变量保存）

复制代码

1. // 递归思路，大事化小，将长列表逐渐二分缩短直至为长度为1的列表，此时可以直接判断是否等于target
2. // 个人想法，做简单递归前可以尝试循环解决，然后再转为递归可能更好书写
3. func search(nums []int, target int) int {
4.         return recursion(nums, 0, len(nums)-1, target)
5. }
7. func recursion(nums []int, low, high, target int)(result int ){
8.         if low > high {   // 参考简单二分的循环条件相反递归的一种极端结束条件
9.                 return -1
10.         }
12.         mid := (low + high) / 2
13.         if nums[mid] == target {
14.                 return mid   // 递归终止条件
15.         }
18.         // 通过保存变量方式可以更直观理解，当让也可以通过直接return 递归函数更简洁
19.         if nums[mid] < target{
20.                 result = recursion(nums, mid+1, high, target) // 仅仅相当于将low = mid+ 1的循环体放入递归中处理
21.         }else {
22.                 result = recursion(nums, low, mid-1, target) // 同理
23.         }
24.         return result
25. }
27. 时间 logn  空间logn

复制代码

27 删除列表元素

1. // 题目真难读懂，简单说就是列表移除某个值元素，然后重新排列，保证剩余元素再列表前几位就行，顺序不论
2. func removeElement(nums []int, val int) int {
3.         // 思路： 最简单遍历
4.         for i := 0; i < len(nums); {
5.                 if nums[i] == val {
6.                         nums = append(nums[:i], nums[i+1:]...) // 本质上删除nums[i]
7.                 } else {
8.                         i++
9.                 }
10.         }
11.         return len(nums)
12. }
14. 时间 遍历n*append移动n次 = n^2  空间 每次append都可能分配新数组所以 n

复制代码

1. func removeElement(nums []int, val int) int {
2.         // 思路：快慢指针，快指针如果不等于val就赋值给慢指针，如果等于那么就++
3.         slow := 0
4.         for fast := 0; fast < len(nums); fast++ {
5.                 if nums[fast] != val {
6.                         nums[slow] = nums[fast]
7.                         slow++
8.                 }
9.         }
10.         return slow
11. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。