13 王子力

尚未进行身份认证

我要认证

星星之火,可以燎原

等级
TA的排名 1w+

leetcode雕虫小技medium 5. Longest Palindromic Substring

题干:https://leetcode.com/problems/longest-palindromic-substring/分析:这题据说有个O(n)的解法,我自己写的O(n^2)的解法不是最优,但是毕竟能过OJ,所以这里就贴上来了,思路是, 分别考虑单数回文和双数回文的情况,从每个中心点开始尝试,向两侧扩张,扩张到回文极限即止, 返回各个中心点情况下的最长回文。代码:pack...

2020-05-07 16:49:03

leetcode雕虫小技medium 424. Longest Repeating Character Replacement

题干:https://leetcode.com/problems/longest-repeating-character-replacement/这题我感觉有点hard难度的味道。先说下思路,要你找修改后最长的连同字符串,这里面变数很多,首先,改哪些位置,第二这些位置改成啥,再然后改完后的连同子串长度是多少,全都是变数,感觉复杂超高。但是如果我们尝试减少一个变数,例如固定住...

2020-05-05 16:35:36

leetcode hard模式专杀 805. Split Array With Same Average

题干:https://leetcode.com/problems/split-array-with-same-average/先记输入数组A的平均值为 v这题别管它题目说得多么花里胡哨,本质上可以转化为,找一个子数组,让这个子数组的平均数等于v即可,可以证明,只要找到了这样一个子数组,那么另外一部分元素组成的子数组平均数也必然等于整体平均数。那么可以这样找:先找一个长度为1的子数...

2020-05-05 14:08:34

leetcode hard模式专杀1269. Number of Ways to Stay in the Same Place After Some Steps

题干:https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/前言:这题确实TMD有点难。我一开始尝试用动态规划,但是没找好状态转移方程,可能是直觉不太好,然后尝试用回溯法来做。之所以用回溯法,是因为我把每一步的决策看成三选一的决策动作,然后通过决策树的回溯遍历,自...

2020-05-04 23:44:50

leetcode雕虫小技mediu 456. 132 Pattern

题干:https://leetcode.com/problems/132-pattern/这题乍一看要找3个index,从暴力计算法的角度需要O(n^3),这种时间复杂度当然不是最优的。要想办法来降低。例如我们可以先找符合j,k约束的两个位置(暴力法的话时间复杂度为O(n^2)),然后再在j以前的序列中找比k还要小的,但是这种找是不是需要从0到j-1一个个去遍历呢?显然有一个...

2020-05-04 17:46:25

F*ck Leetcode medium 1090. Largest Values From Labels

题干:https://leetcode.com/problems/largest-values-from-labels/本体可以看成是背包问题的进阶版,目标类似,是让value最大化,不过有两个约束条件,一是选取综述不超过num_wanted, 二是选出的子集如果用label分组的话,每组的元素数量不超过use_limit。思路大概如下:先把value值分组,并对每组内元素从大到小排...

2020-05-03 23:10:16

leetcode雕虫小技mediu 684. Redundant Connection

题干:https://leetcode.com/problems/redundant-connection/这题地思路不难,就是在边中找环,取环中所有边中index最大者即可。问题是怎么找环呢?我的大体思路是从任意一个顶点开始尝试,使用回溯法,只要发现环路,立即停止并输出该环说是这么说,具体怎么做呢?亲自试了下写起来并没有那么容易。首先得收集一个数据结构,每个顶点对应...

2020-05-03 17:49:37

leetcode雕虫小技medium 641. Design Circular Deque

题干:https://leetcode.com/problems/design-circular-deque/这题跟622类似,算是它的进阶版,要支持双向的queue,大部分代码我都复用622的方案,纬度要注意的一点是deleteLast和deleteFront要注意边界条件,就是当删完之后队列为空时,不要移动currentHead或者currentTail指针位置。代码如下:...

2020-05-02 23:17:32

leetcode 雕虫小技medium 622. Design Circular Queue

题干:https://leetcode.com/problems/design-circular-queue/这题感觉蛮简单的,可能因为条件给得比较充分,约束多,变数小吧。思路就是建立一个整型数组,构造函数按照尺寸初始化之,然后保存两个下标指示变量,分别用于指示下一个将要插入的位置和当前队头index,每次deque或者enque都要更新这两个指示量中的一个。注意所谓circle用循...

2020-05-02 22:22:31

leetcode hard模式专杀214. Shortest Palindrome

题干:https://leetcode.com/problems/shortest-palindrome/虽说是hard模式,这题还真没给我什么hard的感觉。这种回文的问题,多在纸上画画比较利于分析,尤其是通过一种近乎几何直觉的方式会更有帮助。比如给一个字符串aacecaaa,让你左边添加一个字符,变成回文,啥叫回文?就是轴对称嘛,那么就意味着这个补齐的字符串如果是奇数长度,必然...

