标签: LeetCode

LeetCode刷题【902】最大为 N 的数字组合

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如,如果 digits = ['1','3','5'],我们可以写数字,如 '13''551', 和 '1351315'

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

 

示例 1:

输入:digits = ["1","3","5","7"], n = 100
输出:20
解释:
可写出的 20 个数字是:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2:

输入:digits = ["1","4","9"], n = 1000000000
输出:29523
解释:
我们可以写 3 个一位数字,9 个两位数字,27 个三位数字,
81 个四位数字,243 个五位数字,729 个六位数字,
2187 个七位数字,6561 个八位数字和 19683 个九位数字。
总共,可以使用D中的数字写出 29523 个整数。

示例 3:

输入:digits = ["7"], n = 8
输出:1

 

提示:

  • 1 <= digits.length <= 9
  • digits[i].length == 1
  • digits[i] 是从 '1' 到 '9' 的数
  • digits 中的所有值都 不同 
  • digits 按 非递减顺序 排列
  • 1 <= n <= 109

数学方法+递归,10月18日,今天的每日一题,有空偷个闲撸一把

看到题目第一反应是动态规划,然后扫了下题目给了示例,看到这么一段

输入:digits = ["1","4","9"], n = 1000000000
输出:29523
解释:
我们可以写 3 个一位数字,9 个两位数字,27 个三位数字,
81 个四位数字,243 个五位数字,729 个六位数字,
2187 个七位数字,6561 个八位数字和 19683 个九位数字。
总共,可以使用D中的数字写出 29523 个整数。

突然灵光一闪,可以直接用数学方法来解

拿其中的一个示例稍微改下来分解运算试试看,粗略的分解如下

输入:digits = ["1","3","5","7"], n = 1571
 1 5 7 1

 4
 16   4*4
 64   4*4*4
 45   0*4*4*4 + 1 * (2*4*4 + 1 * (3*4 + 1*( 0 + 1*(1))))

最终验证得到 4 + 16 + 64 + 45 = 129 确定正确
如果你能看懂上面最后一行 4位数的组合数量计算公式的话,那么说明你就已经GET到了

数字1571一共有4位,那么我们将结果分为两部分,不满足4位的和满足4位的结果分开计算

不满足4位的部分

  1. 如果只列举一位,那么就有String[] digits种方案,每一个数字都可以列举一次
  2. 如果要列举两位数字的情况,那么每一位都可以列举String[] digits种方案,在本示例中即为4 * 4
  3. 如果要列举三位数字的话,那么同理有4 * 4 * 4中,因为位数小于目标数字n = 1571的4位,所以可以任意组合,不要考虑结果是否会大于1571

接下来第二部分,需要组合4位数字的情况

  1. 我们先取出目标数字1571的第一位数字1,拿到digits数组中比较,发现小于1的没有,但是有等于1的情况
  2. 如果digits中存在小于当前位数字的lessCnt个,那么后面的排列组合可以不考虑。即有lessCnt * digits.length * ...... * digits.length种组合情况
  3. 如果digits中没有当前位的数字,在处理了上一位小于的情况之后,说明后面无论怎么样排序都不会有满足结果小于目标值的情况
  4. 如果存在有等于当前位的数字,那么,我们需要再往后看一位,此时回到了和步骤1相同的处理逻辑部分
  5. 那么第二位是5,digits数组中有[1,3]是小于5的,即可以有两种情况,后面无论如何排列都是满足的,那么得到2 * 4 * 4
  6. digits数组中也包含了5,我们继续看下一位数字7
  7. digits数组中有[1,3,5]小于7,于是有新的可能组合数量 3 * 4,且数组中有数字7,那么继续看下一位数字
  8. 最后一位数字1,同样的,数组中小于1的数字不存在,那么即有0种情况,后面没有4要乘了
  9. 同时数组中包含了1,所以继续看下一位
  10. 最后已经没有下一位了,这里需要返回个1,根据前一步的结果返回0的话显然会造成结果不正确

