Sitch's Blog
0%

发表于 分类于 Valine：

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2]]

思路分析

  • 暴力O(n3) 这样做还不如不做kj

  • 联想两数之和那道题，可以采用map哈希来查找需要的值，但由于要先确定两个数之和，才能知道需要的值，所以有时间O(n2)+空间O(n)。

  • 牺牲O(Nlog N)对数组sort，排序之后找数即可用双指针头尾同步进行

  • 我的做法是，对于a<=b<=c，a+b+c=0，先确定b为center，然后对于center的每一次循环中，都让a,c分别从首尾开始，根据sum=a+b+c与0相比，判断是要a++还是c--。 这里要注意人为考虑特殊情况，注意剪枝，否则像{0,0,0,0,0,0,0,0,0,0,0}会没意义的算很多遍。另外在每个center的内循环中，显然假如最小值大于0，或者最大值小于0，是不可能和为0，可以剪枝。

  • 另外，当数组中有重复数字时，会重复进行循环匹配，因此我额外使用了一个set。

  • if(sum==0)之后，额外加一个if(set.count(vector)==0)来判断是否已经有了相同的组合被存储了，如果没有，则set和result同时存储这个新组合，set中存储是为了对之后判重。

解题代码

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
class Solution 
{
public:
    vector<vector<int threeSum(vector<int& nums) 
    {   
        vector<vector<int result;
        set<vector<int resultset;
        //剪枝
        if (nums.size() <= 2)
   return result;
        
  sort(nums.begin(), nums.end());
        
        //不剪枝会被0吓死=.=
  if (nums[0]=0 ||nums[nums.size()-1]<=0)
  {
   if (nums[0] == 0 &&nums[nums.size()-1]==0)
    result.push_back({ 0,0,0 });
   return result;
  }
        int i;
        int j;
        int center;
        
        
        for(center=0;center<nums.size();center++)
        {
            i=0;
            j=nums.size()-1;
            
            
            while(i!=center &&j!=center)
            {
                if(nums[i]0 || nums[j]<0)
                    break;
                
                int sum=nums[i]+nums[center]+nums[j];
                if(sum==0)
                {
                    vector<int temp ={nums[i],nums[center],nums[j]};
                    if(resultset.count(temp)==0)
                    {   
                        result.push_back(temp);
                        resultset.insert(temp);
                    }
                    i++;
                    j--;
                }
                
                else if(sum<0)
                    i++;
                else if(sum0)
                    j--;
            }
        }
        
        
        
        return result;
    }
};
执行用时 : 424 ms, 在所有 C++ 提交中击败了5.01%的用户 内存消耗 :24.3 MB, 在所有 C++ 提交中击败了7.53%的用户
虽然好像剪枝也做了，但好像效率依然不够高，不知道是不是额外加了个set的问题 看别人的题解，不以b以a为外循环可以避免重复，也就不需要set，但没懂是为什么。 挖个坑，搞懂了再回来看看。

发表于 分类于 Valine：

最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解题思路

  • 一开始我想分解问题，确定一个数，找最接近的两个数，其中找两个数的过程也是通过确定一个数，找最接近的最后一个数。解题不难，但复杂度很高。
  • 又是一个逼近问题，做了几道现在应该领悟到了双指针逼近的方法是一个很好的寻找逼近值的策略。

算法主体

1
2
3
4
5
6
7
8
9
while(i<j)
{
  if(sum<target)
    i++;
  else if(sumtarget)
    j--;
  else if(sum==target)
}

  • 算法简单，但实现细节需要考虑，并不是出口附近的sum就一定是最接近的sum。

假如简单的取上面这个粗糙的循环，对于实例([-101,-100,0,2,3,4,5,6,7,8,9,10],-99)。当i从-100移到0之后，j一直减到i期间的sum都没有i=-100处的sum良好，但却会作为出口给人最优的错觉。

