Sitch's Blog
0%

发表于 分类于 Valine：

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题思路

　这题也是思路比较直接的一题,分析以下几点需求:

  1. 判断重复字符 用int构造一个hash表进行判断即可,注意字符总数,数组空间可以开大一点 (数组初始化的时候没有想到更好的优化效率方案).

  2. 子串检测 数据结构课上有学过kmp算法,因此容易联想到这里为了最佳效率,也应采用窗口移动的算法.

  3. 后事处理 移动窗口之后,由于窗口之外的字符的位置信息还保留在表内,因此需要进行处理 直接思路是使用一个滞后的位置符behind进行遍历清除即可 优化思路: 可以通过判断滞留的位置是否处于现有检测窗口之前,如果是则无视,不需要遍历处理,空间换时间

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {   
        int flag[127];
        for(int i=0;i<127;i++)
            flag[i]=-1;
        int result=0;  
        int max=0;
        int temp=0;
        int start=0;
        
        for(int i=0;i<s.length();i++)
        {
            temp=getNO(s[i]);
            if(flag[temp]<start)
            {
                result++;
                flag[temp]=i;
            }
            else
            {
                if(result=max)
                    max=result;
                
                start=flag[temp]+1;
                result=i-flag[temp];
                flag[temp]=i;
            }
        
        }
        if(result=max)
            return result;
        else
            return max;
    }

    int getNO(char originchar)
    {
        return originchar-' ';
    }
};

发表于 分类于 Valine：

下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

思路分析

①是否存在更大的排列

更大的排列

考虑最大的字典序排列: 降序排列 [1,2,3] → [3,2,1] 对于 [3,2,1] 序列,已经是最大字典序了

假如序列存在一个更大的排列,那它必然不是降序排列 因此判断是否存在下一个排列的条件就是 顺序遍历数组,判断是否完全降序

②找到下一个排列

首先对于[1,2,3,4,5,6],假如我们要人工找到下一个排列,我们知道要把倒数两位调换一下[1,2,3,4,6,5],这样值的变动最小,字典序大小变动也最小.

为什么最后两位调换之后字典序会变大呢?

我们可以发现一个本质: 它们是升序的, 升序排列那么必然就存在可以调换成降序的操作空间,因此可以改动升序关系的任意两位来获取一个更大的字典序 如 [1,2,5,4,3,6]

知道了获得更大序的方法,接下来我们要确定什么操作能得到最小的更大序(下一个更大的序列)

其实字典序类似于数的大小关系. 比如[1,2,3] → [2,1,3][1.3.2]

所以为了找到最小的更大序列,我们操作的升序数对要尽可能的小.所以目标就变成了:

找到最靠后的一对升序数对

[9,8,3,6,5,4]→[9,8,4,3,5,6] 最靠后的/最小的 升序数对是 [3,4],初步调换后是[9,8,4,6,5,3] 显然这个结果还不太对.

找到了最小的升序数对只是保证了在一步操作的范围内,我们增加的值是最小的. 换句话说,其实再多加几步操作才能保证是下一个序列. 来看看我们还差些什么 [9,8,4,6,5,3] →[9,8,4,3,5,6] , 4的后面原本是降序,被整理成了升序

首先在我们的算法里,我们从后往前找一个升序的"峰值" 换句话说,我们在找到""峰值""之前,也即从末尾到"峰值"",必然是降序的,也就是局部最大的序列. 因此我们调换了一对最小的升序对,整个序列在""峰值""之前已经是最小的了, 但在调换位置之后的局部仍然是降序,即现在的序是前半段最小+后半段最大, 因此将""峰值""往后调整成升序,即后半段最小即可构成"最小+最小"的下一个排列.

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public:
    void nextPermutation(vector<int& nums) 
    {
        if(nums.size()<=1)
            return ;
        
        int flag=0;
        int nextid=nums.size()-1;
        int currentid=nextid-1;
        
        while(currentid=0)
        {
            if(nums[nextid]nums[currentid])
            {   
                //从后往前，找到第一组 升序对
               flag=1;
                break;
            }
            
            nextid--;
            currentid--;
        }
        
        if(flag==1)//存在下一个更大排列
        {
                //交换生成新排列
            while(nextid+1<nums.size())
            {
                if(nums[nextid+1]nums[currentid] )
                    nextid++;
                else
                    break;
            }
            tempswap(nums[currentid],nums[nextid]);
            //currentid右边必然是降序
            //将currentid右边升序处理
            nextid=nums.size()-1;
            while(currentid+1<nextid)
            {
                tempswap(nums[nextid],nums[currentid+1]);
                nextid--;
                currentid++;
            }
        }   
        else
        {   //不存在，则倒序
            nextid=nums.size()-1;
            currentid=0;
            while(currentid<nextid)
            {
                tempswap(nums[nextid],nums[currentid]);
                nextid--;
                currentid++;
            }
            
        }
        
        return ;
        
        
        
    }
    
    void tempswap(int& a,int& b)
    {
        int temp=b;
            b=a;
            a=temp;
    }
};