2020-05-02 21:50:43

leetcode hard模式专杀154. Find Minimum in Rotated Sorted Array II

题干:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/前面做了几题sorted array之后,万能pivot函数屡试不爽,但是我仍没想通这题为何是hard模式:我就直接贴代码了:package com.example.demo.leetcode;public class FindM...

2020-05-02 18:12:28

leetcode雕虫小技medium之 153. Find Minimum in Rotated Sorted Array

题干:https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/这题跟之前另一题解法几乎完全一样:https://leetcode.com/problems/search-in-rotated-sorted-array/只需要在返回结果上做点文章即可,不赘述代码贴一下:package com.ex...

2020-05-02 18:03:10

leetcode雕虫小技medium 81. Search in Rotated Sorted Array II

题干:https://leetcode.com/problems/search-in-rotated-sorted-array-ii/这题是上一题:https://leetcode.com/problems/search-in-rotated-sorted-array/的进阶版,所以看本文时最好先看过我上一篇帖子去掉了不重复的条件限制,不要小看这个条件约束,因为当有重复时,会发生...

2020-05-02 17:56:37

leetcode雕虫小技之medium 33. Search in Rotated Sorted Array

题干:https://leetcode.com/problems/search-in-rotated-sorted-array/这题要求搜索的时间复杂度在O(log(n)),很显然的一点是,如果做普通的排序数组的二分搜索,那么这个复杂度完全没问题,只不过现在有一点不同,就是那个pivot是从那个index开始的是unknown的,这是题干所强调的。假设这个pivot能在O(log(...

2020-05-02 17:15:28

leetcode雕虫小技medium 227. Basic Calculator II

题干:https://leetcode.com/problems/basic-calculator-ii/要实现一个简单的加减乘除计算器,假设输入都是合法的计算字符串,不带括号,只有数字,空格,和加减乘除四则运算符号。这题的思路其实本质上就是实现一个语法解析器,让程序从一个字符串知道你想要做什么运算即可。大家想想语法解析器(例如编译器)通常是咋做的,就是从左到右扫描,每扫...

2020-05-02 13:56:52

leetcode雕虫小技medium 450. Delete Node in a BST

题干:https://leetcode.com/problems/delete-node-in-a-bst/这题基本上没什么难度,只要记住一个原则即可,删某节点,调整的原则是将该节点同左子树的最大节点交换,或者同右子树的最小节点交换,才能维持BST属性,并且,如果这个左子树的最大节点不是叶子节点,或者右子树的最小节点不是叶子节点,则这个操作还需要递归地做下去。另外注意一个小t...

2020-05-01 20:51:01

leetcode雕虫小技之60. Permutation Sequence

题干:https://leetcode.com/problems/permutation-sequence/要求1~n(1<=n<=9)的数字的全排列序列,中的第k个字符串。毕竟不是Hard模式,思路还是比较快粗来的,我的思路还是逐层降级法,就是先先确定第一个数字选啥,再确定第二个数字选啥,逐层推下去,直到所有位都选定。产生这个思路的原因是,理论上这题的 暴力解法是把全...

2020-05-01 18:11:35

leetcode hard模式专杀685. Redundant Connection II

https://leetcode.com/problems/redundant-connection-ii/这题做下来总觉得不够hard模式,因为其主要逻辑几乎就在一些简单的几何关系中。画了下图,自己总结了一下所谓多连一条有向边会导致哪些情况。粗略分为两类:1,指向的那个节点是自己的直系祖先,这样会构成环2, 指向的那个节点不是自己的直系祖先,这样会造成简单的“双父”的问题...

2020-05-01 16:31:45

leetcode hard模式专杀440. K-th Smallest in Lexicographical Order

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/这题乍一看有点吓人,主要因为数字的自然顺序和字典顺序之间没有什么非常简单的映射规则,但可以想到的是字典序这个东西在10以内的数字是有一定规律的,例如0,1,2,3,4,5,6,7,8,9既符合数字的自然顺序,又符合字典序,只是每当发生进位时会发生一些变...

2020-05-01 14:18:20

leetcode hard模式专杀87. Scramble String

原题:https://leetcode.com/problems/scramble-string/这题是标准动态规划吧,思路基本上一分钟出来,不过oj提了几次,都是要么边界index写错了,要么时间复杂度超时了,超时问题用memtable解决,边界index问题注意写代码的逻辑即可。思路,划分子问题,划分方法很直观,就是让字符串越划越短即可,短到只有1长度或者2长度,就可以直接...

2020-04-27 19:20:31

查看更多

勋章 我的勋章
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享王者
    分享王者
    成功上传51个资源即可获取