PCH1024

Appearance

数组排序（快排简版） ​

leetcode

js
var sortArray = function (nums) {
    if (nums.length <= 1) return nums;
    let minList = [];
    let maxList = [];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[0]) maxList.push(nums[i]);
        else minList.push(nums[i]);
    }
    return [...sortArray(minList), nums[0], ...sortArray(maxList)];
};
var sortArray = function (nums) {
    if (nums.length <= 1) return nums;
    let minList = [];
    let maxList = [];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > nums[0]) maxList.push(nums[i]);
        else minList.push(nums[i]);
    }
    return [...sortArray(minList), nums[0], ...sortArray(maxList)];
};

数组排序（快排标准版） ​

leetcode

js
var sortArray = function (nums) {
    // 分治递归
    function loop(arr, left, right) {
        if (left < right) {
            const middle = compare(arr, left, right); // 寻找中心并排序大小区间
            loop(arr, left, middle - 1); // 排序小区间
            loop(arr, middle + 1, right); // 排序大区间
        }
    }
    // 快慢指针区间排序
    function compare(arr, left, right) {
        let base = left; // 基准中心
        let slow = left + 1; // 慢指针
        for (let fast = slow; fast <= right; fast++) {
            // 快指针
            if (arr[fast] < arr[base]) {
                // 升序排列
                swap(arr, slow, fast);
                slow++;
            }
        }
        swap(arr, base, slow - 1);
        return slow - 1;
    }
    // 数组项交换
    function swap(arr, a, b) {
        [arr[a], arr[b]] = [arr[b], arr[a]];
    }

    loop(nums, 0, nums.length - 1);

    return nums;
};
var sortArray = function (nums) {
    // 分治递归
    function loop(arr, left, right) {
        if (left < right) {
            const middle = compare(arr, left, right); // 寻找中心并排序大小区间
            loop(arr, left, middle - 1); // 排序小区间
            loop(arr, middle + 1, right); // 排序大区间
        }
    }
    // 快慢指针区间排序
    function compare(arr, left, right) {
        let base = left; // 基准中心
        let slow = left + 1; // 慢指针
        for (let fast = slow; fast <= right; fast++) {
            // 快指针
            if (arr[fast] < arr[base]) {
                // 升序排列
                swap(arr, slow, fast);
                slow++;
            }
        }
        swap(arr, base, slow - 1);
        return slow - 1;
    }
    // 数组项交换
    function swap(arr, a, b) {
        [arr[a], arr[b]] = [arr[b], arr[a]];
    }

    loop(nums, 0, nums.length - 1);

    return nums;
};

数组排序（冒泡） ​

leetcode

js
var sortArray = function (nums) {
    let len = nums.length;
    for (let i = 0; i < len - 1; i++) {
        let hasSorted = false;
        for (let j = 0; j < len - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
                hasSorted = true;
            }
        }
        if (!hasSorted) {
            break;
        }
    }
    return nums;
};
var sortArray = function (nums) {
    let len = nums.length;
    for (let i = 0; i < len - 1; i++) {
        let hasSorted = false;
        for (let j = 0; j < len - 1 - i; j++) {
            if (nums[j] > nums[j + 1]) {
                [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
                hasSorted = true;
            }
        }
        if (!hasSorted) {
            break;
        }
    }
    return nums;
};

数组删除 ​

js
function arrayDelete(arr) {
    let slow = -1; // 慢指针
    let len = arr.length; // 数组长度
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === value) {
            // 查找到删除项
            arr[i] = undefined;
            slow = slow === -1 ? i : slow; // 慢指针记录空项索引
            len--;
        } else if (arr[i] !== value && slow !== -1) {
            // 慢指针有值且非删除项
            arr[slow] = arr[i];
            arr[i] = undefined;
            slow++; // 慢指针记录空项索引
        }
    }
    arr.length = len; // 变更新长度
    return arr;
}
function arrayDelete(arr) {
    let slow = -1; // 慢指针
    let len = arr.length; // 数组长度
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === value) {
            // 查找到删除项
            arr[i] = undefined;
            slow = slow === -1 ? i : slow; // 慢指针记录空项索引
            len--;
        } else if (arr[i] !== value && slow !== -1) {
            // 慢指针有值且非删除项
            arr[slow] = arr[i];
            arr[i] = undefined;
            slow++; // 慢指针记录空项索引
        }
    }
    arr.length = len; // 变更新长度
    return arr;
}

