月度归档: 2022年7月

油猴脚本,抓取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