2 csu_xiji

尚未进行身份认证

暂无相关简介

等级
TA的排名 6k+

力扣 523. 连续的子数组和 hash+dp

https://leetcode-cn.com/problems/continuous-subarray-sum/思路:hash+dphash+dphash+dp。搞一个hashhashhash表,dp[sum]=idp[sum]=idp[sum]=i,表示[0…i][0…i][0…i]的前缀和si%k=sums_i\%k=sumsi​%k=sum,初始可以令dp[0]=−1dp[0]=-1dp[0]=−1,然后遍历整个数组,记录前缀和sis_isi​,如果dp[si%k]dp[s_i\%k]dp[si

2020-05-13 01:38:36

力扣 155. 最小栈 栈+思维

https://leetcode-cn.com/problems/min-stack/思路:用两个栈,第一个栈s1s_1s1​正常做栈的操作,第二个栈s2s_2s2​维持一个单调非升的序列,从而保证最小值就在s2s_2s2​的栈顶,现在考虑怎么维护第二个栈,如果s2s_2s2​为空或者当前要压入的元素<=s2.top()<=s_2.top()<=s2​.top(),那么直接将其压到第二个栈内,否则不做任何操作即可。class MinStack {public: /** in

2020-05-13 00:05:30

力扣 145. 二叉树的后序遍历 非递归版

https://leetcode-cn.com/problems/binary-tree-postorder-traversal/思路:非递归版,这个思路对于前序遍历、中序遍历也适用。左右根,首先获得栈顶,然后判断栈顶是否为空,若不为空,则再次压入该节点,同时压入一个空指针,标记其前一位为根节点,然后压入它右节点、左节点;若栈顶为空,说明前一位也就是当前的栈顶为根节点,那么把它的值放进数组中即可。/** * Definition for a binary tree node. * struct T

2020-05-12 21:30:06

力扣 94. 二叉树的中序遍历 非递归版 栈

https://leetcode-cn.com/problems/binary-tree-inorder-traversal/思路:非递归版,中序遍历——左根右,也就是把左子树遍历完再输出当前节点的值,然后进入右子树,这是一个递归的过程。所以提示我们需要用到循环找到最左侧的节点,然后输出它的值,进入它的右子树再重复上述过程。/** * Definition for a binary tree node. * struct TreeNode { * int val; * Tree

2020-05-12 20:09:01

力扣 144. 二叉树的前序遍历 递归/非递归

https://leetcode-cn.com/problems/binary-tree-preorder-traversal/思路一:根左右,递归版随便写。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), rig

2020-05-12 19:37:26

洛谷 P1429 平面最近点对(加强版)分治/暴力+二分

https://www.luogu.com.cn/problem/P1429思路一:正经解法:分治。首先把nnn个点按照xxx排序,每次按照p[mid].xp[mid].xp[mid].x把点集分成两部分,solve(l,mid)、solve(mid+1,r)solve(l,mid)、solve(mid+1,r)solve(l,mid)、solve(mid+1,r)得到每一部分点对之间的最小值ansansans。那么总体最小值要么等于ansansans,要么等于左右两部分各选一个点组成的点对之间的距离。

2020-05-12 18:10:19

力扣 312. 戳气球 区间dp

https://leetcode-cn.com/problems/burst-balloons/思路:设dp[i][j]dp[i][j]dp[i][j]表示戳破区间[i,j][i,j][i,j]的所有气球所能获得的最大硬币数。为了方便处理,我们在数组开头和结尾各放入一个111,设数组原来有nnn个元素,显然答案为dp[1][n]dp[1][n]dp[1][n]。那么对于区间[i,j][i,j]...

2020-04-26 01:38:13

