题目:思路:请见三数之和点击打开链接因为是求四个数字之和,所以将i作为第一个数字,其他剩下的三个索引分别为left,mid,right,然后在i的遍历数组的时候,剩下的操作思路和三数之和是一样的。其中需要注意的是,因为求的是四个数字的和,所以left,mid,right分别就已经占用了三个数,所以i只能遍历到 nums.size()-3的前一个下标处。同理,在left遍历的时候,只能遍历到nums.size()-2的位置(因为剩下的两个位置要留给mid,right)。此时还是比较nums[mid]+nums[right]和tem的数值,那么tem的数值根据:nums[left]+nums[mid]+nums[right]+nums[i]=target来推导出,其中nums[right]+nums[mid]=target-nums[left]-nums[i].所以可以推出tem = target-nums[left]-nums[i]。然后再根据大小,来移动mid,right就可以了。代码:class So 继续阅读 >>


胡佳露 18/07/13 00:10:42
题目:思路:在三数字之和的解题思路上,将所有的三数字之和遍历,然后进行更新最小值即可。其中需要注意的是所给的target减去三数字之和的话可能会为负数,所以要将负数值处理为正数,然后看哪三个数字之和最接近target值。其中若三数字之和大于了target值的话需要将right向升序数组的前方移动,小于的话需要将mid数值往升序数组后移动。三数之和解题思路点击打开链接。代码:class Solution { public: void sort(vector<int>& nums) { int temp = 0; int len = nums.size(); for(int i=0; i<len; i++) { for(int j=i+1; j<len; j++) { if(nums[i] > nums[j]) 继续阅读 >>


胡佳露 18/07/11 13:08:34
题目:思路:题目要求三数之和为零,即:a+b+c=0; 那么若满足b+c = -a的话就满足题目的第一个要求啦。假设-a = tem 那么 b+c=tem就说明满足条件。这样的话三数之和变成了两数之和,再两个数字和的基础上,只需要找到一个tem为定点以后,然后再判断数组中剩下的数字两两相加是否等于tem即可。若用暴力求解的话会超出时间限制。此时,假设该数组是一个有序数组(升序)的话,那么我们可以知道,从左到右数字时依次增加的。此时设置索引left,mid,right,然后以最左边的点为定点(tem),只需要看nums[mid]+nums[right]+nums[left]?=0即:nums[mid]+nums[right]=-nums[left] ---> nums[mid]+nums[right]=tem。而且题目中要求不能重复,那么当nums[left]判断后,需要判断之前的nums[left-1]和现在的nums[left]是否是相同的数字,若是的话,left继续往后移动,直到移动到不同的数 继续阅读 >>


胡佳露 18/07/10 15:12:14
题目:预备知识:(1)正则表达式的概念是对字符串操作的逻辑公式,是事前定义好的一些特定的字符以及特定字符的组合。这里题目中的p就是正则表达式(字符模式)要判断s是否满足p的字符模式。正则表达式是描述了一种字符串匹配的模式,用来检查一个串中是否含有某种模式的子串,或者将匹配的子串替代又或者从里面取出符合某种模式的子串。所以并不是简单的看是否是子串的问题,例如:s="aaa" p="aaaaa"和s="aaa" p="aaaab"就不匹配,若p中没有特殊字符'*' 和 '.',只有当s="XX" p="XX"时候才匹配。(2)关于特殊字符就是有某些特殊含义或者限制的字符,而且每个特殊字符都有自己的描述。比如题目中的限定字符*表示匹配前面的字符0次或者多次,而且根据题目的描述*前面是需要跟着一个字符或者跟在‘.’后面,假设ab*,那么可以改表达式可以匹配a,b,ab,abbb,abbb(重复b).... 所以其中的b*可以看成是0也可以看出是n个b。但是假如abc*的时候,a,b均不匹配,此时匹配的字符串可以 继续阅读 >>


胡佳露 18/07/04 15:47:54
一、题目描述二、思路(1)可以将该整数转换成字符串,根据字符串的长度奇偶性来确定中间位置,然后首尾进行对比是否是回文数字。此时需要额外空间来存储字符串,然后进行判断(2)可以将整数的最后一半数字进行整数反转,然后将反转的部分与数字的前部分进行比较,判断是否是回文数。也可以将整个整数进行反转然后进行比较,但是会发生溢出情况,所以可以选择只反转数字的后半部分,若与前半部分相同则为回文数。我选择的方案是只对后半部分的数字进行反转,但是反转的停止点是反转的数字是否反转了一半的判断。根据题目中的描述,若该整数是一个负数那么肯定不是回文数,或者该整数的最后一位为0而第一位不为0也不可能是回文数,所以可以直接将这两种情况判断返回false。此时剩下的普通情况的话,此处分为两种情况,若假设该数字是一个回文数,若是回文数的话,长度又分为奇数和偶数。若该整数长度为奇数的话那么反转一半的标志就是反转的数字与目前剩下的前面的那部分数字相同了,此时应停止反转;若该回文整数长度为偶数的话,我们将中间的那个元素归在反转数字中(例如: 继续阅读 >>


胡佳露 18/07/03 14:02:50
一、整数反转题目:给定一个 32 位有符号整数,将整数中的数字进行反转。示例1:输入:123输出:321示例2:输入:-123输出:-321示例3:输入:120输出:21注意:假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231,  231 − 1]。根据这个假设,如果反转后的整数溢出,则返回 0。思路:弹出(栈)和压入(队列)但是根据题目的要求,我们要在溢出前进行检查。所以弹出每个元素,并且入队列后,要进行检查是否会溢出,就是该元素入队列后会不会发生溢出。因为是整数的反转,所以要首先分离出每个元素。通过x%10的数学方法就可以取出最后的一个元素。此时将(x%10)*10进行累加,但是在这之前要判断之前累加的值是否超过了数值范围。假设之前的累加为rev是否大于INT_MAX/10或是否小于INT_MIN/10 还有一种情况就是之前的rev==INT_MAX rex==INT_MIN了,此时要判断目前拿出来的那个数字是否大于7或者是否小于-8 若大于或者小于都会发生溢出。代码:class 继续阅读 >>


胡佳露 18/07/02 18:14:37
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。示例:babad输出:bab(注意aba也是有效答案)思路:1、可以枚举出所有的子串,然后每次都判断该子串是否是回文,若是回文便更新最大长度,并且记录子串的开始位置和结束位置。2、可以从第一个字符为中心向两边检查,若以k为中心 ,那么i往K的左边检测,j往右边检测。若s[i]==s[j]那么说明从i-j的子串为回文,接下来只需要判断s[i-1],s[j+1]是否相同,若相同则也是子串,并更新长度,并更新最长子串的开始位置和结束位置,直到当条件不满足s[i]==s[j]的时候,将中心点k往后移动。方法一(暴力求解)class Solution { public: bool judge(string &s, int star, int end)//判断子串是否是回文,分为奇偶两种情况 { int median; int length = end-star;; 继续阅读 >>


胡佳露 18/06/22 19:44:46
也是看了一篇很好的博客,思路很清晰,只是有些地方感觉博主没有详细解释,后来理解了,做了一个小总结。原博客链接:点击打开链接题目还是昨天的那道题目:给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。示例 1:nums1[1,3]nums2[2]中位数:2.0示例 2:nums1[1,2]nums2[2,3]中位数:(2+2)/2=2.0其中要求算法时间复杂度,也可以利用分治法来解决。此时的分治法,需要将两个有序数组合并看作一个新的数组。然后进行分割。思路总结(具体思路原创博主更为详细,可以参照):1、因为是两个有序数组,所以需要两个割点C1,C2。若将两个数组(都是升序排序的数组)分别在一个割点处分为两半,那么L1(数组前半部分的最右边的元素)一定是小于R1(数组后半部分最左边的元素),同理L2<R2。 因为要找两个有序数组的中位数(为了方便奇偶性的区分,我们将两个数组分别虚拟设置为奇数,所以两个数 继续阅读 >>


胡佳露 18/06/20 22:47:58
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。示例 1:nums1[1,3]nums2[2]中位数:2.0示例 2:nums1[1,2]nums2[2,3]中位数:(2+2)/2=2.0思路:因为是两个已经有序的数组,要求中位数,只需要将两个数组合并成一个有序数组,然后根据数组元素个数的奇偶性,分开来便可以求出中位数,若最后合并成功的数组名为K的话,(偶数的话中位数=K[(N/2)]+K[(N/2-1)]/2)(奇数的话中位数=K[(N/2)])。并且题目要求时间复杂度为O(log(M+N)),所以在排序的时候,要考虑时间复杂度。代码实现(c++):class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 继续阅读 >>


胡佳露 18/06/19 15:44:30
题目:给定一个字符串,找出不含有重复字符的最长子串的长度。示例:给定 "abcabcbb" ,没有重复字符的最长子串是 "abc" ,那么长度就是3。给定 "bbbbb" ,最长的子串就是 "b" ,长度是1。给定 "pwwkew" ,最长子串是 "wke" ,长度是3。请注意答案必须是一个子串,"pwke" 是 子序列  而不是子串。暴力解决方法:首先枚举出所有的子串,用star记录子串的起始点,end记录子串的末尾。枚举出所有的子串之后,开始检查子串中是否存在重复的字符,若存在则该子串不符合要求,若该子串中不存在重复的字符,那么将该子串的长度与之前的最大长度相比,若比最大长度还长,那么更新最大长度的值。最后返回最长长度。要点:(1)枚举出所有的子串 (2)要求该子串中没有重复的字符,若存在重复的字符则不符合题目要求(3)更新不重复子串中的长度代码实现(c语言)/*更新最长长度*/ int Max(int a, int b) { int max=0; return max = a> 继续阅读 >>


胡佳露 18/06/15 16:05:34