代码随想录：数组篇

[TOC]

数组篇总结

首先跟着代码随想录刷了一刷，大概接触到题型有二分法、移除元素/排序、滑动窗口、模拟行为

• 二分法

  • 确定好左右边界，以及mid的变化就好

• 移除元素

  • for循环暴力！
  • 快慢指针： 快指针去探索找寻符合条件的宝藏，然后交给慢指针
  • 使用堆栈或者队列

• 排序

  • 首尾双指针

• 滑动窗口

  • 双层for循环暴力！ 其实这种也是滑动窗口，只是完全是无脑滑动（以边界条件为条件）
  • 双指针滑动，两个for循环（上面是n*n，这个是2n），且移动条件为场景需求条件（使用hashmap进行维护）

• 模拟行为

  • 害。。听天由命，画图吧。

可能这里更多的是用go去实现吧，因为go语言我也是刚学，然后语法都不太稳固那种，更别说使用什么api了，所以感觉就是算法和go都拿。有思路但是go很卡壳的话就先用Java写一下然后查go的语法然后用go写

二分法

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

====本题目有着月份的跨越，所以java版本思路和go差别还是有的。Java是二分找到一次后左右依次扩张（顺序遍历），而go版本是继续使用二分去左右扩张

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
        int left = 0;
        int right = nums.length - 1;
        if(right>0&&nums[left]==nums[right]&&nums[left]==target){
            return new int[]{left,right};
        }
        while(left<=right){
            int mid = (left+right)>>>1;
            if(target==nums[mid]){
                int l=mid;
                int r=mid;
                while(l>=left&&nums[l]==target){
                    l--;
                }
                while(r<=right&&nums[r]==target){
                    r++;
                }
                return new int[]{++l,--r};
            }
            else if(target<nums[mid]) {
                right=mid-1;
            }
            else
                left=mid+1;
        }

        return new int[]{-1,-1};
    }

}

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

     left := searchLeft(nums,target)
     if left==len(nums)||nums[left]!=target {
        return []int{-1,-1}
     }
    right := searchRight(nums,target)
    return []int{left,right}
}

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

}

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

移除元素

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

func moveZeroes(nums []int)  {
    slow:=0
    for fast:=0;fast<len(nums);fast++{
        // 由fast开路
        if nums[fast]!=0 {
            nums[slow],nums[fast] = nums[fast],nums[slow]
            slow++
        }
    }
}

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int indexS=s.length()-1;
        int indexT=t.length()-1;
        int skipS=0;
        int skipT=0;
        while(indexS>=0||indexT>=0){
            while(indexS>=0){
                if(s.charAt(indexS)=='#'){
                    skipS++;
                    indexS--;
                }else if(skipS>0){
                    skipS--;
                    indexS--;
                }else{
                    break;
                }
            }
            while(indexT>=0){
                 if(t.charAt(indexT)=='#'){
                    skipT++;
                    indexT--;
                }else if(skipT>0){
                    skipT--;
                    indexT--;
                }else{
                    break;
                }
            }
            if(indexS>=0&&indexT>=0){
                if(s.charAt(indexS)!=t.charAt(indexT)){
                    return false;
                }
            }
            else{
                if(indexS>=0||indexT>=0){
                    return false;
                }
            }
            indexS--;
            indexT--;
        }
        return true;
    }
}

func backspaceCompare(s string, t string) bool {
    skipS,skipT := 0,0
    i,j := len(s)-1,len(t)-1
    for i>=0 || j>=0 {
        for i>=0 {
            if s[i]=='#'{
                skipS++
                i--
            }else if skipS>0{
                skipS--
                i--
            }else {
                break
            }
        }
        for j>= 0{
            if t[j]=='#'{
                skipT++
                j--
            }else if skipT > 0{
                skipT--
                j--
            }else {
                break
            }
        }
        if i>=0 && j >=0 {
            if s[i] != t[j] {
                return false
            }
        }else if i>=0 || j>=0 {
            return false
        }
        i--
        j--
    }
    return true
}

排序

977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