代码

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        int size = getSize(n);
        int ans = 0;
        int t = digits.length;
        //低位数的直接相加
        while (--size>0){
            ans += t;
            t *= digits.length;
        }
        int[] intDigtis = getIntDigtis(digits);
        int[] nArr = getNArr(n);
        //最高位数的分区段统计数量
        ans += splitCnt(intDigtis,nArr, 0);
        return ans;
    }

    int splitCnt(int[] digits, int[] arr, int idx){
        if (idx == arr.length){
            return 1;
        }
        //比arr[idx]小的数字有个lessCnt个,相等的有equalCnt个
        int lessCnt = 0;
        int equalCnt = 0;
        for (int i = 0; i < digits.length; i++) {
            if (digits[i] > arr[idx]){
                break;
            }
            if (digits[i] < arr[idx]){
                lessCnt++;
            }
            if (digits[i] == arr[idx]){
                equalCnt++;
            }
        }
        for (int i = idx+1; i < arr.length; i++) {
            lessCnt *= digits.length;
        }
        return lessCnt + (equalCnt * splitCnt(digits,arr,idx+1));
    }

    final static int[] mod = {
            0,
            1,
            10,
            100,
            1000,
            10000,
            100000,
            1000000,
            10000000,
            100000000,
            1000000000
    };

    final static int [] sizeTable = {
            9,
            99,
            999,
            9999,
            99999,
            999999,
            9999999,
            99999999,
            999999999,
            Integer.MAX_VALUE
    };

    static int getSize(int x) {
        for (int i=0; ; i++)
            if (x <= sizeTable[i])
                return i+1;
    }

    int[] getIntDigtis(String[] digtis) {
        int[] intDigtis = new int[digtis.length];
        for (int i = 0; i < digtis.length; i++) {
            intDigtis[i] = digtis[i].charAt(0)-'0';
        }
        return intDigtis;
    }

    int[] getNArr(int n){
        int size = getSize(n);
        int[] nArr = new int[size];
        int i = size;
        while (n > 0){
            nArr[size-i] = n/mod[i];
            n %= mod[i];
            i--;
        }
        return nArr;
    }
}

思路想明白了的话,还是不算太复杂的,主要是全位数部分计算的方法要递归起来实现的话,略微有点点显得绕

油猴脚本,抓取LeetCode题解[3]

再更新一下,接之前的版本油猴脚本,抓取LeetCode题解[2],在原来的基础上增加了单独抓取单篇题解的功能,再做这个的时候其实遇到个问题,主要难点在于如何监听浏览器地址栏的变化,另开一个文章来说《无刷新页面监听URL变化实现

至于新增这个功能的原因如下,在使用初版的功能全量的抓取了自己的题解文章之后,对于每天新增的题解不能单独抓取补充到indexDB之中,只能再次全量抓取一下,显然不太方便,所以又改进了下增加了这样的功能

另外我试了下,这个抓取用户题解文章列表的接口是不做权限验证的,也就是说A用户可以抓取B用户的所有题解列表,我找了下使用场景,当A用户点开某个B用户的LeetCode个人主页的时候,下面有一块展示区域是防止当前B用户的题解列表的。这是一个正常使用的场景,也就是说,你可以抓取任何你喜欢的用户的所有题解列表

另外修改了一点样式。在右边单独建了小的Panel把按钮都放进去,到处分散的不大好看,

下一步内容,解析题目、题解中的图片标签,抓取图片内容并base64之后作为文本保存下来,使题解内容脱离对力扣图片资源的依赖

Continue reading

油猴脚本,抓取LeetCode题解[2]

接上篇,油猴脚本,抓取LeetCode题解,补充改版了下,顺便为啥要写这个呢?原因其实很简单,因为之前写了很多题解,都是直接在LeetCode上写的,加起来有快400篇了吧,然后自己这边博客每篇都要搬运一下,比较麻烦费事,所以才想着写了这么个工具。

