Leetcode-数组系列1

返回总目录

日刷leetcode–简单版

---

169.多数元素

解题思路：

1. 利用哈希表存储每个字符出现的个数，出现次数大于n/2的即为多数元素
2. 根据题意，多数元素的个数大于n/2，每次遇到多数元素就将个数+1，否则减一，值为负数时则证明当前选取的这个数不是多数元素，则更换多数元素继续循环(摩尔投票法)
   
   上图来着，题169解解摩尔投票法
3. 排序，取下标为len(nums)/2的值

示例代码：

// map解法
func majorityElement(nums []int) int {
	mapArr := make(map[int]int)
	for _, v := range nums {
		if _, ok := mapArr[v]; !ok {
			mapArr[v] = 1
		} else {
			mapArr[v]++
		}
	}

	for k, v := range mapArr {
		if v > len(nums)/2 {
			return k
		}
	}
	return 0
}


func majorityElement0(nums []int) int {
	mapArr := make(map[int]int)
	for _,v := range nums{
		mapArr[v] ++
		if mapArr[v] > len(nums)/2{
			return v
		}
	}
	return 0
}


// 题目中保证了众数出现次数多余一半,所以遇到众数+1,非众数-1的最终结果始终大于1
func majorityElement1(nums []int) int {
	count, repeat := 0, nums[0]
	for k, v := range nums {
		if v == repeat {
			count++
		} else {
			count--
			if count == 0 && k<len(nums) {
				repeat = nums[k+1]
			}
		}
	}
	return repeat
}

// 先排序直接找 len/2的数
func majorityElement2(nums []int) int{
	sort.Ints(nums)
	return nums[len(nums)/2]
}

217.多数元素

解题思路：

1. 哈希表

示例代码:

func containsDuplicate(nums []int) bool {
	mapArr := make(map[int]bool)
	for _, v := range nums {
		if mapArr[v] {
			return true
		}
		mapArr[v] = true
	}
	return false
}

219. 存在重复元素 II

解题思路：

1. 哈希表，不存在则存入，存在这判断两个下标之间的差值是否小于k

示例代码：

func containsNearbyDuplicate(nums []int, k int) bool {
	mapArr := make(map[int]int)
	for key, val := range nums {
		if v, ok := mapArr[val]; ok {
			if key-v <= k {
				return true
			}
		}
		mapArr[val] = key
	}
	return false
}

228. 汇总区间

解题思路：

1. 判断相邻元素差值是否为1，不分1则处于下一个区间，注意处理最后一个元素

示例代码：

func summaryRanges(nums []int) []string {
	var rStr []string
	if len(nums) == 0 {
		return rStr
	}
	var head, tail int
	head, tail = nums[0], nums[0]
	for i := 1; i < len(nums); i++ {
		if nums[i] != tail+1 {
			if head == tail {
				rStr = append(rStr, strconv.Itoa(head))
			} else {
				rStr = append(rStr, strconv.Itoa(head)+"->"+strconv.Itoa(tail))
			}
			head = nums[i]
			tail = nums[i]
		}else{

			tail = nums[i]
		}
	}
	if head == tail {
		rStr = append(rStr, strconv.Itoa(head))
	} else {
		rStr = append(rStr, strconv.Itoa(head)+"->"+strconv.Itoa(tail))
	}
	return rStr
}


func summaryRanges1(nums []int) []string {
	var rStr []string
	for i,j :=0,0; j<len(nums);{
		if j+1 < len(nums) && nums[j+1] == nums[j]+1{
			j++
			continue
		}
		if i==j {
			rStr = append(rStr, strconv.Itoa(nums[i]))
		}else{
			rStr = append(rStr, strconv.Itoa(nums[i]) + "->" + strconv.Itoa(nums[j]))
		}
		i = j+1
		j++
	}
	return rStr
}

268. 丢失的数字

解题思路：

1. 哈希表，循环一次将数组元素存下来，在循环0-len(nums)，不存在的就是丢失的
2. 排序后遍历，下标和数组不相等这标识此下标树缺失
3. 数学方式，通过高斯求和n*(n+1)/2算出所有的和，再减去所有的数组元素，剩下的就是丢失的树
4. 异或运算

示例代码：

// 哈希
func missingNumber1(nums []int) int {
	mapArr := make(map[int]bool)
	for _, v := range nums {
		mapArr[v] = true
	}
	for i := 1; i <= len(nums); i++ {
		if _, ok := mapArr[i]; !ok {
			return i
		}
	}
	return 0
}

// 排序

func missingNumber2(nums []int) int {
	sort.Ints(nums)
	for k, v := range nums {
		if k != v {
			return k
		}
	}
	return len(nums)
}

// 数学
func missingNumber3(nums []int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	return len(nums)*(len(nums)+1)/2 - sum
}

// 异或位运算
func missingNumber4(nums []int) int {
	miss := len(nums)
	for k, v := range nums {
		miss ^= k ^ v
	}
	return miss
}

283. 移动零

解题思路

1. 双指针，A一直向右移动，遇到非0的与B交换即可
   

示例代码：

func moveZeroes(nums []int) {
	for i, j := 0, 0; i < len(nums); i++ {
		if nums[i] != 0 {
			nums[i], nums[j] = nums[j], nums[i]
			j++
		}
	}
	fmt.Println(nums)
}