资讯专栏INFORMATION COLUMN

leetcode 一些算法题目记录

mayaohua / 3474人阅读

摘要:题目全部用做的,基本上每天一题的节奏。题目这里记录自己对一些题目的思路和想法数字回文,说不能用额外的空间一下子懵逼了,第一概念就是换成字符串比较,但是感觉这样子做就没有意义了。找出任意两条线段与轴组成的木桶,可以盛水最大的值。

前言

原文地址

无意间发现 LeetCode 这个网站,一下子就陷进去了,大学时候看舍友参加 acm 一天到晚刷题,对算法总有点特殊的情怀。本以为我永远是接触不到这个了,没想到 leetcode 却让我感觉到 Accepted 这个单词的特殊魅力。

个人

首先自己并不是为了找工作去刷题的,纯粹享受做题的过程和ac的快感。题目全部用 JavaScript 做的,基本上每天一题的节奏。开始总是想着怎么把答案解出来就好,经常 TLE ,感觉一路做下来自己慢慢会考虑复杂度,逻辑严谨性也在逐步加强,对特殊值的考虑越来越多,相比于算法能力的提升我更欣喜看到自己逻辑严谨性加强,感觉这对自己后面的道路帮助会很大。

题目

这里记录自己对一些题目的思路和想法

Palindrome Number

`

1         =>   true;
21         =>   false;
303        =>   true;

`

数字回文,说不能用额外的空间一下子懵逼了,第一概念就是换成字符串比较,但是感觉这样子做就没有意义了。看了别人思路发现给的数字每次取 10 的余数拼起来正好是数字倒过来写。如果只取出一半,原数字也舍弃一半 正好就是回文的两个内容。有了思路就好做了判断下特殊条件,比较最后两个数字就可以了,如果是奇数位数字就减掉中间一位再比较。

    var max = Math.pow(2,31) - 1
    var isPalindrome = function(x) {
        if (x < 0 || x > max || (x != 0 && x % 10 == 0)) return false
        if (x < 10) return true
        var num = 0
        while(x > num) {
            num = num * 10 + x % 10
            x = Math.floor(x / 10)
        }
        return num == x || (x != 0 && Math.floor(num / 10) == x)
    };
    
Container With Most Water

`

给定一个数组,想象成一个二位坐标系,数组中每一个元素 a[i] => n 就是坐标系上的一条线段[ (i,0) => (i,x) ]。找出任意两条线段与 x 轴组成的木桶,可以盛水最大的值。

`

看到题目想了一下就想着两层循环去计算,果然就超时了,看了看别人的思路,开始就算出0到最后一个线段组成的木桶的面积,然后找出线段比较短的一条向中间靠拢,如果下一条线段比当前线段还短就忽略,反之就继续循环计算。想了想这样做也是合理的如果下一条线段比当前的还短那组成的面积肯定比较小。有了思路就好做了

    var maxArea = function(height) {
        let i = 0, l = height.length -1, res = 0
            
        while(i < l) {
            var h = Math.min(height[i],height[l])
            res = Math.max(res, (l-i) * h)
            if(height[i] < height[l]) {
                while(height[i] <= h && i < l){i++}
            } else {
                while(h >= height[l] && i < l){l--}
            }
        }
        return res
    }
    
Regular Expression Matching

`

实现正则,
"." Matches any single character.
"*" Matches zero or more of the preceding element.
isMatch("aa","a") → false 
isMatch("ab", ".*") → true     
isMatch("aab", "c*a*b") → true

`
刚开始看到这题目还是比较懵的,感觉要判断的好多,后面从递归判断做就有思路了,从正则表达式入手,先判断第二位是不是 * ,如果不是就判断第一位然后截取一位递归,如果是就先去除正则前两位递归,不行再判断第一个是不是相等然后循环递归

    var isMatch = function(s, p) {
        if(p[0] === undefined) return s[0] === undefined
        if (p[1] != "*") {
           if (s[0] === p[0] || (p[0] === "." && s[0] !== undefined)) 
               return isMatch(s.substr(1), p.substr(1))
           else 
               return false
        } else {
            if (isMatch(s, p.substr(2)))return true
            let index = 0
            while(index <= s.length && (s[index] === p[0] || p[0] === ".")){
                if(isMatch(s.substr(++index), p.substr(2))) return true
            }
            return false
        }
    }
    