这次改进做了如下

  1. 引入了IndexDBWrapper(https://www.npmjs.com/package/indexdbwrapper/v/1.0.4),封装了IndexDB的操作过程
  2. 直接任何力扣页面都可以操作了,账户需要登录
  3. 直接抓取我的题解了列表,之后根据列表再抓取题目和自己写的题解
  4. 使用了CustomEvent,抓取了列表之后,发起一个事件,页面同时监听事件,得到列表后进行抓取详细内容
  5. 定义了MY_ACCOUNT,需要手动替换为自己的账号ID
  6. 完成后点击下载按钮生成一个json文件下载
  7. 代码中对返回结果内容的字段进行了一些删除,删掉不需要的字段信息,缩小下载文件的大小

之后要做的事情,既然之前自己的写的题解已经拿到了,那么就是想办法再展示出来了,下一步可能想把下载得到的文件通过一个前端项目展示出来,不过这里还是有点问题,部分题解中含有图片内容,这个内容还是存在LeetCode服务器上的,这个还需要另外再想办法获取下来

Continue reading

油猴脚本,抓取LeetCode题解

用来抓取自己之前写的LeetCode刷题写的题解

// ==UserScript==
// @name         LeetCode Test
// @namespace    http://tampermonkey.net/
// @version      0.1
// @description  try to take over the world!
// @author       You
// @match        https://leetcode.cn/problems/*/solution/*
// @grant        none
// ==/UserScript==





(function() {
    'use strict';
    let createButton = (func, btnText, top) => {
        let btn = document.createElement("button")
        btn.style.position = "fixed"
        btn.style.right = 0
        // btn.style.top='30%'
        btn.style.top = top
        btn.style.padding = "10px"
        btn.style.zIndex = 99999
        btn.innerText = btnText
        btn.addEventListener("click", func)
        document.body.append(btn)
    }

    let dbName = 'solutionArticle', version = 1, storeName = 'mySolution'

    let indexedDB = window.indexedDB
    let db
    const request = indexedDB.open(dbName, version)
    request.onsuccess = function(event) {
        db = event.target.result // 数据库对象
        console.log('数据库打开成功')
    }

    request.onerror = function(event) {
        console.log('数据库打开报错')
    }

    request.onupgradeneeded = function(event) {
        // 数据库创建或升级的时候会触发
        console.log('onupgradeneeded')
        db = event.target.result // 数据库对象
        let objectStore
        if (!db.objectStoreNames.contains(storeName)) {
            objectStore = db.createObjectStore(storeName, { keyPath: 'questionFrontendId' }) // 创建表
            // objectStore.createIndex('name', 'name', { unique: true }) // 创建索引 可以让你搜索任意字段
        }
    }
    let saveToIndeDB = (data)=>{
        let request = db.transaction([storeName], 'readwrite') // 事务对象 指定表格名称和操作模式("只读"或"读写")
        .objectStore(storeName) // 仓库对象
        .add(data)

        request.onsuccess = function(event) {
            console.log('数据写入成功')
        }

        request.onerror = function(event) {
            console.log('数据写入失败')
            throw new Error(event.target.error)
        }
    }
    let cursorGetData = () =>{
        let list = []
        let store = db.transaction(storeName, 'readwrite') // 事务
        .objectStore(storeName) // 仓库对象
        let request = store.openCursor() // 指针对象
        return new Promise((resolve, reject) => {
            request.onsuccess = function(e) {
                let cursor = e.target.result
                if (cursor) {
                    // 必须要检查
                    list.push(cursor.value)
                    cursor.continue() // 遍历了存储对象中的所有内容
                } else {
                    resolve(list)
                }
            }
            request.onerror = function(e) {
                reject(e)
            }
        })
    }

    createButton( ()=>{
        cursorGetData().then(list=>{
            console.log(list)
        })
    } , "列表", "160px")




    let key = ''
    let addLocal = (k,v)=>{
        let oldJson = localStorage.getItem(key)
        if(null==oldJson){
            oldJson = {}
        }else{
            oldJson = JSON.parse(oldJson);
        }
        oldJson[k] = v;
        localStorage.setItem(key,JSON.stringify(oldJson))
    }
    let getQuestion = (slug)=>{
        let p = {
            "operationName":"questionData",
            "variables":{"titleSlug":slug},
            "query":"query questionData($titleSlug: String!) {\n  question(titleSlug: $titleSlug) {\n    questionId\n    questionFrontendId\n    categoryTitle\n    boundTopicId\n    title\n    titleSlug\n    content\n    translatedTitle\n    translatedContent\n    isPaidOnly\n    difficulty\n    likes\n    dislikes\n    isLiked\n    similarQuestions\n    contributors {\n      username\n      profileUrl\n      avatarUrl\n      __typename\n    }\n    langToValidPlayground\n    topicTags {\n      name\n      slug\n      translatedName\n      __typename\n    }\n    companyTagStats\n    codeSnippets {\n      lang\n      langSlug\n      code\n      __typename\n    }\n    stats\n    hints\n    solution {\n      id\n      canSeeDetail\n      __typename\n    }\n    status\n    sampleTestCase\n    metaData\n    judgerAvailable\n    judgeType\n    mysqlSchemas\n    enableRunCode\n    envInfo\n    book {\n      id\n      bookName\n      pressName\n      source\n      shortDescription\n      fullDescription\n      bookImgUrl\n      pressImgUrl\n      productUrl\n      __typename\n    }\n    isSubscribed\n    isDailyQuestion\n    dailyRecordStatus\n    editorType\n    ugcQuestionId\n    style\n    exampleTestcases\n    jsonExampleTestcases\n    __typename\n  }\n}\n"
        }
        let options = {
            method: 'POST',
            headers: {
                'Accept': 'application/json',
                'Content-Type': 'application/json'
            },
            body: JSON.stringify(p)
        }
        fetch("https://leetcode.cn/graphql/",options).then((res)=>{
            if(res.ok){
                //如果取数据成功
                res.json().then((data)=>{
                    //转化为json数据进行处理
                    console.log(data.data)
                    let question = data.data.question
                    addLocal('questionTitle',question.translatedTitle)
                    addLocal('questionFrontendId',question.questionFrontendId)
                    addLocal('questionFullTittle',"LeetCode刷题【"+question.questionFrontendId+"】"+question.translatedTitle)
                    let questionContentAppend = "<div>Related Topics</div><div><ul>"
                    let questionTags = [];
                    for(let tag of question.topicTags){
                        questionTags.push(tag.translatedName);
                        questionContentAppend += "<li>"+tag.translatedName+"</li>"
                    }
                    questionContentAppend += "</ul></div></div><br><div><li>👍 "+question.likes+"</li><li>👎 "+question.dislikes+"</li></div>"
                    addLocal('questionContent',question.translatedContent+questionContentAppend)
                    addLocal('questionTags',questionTags)
                    addLocal('questionTagsStr',"算法,LeetCode,"+questionTags.join(",")+",")
                    saveToIndeDB(JSON.parse(localStorage.getItem(key)))

                })
            }else{
                console.log(res.status);
                //查看获取状态
            }
        }).catch((res)=>{
            //输出一些错误信息
            console.log(res.status);
        })
    }
    let pathname = window.location.pathname
    let param = {
        "operationName":"solutionDetailArticle",
        "variables":{
            "slug":pathname.split("/")[4],
            "orderBy":"DEFAULT"
        },
        "query":"query solutionDetailArticle($slug: String!, $orderBy: SolutionArticleOrderBy!) {\n  solutionArticle(slug: $slug, orderBy: $orderBy) {\n    ...solutionArticle\n    content\n    question {\n      questionTitleSlug\n      __typename\n    }\n    position\n    next {\n      slug\n      title\n      __typename\n    }\n    prev {\n      slug\n      title\n      __typename\n    }\n    __typename\n  }\n}\n\nfragment solutionArticle on SolutionArticleNode {\n  rewardEnabled\n  canEditReward\n  uuid\n  title\n  slug\n  sunk\n  chargeType\n  status\n  identifier\n  canEdit\n  canSee\n  reactionType\n  reactionsV2 {\n    count\n    reactionType\n    __typename\n  }\n  tags {\n    name\n    nameTranslated\n    slug\n    tagType\n    __typename\n  }\n  createdAt\n  thumbnail\n  author {\n    username\n    profile {\n      userAvatar\n      userSlug\n      realName\n      __typename\n    }\n    __typename\n  }\n  summary\n  topic {\n    id\n    commentCount\n    viewCount\n    __typename\n  }\n  byLeetcode\n  isMyFavorite\n  isMostPopular\n  isEditorsPick\n  hitCount\n  videosInfo {\n    videoId\n    coverUrl\n    duration\n    __typename\n  }\n  __typename\n}\n"
    }
    let options = {
        method: 'POST',
        headers: {
            'Accept': 'application/json',
            'Content-Type': 'application/json'
        },
        body: JSON.stringify(param)
    }
    fetch("https://leetcode.cn/graphql/",options).then((res)=>{
        if(res.ok){
            //如果取数据成功
            res.json().then((data)=>{
                //转化为json数据进行处理
                //console.log(data);
                let {data:solutionArticle} = data
                let {solutionArticle:{author,content,question,title}} = solutionArticle
                if(author.username != "cheungq-6"){
                    return
                }
                console.log(solutionArticle)
                getQuestion(question.questionTitleSlug)
                key = '_____'+question.questionTitleSlug
                console.error("key:"+key)
                addLocal('title',title)
                addLocal('content',title+"\n"+content)
                addLocal('slug',question.questionTitleSlug)
            })
        }else{
            console.log(res.status);
            //查看获取状态
        }
    }).catch((res)=>{
        //输出一些错误信息
        console.log(res.status);
    })
    // Your code here...
})();

抓到的数据最终存到indexdDB中,中间存了下localStorage,后来改的存indexdDB,但是没删掉中间存localStorage的过程

动态规划入门(个人总结)

本篇其实是去年的时候在部门内部做的一次简单的分享的内容,也是对自己坚持学习了一个多月的动态规划内容的一些简单的总结和整理

从斐波那契数列到01背包问题

起始

在正式介绍动态规划之前,我们先从一个简单且不陌生的题目开始
斐波那契数列

首先我们来看下这个题目
斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由01开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1)&nbsp;= 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