发表于 分类于 Valine：

最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()"

思路分析

错误思路规避

刚看到括号对, 第一反应就是栈操作的括号匹配, 认为只要匹配到匹配失败的时候记录这条括号串的长度, 在遍历完整个串之后, 通过最大值筛选就获得了最长有效括号长度. 然而事实证明困难题没有那么憨憨 对于"( ) ( ( )"显然简单的匹配栈会把这个长度定为4,实际上只有2 ##### 问题出在哪呢? ( ) ((((((((( ( ) 在两个正常括号中间的压栈操作不会终止长度的累积 当然也不能粗暴的终止,毕竟也有( ) ( ( ( ( ) ) ) ) ) 的情况

改良方法

参考了题解大神的思路之后, 明白了单纯压char型 ' ( '入栈是一种很憨憨的行为...... 同样是压栈匹配, 人家压的下标.....消耗一样,却额外带来了位置信息

匹配时括号对会产生一个位置差, 而对于这个差内部肯定是合法的括号串. ( ~~~~~~~) 假如是非法串, 要么是 ( 多了,那匹配时会匹配内部多的 ( ,而不是外部那个. 要么是 ) 多了, 那肯定已经把栈清空了, 外围也不会有匹配括号.

每次匹配成功会通过位置差得到一个当前长度信息length=i-stack.top() 注意这里的top是已经匹配pop出一个( 之后,再取的top,此时的top为目前合法字符串的开始位置的前一个 假如top和pop为同一个,对于 ((())) 的嵌套形式是没问题的, 但对于连串形式如: 例如 ( ( ) ( ) ( ) ( ) ( ) ) ) string[9]和string[10]匹配了,目前合法长度肯定不是10-9=1...实际上是10-0=10

也因为这个i-top的方法,我们需要在最开始的栈底压入一个-1, 代表字符串开头 针对 ( ) ( ) ( ) 的情况, 最后一个右括号pop完, 不压入一个-1你让人家减谁去算长度....

顺带一提原方法错误的案例 再看( ) ( ( ), 原方法因为是只要不匹配失败, 每过一位都会长度++,因此产生错误结果 4 而利用位置信息差算长度的方法, 只会算出两个长度为2 的括号对 ,最大也就是2.

题解代码

算法比较简单, 但分析细节还是比较令人舒适的~ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int longestValidParentheses(string s) 
    {   
        int result=0;
        int i=0;
        stack<int left;
        left.push(-1);//压入字符串头，以防（）（）（）（）情况

        while(i<s.size())
        {
            if(s[i]=='(')   //左括号 下标 入栈
                left.push(i);
            else    //右括号消除一个左括号，并用下标差计算长度
            {
                left.pop();
                if(left.empty()!=true)
                {
                    if(i-left.top()result)
                        result=i-left.top();  
                }
                else
                    left.push(i);
                  
            }

            i++;
        }

        return result;
    }
};

发表于 分类于 Valine：

寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0

示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5

思路分析

首先, 题目有 log 时间复杂度限制，不能重组数组暴力解决

已知, 两数组有序不为空，找到中位数的难点在于怎么把两个数组的数一起考虑

目标, 中位数定义：将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。所以我们其实是找一个方法，把两个数组同时划分成两块，左边块的所有数都比右边块的所有数要小。 若分割后左边有 k 个数，此时划分的边界有 LMax1,LMax2,RMin1,RMin2：

  • Max(LMax1,LMax2) 必然是第 k 个数
  • Min(RMin1,RMin2) 必然是第 k+1 个数

即我们可以定位到第 k 个数，中位数的序号 k 也可通过数组长度得到。因此，我们需要：

两个数组同时分割成有大小关系的两块，左块总共有 k 个数，k 为中位数序号，此时中位数要么是第 k 个，要么是第 k 个和第 k+1 个，都可以在边界找到

题解分析 （链接原高赞题解）

分割主体思路

要把两数组同时分割成两块，先看单一数组的内部。因为数组是有序的，所以假如在中间一割，同一数组的左边肯定小于右边。

为了达到我们两个数组整体分割的目标，我们还需要满足对一个数组都有，分割的左边最大值小于另一个数组的右边最小值，这样左边的整体必然就会小于右边的整体。

另外注意切割后要满足左大块总共有 k 个数。

题解示意图，来自 LeetCode 扁扁熊

边界数赋值

假如分割点恰巧在有数的位置 C, 为方便比较大小，LMax=RMin=L[C], 即中位数同时分给两边。

假如分割点在两数之间，即 LMax 和 RMin 即分属两边。

假想放大数组

因为无法用整数下标表示描述在两数之间的位置，但实际存在这种分割情况。 所以我们不妨将每个数组放缩成 2m+1 的长度, 即给两数之间也加入一个标识位置。 例如 [1,2,3] 假想放缩成 [# ,1,#,2,#,3,#],

此时：数的实际位置=假想位置/2， 两数之间的假想位置=数的假想位置+-1。

设放大后对一个数组切割的假想下标（虚位）为 C。 此时无论 C 是数的虚位还是空的虚位, 都满足 LMax=L[(C-1)/2] RMin=L[C/2], 注意放缩产生的虚位是假想的，因此访问时要转换回实位

例如对于 [# ,1,#,2,#,3,#] 2 的原下标是 1, 假想下标是 3, 3/2=1 若此时以，C=3 为切割位置，即切在点上，则 LMax=L[(C-1)/2]=L[1]=2,RMin=L[C/2]=L[1]=2 若以 C=4 为分割处，即切在空上，LMax=L[1]=2,RMin=L[2]=3.

放大数组后，切点切空都可以用同一个式子正确给 LMax 和 RMin 赋值

左块确保有 k 个数

因为放大后数组总长度是 2m+2n+2，所以中位数在是 第 m+n+1 数和第 m+n+2 数相加的平均值。

因此有 k=m+n+1，且 C2=m+n-C1。

真实数组序号从 0 开始，所以 C1+C2=k-1, 左块才有 k 个数，不是 C1+C2=m+n+1。

切割终止条件

好，现在我们随便怎么切，都能确保左边是 k 个数。但是注意为了维护左块所有数一定小于右块所有数，我们需要有LMax<=RMin

处理边界情况

切割时切割点可能在数组最左边或者最右边，此时直观上理解可知，切最左边的时候，LMax=无穷小，切最右边的时候 RMin=无穷大

切割点遍历方式

切割点选择方式确定后，我们要逐步逼近正确的切割点 类似于查找算法，此时可用二分法进行逼近，满足效率 O(log).

最终代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# include <vector        //注意头文件的加入，否则 INT_MIN 之类的可能无法使用
# include <stdio.h
using namespace std;

class Solution {
public:
    double findMedianSortedArrays(vector<int& nums1, vector<int& nums2) 
    {  
        int length1=nums1.size();
        int length2=nums2.size();
        if(length1length2)        //节省效率，以最短的数组为主切割 C1
            return findMedianSortedArrays(nums2,nums1);
        int LMax1;
        int LMax2;
        int RMin1;
        int RMin2;
      
        int k=length1+length2;
        int c1;
        int c2;//切割点
        int lo=0;//二分逼近变量
        int hi=length1*2;
        
        //二分确定切割点
        while(lo<=hi)  //写 LMax1RMin2 || LMax2RMin1 为什么不可以
        {
            //计算切割点，保持了左边都是 k 个数
            c1=(lo+hi)/2;
            c2=k-c1;
            
            //计算四个边界值
           (c1==0) ? LMax1=INT_MIN : LMax1=nums1[(c1-1)/2];
            (c1==2*length1) ? RMin1=INT_MAX : RMin1=nums1[c1/2];
             (c2==0) ? LMax2=INT_MIN : LMax2=nums2[(c2-1)/2];
            (c2==2*length2) ? RMin2=INT_MAX : RMin2=nums2[c2/2];
            

            if(LMax1RMin2)//左上大于右下，左下显然小于右下，切多了，hi 降低
                hi=c1-1;          
            else if(LMax2RMin1)//左下大于右上，左上显然小于右上，少了。lo 升高
                lo=c1+1;
            else       //左上小于右上右下，左下小于右上右下，目标条件。
                break;
            
        }
        
        int LMax,RMin;
        LMax=(LMax1LMax2)?LMax1:LMax2;
        RMin=(RMin1<RMin2)?RMin1:RMin2;
        
        return (LMax+RMin)/2.0;
        
    }
};

这个题目细节比较复杂，代码相对来说挺清晰简洁。

发表于 分类于 Valine：

字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

输入: num1 = "2", num2 = "3" 输出: "6"

示例 2:

输入: num1 = "123", num2 = "456" 输出: "56088"

说明：

num1 和 num2 的长度小于110。 num1 和 num2 只包含数字 0-9。 num1 和 num2 均不以零开头，除非是数字 0 本身。 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

题目分析

//1 2 3 num1 //4 5 6 num2 //7 3 8+6 1 5 * 10+..... reverseresult

1. 竖式暴力模拟

因为现实竖式乘法是从右到左落位, 程序从左到右方便一些,所以运算过程中是反向存储的乘法结果,最后需要翻转.

当然这个可以优化

1.1 整数相乘直接思维是按竖式相乘, 显而易见两次循环,外层num2,内层num1

1.2 对num2的最后一位,乘num1一遍,currentresult保存这遍的结果

1.3 result累加上currentresult, (加法也有点麻烦, 还得写个加法函数

1.4 因为最后一位乘过了就没用了,num2.pop_back()

1.5 注意乘完一个数, 下一个currentresult要向左移一位,即X10尾部添0, 而我们又是反向存储,所以需要在currentresult头部加i个"0", i=pop次数

1.6 num2所有数都用过了即num2="",结束循环

1.7 考虑一些收尾工作,进位有没有多, 要不要连续进位

1.8 将累加结果result反转, 得到真实结果

可以看到暴力法虽然思路直接,但是需要处理的东西也不少,而且时间空间效率都不理想, 权当一个编码锻炼.

暴力代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Solution {
public:
 string multiply(string num1, string num2)
 {
  if (num1 == "0" || num2 == "0")
   return "0";

  string result;
  string tempresult;
  string zerostring;
  int i;
  int cflag = 0;
  while (num2 != "")//num1对num2每个数逐个相乘,每次result=result+currentresult*10
  {
   for (i = num1.size() - 1; i = 0; i--)
   {
    tempresult.push_back('0' + ((num1[i] - '0')*(num2.back() - '0') + cflag) % 10);
    cflag = ((num1[i] - '0')*(num2.back() - '0') + cflag) / 10;
   }
   //乘到最后一个数还剩下cflag
   if (cflag  0)
    tempresult.push_back('0' + cflag);
   //用零串移位
   tempresult = zerostring + tempresult;
   //相加上下两个字符串
   ADDstring(result, tempresult);
   //乘完num2的一个数num2把用过的数pop
   num2.pop_back();
   //临时数据清空
   tempresult.clear();
   zerostring += "0";
   cflag = 0;
  }
  //1 2 3
  //4 5 6
  //7 3 8+6 1 5 * 10
  string reverseresult;
  for (int j = result.size() - 1; j = 0; j--)
   reverseresult.push_back(result[j]);
  return reverseresult;
 }

 void ADDstring(string& up, string& down)//up和down字符串数值相加,结果存在up里,仅适用倒序存储
 {
  int j = 0;
  int cflag = 0;
  int temp = 0;
  //result接在up上面
  while (j < down.size())
  {
   if (j < up.size())//up[j]存在
   {
    temp = (up[j] - '0') + (down[j] - '0') + cflag;
    up[j] = (temp) % 10 + '0';
    cflag = (temp) / 10;
   }
   else//up[j]不存在
   {
    up.push_back(((down[j] - '0') + cflag) % 10 + '0');
    cflag = ((down[j] - '0') + cflag) / 10;
   }

   j++;
  }
  while (cflag != 0)
  {
   if (j < up.size())//up[j]存在
   {
    temp = (up[j] - '0') + cflag;
    up[j] = (temp) % 10 + '0';
    cflag = (temp) / 10;
   }
   else//up[j]不存在
   {
    up.push_back(cflag % 10 + '0');
    cflag = cflag / 10;
   }
  }


 }
 
};

2. 优化思路——每一位数的乘法运算对result影响分析

//1 2 3 num1[i] //为示范简单,这里序号从右往左编码,程序中需要转换 //4 5 6 num2[j] //例如num1[0]和num2[0]相乘 : 3X6=18 肯定影响到了result[0+0],有进位则会影响到result[0+0+1], result其他的值则肯定不会改变

2.1 优化分析: 在竖式中,从右向左编码, 两个数num1[i], num2[j]相乘, 则只会影响到result[i+j] , result[i+j+1]两位的结果

2.2 因此我们不需要临时存储的容器currentresult, 只需要在 result中修改受影响的两位即可

2.3 另外num2.pop_back虽然符合直觉习惯,但显然我们可以通过移动下标来代替反复的pop

事实证明对于一些修改字符串的操作还是小心为慎, 虽然pop这个操作看起来只需要剪掉尾巴就好, 应该耗时影响不大 , 但事实上我卡在80%就是因为它!!!!, 优化掉后直接97%= =.

2.4 反转问题: 同上可知, 乘法最远也就影响到result[length1+length2+1]. 即result长度已知, 因此可以反向填充result即可避免最后还得反转

暴力法时因为不清楚result到底会有多长, 所以不能反向填充.

2.5 另外还有一些小细节思考

比如连续进位有没有问题

循环结束需不需要有收尾整理

我们现在result里填充了[length1+length2+1]的 '0' 方便我们后续反向填充和累加, 但是result[0]是最后一位进位的结果, 假如最后没有进位呢?

优化代码, 超越97%时间,86%内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
 string multiply(string num1, string num2)
 {
  if (num1 == "0" || num2 == "0")
   return "0";

           
  string result;
        int totallength=num1.size()+num2.size();//result最大可能长度
  int i;
        int j=0;
  int cflag =0;
        int temp=0;//i+j位和存储器


        for(i=0;i<totallength;i++)//初始化填充
        {
            result.push_back('0');
        }
        //反向填充,可以不需要在最后reverse,....好像对效率影响不大
        //把num2.pop()删掉了,终于从8ms提到了4ms......
  while (j<num2.size())//num1[i]Xnum2[j] 只影响result的[i+j]和[i+j+1],因此相比暴力相加,可以优化中间步骤
  {
   for (i = num1.size() - 1; i = 0; i--)
   {   //因为要改变i+j位,所以先计算出i+j+1位,(程序用的i和注释i不是一个)
                temp=(result[totallength-1-((num1.size()-i-1)+j)]-'0')+ (num1[i] - '0')*(num2[num2.size()-1-j] - '0');
                //连续进位怎么办?临时存储?循环清理干净?
                //临时存储试试
                result[totallength-1-((num1.size()-i-1)+j+1)]+=temp/10;
    result[totallength-1-((num1.size()-i-1)+j)]='0'+temp%10;
   }
            
            
            j++;
  }
        //不需要检查最后一位要不要进位
       
  //1 2 3
  //4 5 6
  //7 3 8+6 1 5 * 10

        //跳过头部的0
        if(result[0]!='0')
      return result;
        else
            return result.substr(1);
 }

 
};

string.pop_back()真的卡了我好久, 左优化右优化, 去头部0的方法换了又换, 就是卡在80% .......谨慎考虑库函数的效率.