LeetCode题目练习记录 _数组和链表02

LeetCode题目练习记录 _数组和链表02 _20211008

11. 盛最多水的容器

难度中等2834

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

说明：你不能倾斜容器。

示例 1：

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

示例 2：

输入：height = [1,1]
输出：1

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

输入：height = [1,2,1]
输出：2

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

方法一：双指针 左右指针，短板弃之

// java
class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length -1;
        int ans = 0;
        while(left < right) {
            int area = Math.min(height[left],height[right]) * (right-left);
            ans = Math.max(ans,area);
            if (height[left] <= height[right]){
                ++left;
            }else{
                --right;
            }
        }
        return ans;
    }
}

// go
func maxArea(height []int) int {
    i,j :=0,len(height)-1
    m:=0
    for i<j{
        cur:=(j-i)*min(height[i],height[j])
        if cur>m{
            m=cur
        }
        if (height[i]<height[j]) {
            i++
        }else {
            j--
        }
    }
    return m
}

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

// go
func maxArea(height []int) int {
    lenA := len(height)
    i,j :=0,lenA-1
    maxAreaC := 0
// 更直接的运算方式 会带来更快的 运行速度
    for{
        if i == j {
            break
        }

        write := false
        minH := height[i]
        if height[j]<minH{
            minH = height[j]
            write = true
        }
        curArea := (j-i)*minH

        if write{
            j --
        }else{
            i++
        }

        if curArea > maxAreaC{
            maxAreaC = curArea
        }
    }
    return maxAreaC
}

方法二：暴力 ——会超时！

// java
class Solution {
    public int maxArea(int[] height) {

        int maxarea = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                maxarea = Math.max(maxarea, Math.min(height[i], height[j]) * (j - i));
        return maxarea;
    }
}

283. 移动零

难度简单1259

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

示例:

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

说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

方法一：双指针 —— 快慢指针法

// go
// 双指针 —— 快慢指针法
func moveZeroes(nums []int)  {
    left, right, n := 0, 0, len(nums)
    for right < n {
        if nums[right] != 0 {
            nums[left], nums[right] = nums[right], nums[left]
            left ++
        }
        right ++
    }
}
// 右指针走在前，左指针走在后，如果右指针指向 0 不要动它，右指针继续超前遍历，遇到非0就和左指针交换，交换之后左指针 向前一步 右指针也要向前，这样就能保证 把所有非0元素移动到前面来

方法二：双指针 —— 补0覆盖

// go
func moveZeroes(nums []int)  {
    nowIdx := 0
    for _,x := range nums {
        if x != 0 {
            nums[nowIdx] = x
            nowIdx++
        }
    }
    for i := nowIdx; i < len(nums); i++ {
        nums[i] = 0
    }
}

70. 爬楼梯

难度简单1924

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

这本质就是一个数学题，需要一定的线代知识，太多思路就不展开了，官方题解都有

方法一：动态规划

// go
func climbStairs(n int) int {
    p, q, r := 0, 0, 1
    // 一步没走，现在只有一个办法，去走上第一级台阶
    for i := 1; i <= n; i++ { // 走起来了
        p = q // 走上上一个台阶需要的步数
        q = r // 走上一个台阶需要的步数
        r = p + q  // 走当前台阶需要的步数
        // 不断迭代，小步慢走
    }
    return r
}

方法二：矩阵快速幂

// go
type matrix [2][2] int

func climbStairs(n int) int {
    res := pow(matrix{{1,1},{1,0}},n)
    return res[0][0]
}

func pow(a matrix,n int) matrix {
    res := matrix{{1,0},{0,1}}
    for ; n > 0; n >>= 1 {
        if n&1 == 1 {
            res = mul(res, a)
        }
        a = mul(a,a)
    }
    return res
}

func mul(a, b matrix) (c matrix) {
    for i :=0; i < 2; i++ {
        for j := 0; j < 2; j++ {
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
        }
    }
    return c
}

方法三：通项公式

// go
func climbStairs(n int) int {
    sqrt5 := math.Sqrt(5)
    pow1 := math.Pow((1+sqrt5)/2,float64(n + 1))
    pow2 := math.Pow((1-sqrt5)/2,float64(n + 1))
    return int(math.Round((pow1-pow2)/sqrt5))
}

15. 三数之和

难度中等3846

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

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

示例 2：

输入：nums = []
输出：[]

示例 3：

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

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

// java
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if(nums == null || nums.length <= 2){
            return Collections.emptyList();
        }
        Set<List<Integer>> result = new LinkedHashSet<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            int head = i+1;
            int tail = nums.length -1;
            while(head<tail){
                int sum = - (nums[head]+nums[tail]);
                if(sum == nums[i]){
                    List<Integer> value = Arrays.asList(nums[i],nums[head],nums[tail]);
                    result.add(value);
                }
                if(sum <= nums[i]){
                    tail--;
                }else{
                    head++;
                }
            }
        }
        return new ArrayList<>(result);
}
}

// go
func threeSum(nums []int) [][]int {
    n := len(nums)
    sort.Ints(nums)
    ans := make([][]int, 0)
    for first := 0;first < n; first ++ {
        if first > 0 && nums[first] == nums[first - 1] {
            continue
        }
        third := n-1
        target := -1 * nums[first]
        for second := first + 1 ;second < n ; second++ {
            if second > first + 1 && nums[second] == nums[second - 1] {
                continue
            }
            for second < third && nums[second] + nums[third] > target {
                third--
            }
            if second == third {
                break
            }
            if nums[second] + nums[third] == target { // if a + b = -c 将 abc加入结果集
                ans = append(ans,[]int{nums[first],nums[second],nums[third]})
            }
        } 
    }
    return ans 
}

// js
var threeSum = function(nums){
            let arr = [];
            nums.sort((a,b) => {
                return a - b;
            })
            for(let i = 0;i < nums.length;i++){
                if(i > 0 && nums[i] === nums[i - 1]) continue;
                let left = i + 1,right = nums.length - 1;
                let a = nums[i];
                while(left < right){
                    let b = nums[left];
                    let c = nums[right];
                    if(a + b + c === 0){
                        arr.push([a,b,c]);
                        //神来之笔，诸位道友有想过for循环这么用吗
                        for(left++;left < right && nums[left] === nums[left - 1];left++);
                    }else if(a + b + c < 0){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
            return arr;
        }