leetcode例题

11 盛水最多的容器

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

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

提示：
	n = height.length
	2 <= n <= 3 * 104
	0 <= height[i] <= 3 * 104

来源：https://leetcode-cn.com/problems/container-with-most-water/

解题思路

这道题实际上就是求Max[ ( j-i ) * min( height[i], height[j] )]。 用左右两个指针表示左右边界，求解可行解，然后进一步移动指针，直到两个指针碰到为止求出最佳解。

主要难度在于每次如何移动指针，首先确定的是每次求解完可行解之后一定会移动指针，所以j-i一定会小1（每次移动一个单位),要求最大解，就需要移动值更小的指针。

具体证明参考官方题解： leetcode-cn.com/problems/co…

/**
 * @param {number[]} height
 * @return {number}
 */
let maxArea = function(height) {
    let left = 0, right = height.length - 1;
    let max = -1;
    while(left <= right){
        let sum = (right - left) * Math.min(height[left],height[right]);
        max = sum > max ? sum : max;
        if(height[left] > height[right]) {
            right--;
        }else{
            left++;
        }
    }
    return max;

};

167两数之和 II - 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:
返回的下标值（index1 和 index2）不是从零开始的。	
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

leetcode-cn.com/problems/tw…

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    while(left < right){
        let sum = numbers[left] + numbers[right];
        if(sum === target)
            return [left + 1,right + 1];
        else if(sum < target){
            left++;
        }else{
            right--;
        }
    }
};

16 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

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

提示：
	3 <= nums.length <= 10^3
	-10^3 <= nums[i] <= 10^3
	-10^4 <= target <= 10^4

来源：https://leetcode-cn.com/problems/3sum-closest/

解题思路

这道题条件是min|(a+b+c)-target|，暴力求解就是三个for循环,时间复杂度是O(N^3)。

进行优化,首先对数组进行排序(递增),然后最外层循环数组选出第一个数a,那么循环内部就 是求最接近target - a 的两个数的和,这样就可以用双指针算法(同上一道题)。最后时间复杂度是O(N^2)。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
let threeSumClosest = function(nums, target) {
    let sum = 0;//最接近的和
    let gap = Infinity;//差值
    nums = nums.sort(function(a, b){return a - b});//要对sort函数进行修正

    for(let a = 0; a < nums.length-2; a++){
        //枚举第一个数,a后面还有两个指针，所以最多道nums.length - 3
        let left = a + 1;
        let right = nums.length -1;

        while(left < right){
            let res = nums[a] + nums[left] + nums[right];
            let gapNow = Math.abs(res - target);
            if(gapNow < gap){//是个更优的可行解
                gap = gapNow;
                sum = res;
            }
            if(res > target){
                right--;
            }else{
                left++;
            }
        }
        
    }
    return sum;
};

240 搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。 每列的元素从上到下升序排列。

示例:
现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30],
]
给定 target = 5，返回  true。
给定  target = 20，返回  false。

leetcode-cn.com/problems/se…

解题思路

该矩阵是有顺序的，左上角最小，右下角最大，所以可以从左下角或者右上角开始搜索。

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let width = matrix[0].length;
    let left = 0;
    let down = matrix.length - 1;
    //从左下角开始搜索
    while(left < width && down >= 0){
        let now = matrix[down][left];
        if(now === target)
            return true;
        else if(now > target){
            down--;
        }else{
            left++;
        }
    }
    return false;

};

26 删除排序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例  1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

示例  2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

解题思路1

看到这道题时首先想到要判重，所以采用了map来计数，然后用left指针指向可以存放下一个不重复元素的位置，right指针用来遍历数组，一旦遇到第一次出现的数就加入map，并且赋值给left所在位置。

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let map = {};//存放数组元素是否出现过
    let left = 0;
    let right = 0;
    while(right < nums.length){
        if(!map[nums[right]]){
            map[nums[right]] = 1;
            nums[left] = nums[right];
            left++;
        }
        right++;
    }
    return left;
};

解题思路2

看到题解之后发现判重的步骤可以更简单一点，因为该数组是有序数组，所以重复的数一定放在一起,这样只用判断left指针和right指针所指的数是否一样，不一样就赋值即可。

解法一更适合 无序的 有重复元素的数组。

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let left = 0;//left指向上一次查出的不重复元素
    let right = 0;
    while(right < nums.length){

        if(nums[left]!=nums[right]){
            left++;
            nums[left] = nums[right];
        }
        right++;
    }
    return ++left;//Left是最后一个不重复元素的索引，长度=索引+1
};

283 移动零

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

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。

leetcode-cn.com/problems/mo…

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let left = 0;
    let right = 0;
    while(right < nums.length){
        if(nums[right]!=0){
            nums[left] = nums[right];
            left++;
        }
        right++;
    }
    while(left < nums.length){
        nums[left] = 0;
        left++;
    }
    return;
};

392 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.

链接：https://leetcode-cn.com/problems/is-subsequence

TODO后续挑战 :

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10 亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

参考：https://leetcode-cn.com/problems/is-subsequence/solution/dui-hou-xu-tiao-zhan-de-yi-xie-si-kao-ru-he-kuai-s/

解题思路

i指针遍历s ,j指针遍历t ,在遍历t的时候发现此时t[j]和s[i]相同，i++,如果可以遍历完s说明匹配到子序列，否则就是没有

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    let i = 0;
    let j = 0;
    let sLen = s.length;
    let tLen = t.length;
    while(i < sLen && j < tLen){
        if(s[i] === t[j]){
            i++;
        }
        j++;
    }
    if(i === sLen)
        return true;
    else
        return false;
};

524 删除字母匹配到字典中最长的单词

给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:
输入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出:
"apple"
示例 2:
输入:
s = "abpcplea", d = ["a","b","c"]
输出:
"a"
说明:
所有输入的字符串只包含小写字母。
字典的大小不会超过 1000。
所有输入的字符串长度不会超过 1000。

链接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting

解题思路

先把d按字典序排列，遍历字典数组，比较每一个字符串和s。(比较方法同上一道题)。

/**
 * @param {string} s
 * @param {string[]} d
 * @return {string}
 */
var findLongestWord = function(s, d) {
    d = d.sort();//按字典序排序
    let max = -1;//最长的长度
    let index = -1;//字典最大匹配字符串的下标
    for(let i = 0; i < d.length; i++){
        let l = 0;
        let r = 0;
        while(l < s.length && r < d[i].length){
            if(s[l] === d[i][r]){
                r++;
            }
            l++;
        }
        if(r === d[i].length && d[i].length > max){
            max = d[i].length;
            index = i;
        }
    }
    return max === -1? "":d[index];
};

455 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：
你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: [1,2], [1,2,3]	
输出: 2
解释: 
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

链接：https://leetcode-cn.com/problems/assign-cookies

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    g = g.sort((a,b)=>{return a - b});
    s = s.sort((a,b)=>{return a - b});
    let i = 0;
    let j = 0;
    while(i < g.length && j < s.length){
        if(s[j] >= g[i]){
            i++;
        }
        j++;
    }
    return i;
};

125 验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false

leetcode-cn.com/problems/va…

解题思路

用正则提取出相应的字符串，统一大小写。用两个指针从两边向中间遍历，判断是否相同。

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    //使用正则提取出只有字母和数字的字符串，然后转变成小写
    let value = s.replace(/[^a-z0-9]/ig,'').toLowerCase();
    if(value==='')
        return true;

    let left = 0;
    let right = value.length - 1;
    let flag = true;
    while(left < right){
        if(value[left] != value[right]){
            return false;
        }
        left++;
        right--;
    }
    return true;
};