这里我们题面已经明确的给出了实现的逻辑了,是的,就是一眼就能看出来的递归。

最基本的实现代码如下,非常的简单,也很好理解

class Solution {
    public int fib(int n) {
        if (n<2){
            return n;
        }
        return fib(n-1) + fib(n-2);
    }
}

但是,真的就这样结束了么?显然不是,首先我们能直观的看到这个是一个递归的过程,如果输入的n不是很大尚且还好,但是当你的n足够大的时候,比如20000?虽然这也不是非常大,那么会发生什么呢?

此时也许你会说,那我可以改jvm参数,增大可用栈深度,那你的栈深度又能增加到多少呢?200万?还是2000万? 我们不妨仔细分析一下这个过程

F(   n   ) = F(n - 1) + F(n - 2)
F( n - 1 ) = F(n - 2) + F(n - 3)
F( n - 2 ) = F(n - 5) + F(n - 4)
F( n - 3 ) = F(n - 4) + F(n - 5)

可以很容易的看出来,中间经历的大量的重复运算,思考一下,我们是不是有什么办法能把这个中间的大量的重复运算的过程省略过去呢?

这个时候你也许会想到哈希表,是的,这个方向是对的,不过在面对这种int的key的时候,我们一般有一种更加简单更加轻便的作法来实现哈希表的功能,那就是数组。我们可以声明一个int[]的数组来实现我们需要的功能,且其本身比Map型数据结构更加的轻便简单,相对的速度也更快