接雨水 ​

leetcode

js
/**
 * 前缀（含自身）最大值 l_max
 * 后缀（含自身）最大值 r_max
 * 存水条件：Math.min(l_max, r_max) 是否大于 自身
 */
var trap = function (height = []) {
    let sum = 0;
    let l_max = height[0];
    let r_max = height[height.length - 1];
    let left = 0;
    let right = height.length - 1;
    while (left <= right) {
        l_max = Math.max(height[left], l_max);
        r_max = Math.max(height[right], r_max);
        if (l_max < r_max) {
            sum += l_max - height[left++];
        } else {
            sum += r_max - height[right--];
        }
    }
    return sum;
};
/**
 * 前缀（含自身）最大值 l_max
 * 后缀（含自身）最大值 r_max
 * 存水条件：Math.min(l_max, r_max) 是否大于 自身
 */
var trap = function (height = []) {
    let sum = 0;
    let l_max = height[0];
    let r_max = height[height.length - 1];
    let left = 0;
    let right = height.length - 1;
    while (left <= right) {
        l_max = Math.max(height[left], l_max);
        r_max = Math.max(height[right], r_max);
        if (l_max < r_max) {
            sum += l_max - height[left++];
        } else {
            sum += r_max - height[right--];
        }
    }
    return sum;
};

三数之和 ​

leetcode

js
/**
 * 先排序得到非递减数组
 * 再遍历，每次固定一个数组，余下两个数字做相向指针运动
 * 优化1: arr[i] + arr[n-1] + arr[n-2] 小于 sum，本次无解跳过
 * 优化2: arr[i] + arr[i+1] + arr[i+2] 大于 sum，本题无解跳出
 * 优化3: i>0 && nums[i]===nums[i - 1], 相同值，已计算，本次跳过
 * 查找三数之和
 */
var threeSum = function (nums) {
    let target = 0;
    // 结果
    let res = [];
    // 非递减
    nums.sort((a, b) => a - b);
    // 数组项个数
    let n = nums.length;
    // 遍历
    for (let i = 0; i < n - 2; i++) {
        // 相同值跳过 i
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        // 首位的和小于目标值，则当前项全部情况都小于目标值，跳过 i
        if (nums[i] + nums[n - 1] + nums[n - 2] < target) continue;
        // 连续的和大于目标值，则所有情况也必然大于目标值，关闭 for
        if (nums[i] + nums[i + 1] + nums[i + 2] > target) break;
        // 借用两数之和的相向指针思想
        const x = nums[i];
        let j = i + 1;
        let k = n - 1;
        // 相向指针运动条件
        while (j < k) {
            let sum = x + nums[j] + nums[k];
            if (sum > target) {
                k--;
            } else if (sum < target) {
                j++;
            } else {
                res.push([x, nums[j], nums[k]]);
                for (j++; j < k && nums[j] === nums[j - 1]; j++);
                for (k--; j < k && nums[k] === nums[k + 1]; k--);
            }
        }
    }

    return res;
};
/**
 * 先排序得到非递减数组
 * 再遍历，每次固定一个数组，余下两个数字做相向指针运动
 * 优化1: arr[i] + arr[n-1] + arr[n-2] 小于 sum，本次无解跳过
 * 优化2: arr[i] + arr[i+1] + arr[i+2] 大于 sum，本题无解跳出
 * 优化3: i>0 && nums[i]===nums[i - 1], 相同值，已计算，本次跳过
 * 查找三数之和
 */