错误经验：最优解也并不是取最后一次i变动的sum和最后一次j变动的sum，因为可能变i变j再变i反复变化，然而最优解其实一直停留在第一个变i之前。

  • 我自己的解决办法是把所有的sum都存储起来，最后统一遍历找出最优解，但显然这样需要花一点点时间。

题解代码

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
class Solution {
public:
 int threeSumClosest(vector<int& nums, int target)
 {
  int result;
  sort(nums.begin(), nums.end());
  vector<int sums;
  int a;
  int b;
  int c;
  int sum;
  int resultdistance = INT_MAX;

  for (a = 0; a < nums.size() - 2; a++)
  {
   b = a + 1;
   c = nums.size() - 1;

   while (b < c)
   {
    sum = nums[a] + nums[b] + nums[c];

    
    sums.push_back(sum);
    if (sum < target)
     b++;
    else if (sum  target)
     c--;
    else
     return sum;
   }

  }
        
        for(int i=0;i<sums.size();i++)
        {
            if(abs(target - sums[i]) < resultdistance)
    {
     result = sums[i];
     resultdistance = abs(target - result);
    }
        }

  return result;
 }


};

不存储所有结果，直接在每个sum之后与result比较，效率比存储的高了4ms。

提交结果 执行用时 内存消耗 语言
2019.9.15 通过 12 ms 8.7 MB
2019.9.11 通过 16 ms 12.9 MB

8ms可能是做不到了，量级上应该一样。

发表于 分类于 Valine：

括号生成

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[ "((()))", "(()())", "(())()", "()(())", "()()()"]

题解分析

  • 一开始我想创建一个2n的string数组 因为string（包括子串）第一个空位一定会是' ( ' 因此我的算法思路是 第一位肯定是' ( ' 不变，然后在剩下的length-1空位中遍历选一处插入')' 然后递归进入子串插入，也是子串第一位 '( ' 不变，遍历剩下的空位一次次插入 ')' ，直到递归完成括号串。 这种算法不能避免重复，而且我在创建动态长度的字符串这里就失败了=。= 但没看到相似的思路，因此写下来说不定以后能够优化一下。

  • 标准思路

递归对每一位进行检测，如果' ( '数量少，则这一位插入' ( '进入递归，否则插入' ）'进行递归，直到填满。

因为这种方法会遍历完所有'（'可能的位置，进而能够确定括号串，因此不会重复也不会遗漏。

  • 递归法代码

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
class Solution {
public:
    vector<string generateParenthesis(int n)
    {
        vector<string result;
       
        Recursion(n,"",0,0,result);
        return result;
    }
    
    
 void  Recursion(int n,string temp,int left ,int right,vector<string& result)
    {
        if(temp.size()== 2*n)
        {
            result.push_back(temp);
            return;
        }
     
        if(left<n)
            Recursion(n,temp+'(',left+1,right,result);
        
        if(right<left)
            Recursion(n,temp+')',left,right+1,result);
    }
};
提交时间 提交结果 执行用时 内存消耗 语言
2 天前 通过 20 ms 17 MB Cpp

  • 动态规划

因为递归法效率还没有极致，因此看了看题解大神的解法，发现了一位用动态规划的人才。 给上链接 ：

闭合数的合理解释-Jerry Peng

  • 算法分析 对于每个n对括号的括号串S[n] 都可以划分为两个部分 S[n] = '(' + S[c] + ')' + S[n-c-1]; 第一对括号里面带着c长度的子问题， 右边剩下部分n-c-1长度的子问题 自底向上，存储子问题结果，逐步合并到n长度的问题。 因为要找到所有可能结果，因此c的取值需要遍历所有可能。

  • 动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<string generateParenthesis(int n)
    {
       map<int,vector<string resultmap;
        resultmap[0].push_back("");
        for(int i=1;i<=n;i++)
            for(int j=0;j<i;j++)
                for(string left: resultmap[j])
                    for(string right: resultmap[i-j-1])
                    resultmap[i].push_back("("+left+")"+right);
        
        return resultmap[n];
    }
};