而且,这个过程中,我们不再是从F(N)F(0)求解,而是正向的从0N求解,那么代码如下

class Solution {
    public int fib(int n) {
        if (n<2){
            return n;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        int idx = 1;
        while (++idx <=n){
            dp[idx] = dp[idx-1] + dp[idx-2];
        }
        return dp[n];
    }
}

我们在算法中,给这样这种的数组一个独特的名字叫滚动数组,这样是不是就规避了最大栈深度的限制了呢?那我们入参给个Integer.MAX_VALUE看看会发生什么?内部的值相加是否会超出int型上限我们姑且先不论,直接入参给入跑一下看看

那么接下来我们要对这份代码再做一点优化,而数组长度上限的问题,你可以自己再思考下看看这个问题"java中数组的长度上限是多少"而又为什么会有这个上限。

拓展小知识:循环遍历和递归是可以相互转化的,最经典的例子莫过于二叉树的深度优先搜索(DFS)和广度优先搜索(BFS),一个是递归遍历,一个是循环遍历,这是另外一个不小的话题,这里不做展开讨论了

现在我们再次观察下这份代码,n位置的值,只和n-1n-2位置的值有关,那么我们就确实没有必要声明一个长度为n+1的数组,对此我们做一点点修改

Continue reading

LeetCode刷题【941】有效的山脉数组

给定一个整数数组 arr,如果它是有效的山脉数组就返回 true,否则返回 false

让我们回顾一下,如果 arr 满足下述条件,那么它是一个山脉数组:

  • arr.length >= 3
  • 在 0 < i < arr.length - 1 条件下,存在 i 使得:
    • arr[0] < arr[1] < ... arr[i-1] < arr[i]
    • arr[i] > arr[i+1] > ... > arr[arr.length - 1]

 

示例 1:

输入:arr = [2,1]
输出:false

示例 2:

输入:arr = [3,5,5]
输出:false

示例 3:

输入:arr = [0,3,2,1]
输出:true

 

提示:

  • 1 <= arr.length <= 104
  • 0 <= arr[i] <= 104
Related Topics
  • 数组

  • 👍 178
  • 👎 0
  • 双指针从两头往中间遍历
    双指针从两头往中间遍历
    最终判断两个指针是否在中间相遇,相遇点不能是左边界也不能是又边界

    代码

    class Solution {
        public boolean validMountainArray(int[] arr) {
            int l = 0;
            int r = arr.length-1;
            while (l<r && arr[l+1] > arr[l]){
                l++;
            }
            while (r>0 && arr[r-1] > arr[r]){
                r--;
            }
            return l==r && l!=0 && l != arr.length-1;
        }
    }

    LeetCode刷题【1518】换酒问题

    小区便利店正在促销,用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。

    如果喝掉了酒瓶中的酒,那么酒瓶就会变成空的。

    请你计算 最多 能喝到多少瓶酒。

     

    示例 1:

    输入:numBottles = 9, numExchange = 3
    输出:13
    解释:你可以用 3 个空酒瓶兑换 1 瓶酒。
    所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
    

    示例 2:

    输入:numBottles = 15, numExchange = 4
    输出:19
    解释:你可以用 4 个空酒瓶兑换 1 瓶酒。
    所以最多能喝到 15 + 3 + 1 = 19 瓶酒。
    

    示例 3:

    输入:numBottles = 5, numExchange = 5
    输出:6
    

    示例 4:

    输入:numBottles = 2, numExchange = 3
    输出:2
    

     

    提示:

    • 1 <= numBottles <= 100
    • 2 <= numExchange <= 100
    Related Topics
    • 数学
    • 模拟

  • 👍 140
  • 👎 0
  • 模拟,记得一次换不了的剩余空瓶可以攒着一起换
    没啥好说的,直接模拟,需要有一天个注意的地方,我们需要记录下没被换掉的剩余的空瓶

    可以几次攒下来不够换的空瓶,攒够了numExchange个后来换

    所以

    1. 初始我们买了numBottles瓶,喝了这么多之后就有这么多空瓶
    2. 第一次换酒剩余了left = numBottles%numExchange;瓶无法兑换
    3. 第一次换酒换到了numBottles /= numExchange;瓶,即喝到的瓶数增加了这么多
    4. 那么此时手中剩余空瓶数量为numBottles + left瓶空瓶,重新回到步骤1开始模拟

    代码

    class Solution {
        public int numWaterBottles(int numBottles, int numExchange) {
            int ans = numBottles;
            int left = 0;
            while (numBottles >= numExchange){
                left = numBottles%numExchange;
                numBottles /= numExchange;
                ans += numBottles;
                numBottles += left;
            }
            return ans;
        }
    }