5 Shane Zhao

尚未进行身份认证

医学影像分析,计算机视觉

等级
TA的排名 9k+

leetcode139 单词拆分

给定一个非空字符串s和一个包含非空单词列表的字典wordDict,判定s是否可以被空格拆分为一个或多个在字典中出现的单词。说明:拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例1:输入:s=“leetcode”,wordDict=[“leet”,“code”]输出:true解释:返回true因为“leetcode”可以被拆分成...

2019-09-14 17:29:21

最长回文子串

dabadcmnm最长回文子串为dabad此题有多种解法,暴力法就是逐个子串来比较,记录最长子串,复杂度太高。动态规划当子串是回文子串时候,我们只需要看两遍新添的两个字符是否相等,若相等则最新串也是最长子串;若不等,则新串不是回文子串。这也是此题的状态转移方程。例如,aba是回文子串,当aba子串两端新添的两个字符相等时候,新串dabad也是回文子串。我们可以用一个二维数组dp记录所有的...

2019-08-30 17:14:53

House Robber

Youareaprofessionalrobberplanningtorobhousesalongastreet.Eachhousehasacertainamountofmoneystashed,theonlyconstraintstoppingyoufromrobbingeachofthemisthatadjacenthouse...

2019-08-28 14:34:02

Valid Sudoku

Determineifa9x9Sudokuboardisvalid.Onlythefilledcellsneedtobevalidatedaccordingtothefollowingrules:Eachrowmustcontainthedigits1-9withoutrepetition.Eachcolumnmustcontain...

2019-08-27 14:14:04

322. Coin Change

Youaregivencoinsofdifferentdenominationsandatotalamountofmoneyamount.Writeafunctiontocomputethefewestnumberofcoinsthatyouneedtomakeupthatamount.Ifthatamountofmoney...

2019-08-26 17:27:54

Dungeon Game

Thedemonshadcapturedtheprincess§andimprisonedherinthebottom-rightcornerofadungeon.ThedungeonconsistsofMxNroomslaidoutina2Dgrid.Ourvaliantknight(K)wasinitiallyposit...

2019-08-23 20:34:54

数组中超过一半的数

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。这个题目看到了首先会想到排序,然后统计个数。O(nlogn)了,不够快超过一半的数字肯定会是中位数,尝试快排的思想,找到中位数即可。这儿遇到一个坑,就是写partition函数的时候nu...

2019-08-21 10:50:25

链表反转+交叉链接

给个链表1->2->3->4->5->6把它变成1->6->2->5->3->4先把后半段链表反转,然后交叉链接前后半段链表即可#include<iostream>#include<iomanip>#include<vector>#include<algorithm>#...

2019-08-14 11:01:18

链表快排

快排的核心在于根据哨兵将节点二分,使用双指针分别从头和尾开始遍历即可完成。可是链表的访问时单向的,无法使用一个指针从后往前访问节点。换个思路来解,我们的目的还是要将数据二分嘛。还是用双指针,慢指针i指向头结点,快指针j从第二个节点开始遍历,一旦遇到节点值小于哨兵的key,那说明j指向的节点应该在哨兵前,这时候我们将慢指针后移一步,然后替换i和j的值。替换后保证了j的值大于...

2019-08-13 23:11:35

翻转单词序列

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student.aamI”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“Iamastudent.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?这道题用栈来解非常简单,坑在于牛客...

2019-08-08 17:36:11

八皇后问题

八皇后问题,太经典了。这儿记录一个回溯写法。回溯法适用于求解含有多个步骤的问题,且每个步骤都有多个选择,每次我们只选一个选择去求解,若达到解的条件则为一个解,若无解那么回到上一步换一个选择继续求解。八个皇后在水平竖直对角方向都不能共线,那这肯定作为求解过程中的限制。我们用一个数组记录每个皇后在对应行上的位置。假设棋盘有n格,每个皇后就有n个选择,每次选一个,然后判断该皇后在这儿会不会与已有皇...

2019-08-02 10:59:59

Longest Consecutive Sequence

Givenanunsortedarrayofintegers,findthelengthofthelongestconsecutiveelementssequence.YouralgorithmshouldruninO(n)complexity.Example:Input:[100,4,200,1,3,2]Output:4Explan...

2019-08-01 15:35:01

编码字符串,使得总长度最短

字符串“liulishuo”,我们需要对该字符串每个字符编码,使得编码后的字符串总长度最小。我们可以通过哈夫曼树来对字符编码,累积树中非叶子节点的和即为所求总长度。总长度也等于词频1字符长度1+词频2字符长度2+…/*liulishuo23对字符串编码,使得编码后的总长度最短;哈夫曼编码,总长度=字符长度1*频数1+字符长度2*频数2利用最小堆找最小元素*/intMinLe...

2019-08-01 11:49:24

Pow(x, n)

Implementpow(x,n),whichcalculatesxraisedtothepowern(xn).Example1:Input:2.00000,10Output:1024.00000Example2:Input:2.10000,3Output:9.26100该题简单的循环累乘会超时,时间复杂度O(n).不够快!可以用分治法将复杂度...

2019-08-01 11:01:27

Lowest Common Ancestor of a Binary Search Tree

Givenabinarysearchtree(BST),findthelowestcommonancestor(LCA)oftwogivennodesintheBST.AccordingtothedefinitionofLCAonWikipedia:“Thelowestcommonancestorisdefinedbetweent...

2019-07-29 00:06:07

Validate Binary Search Tree

Givenabinarytree,determineifitisavalidbinarysearchtree(BST).AssumeaBSTisdefinedasfollows:Theleftsubtreeofanodecontainsonlynodeswithkeyslessthanthenode’skey.Therig...

2019-07-28 21:11:58

二叉树非递归遍历方式

前序遍历:root,left,right用栈实现非递归遍历,访问root,将right先存栈,然后left再存栈vector<int>preorderTraversal(TreeNode*root){stack<TreeNode*>s;vector<int>res;if(!root)retu...

2019-07-26 17:54:21

3Sum

Givenanarraynumsofnintegers,arethereelementsa,b,cinnumssuchthata+b+c=0?Findalluniquetripletsinthearraywhichgivesthesumofzero.Note:Thesolutionsetmustnotcontai...

2019-07-25 19:39:50

Top K Frequent Elements

Givenanon-emptyarrayofintegers,returnthekmostfrequentelements.Example1:Input:nums=[1,1,1,2,2,3],k=2Output:[1,2]Example2:Input:nums=[1],k=1Output:[1]输出数组内最重复的k个数。emmm,...

2019-07-24 19:39:19

Sliding Window Maximum

Givenanarraynums,thereisaslidingwindowofsizekwhichismovingfromtheveryleftofthearraytotheveryright.Youcanonlyseetheknumbersinthewindow.Eachtimetheslidingwindowm...

2019-07-20 19:34:23

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。