var threeSum = function (nums) {
    let target = 0;
    // 结果
    let res = [];
    // 非递减
    nums.sort((a, b) => a - b);
    // 数组项个数
    let n = nums.length;
    // 遍历
    for (let i = 0; i < n - 2; i++) {
        // 相同值跳过 i
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        // 首位的和小于目标值，则当前项全部情况都小于目标值，跳过 i
        if (nums[i] + nums[n - 1] + nums[n - 2] < target) continue;
        // 连续的和大于目标值，则所有情况也必然大于目标值，关闭 for
        if (nums[i] + nums[i + 1] + nums[i + 2] > target) break;
        // 借用两数之和的相向指针思想
        const x = nums[i];
        let j = i + 1;
        let k = n - 1;
        // 相向指针运动条件
        while (j < k) {
            let sum = x + nums[j] + nums[k];
            if (sum > target) {
                k--;
            } else if (sum < target) {
                j++;
            } else {
                res.push([x, nums[j], nums[k]]);
                for (j++; j < k && nums[j] === nums[j - 1]; j++);
                for (k--; j < k && nums[k] === nums[k + 1]; k--);
            }
        }
    }

    return res;
};

两数之和 ​

leetcode

js
var twoSum = function (nums, target) {
    let obj = { [target - nums[0]]: 0 };
    for (let i = 1; i < nums.length; i++) {
        if (obj[nums[i]] !== undefined) {
            return [obj[nums[i]], i];
        }
        obj[target - nums[i]] = i;
    }
    return [];
};
var twoSum = function (nums, target) {
    let obj = { [target - nums[0]]: 0 };
    for (let i = 1; i < nums.length; i++) {
        if (obj[nums[i]] !== undefined) {
            return [obj[nums[i]], i];
        }
        obj[target - nums[i]] = i;
    }
    return [];
};

买卖股票的最佳时机 ​

leetcode

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

js
var maxProfit = function (prices) {
    let max_profit = 0; // 历史最大收益
    let min_prices = prices[0]; // 历史最小价格
    for (let i = 1; i < prices.length; i++) {
        let profit = prices[i] - min_prices;
        max_profit = Math.max(max_profit, profit);
        min_prices = Math.min(min_prices, prices[i]);
    }
    return max_profit;
};
var maxProfit = function (prices) {
    let max_profit = 0; // 历史最大收益
    let min_prices = prices[0]; // 历史最小价格
    for (let i = 1; i < prices.length; i++) {
        let profit = prices[i] - min_prices;
        max_profit = Math.max(max_profit, profit);
        min_prices = Math.min(min_prices, prices[i]);
    }
    return max_profit;
};

买卖股票的最佳时机 II ​

leetcode

js
var maxProfit = function (prices) {
    // 阶段累加收益
    let sum = 0;
    // 同向双指针
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[j] <= prices[i]) {
                // 小于等于，原地卖出
                break;
            } else if (prices[j] > prices[i] && prices[j + 1] > prices[j]) {
                // 大于且后序还有更大利润
                continue;
            } else {
                // 见好就收
                sum += prices[j] - prices[i];
                i = j;
                break;
            }
        }
    }
    return sum;
};
var maxProfit = function (prices) {
    // 阶段累加收益
    let sum = 0;
    // 同向双指针
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            if (prices[j] <= prices[i]) {
                // 小于等于，原地卖出
                break;
            } else if (prices[j] > prices[i] && prices[j + 1] > prices[j]) {
                // 大于且后序还有更大利润
                continue;
            } else {
                // 见好就收
                sum += prices[j] - prices[i];
                i = j;
                break;
            }
        }
    }
    return sum;
};

洗牌 ​