Is Circular

看到一个面试题,JSON.stringify 是 javascript 的一个方法返回一个json格式的字符串,效果如下

    const obj = {a:1, b:2}
    JSON.stringify(obj) // => "{"a":1,"b":2}"
   

当要转化的对象有“环”存在时(子节点属性赋值了父节点的引用),为了避免死循环,JSON.stringify 会抛出异常,例如:

    var a = [1]
    a.push(a)
    JSON.stringify(a) // => Uncaught TypeError: Converting circular structure to JSON

写一个函数判断参数是否包含 ,自己想到的是用 map 对象把是对象的值做为键存储值,然后判断值是否存在来判断是否回环, 要注意每一次要用一个新的 map 对象,避免同级别相互引用判断错误的情况

    let isCircular = (o) => {
        var flag = false
        const func = (obj, map = new Map()) => {
            map.set(obj, true)
            Object.values(obj).forEach(d=> {
                if (flag) return
                if (typeof d == "object") {
                    if (map.get(d)) {
                        flag = true
                        return
                    } else {
                        let newmap = new Map(map)
                        func(d, newmap)
                    }
                }
            })
        }
        func(o)
        return flag
    }
Submission Details
给一个数字,写一个函数根据数字生成所有形式良好的括号组合
2 => ["()()", "(())"]
3 => 
    [
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

想了一下有一个思路,就是根据 () 里面的包含几个子 () 来得出所有情况。 比如给出的数字是5, 那么循环到5,第n 就有 ( [func(n)的结果] ) * func(4-n)的结果

一直想着以一个优雅的方式处理边界的问题,但是想半天都没结果,只能写的丑陋点了。

    var generateParenthesis = function(n) {
        if(n == 0) return []
        if(n == 1) return ["()"]
        let arr = []
        for(let i = 0; i < n; i++) {
            if( i == 0) {
                arr = arr.concat(generateParenthesis([n-1]).map(d => "()" + d ))
            } else if (i == n-1){
                arr = arr.concat(generateParenthesis([n-1]).map(d => "(" + d + ")"))
            } else {
                generateParenthesis(i).forEach(d => {
                    let eachres = "(" + d +")"
                    generateParenthesis(n- i -1).forEach(c => {
                        arr.push(eachres + c)
                    })
                })
            }
        }
        return arr
    };

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/85109.html

相关文章

  • LeetCode 攻略 - 2019 年 8 月上半月汇总(109 题攻略)

    摘要:每天会折腾一道及以上题目,并将其解题思路记录成文章,发布到和微信公众号上。三汇总返回目录在月日月日这半个月中,做了汇总了数组知识点。或者拉到本文最下面,添加的微信等会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。 LeetCode 汇总 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...

    tracy 评论0 收藏0
  • LeetCode 攻略 - 2019 年 7 月上半月汇总(55 题攻略)

    摘要:微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容,进行补充,并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目录 不...

    warmcheng 评论0 收藏0
  • LeetCode 攻略 - 2019 年 7 月下半月汇总(100 题攻略)

    摘要:月下半旬攻略道题,目前已攻略题。目前简单难度攻略已经到题,所以后面会调整自己,在刷算法与数据结构的同时,攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题,目前已攻略 100 题。 一 目录 不折腾的前端,和咸鱼有什么区别...

    tain335 评论0 收藏0
  • Python 后端开发面试记录

    摘要:辛苦面试了好多家大小公司,在面试中也发现了自己的很多不足,也有很多的感悟,这里记录一下,为的是之后的学习与提高更有针对性。面试中的的题目就是准备不足的充分表现。其实大部分面试官都不会给什么反馈,只是机械地听答案,记录评价。 辛苦面试了好多家大小公司,在面试中也发现了自己的很多不足,也有很多的感悟,这里记录一下,为的是之后的学习与提高更有针对性。 关于刷题 LeetCode 要刷,面试...

    PascalXie 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<