logo

新编程学习网
【算法题】字符串和数组类型题目
首页>内容详情

【算法题】字符串和数组类型题目

大熊•

toc

文本占位符

无重复字符的最长子串

题目：无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
算法：使用Map + 快慢 指针方式，从左到右依次判断是否有重复，最终找到最长的长度。

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func lengthOfLongestSubstring(s string) int {
    if len(s) == 0 {
        return 0
    }
    size := len(s)
    maxGain := 0
    m := make(map[byte]bool)
    i, j := 0, 0
    for j < size {
        if m[s[j]] == true {
            for i <= j{
                delete(m, s[i])
                i++
                if s[i-1] == s[j] {
                    break
                } 
            }
        }
        m[s[j]] = true
        j++
        maxGain = max(maxGain, j-i)
    }
    return maxGain
}

求子集

题目78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
算法：递归，当前的数字 选择 或者是 不选择。 递归达成条件是长度达到位置。

func subsets(nums []int) [][]int {
    t := []int{}
    ans := [][]int{}
    var dfs func(index int)
    dfs = func(index int) {
        if index == len(nums) { // 递归终止条件
            ans = append(ans, append([]int(nil), t...))
            return
        }
        t = append(t, nums[index]) // 选择当前数字
        dfs(index+1)
        t = t[:len(t)-1] 
        dfs(index+1) // 不选择当前数字
    }
    dfs(0)
    return ans
}

子集 II

题目：子集II 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：输入：nums = [0] 输出：[[],[0]]

算法：排序，递归，做剪枝条件：判断是否已经进过队列。

