力扣小记 300、354、51、53

突发奇想偶尔记录一两道算法题，算是记录也算是鞭策。
嘛。。希望能坚持下去

300.最长递增子序列

https://leetcode.cn/problems/longest-increasing-subsequence

思路:
LIS递增子序列, 定义dp数组, 第i个元素的最大递增子序列是dp[i], 遍历dp数组找出最大值即是答案。

func lengthOfLIS(nums []int) int {
    n := len(nums)
    res := 0
    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = 1 // 元素本身也算一个子序列, 所以要初始化为1
    }
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] { // 当后面元素大于前面元素 比较两者的最大递增子序列并加1
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }
    }
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

354.俄罗斯套娃信封问题

https://leetcode.cn/problems/russian-doll-envelopes

思路:
这里想到用动态规划。本质是一道LIS题, 只不过是二维的, 需要先转换一下, 先按宽度升序再按相同高度降序, 在把高度拿出来在此基础上求递增LIS的长度。

func maxEnvelopes(envelopes [][]int) int {
    sort.Slice(envelopes, func(i, j int) bool {
		if envelopes[i][0] == envelopes[j][0] {
			return envelopes[j][1] < envelopes[i][1]
		}
		return envelopes[i][0] < envelopes[j][0]
	})
    n := len(envelopes)
    height := make([]int, n)
    dp := make([]int, n)
    for i := 0; i < n; i++ {
        height[i] = envelopes[i][1]
        dp[i] = 1
    }
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if height[i] > height[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    res := 0
    for i := 0; i < n; i++ {
        res = max(res, dp[i])
    }
    return res
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

51.N皇后

https://leetcode.cn/problems/n-queens

思路:
经典题型了, DFS+回溯把所有可能的结果穷举出来

var res [][]string
func solveNQueens(n int) [][]string {
    res = [][]string{}
    board := make([][]string, n)
    for i := 0; i < n; i++ {
        board[i] = make([]string, n)
    }
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            board[i][j] = "."
        }
    }
    backtrack(board, 0) //从第一行开始
    return res
}

func backtrack(board [][]string, row int) {
    size := len(board)
    if row == size {
        temp := make([]string, size)
        for i := 0; i < size; i++ {
            temp[i] = strings.Join(board[i], "") // 二维转一维
        }
        res = append(res, temp) // 找到一个可行解存入进去
        return
    }
    for col := 0; col < size; col++ {
        if !isValid(board, row, col) {
            continue
        }
        board[row][col] = "Q"
        backtrack(board, row+1)
        board[row][col] = "."
    }
}

// 检测该位置是否合法
func isValid(board [][]string, row, col int) bool {
    n := len(board)
    for i := 0; i < row; i++ {
        if board[i][col] == "Q" {
            return false
        }
    }
    for i := 0; i < n; i++ {
        if board[row][i] == "Q" {
            return false
        }
    }
    for i, j := row, col; i >= 0 && j >= 0; i, j = i-1, j-1 {
        if board[i][j] == "Q" {
            return false
        }
    }
    for i, j := row, col; i >= 0 && j < n; i, j = i-1, j+1 {
        if board[i][j] == "Q" {
            return false
        }
    }
    return true
}

53.最大子数组和

https://leetcode.cn/problems/maximum-subarray

思路:
这道题最先想到的就是滑动窗口, 通过两个指针根据条件不断缩放窗口更新最大值; 也可以用动态规划, 定义dp数组i为nums[i]结尾最大子数组和dp[i]

滑动窗口:

func maxSubArray(nums []int) int {
    left, right := 0, 0
    sum, maxSum := 0, math.MinInt
    n := len(nums)
    for right < n {
        sum += nums[right]
        right++
        maxSum = max(maxSum, sum)
        for sum < 0 {
            sum -= nums[left]
            left++ 
        }
    }
    return maxSum
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

动态规划

func maxSubArray(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    dp := make([]int, n)
    res := nums[0]
    dp[0] = nums[0]
    for i := 1; i < n; i++ {
        dp[i] = max(nums[i], nums[i] + dp[i-1])
        res = max(res, dp[i])
    }
    return res
}

func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}