func sortedSquares(nums []int) []int {
	temp := make([]int, len(nums))
	left, right := 0, len(temp)-1
	i := right
	for left <= right {
		if -nums[left] > nums[right] {
			temp[i] = nums[left] * nums[left]
            left++
		} else {
			temp[i] = nums[right] * nums[right]
            right--
		}
		i--
	}
	return temp
}

滑动窗口

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

func minSubArrayLen(target int, nums []int) int {
    n :=len(nums)
	length := n+1
	left, right := 0, 0
	sum := 0
	for ; right < n; right++ {
		sum += nums[right]
		for sum >= target {
			sum -= nums[left]
			if length > right-left + 1 {
                length = right-left +1
            } 
			left++
		}
	}
	if length > n{
		return 0
	}
	return length
}

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

• 1 <= fruits.length <= 105
• 0 <= fruits[i] < fruits.length

func totalFruit(fruits []int) int {
	ans := 0
	cnt := map[int]int{}
	left := 0
	for right, value := range fruits {
		cnt[value]++
		if len(cnt) > 2 {
			d := fruits[left]
			left++
			cnt[d]--
			if cnt[d] == 0 {
				delete(cnt, d)
			}
		}
		ans = max(ans, right-left+1)
	}
	return ans
}

---

坑爹的模拟行为

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

• 1 <= n <= 20

class Solution {
    public int[][] generateMatrix(int n) {
        int[][]matrix = new int[n][n];
        int top=0;
        int bottom=n-1;
        int left=0;
        int right=n-1;
        int ans=1,pow =n*n;
        while(ans<=pow){
            // 顶
            for(int i=left;i<=right;i++) matrix[top][i]=ans++;
            top++;
            // 右
            for(int i=top;i<=bottom;i++) matrix[i][right]=ans++;
            right--;
            // 底
            for(int i=right;i>=left;i--)matrix[bottom][i]=ans++;
            bottom--;
            // 左
            for(int i=bottom;i>=top;i--) matrix[i][left]=ans++;
            left++;
        }
        return matrix;
    }
}

func generateMatrix(n int) [][]int {

	loop := 1   
	offset := 1 
	startX, startY := 0, 0
	ans := 1 
	arrays := make([][]int, n)
	for i := range arrays {
		arrays[i] = make([]int, n)
	}
	for loop <= n/2 {
		// 顶部
		for ; startY < n-offset; startY++ {
			arrays[startX][startY] = ans
			ans++
		}
		// 右边
		for ; startX < n-offset; startX++ {
			arrays[startX][startY] = ans
			ans++
		}
		// 底部
		for ; startY >= offset; startY-- {
			arrays[startX][startY] = ans
			ans++
		}
        // 左边
		for ; startX >= offset; startX-- {
			arrays[startX][startY] = ans
			ans++
		}
		startX++
		startY++
		loop++
		offset++
	}
	if n%2 == 1 {
		arrays[startX][startY] = ans
	}
	return arrays
}

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

func spiralOrder(matrix [][]int) []int {

	lenX := len(matrix)
	if lenX == 0 {
		return []int{}
	}
	lenY := len(matrix[0])
	if lenY == 0 {
		return []int{}
	}

	top, right, bottom, left := 0, lenY-1, lenX-1, 0
	total := lenX * lenY
	arrays := make([]int, total)
	ans := 0
	for ans < total {
		// 顶
		for i := left; i <= right && ans < total; i++ {
			arrays[ans] = matrix[top][i]
			ans++
		}
		top++
		// 右
		for i := top; i <= bottom && ans < total; i++ {
			arrays[ans] = matrix[i][right]
			ans++
		}
		right--
		// 底
		for i := right; i >= left && ans < total; i-- {
			arrays[ans] = matrix[bottom][i]
			ans++
		}
		bottom--
		for i := bottom; i >= top && ans < total; i-- {
			arrays[ans] = matrix[i][left]
			ans++
		}
		left++
	}
	return arrays
}
func main() {
	arrays := [][]int{{1}, {5}, {9}}
	order := spiralOrder(arrays)
	for i := range order {
		print(order[i])
	}
}