【近日力扣】单词拆分+合并区间+链表排序+调整数组顺序使奇数位于偶数前面

单词拆分(中等)

  • 动态规划
    • ”leetcode“ 是否可被组成,可分解成——步长为 1 时,“l” 是否存于字典且后续子串可被组成,等等;步长为 2 时,“le” 是否存于字典且后续子串可被组成,等等;步长为 3 时,“lee” 是否存于字典且后续子串可被组成,等等
    • 以此类推,设dp[i]表示s[0, i]的字符串是否可被组成,设j为当前步长,若要dp[i]为真,则需dp[j]为真且s[j, i - j]存在字典中,由此推出递推式:dp[i] = dp[j] && isTrue(s[j, i - j])
var wordBreak = function(s, wordDict) {
	// Set对象去重,且has方法来判断是否为真很方便
    let set = new Set(wordDict)
    // 填充数组为false,为什么要多出一位?
    let dp = new Array(s.length + 1).fill(false)
    dp[0] = true // 边界:定义空串为真
    // i可以等于s.length 和上述多出一位有什么联系?思考substr用法
    for (let i = 1; i <= s.length; i++) {
    	// 字长不能超过当前判断的子串长度
        for (let j = 0; j < i; j++) {
            if (dp[j] && set.has(s.substr(j, i - j))) {
                dp[i] = true
                break
            }
        }
    }
    return dp[s.length]
};

合并区间(中等)

  • 排序:只要把区间集合按左端点按升序排列,可以令可合并的条件简化——只要第二个区间的左端点落在第一个区间中,且右端点不是,这两个区间就可以合并。如果未排序?则可合并区间隔了一段距离,判断条件将复杂许多
var merge = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0])
    let res = []
    let cur = intervals[0]
    for (let i = 1; i < intervals.length; i++) {
    	// 判断当前区间的左端点是否落于cur的区间中
        if (cur[1] >= intervals[i][0]) {
        	// 判断右端点
            if (cur[1] < intervals[i][1]) {
            	// 合并
                cur = [cur[0], intervals[i][1]]
            } 
        } else {
            res.push(cur)
            cur = intervals[i]
        }
    }
    res.push(cur)
    return res
};

链表排序(中等)

  • 归并排序
    • 进阶要求O(nlogn)的时间复杂度,自然想到归并排序、快速排序、堆排序,这里选取了归并排序
    • 该问题其实可分解为归并排序 + 双指针找单链表中点 + 合并两个排序链表三个小题的组合。整体来说改题书写还是太复杂了,多用 JS 现成的方法会好一点点
var sortList = function(head) {
    if (!head || !head.next) return head
    let left = head
    let right
    let slow = head, fast = head.next
    // 《双指针找链表中点》
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
    }
    right = slow.next
    slow.next = null
    // 《合并两个排序链表》
    let merge = (l, r) => {
        let head = new ListNode(0)
        let cur = head
        while (l !== null && r !== null) {
            if (l.val < r.val) {
                cur.next = l
                l = l.next
            } else {
                cur.next = r
                r = r.next
            }
            cur = cur.next
        }
        if (l) cur.next = l
        if (r) cur.next = r
        return head.next
    }
    // 《归并排序》
    return merge(sortList(left), sortList(right))
};

调整数组顺序使奇数位于偶数前面(简单)

  • 暴力:for 循环判断奇偶
var exchange = function(nums) {
    let a1 = [], a2 = []
    for (let i = 0; i < nums.length; i++) {
        nums[i] % 2 === 0 ? a2.push(nums[i]) : a1.push(nums[i])
    }
    return [...a1, ...a2]
}
  • 双指针:双指针指向两端,往中间遍历(非同步),只要遇到左指针指向偶数、右指针指向奇数的情况,就交换两数
var exchange = function(nums) {
    for (let i = 0, j = nums.length - 1; i < j;) {
        if (nums[i] % 2 === 0 && nums[j] % 2 === 1) {
            [nums[i], nums[j]] = [nums[j], nums[i]]
            i++
            j--
            continue
        }
        nums[i] % 2 === 0 ? j-- : i++
    }
    return nums
};

如果觉得对你有帮助的话,点个赞呗~

反正发文又不赚钱,交个朋友呗~

如需转载,请注明出处foolBirdd

上一篇:let 到底有无变量提升


下一篇:风尚云网-JS相关综合面试题(不看后悔系列)持续更新...