提交时间 提交结果 执行用时 内存消耗 语言
2 天前 通过 12 ms 9.6 MB Cpp

有想过为什么不直接分为left 和 right 两个部分，一定要套个括号 　——假如只分两半left 和 right，那在求解S[n]遍历的时候肯定要遍历到S[n]自身，因此需要先固定好一对括号，这样遍历会停止在S[n-1]的子问题，然后合并出待解的S[n]问题。

发表于 分类于 Valine：

合并K个链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入: [ 　1-4-5,   　1-3-4,   　2-6] 输出: 1-1-2-3-4-4-5-6

解题分析

  • 因为之前做过2个排序链表的合并，所以这里主要想法是两两归并。 两个链表合并：双指针判断对应节点大小，依次插入新链表，若一个链表用尽，则在result链表后接上另一个链表即可。

  • 归并其实也有讲究，我一开始直接用的是顺序归并result=mergeTwoLists(result,temp)，其实浪费了很多效率，把不必要的排序比较一遍又一遍的做。

  • 如下方题解代码，使用了折半归并（直观描述词）。每次合并List i =mergeTwoLists(List i,List i+halflength). 直到长度为1即完成。

题解代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*& lists) 
    {
        ListNode* result=NULL;
        int length=lists.size();
        if(length==0)
            return NULL;
        while(length1)
        {
            int temp=(length+1)/2;
            for(int i=0;i<length/2;i++)
                lists[i]=mergeTwoLists(lists[i],lists[i+temp]);
            
            length=temp;
        }
        
        
        return lists[0];
    }
    
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
   {
   
    ListNode result(0);
    ListNode* another = &result;

    while (l1 != NULL && l2 != NULL)
    {
   
     if (l1-val <= l2-val)
     {
      another-next = l1;
      l1 = l1-next;  
     }
     else
     {
      another-next = l2;
      l2 = l2-next;
     }
              
              another = another-next;
    }
                   
          another-next=(l1==NULL)?l2:l1;
    return (&result)-next;
   }
};

发表于 分类于 Valine：

实现 strStr() 函数

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1:

输入: haystack = "hello", needle = "ll" 输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

显然这题主要目标是在主串中找到一个模式串，而我在数据结构课中有学到KMP算法，因此我首选题解就是实现KMP。

KMP （主要思想：不回退的主串查找位，有效利用失败信息）

暴力法存在的问题

主串abcdabcdabce，模式串abcdabce. 标志位 i，j

我们可以知道第一次匹配会在abcdabcdabce，abcdabce处失败 在暴力法中，失败后 i ++，j=0，从i=1，j=0 处再次开始一轮匹配。 即主串明明匹配到了第8位，失败后却还要回退到第二位开始新的匹配，无疑浪费了很多时间。

失败返回的有效信息

模式串在 e 处失败，可以带给我们什么有效信息：

  1. 主串前面有abcdabc
  2. 主串这一位不为e

利用返回的有效信息

已经已知主串有了这七个字符，按人的思维去分析的话，可以知道主串前四位abcd都没必要去做新的匹配模式串的循环了，因为一定会失败，而5 ~ 7位abc虽然是在匹配模式串的5 ~ 7位匹配出来的，但是却也可以匹配模式串的前三位。因为这些都是已知信息，所以我们可以直接当失败处abcdabcd已经匹配了模式串的abc，只需要拿d去匹配d即可。

相当于不仅没回退，还可以在当前位置上直接跳过模式串前三位进行后续匹配。

而把上面的思路写成逻辑，我们就需要分析其产生的原因条件，以及导出的结果

为什么恰巧可以跳过呢？让我们来看一下跳过时的环境条件

  1. 失败前的倒数几位，刚好可以拿去匹配正数前几位，因此相当于匹配好了前几位
  2. 这种在某一位失败之后能否产生跳跃的信息，只和模式串本身有关，和主串无关，因为我们是用失败的倒数几位去匹配前几位，全是模式串自己。

