华科不平凡 level
获赞
1857
粉丝
101
关注
29
看过 TA
244
男
华中科技大学
2021
C++
IP属地：未知
暂未填写个人简介
私信
关注
发布(141) 评论 刷题 收藏
2020-09-03 17:47
华中科技大学 C++
在转动过的有序数组中寻找目标值
对旋转数组进行均等划分后，总有一边是有序的，如：  10 11 12 13 14 15 1 2 3 10 11 15 1 2 3 4 5 6 7 8  我们定位到有序的一边后，对比target与有序子数组的左右边界，就可以作出搜索左侧还是右侧的决策。 代码如下：  第16行必须是<=，不能是<，举例——从[3,1]中查找1  // // Created by jt on 2020/9/3. // class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @param target int整型...
ypqhappy：做过几个类似的题目 感觉题目默认就是升序（只针对做题来说的话）
刷遍天下无敌手
0 点赞 评论 收藏
分享
2020-09-03 16:01
华中科技大学 C++
矩阵查找
本篇内容虽多，但有助于系统构建对二分查找的知识体系，如果您还不能闭着眼睛写二分的话，建议仔细看看哦～  二分查找是一个思路很简单、但实现起来有点恼人的算法。正所谓知己知彼，胜乃不怠；知天知地，胜乃不穷，我们先对二分法这个“敌人”做一个简单的分类：  按查找区间分类——闭区间[..]和左闭右开区间[..) 按具体任务分类——寻找特定值、寻找左侧边界和寻找右侧边界  寻找特定值 给定一个有序数组，如[1, 2, 5, 8, 9, 13, 19, 20, 68]，查找19的位置： int binarySearch(vector<int> array, int target) { int ...
so_what_xxxx：将操作抽象出来，岂不是更能很好的套用二分 private int[][] matrix=null; private int end; public boolean searchMatrix (int[][] matrix, int target) { // write code here if(matrix==null) return false; if(matrix.length==0) return false; this.matrix=matrix; this.end=matrix.length*matrix[0].length; if(this.end==1) { if(matrix[0][0]==target) { return true; }else { return false; } } return halfsearch(target,1,end); } public int lengthTox(int length) { return (length-1)/this.matrix[0].length; } public int lengthToy(int length) { return length-lengthTox(length)*this.matrix[0].length-1; } public int xyTolength(int x,int y) { return x*this.matrix[0].length+y+1; } public boolean halfsearch(int target,int left,int right) { //边界条件 if(target>this.matrix[lengthTox(right)][lengthToy(right)]||target<this.matrix>this.matrix[lengthTox(mid)][lengthToy(mid)]){ left=mid; } if(target</this.matrix>
刷遍天下无敌手
0 点赞 评论 收藏
分享
2020-09-03 11:04
华中科技大学 C++
最大子数组
两种方法——&nbsp;&nbsp;贪心思维，设arr[i]为以元素i结尾的子数组的最大和，那么arr[i]&nbsp;=&nbsp;max(arr[i-1]+nums[i],&nbsp;nums[i])，最大的arr[i]即是答案&nbsp;分治思维，思路很简单，最大子数组和要么存在于左侧区间，要么存在于右侧区间，要么存在于跨越左右侧的区间&nbsp;&nbsp;显然，贪心法的时间复杂度为O(n)，分治法的时间复杂度为O(nlogn)&nbsp;&nbsp;一直对“贪心”算法的概念比较模糊（或排斥），可能因为贪心这个词语不是那么正面吧，但这恰恰表明了贪心的核心：每一步都获取当前位置/状态下的最优值。联想到动态规划算法，不也是每一步都获取了当前的最优值吗？但贪心最后的解是每一步最优值中再取最...
刷遍天下无敌手
0 点赞 评论 收藏
分享
2020-09-03 09:39
华中科技大学 C++
0 点赞 评论 收藏
分享
2020-09-02 19:32
华中科技大学 C++
最大矩形区域面积
从这个问题想到单调栈结构确实有点不容易，我们举例说明：&nbsp;&nbsp;0&nbsp;0&nbsp;1&nbsp;1&nbsp;0&nbsp;1&nbsp;1&nbsp;0&nbsp;0&nbsp;1&nbsp;1&nbsp;1&nbsp;0&nbsp;1&nbsp;0&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;0&nbsp;1&nbsp;0&nbsp;0&nbsp;0&nbsp;0&nbsp;1&nbsp;1&nbsp;&nbsp;然后将每个元素转化为该元素及上面相连的1的个数和：&nbsp;&nbsp;0&nbsp;0&nbsp;1&nbsp;1&nbsp;0&nbsp;1&nbsp;1&nbsp;0&nbsp;0&nbsp;2&nbsp;2&nbsp;1&nbsp;0&nbsp;2&nbsp;0&nbsp;1&nbsp;3&nbsp;3&nbsp;2&nbsp;1&nbsp;0&nbsp;1&nbsp;0&nbsp;0&nbsp;0&nbsp;0&nbsp;2&nbsp;1&nbsp;&nbsp;以第3行为例，转化成柱形图，下图：&nbsp;&nbsp;&nbsp;是不是很熟悉呢？对的，其实这就是单调栈结构的一个典型应用，以求上面图片中最大矩形面积为例，单调栈的实现如下（建议作为单调栈题目的模版去记忆）：&nbsp;int&nbsp;monotoneStack(vector&lt;int&gt;&nbsp;&a...
刷遍天下无敌手
0 点赞 评论 收藏
分享
2020-09-02 11:53
华中科技大学 C++
杨辉三角（常数级别空间复杂度）
做这种模拟类型的算法题，有三个要诀：快、准、狠，缺一不可：&nbsp;&nbsp;快，时间控制在30分钟以内，这样才能预留充分时间给后面的题目&nbsp;准，找准边界条件&nbsp;狠，一旦有把握，毫不犹豫的动手写代码&nbsp;&nbsp;&nbsp;此类题目很重要的几个特性：🅐对称&nbsp;🅑旋转&nbsp;🅒重复...，利用这些特性可以大大减少代码量&nbsp;&nbsp;由于模拟类型题目变化多端，要做到快准狠实属不易，需要我们快速分析，快速找规律。以本题为例，当rowIndex=5时，数组为1&nbsp;5&nbsp;10&nbsp;10&nbsp;5&nbsp;1，我们用1初始化这个数组，再一步步得出结果：&nbsp;&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;边界为(0,&nbsp;0)&nbsp;中间节点为0&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;1&nbsp;边界为(0,&nbsp;1)&nbsp;中间节点为0&nbsp;1&nbsp;2&nbsp;...
刷遍天下无敌手
0 点赞 评论 收藏
分享
2020-09-01 18:21
华中科技大学 C++
最小覆盖子串
这道题目用到了滑动窗口这一大杀器，它可以解决如下问题：&nbsp;&nbsp;最小覆盖子串（LeetCode76）&nbsp;字符串排列（LeetCode567）&nbsp;统计字母异位词（LeetCode438）&nbsp;最长无重复子串（LeetCode3）&nbsp;&nbsp;滑动窗口的基本思想：&nbsp;&nbsp;用两个字典分别维护窗口中字符的统计数量、以及被求解子串中字符的统计数量&nbsp;用双指针遍历主字符串，双指针的初始值均为0，窗口的范围是[left,&nbsp;right)（左闭右开）&nbsp;遍历过程中，不断增大、缩小窗口，并更新状态&nbsp;&nbsp;下面是滑动窗口的基本模版(其中...需要根据题目要求进行修改)：&nbsp;void&nbsp;window(string&nbsp;s,&nbsp;string&nbsp;t)&nbsp;{&nbsp;unorde...
刷遍天下无敌手
0 点赞 评论 收藏
分享
2020-09-01 16:11
已编辑
华中科技大学 C++
0 点赞 评论 收藏
分享

创作者周榜

更多
关注他的用户也关注了：
牛客网
牛客企业服务