leetcode_双指针合集

One minute read
LeetCode
面试 • 算法 • 数据结构

11. 盛最多水的容器

题目

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/container-with-most-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

双指针往中间逼近，更新最大值

逼近原则：哪个比较低就往中间逼近（贪心思维）

func maxArea(height []int) int {
    low, high := 0, len(height)-1
    var max int
    for low < high {
        now := min(height[low], height[high])*(high-low)
        if max < now {
            max = now
        }
        
        if height[low] < height[high] {
            low++
        } else {
            high--
        }
    }
    return max
}

func min(x, y int) int {
    if x > y {
        return y
    }
    return x
}

面试题 17.11. 单词距离

题目

有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离(相隔单词数)。如果寻找过程在这个文件中会重复多次，而每次寻找的单词不同，你能对此优化吗?

示例：

输入：words = ["I","am","a","student","from","a","university","in","a","city"], word1 = "a", word2 = "student"
输出：1

提示：

  • words.length <= 100000

解答

func findClosest(words []string, word1 string, word2 string) int {
    min := math.MaxInt32
	var w1, w2 int = 2*(len(words)-1), len(words)-1
    for k, v := range words {
        if v == word1 {
            w1 = k
        }
        if v == word2 {
            w2 = k
        }
        min = minInt(min, absInt(w1-w2))
    }
    return min
}

func minInt(x, y int) int {
    if x > y {
        return y
    }
    return x
}

func absInt(x int) int {
    if x >= 0 {
        return x
    }
    return -x
}

分享：