力扣 309. 最佳买卖股票时机含冷冻期 dp

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/思路:dp[i]dp[i]dp[i]表示第iii天最多能赚多少钱,很容易写出O(n2)O(n^2)O(n2)的dpdpdp。class Solution {public: int maxProfit(vector<int...

2020-04-26 00:04:11

力扣 279. 完全平方数 dp

https://leetcode-cn.com/problems/perfect-squares/思路:dpdpdp,列出n\sqrt nn​个完全平方数,问题就转化成了完全背包问题。class Solution {public: int numSquares(int n) { vector<int> dp(n+1,0x3f3f3f3f); ...

2020-04-25 21:46:45

力扣 76. 最小覆盖子串 滑动窗口

https://leetcode-cn.com/problems/minimum-window-substring/思路:滑动窗口,搞两个指针l=r=0l=r=0l=r=0,把rrr右移直到满足题意,然后再把lll右移直到不满足题意,这时记录一下最小值,重复这个过程即可。class Solution {public: int viss[256]; int vist[256]...

2020-04-25 21:31:44

网易游戏雷火2020春招游戏研发工程师笔试题0425 前三题题解

第一题大概题面:思路:dfs/bfsdfs/bfsdfs/bfs,直接计算答案呢不好算,我们考虑先设ans=6∗nans=6*nans=6∗n,然后把多算的面(内部的面)减掉,考虑一个立方体的坐标为(x,y,z)(x,y,z)(x,y,z),很容易得到与它相邻的666个面的坐标,如果这些坐标也有立方体,就减去相应的贡献即可,注意每次dfs/bfsdfs/bfsdfs/bfs的时候需要把一个连通...

2020-04-25 17:20:38

力扣 32. 最长有效括号 思维\栈

https://leetcode-cn.com/problems/longest-valid-parentheses/思路一:初始置cur=ct=0cur=ct=0cur=ct=0,如果遇到(((,就令cur、ctcur、ctcur、ct自增,否则令curcurcur自减,ctctct自增,那么当cur=0cur=0cur=0时说明当前子串匹配了,我们可以令ans=max(ans,ct)ans...

2020-04-25 00:25:26

力扣 44. 通配符匹配 dp

https://leetcode-cn.com/problems/wildcard-matching/思路:dp[i][j]dp[i][j]dp[i][j]表示aaa的前iii个字符和bbb的前jjj个字符能否匹配。那么答案就是dp[n][m]dp[n][m]dp[n][m],现在考虑怎么转移,因为两个字符串的下标都是从000开始的,所以要通过i−1、j−1i-1、j-1i−1、j−1的关系来...

2020-04-24 20:08:02

面试题35. 复杂链表的复制 哈希表/思维

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/思路一:借助哈希表,建立新旧节点之间的映射即可。/*// Definition for a Node.class Node {public: int val; Node* next; Node* random; Nod...

2020-04-24 18:06:32

力扣 645. 错误的集合 位运算

https://leetcode-cn.com/problems/set-mismatch/思路:做法很多,只考虑空间O(1)O(1)O(1)的方法。设答案为a、ba、ba、b,数组的异或和为sumsumsum,再对所有的1<=i<=n1<=i<=n1<=i<=n做一遍sum xor isum\ xor\ isum xor&nb...

2020-04-24 17:21:07

力扣 面试题56 - I. 数组中数字出现的次数 异或思维

https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/submissions/思路:如果某个数字出现了奇数次,其他数字出现了偶数次,那么将全员异或就可得到答案。但是这道题有两个数字都出现了奇数次,如果我们能把这两个数字分到两个不同的组内,然后对每个组单独求异或和,就可以得到答案了。怎么保证分组的...

2020-04-24 16:43:58

力扣 面试题07. 重建二叉树 递归分治/非递归版

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/思路:先序遍历:根左右。中序遍历:左根右。那么可以由先序遍历得到根节点的值,依据此值再找到根节点在中序遍历的位置,那么就可以分出左子树和右子树,分治下去即可。/** * Definition for a binary tree node. * struct TreeNo...

2020-04-24 16:18:43

力扣 面试题47. 礼物的最大价值 dp

https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/思路:dp[i][j]dp[i][j]dp[i][j]表示走到第iii行第jjj列所能获得的最大价值,显然有:dp[i][j]=max(dp[i][j−1],dp[i−1][j])+price[i][j]dp[i][j]=max(dp[i][j-1],dp[i-1][j]...

2020-04-24 14:28:47

力扣 面试题32 - I. 从上到下打印二叉树 bfs

https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/思路:bfsbfsbfs即可,每次处理一整个层次。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *l...

2020-04-24 14:16:48

力扣 面试题63. 股票的最大利润 贪心/dp

https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/思路一:贪心,因为只能买卖一次,所以只要知道[1…i][1…i][1…i]的最小值MiniMin_iMini​和[i…n][i…n][i…n]的最大值MaxiMax_iMaxi​,就可以更新ans=max(ans,Maxi−Mini)ans=max(ans,Max_i-...

2020-04-24 14:13:12

查看更多

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