js
function shuffle(arr) {
    for (let i = 0; i < arr.length; i++) {
        // 随机位置
        const j = Math.floor(Math.random() * arr.length);
        // 元素交换
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
}
function shuffle(arr) {
    for (let i = 0; i < arr.length; i++) {
        // 随机位置
        const j = Math.floor(Math.random() * arr.length);
        // 元素交换
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
}

括号生成 ​

leetcode

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

js
// 假设 "（"是 1, ")"是 -1，前缀和只能 >= 0
var generateParenthesis = function (n) {
    let res = [];
    function loop(n, sum, str) {
        if (n === 0 || n < sum) {
            sum === 0 && res.push(str);
            return;
        }
        if (sum > 0) {
            loop(n - 1, sum + 1, str + "(");
            loop(n - 1, sum - 1, str + ")");
        }
        if (sum === 0) {
            loop(n - 1, sum + 1, str + "(");
        }
    }
    loop(n * 2, 0, "");
    return res;
};
// 假设 "（"是 1, ")"是 -1，前缀和只能 >= 0
var generateParenthesis = function (n) {
    let res = [];
    function loop(n, sum, str) {
        if (n === 0 || n < sum) {
            sum === 0 && res.push(str);
            return;
        }
        if (sum > 0) {
            loop(n - 1, sum + 1, str + "(");
            loop(n - 1, sum - 1, str + ")");
        }
        if (sum === 0) {
            loop(n - 1, sum + 1, str + "(");
        }
    }
    loop(n * 2, 0, "");
    return res;
};

有效的括号字符串 🌟 ​

leetcode 给你一个只包含三种字符的字符串，支持的字符类型分别是 '('、')' 和 '*'。请你检验这个字符串是否为有效字符串，如果是有效字符串返回 true 。

  • '*' 可以被视为单个右括号 ')' ，或单个左括号 '(' ，或一个空字符串。
  • 一个空字符串也被视为有效字符串。
js
/**
 * 贪心
 *      (       (       *       *       )       )
 * min  +       +       -/0     -/0     -       -     最小待匹配左括号 ( 数量
 * max  +       +       +       +       -       -     最大待匹配左括号 ( 数量
 */
var checkValidString = function (s) {
    let min = 0; // 待匹配左括号 ( 数量
    let max = 0; // 待匹配左括号 ( 数量
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            min++;
            max++;
        } else if (s[i] === ")") {
            // 当最小值为 0 时，不应将最小值继续减少，以确保最小值非负。
            min = Math.max(min - 1, 0);
            max--;
            if (max < 0) {
                // 任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，
                // 说明没有左括号可以和右括号匹配，返回 false
                return false;
            }
        } else {
            // 当最小值为 0 时，不应将最小值继续减少，以确保最小值非负。
            min = Math.max(min - 1, 0);
            max++;
        }
    }
    // 遍历结束时，所有的左括号都应和右括号匹配，
    // 因此只有当最小值为 0 时，字符串 s 才是有效的括号字符串。
    return min === 0;
};
/**
 * 贪心
 *      (       (       *       *       )       )
 * min  +       +       -/0     -/0     -       -     最小待匹配左括号 ( 数量
 * max  +       +       +       +       -       -     最大待匹配左括号 ( 数量
 */
var checkValidString = function (s) {
    let min = 0; // 待匹配左括号 ( 数量
    let max = 0; // 待匹配左括号 ( 数量
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            min++;
            max++;
        } else if (s[i] === ")") {
            // 当最小值为 0 时，不应将最小值继续减少，以确保最小值非负。
            min = Math.max(min - 1, 0);
            max--;
            if (max < 0) {
                // 任何情况下，未匹配的左括号数量必须非负，因此当最大值变成负数时，
                // 说明没有左括号可以和右括号匹配，返回 false
                return false;
            }
        } else {
            // 当最小值为 0 时，不应将最小值继续减少，以确保最小值非负。
            min = Math.max(min - 1, 0);
            max++;
        }
    }
    // 遍历结束时，所有的左括号都应和右括号匹配，
    // 因此只有当最小值为 0 时，字符串 s 才是有效的括号字符串。
    return min === 0;
};

全排列 ​

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

js
var permute = function (nums) {
    let res = [];
    function loop(arr, used) {
        if (arr.length && arr.length === nums.length) {
            return res.push(arr);
        }
        for (let i = 0; i < nums.length; i++) {
            const num = nums[i];
            if (used[num]) continue;
            loop(arr.concat([num]), Object.assign({ [num]: true }, used));
        }
    }
    loop([], {});
    return res;
};
var permute = function (nums) {
    let res = [];
    function loop(arr, used) {
        if (arr.length && arr.length === nums.length) {
            return res.push(arr);
        }
        for (let i = 0; i < nums.length; i++) {
            const num = nums[i];
            if (used[num]) continue;
            loop(arr.concat([num]), Object.assign({ [num]: true }, used));
        }
    }
    loop([], {});
    return res;
};

༼ つ/̵͇̿̿/’̿’̿ ̿ ̿̿ ̿̿◕ _◕ ༽つ/̵͇̿̿/’̿’̿ ̿ ̿̿ ̿̿ ̿̿

COPYRIGHT © 1992-PRESENT PCH1024-V1.0.64