func sort(nums []int) {
    for i:=0; i<len(nums); i++ {
        for j:=0; j<len(nums)-i-1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
}
func subsetsWithDup(nums []int) [][]int {
    sort(nums)
    t := []int{}
    ans := [][]int{}
    var dfs func(isPick bool, index int)
    dfs = func(isPick bool, index int) {
        if index == len(nums) {
            ans = append(ans, append([]int(nil), t...))
            return
        }
        dfs(false, index+1)
        if !isPick && index > 0 && (nums[index-1] == nums[index]) {
            return
        }
        t = append(t, nums[index])
        dfs(true, index+1)
        t = t[:len(t)-1]
    }
    dfs(false, 0)
    return ans
}

组合总和

题目：LCR 081. 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。

candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的唯一组合数少于 150 个。

算法：对于这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。 将问题化解为子问题。 注意里面的数字可以被无限制的使用。

func sort(candidates []int) {
    size := len(candidates)
    for i:=0; i<size; i++ {
        for j:=0; j<size-i-1; j++ {
            if candidates[j] > candidates[j+1] {
                candidates[j], candidates[j+1] = candidates[j+1], candidates[j]
            }
        }
    }
}
func combinationSum(candidates []int, target int) [][]int {
    sort(candidates)
    ans := [][]int{}
	var dfs func(index int, nums []int, sum int)
        dfs = func(index int, nums []int, sum int) {
        if target == sum {
            ans = append(ans, append([]int(nil), nums...))
            return
        }
        if sum > target {
            return
        }
        for i:=index; i<len(candidates); i++ { // candidates 中的数字可以循环使用，因此这里可以再次进入循环
            // 选择当前数字
            nums = append(nums, candidates[i])
            dfs(i, nums, candidates[i]+sum)
            nums = nums[:len(nums)-1]
            // 上面的退出来就表示不选择当前数字,跳过对当前的sum不影响
        }
    }
    dfs(0, []int{}, 0)
    return ans
}

组合总和2

题目：LCR 082. 组合总和 II

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出:[[1,1,6],[1,2,5],[1,7],[2,6]]

示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 输出: [[1,2,2],[5]]

func sort(array []int) {
    for i:=0; i<len(array); i++ {
        for j:=0; j<len(array)-i-1; j++ {
            if array[j] > array[j+1] {
                array[j], array[j+1] = array[j+1], array[j]
            }
        }
    }
}
func combinationSum2(candidates []int, target int) [][]int {
    ans := [][]int{}
    sort(candidates)
    var dfs func(index int, nums []int, sum int) 
    dfs = func(index int, nums []int, sum int) {
        if sum == target {
            ans = append(ans, append([]int(nil), nums...))
            return
        }
        for i:=index; i<len(candidates); i++ { // 应该是比起始位置大
            if i > index && (candidates[i] == candidates[i-1]) {
                continue;
            }
            nums = append(nums, candidates[i])
            dfs(i+1, nums, sum+candidates[i])
            nums = nums[:len(nums)-1]
        }
    }
    dfs(0, []int{}, 0)
    return ans    
}

判断数组中是否包含和为sum 的 n个数子序列。

这个题目在面试中经常会遇到，是组合总和2的延伸题目。
leetcode的题目没有找到，这里用了求不重复的子集的方法，把所有的子集都求出来。

例题:
不允许重复使用里面数字，求和为7 的 3个子序列
输入：arr=[1, 5, 6, 2, 4, 3], length=3, target=7 输出：[[1 2 4]]

package main

import "fmt"

func sort(candidates []int) {
    size := len(candidates)
    for l := 0; l < size; l++ {
        for i := 0; i < size-1-l; i++ {
            if candidates[i] > candidates[i+1] {
                candidates[i], candidates[i+1] = candidates[i+1], candidates[i]
            }
        }
    }
}
func getCombineResult(arr []int, length int, target int) [][]int {
    fmt.Println(arr)
    ans := [][]int{}

    var dfs func(index int, candidates []int, sum int)
    dfs = func(index int, candidates []int, sum int) {
        if sum > target {
            return
        }
        if (sum == target) && (len(candidates) == length) { // 找到了
            ans = append(ans, append([]int(nil), candidates...))
            return
        }
        for i := index; i < len(arr); i++ {
            if i > index && (arr[i-1] == arr[i]) {
                continue
            }
            candidates = append(candidates, arr[i])
            dfs(i+1, candidates, arr[i]+sum) // ❗️ 这个地方是 i+1,
            candidates = candidates[:len(candidates)-1]
        }
    }
    dfs(0, []int{}, 0)
    return ans
}
func main() {
    // 不允许重复使用，和为7 的 三个子序列
    var arr []int = []int{1, 5, 6, 2, 4, 3}
    fmt.Println(getCombineResult(arr, 3, 7))
}

全排列

题目：46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：输入：nums = [0,1] 输出：[[0,1],[1,0]]

示例 3：输入：nums = [1] 输出：[[1]]

算法：从第一位开始逐步与后边的数字选择交换。

func swap(arr []int, i int, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}
func permute(nums []int) [][]int {
    ans := [][]int{}
    var dfs func(index int, nums []int)
    dfs = func(index int, nums []int) {
        if index == len(nums) {
            ans = append(ans, append([]int(nil), nums...))
            return
        }
        for i:=index; i<len(nums); i++ {
            // 交换
            swap(nums, index, i)
            dfs(index+1, nums) // ❗️ 这个地方是 index+1, 相当于划分子问题
            swap(nums, i, index)
            // 还原就是 不交换
        }
    }
    dfs(0, nums)
    return ans;
}

全排列 II

题目：47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1： 输入：nums = [1,1,2] 输出：[[1,1,2], [1,2,1], [2,1,1]]
示例 2：输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

算法：每次循环用个map 记录下是否被交换过。

func swap(nums []int, i int, j int) {
    nums[i], nums[j] = nums[j], nums[i]
}
func permuteUnique(nums []int) [][]int {
    ans := [][]int{}
    var dfs func(index int, nums []int) 
    dfs = func(index int, nums []int) {
        if index == len(nums) {
            ans = append(ans, append([]int(nil), nums...))
            return
        }
        m := make(map[int]bool)
        for i:=index; i<len(nums); i++ {
            if _, ok := m[nums[i]]; ok {
                continue;
            }
            m[nums[i]] = true
            swap(nums, index, i)
            dfs(index+1, nums)
            swap(nums, i, index)
        }
    }       
    dfs(0, nums)
    return ans
}

最大子数组和

字节跳动面试题
题目：53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

示例 1：输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：输入：nums = [1] 输出：1
示例 3：输入：nums = [5,4,-1,7,8] 输出：23

算法：要么选择自身，要么选择自身+前值。

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func maxSubArray(nums []int) int {
    maxGain := ^int(^uint(0) >> 1)
    pre :=0
    for i:=0; i<len(nums); i++ {
        pre = max(pre+nums[i], nums[i])
        maxGain = max(maxGain, pre)
    }
    return maxGain
}

查找总价格为目标值的两个商品

题目：LCR 179. 查找总价格为目标值的两个商品

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

示例 1： 输入：price = [3, 9, 12, 15], target = 18 输出：[3,15] 或者 [15,3]

func twoSum(nums []int, target int) []int {
    i, j:= 0, len(nums)-1
    for i < j {
        if nums[i] + nums[j] > target {
            j--
        }else if nums[i] + nums[j] == target {
            return []int{nums[i], nums[j]}
        } else {
            i++
        }
    }
    return []int{}
}

逆序输出数字

写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。
要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串。

package main

import (
    "fmt"
    "strconv"
)

// 写一个函数，输入 int 型，返回整数逆序后的字符串。如：输入整型 1234，返回字符串“4321”。
// 要求必须使用递归函数调用，不能用全局变量，输入函数必须只有一个参数传入，必须返回字符串。
func reverse(a int) int {
    result := ""
    for a > 9 {
        result += strconv.Itoa(a % 10) // ❗️不能使用string
        a = a / 10
    }
    result += strconv.Itoa(a)
    if value, err := strconv.Atoi(result); err == nil {
        return value
    }
    return 0
}
func main() {
    fmt.Println(reverse(1234))
}

搜索二维矩阵

题目：74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。
    给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

算法：从左下角 开始向 右上角 搜索，判断是否存在相应的值。

func searchMatrix(matrix [][]int, target int) bool {
    row, col := len(matrix), len(matrix[0])
    i, j := row-1, 0
    for i >=0 && j<col {
        if matrix[i][j] > target {
            i--
        }else if matrix[i][j] == target {
            return true
        }else {
            j++
        }
    }
    return false
}

相似题目: 题目：搜索二维矩阵 II

乘积最大子数组

题目：乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

算法：利用dp矩阵算出前面的最大值 和 最小值。存储下来，然后遍历最大的列表获得其中最大的值。

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func maxProduct(nums []int) int {
    size := len(nums)
    dp := make([][]int, 2)
    dp[0] = make([]int, size)
    dp[1] = make([]int, size)
    dp[0][0] = nums[0] // 大
    dp[1][0] = nums[0] // 小
    for i:=1; i<len(nums); i++ {
        dp[0][i] = max( max(nums[i] * dp[0][i-1], nums[i]*dp[1][i-1]), nums[i] )
        dp[1][i] = min( min(nums[i] * dp[0][i-1], nums[i]*dp[1][i-1]), nums[i] )
    }
    maxGain := dp[0][0]
    for i:=0; i<size; i++ {
        maxGain = max(maxGain, dp[0][i])
    }
    return maxGain
}

最接近的三数之和

题目：最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

示例 1：输入：nums = [-1,2,1,-4], target = 1 输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

算法：排序后，固定第一个，然后移动后边的两个。获得最接近的值。


func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func partition(array []int, left int, right int) int {
    var pivot = left
    index := pivot + 1
    for i := index; i <= right; i++ {
        if array[i] < array[pivot] {
            array[index], array[i] = array[i], array[index]
            index++
        }
    }
    array[pivot], array[index-1] = array[index-1], array[pivot]
    return index - 1
}

func quickSort(array []int, left int, right int) {
    if left < right {
        pivot := partition(array, left, right)
        quickSort(array, left, pivot-1)
        quickSort(array, pivot+1, right)
    }
}

func threeSumClosest(nums []int, target int) int {
    quickSort(nums, 0, len(nums)-1)
    minClosed := int(^uint(0) >> 1)
    ans := int(^uint(0) >> 1)
    for i := 0; i < len(nums); i++ {
        j := i + 1
        k := len(nums) - 1
        for j < k {
            sum := nums[i] + nums[j] + nums[k]
            if abs(sum-target) < minClosed {
                minClosed = abs(sum - target)
                ans = sum
            }
            if sum-target > 0 {
                k--
            } else if sum-target == 0 {
                return sum
            } else {
                j++
            }
        }
    }
    return ans
}

买卖股票的最佳时机 II

算法：后边的数字比前面大，就求差作为利润。 也可以使用dp矩阵，分别表示卖出和不卖出的收益。

func maxProfit(prices []int) int {
    maxGain := int(^uint(0) >> 1)
    profit := 0
    for i:=0; i<len(prices); i++ {
        if prices[i] < maxGain {
            maxGain = prices[i]
        } else {
            profit += prices[i] - maxGain
            maxGain = prices[i]
        }
    }
    return profit
}

买卖股票的最佳时机I

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func maxProfit(prices []int) int {
      minPrice := int(^uint(0) >> 1)
    maxGain := 0
    for i := 0; i < len(prices); i++ {
        if prices[i] > minPrice {
            maxGain = max(prices[i]-minPrice, maxGain)
        } else {
            minPrice = prices[i]
        }
    }
    return maxGain
}

不同路径

题目：62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 Start ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 Finish ）。问总共有多少条不同的路径？

算法：还是dp矩阵，从上到下，从左到右进行填充。 这个问题和上楼梯的问题解法是一致的。

func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i:=0; i<len(dp); i++ {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for i:=0; i<len(dp[0]); i++ {
        dp[0][i] = 1
    } 
    fmt.Println(dp)
    for i:=1; i<m; i++ {
        for j:=1; j<n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

其他（放水题）

  1. 一个数组，去掉相邻元素的重复值，保留一个重复值.示例：输入 [1,3,5,5,5,3,4,6,6,7,4] 输出[1,3,5,3,4,6,7,4]
  2. 一个数组，去掉相邻元素的重复值，去掉所有重复值 示例：输入 [1,3,5,5,5,3,4,6,6,7,4] 输出[1, 4, 7, 4]
  3. 题目：删除字符串中的所有相邻重复项。算法：这种问题就是利用栈处理。
  4. 题目：1209. 删除字符串中的所有相邻重复项 II。 利用双栈, 一个栈存当前数字，一个存对应的个数.
  5. 题目：334. 递增的三元子序列。
  6. 题目：重复的子字符串
  7. 剑指 Offer II 016. 不含重复字符的最长子字符串 算法：用滑块的方法解决。 可以单独申请一个栈，然后不断的向里面push，并切割出来。
  8. 两个大数相加 ，要求显示相加的结果。 核心方法:大数相加，直接使用逆序为数组逐项相加。
  9. leetcode 20. 有效的括号. 用的是栈的方式。
  10. 给定一个整数数组 ，其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。 示例：输入: [4,3,2,7,8,2,3,1] 输出: [2,3]
  11. 在一个整数的数组中，找到两个数的和等于某个数，返回这两个数的下标 [使用了map，小米的面试中遇到了]
  12. 判断是否括号是否合法，有三种括号() [] {}
  13. 给定一个字符串，找出最长的一个子串，其中没有重复的字符
  14. 给定一个数组，包括0，1，2三种数组，原地排序，一遍走完。 核心方法:前后指针的方法。
  15. leetcode 剑指 Offer II 085. 生成匹配的括号
    算法：回溯，左右括号一次递归，并进行剪纸。
func generateParenthesis(n int) []string {
    ans := []string{}
    var dfs func(s string, open int, close int)
    dfs = func(s string, open int, close int) {
        if open > n || close > open {
            return
        }
        if close + open == 2*n {
            ans = append(ans, s)
        }
        dfs(s+"(", open+1, close)
        dfs(s+")", open, close+1)
    }
    dfs("", 0, 0)
    return ans;
}
  1. 题目：150. 逆波兰表达式求值 使用栈解决问题，如果遇到了符号就处理栈顶。
  2. 题目：最小的K个数仓库管理员以数组 stock 形式记录商品库存表，其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量，返回 顺序不限。
    算法：快排的一种应用场景。
func partition(array []int, left int, right int) int{
    pivot := left
    index := pivot+1
    for i:=index; i<=right; i++ {
        if array[i] < array[pivot] {
            array[i], array[index] = array[index], array[i]
            index+=1
        }
    }
    array[pivot], array[index-1] = array[index-1], array[pivot]
    return index-1
}
func quickSort(array []int, left int, right int, k int)  {
    if left >= right {
        return
    }
    pivot := partition(array, left, right)
    if pivot == k {
        return
    }
    quickSort(array, left, pivot-1, k)
    quickSort(array, pivot+1, right, k)
    return
}
func inventoryManagement(stock []int, cnt int) []int {
    quickSort(stock, 0, len(stock)-1, cnt)
    return stock[:cnt]
}
  1. 题目：零钱兑换问题
    示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

算法：一个一个的填充重量，获得状态转移方程，最终求得最后的解。 遍历amout， 和 coin，看看当前金币能否放下，可以的话，取的他前面的值。

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func coinChange(coins []int, amount int) int {
    MAX_INT := int(^uint(0) >> 1)
    dp := make([]int, amount+1)
    for i:=0; i<len(dp); i++ {
        dp[i] = MAX_INT
    }
    dp[0] = 0
    for i:=1; i<=amount; i++ {
        for _, coin := range coins {
            if i >= coin { // 说明能够
                if dp[i-coin] != MAX_INT { // 说明此此条件可以达到
                    dp[i] = min(dp[i], dp[i-coin] + 1)
                }
            }
        }
    }
    if dp[amount] == MAX_INT {
        return -1
    } else {
        return dp[amount]
    }
}
  1. 题目：搜索旋转数组的最小值
    算法：二分搜索的一种方式
func stockManagement(stock []int) int {
    l, r := 0, len(stock)-1
    for l < r {
        mid := (l+r) >> 1
        if stock[mid] == stock[r] {
            r -= 1
        } else if (stock[mid]<stock[r]) {
            r = mid
        } else {
            l = mid+1
        }
    }
    return stock[l]
}
  1. 题目：搜索旋转排序数组
    示例 1： 输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
    算法：二分搜索扩展
func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := (left + right) >> 1
        if nums[mid] == target {
            return mid
        }
        if nums[0] <= nums[mid] { // 左边是单调区间
             if nums[0] <= target && target < nums[mid] {
                 right = mid - 1
             }else {
                 left = mid + 1
             }
        } else {
            if target > nums[mid] && target <= nums[len(nums)-1] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    return -1
}

  1. 题目：单词距离 算法：[遍历出来所有的位置。保存在两个数组中，然后比较0位置的大小，不断的进栈和出栈]

  2. 题目：93. 复原 IP 地址
    算法：取数字还是字符进行拆分子问题。

func isVaildIP(s string) bool{
    ip := strings.Split(s, ".")
    for i:=0; i<len(ip); i++ {
        if ip[i] == "" {
            return false
        }
        if len(ip[i]) > 1  && (ip[i][0] == '0') {
            return false
        }
        if val, err :=  strconv.ParseInt(ip[i], 10, 64); err == nil {
            if val > 255 {
                return false
            }
        } else {
            return false
        } 
    }
    return true
}
func restoreIpAddresses(s string) []string {
    ans := []string{}
    var dfs func(temp string, dot int, index int)
    dfs = func(temp string, dot int, index int) {
        if index >= len(s) { // s字符串长度不够用了
            return
        }
        if dot >= 3 { // 如果插入的点达标了
            ip := temp + s[index:]
            if isVaildIP(ip) {
                ans = append(ans, temp + s[index:])
            }
            return
        }
        dfs(temp + ".", dot+1, index)
        dfs(temp + string(s[index]), dot, index+1)
    }
    dfs("", 0, 0)
    return ans
}
  1. 题目：11. 盛最多水的容器
    算法：左右两边谁短板，谁移动，找到最大的值。
func maxArea(height []int) int {
    l, r := 0, len(height)-1
    maxGain := 0
    for l < r {
        maxGain = max(maxGain, (r-l) * min(height[l], height[r]))
        if height[l] < height[r] {
            l++
        } else {
            r--
        }
    }
    return maxGain
}

  1. 题目：581. 最短无序连续子数组
    方法：从前往后找比前面最大的要小的最后一个数，同理另外一个相反。

  2. 题目：颜色分类
    核心方法: p0,p1 指向[0,1]结束位置. 如果是1 这换p1。 如果是0则换两次。

func sortColors(nums []int)  {
    p0, p1 := 0, 0
    for i, c := range nums {
        if c == 0 {
            nums[i], nums[p0] = nums[p0], nums[i]
            if p0 < p1 {
                nums[p1], nums[i] = nums[i], nums[p1]
            }
            p0++
            p1++
        } else if c == 1 {
            nums[i], nums[p1] = nums[p1], nums[i]
            p1++
        }
    }
}

  1. 最小栈 leetcode 155 核心方法: 建立另外一个数组，时刻都保存当前的最小值。同样的跟随主栈进出栈。

  2. 面试题 08.05. 递归乘法
    考察了对计算机底层原理的理解深度。

func multiply(A int, B int) int {
    if A > B {
        return multiply(B, A)
    }
    if A == 1 {
        return B
    }
    if A % 2 == 0 {
        return multiply(A >> 1, B) << 1
    } else {
        return (multiply(A >> 1, B) << 1) + B
    }
}
  1. 有效三角形的个数 leetcode 611. 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数
关于我
loading
在线编辑器

Copyright © 2024 编程学习网，帮助新手快速入门，高级编程的工具箱。  版权所有 ICP证：京ICP备15048378号-3联系作者