leetBook_数组和字符串

理解数组的基本概念及其操作方式；
理解二维数组的基本概念，熟悉二维数组的使用；
了解字符串的概念以及字符串所具有的不同特性；
理解字符串匹配中的 KMP 算法；
能够运用双指针解决实际问题。

数组简介

集合列表与数组

集合:由一个或多个确定的元素构成的整体

集合里的元素类型不一定相同,集合里的元素没有顺序

列表:一种数据项构成的有限序列,即按照一定的线性顺序,排列而成的数据项的集合

列表的概念是在集合的特征上形成的,他具有顺序,且长度是可变的.

列表最常见的形式有数组和链表;栈和队列是两种特殊类型的列表

数组:列表的实现方式之一

如何区分列表和数组:索引

数组中的元素在内存中是连续存储的,且每个元素占用相同大小的内存

相反,列表中的元素在内存中可能彼此相邻,也可能不相邻.比如链表的元素在内存中则不一定是连续的

列表是集合的一种表现形式,在集合的特征上形成的;数组是列表的一种实现方式,链表是列表的另一种实现方式.

数组的操作

连续存储

读取元素:按照索引访问 , o(1)

查找元素:全数组遍历,o(n)

插入元素:要挪位子,很麻烦.如果需要频繁地对数组元素进行插入操作，会造成时间的浪费。事实上，另一种数据结构，即链表可以有效解决这个问题。

删除元素:删掉后,把后面的挪到前面,很麻烦.删除操作具有线性时间复杂度，即时间复杂度为 O(N)，N 为数组的长度。

题目

寻找数组的中心索引

给你一个整数数组 nums ，请计算数组的中心下标。

数组中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回 -1 。

//前缀和 + 逐项遍历
func pivotIndex(nums []int) int {
   preSum := make([]int, len(nums)+1, len(nums)+1)
   preSum[0] = 0
   for i := 0; i < len(nums); i++ {
      preSum[i+1] = nums[i] + preSum[i]
   }

   for i := 1; i < len(preSum); i++ {
      left := preSum[i-1]
      right := preSum[len(preSum)-1] - preSum[i]

      if left == right {
         return i - 1
      }
   }

   return -1
}

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

//二分法
func searchInsert(nums []int, target int) int {
left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		}
	}
	return left
}

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

//不太会啊 数组有序问题 最好先排个序 思路可能会开阔一点
func merge1(intervals [][]int) [][]int {
   res := make([][]int, 0)
   sort.Slice(intervals, func(i, j int) bool {
      return intervals[i][0] < intervals[j][0]
   })
   res = append(res, intervals[0])

   for i := 1; i < len(intervals); i++ {
      //如果这个左端点 比 前一个的端点小 说明有重合  有重合还得判断这个的右端点是否会比前一个的右端点大 大的话才会覆盖 小的话顶多算子集
      if intervals[i][0] <= res[len(res)-1][1] {
         if res[len(res)-1][1] < intervals[i][1] {
            res[len(res)-1][1] = intervals[i][1]
         }
      } else {
         res = append(res, intervals[i])
      }
   }

   return res
}

二维数组简介

二维数组

二维数组是一种结构较为特殊的数组,只是将数组中的每个元素变成了一堆数组.

二维数组的本质上仍然是一个一维数组,内部的一维数组仍然从索引0开始,我们可以将它看作一个矩阵,并处理矩阵的相关问题.

题目

旋转矩阵

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

//属实不会 二维数组翻转的话 根据对角线翻转 然后再横向翻转  多试一试
func rotate1(matrix [][]int) {
   //正对角线翻转
   for i := 0; i < len(matrix); i++ {
      for j := 0; j <= i; j++ {
         matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
      }
   }

   //水平横向翻转
   for i := 0; i < len(matrix); i++ {
      for j := 0; j < len(matrix[i])/2; j++ {
         matrix[i][j], matrix[i][len(matrix[i])-1-j] = matrix[i][len(matrix[i])-1-j], matrix[i][j]
      }
   }

   return
}

零矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

//使用数组作为桥梁 存一下
func rotate(matrix [][]int) {
   res := make([]int, 0, len(matrix)*len(matrix))
   //代表列
   for i := 0; i < len(matrix[0]); i++ {
      //代表行
      for j := len(matrix) - 1; j >= 0; j-- {
         res = append(res, matrix[j][i])
      }
   }

   index := 0
   for i := 0; i < len(matrix); i++ {
      for j := 0; j < len(matrix[i]); j++ {
         matrix[i][j] = res[index]
         index++
      }
   }
   return
}

func setZeroes1(matrix [][]int) {
   m := make(map[[2]int]bool)
   for i := 0; i < len(matrix); i++ {
      for j := 0; j < len(matrix[i]); j++ {
         if matrix[i][j] == 0 {
            m[[2]int{i, j}] = true
         }
      }
   }

   for ints := range m {
      for i := 0; i < len(matrix[ints[0]]); i++ {
         matrix[ints[0]][i] = 0
      }
      for i := 0; i < len(matrix); i++ {
         matrix[i][ints[1]] = 0
      }
   }
}

func setZeroes(matrix [][]int) {
   mRow := make(map[int]bool)
   mCol := make(map[int]bool)
   for i := 0; i < len(matrix); i++ {
      for j := 0; j < len(matrix[i]); j++ {
         if matrix[i][j] == 0 {
            mRow[i] = true
            mCol[j] = true
         }
      }
   }

   for i := 0; i < len(matrix); i++ {
      for j := 0; j < len(matrix[i]); j++ {
         if mRow[i] || mCol[j] {
            matrix[i][j] = 0
         }
      }
   }
}

对角线遍历

给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

//对角线的特征是 行索引和列索引和相等 可以利用和是奇数和偶数来判断 正向遍历还是反向遍历
func findDiagonalOrder(mat [][]int) []int {
   res := make([]int, 0, 0)
   if len(mat) == 1 {
      return mat[0]
   }
   if len(mat[0]) == 1 {
      for _, ints := range mat {
         res = append(res, ints[0])
      }
      return res
   }

   sum := len(mat) + len(mat[0])
   for i := 0; i <= sum; i++ {
      for j := 0; j <= i; j++ {
         if i%2 == 0 {
            if i-j >= 0 && i-j < len(mat) && j >= 0 && j < len(mat[0]) {
               res = append(res, mat[i-j][j])
            }
         } else {
            if j >= 0 && j < len(mat) && i-j >= 0 && i-j < len(mat[0]) {
               res = append(res, mat[j][i-j])
            }
         }
      }
   }
   return res
}

字符串

字符串简介

字符串的基本操作对象通常是字符串整体或者其子串

I like leetcode 反向输出更愿意接受Leetcode like I 而不是edocteel ekil I

字符串的比较和连接操作相对复杂
语言支持运算符重载那么就可以对字符串进行==比较
字符串进行连接操作,根据语言的不同效率不同
- C++可以修改字符串在连接操作的时候效率就比较高
- Java Go 不能修改字符串在连接操作的时候就会重新分配内存给新字符串然后再拷贝就的字符串中的内容到新的内存地址中这样就会造成效率下降
- 因此如果需要连接可以尝试使用stringbuilder数据结构或者转换成[]byte切片进行连接或者修改