因此我们可以找到跳过的思路，对于匹配失败时：

  1. 假如模式串在这个字符之前的倒数几位能和整数几位匹配，那就直接略过，i 不变，j 跳到整数几位的后一位接着匹配
  2. 假如不能形成这种前后缀的匹配，则直接让 i ++，在下一位开始全新的匹配

i 不用回到这次匹配的开头再i++，假如回到开头再 i++ ，我们的目标是当前匹配失败了，主串字符串匹配区间右移一位是不是能匹配成功。然而这种匹配成功的条件必须是区间右移后，和移动前的重叠区域字符相同。即在重叠区域内，pat[i+1]==pat[i]。用人话翻译就是，只有str=aaaaax pat=aaaax这种前部分字符只有一个的情况才有移动区间匹配成功的可能。然而我们可以从实例中看到，这种字符串情况也包含在跳过的思路中，也恰好满足跳过的条件，甚至不用回移不用使j=0开始匹配，只需要接着从跳到的 j 处匹配就解决了这个情况。

创造跳跃数组

我们知道，KMP主要算法就是在失败时，通过跳跃到恰当的位置接着匹配。 而这个恰当的位置 k 满足：k之前的所有k位，即前缀，和失败处的倒数k位，即后缀，恰好相同，此时失败即可跳到k处。

所以我们要解决的就是，在开始查找模式串之前，先对模式串每一位 j 进行前后缀检测，存在满足的前后缀即可令 jump[j]=k 存储在该处失败可跳跃到的位置。不存在则存入 -1 作为标志即可

因为跳跃位置只与模式串本身有关，因此事先处理好一次即可对任何主串复用。

当然检测前后缀也不是一个简单的事，KMP中构造跳跃数组的过程中也是用了KMP自己.......作为学习者只能对创造者表示敬佩，这里用伪代码描述一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
因为在0位失败肯定没法跳跃，令jump[0]=-1 
设置好跳跃定位标志 k=-1
对模式串每一位 i
    假如 i  k 位相同，或者k==-1
      即看作前后缀目前为止相同
      i, k 到下一位
      对于已经处理好前后缀之后的下一位，只需把跳跃信息给它即可
          假如下一位与跳跃位不同
              把已经处理好的k作为它的跳跃位即可，jump[i]=k
          假如下一位与跳跃位相同
              （比如在a失败，跳到的地方还是a，那就没有再比一次的必要了）
              把跳跃位的跳跃位作为它的跳跃位hhh jump[i]=jump[k]
   假如 i k 位不同 （他们的跳跃信息已经被处理好了）
      （内用KMP，即相当于后缀作为主串，前缀作为模式串，此时匹配失败了，前缀跳到跳跃位接着匹配）
      k=jump[k]

处理好跳跃数组（失效数组）之后，即可按数组的跳跃信息进行利用匹配.匹配过程看下方代码即可，并不难:

KMP解题代码

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
class Solution {
public:
    int strStr(string haystack, string needle) 
    {   
        if(needle=="")
            return 0;
        
        //KMP
 
        int jump[needle.size()];
        jump[0]=-1;
        int k=-1;
        int i=0;
        //创建失效数组  abcabcd
        while(i<needle.size()-1)
        {
            if(k==-1 || needle[i]==needle[k])
            {
                i++;
                k++;
                
                if(needle[i]!=needle[k])
                    jump[i]=k;
                else
                    jump[i]=jump[k];
            }
            else    //内置kmp
                k=jump[k];
        }
                
  
        
        int x=0;
        int y=0;
        while(x<haystack.size() && y<int(needle.size())) //注意这里int化！！！！！！看bug看了好久，size返回值是unsignedint
        {
            if(y==-1 ||haystack[x]==needle[y])
            {
                x++;
                y++;
            }
            else
               y=jump[y];
            
        }
        
        if(y==needle.size())
            return x-y;
        else
            return -1;
        
        
        
    }
};