LeetCode中级算法之数组和字符串_leecode 数组字符元素和

三数之和

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]
1
2
3
4
5
6

Solution：
这道题如果直接用遍历的话，时间复杂度是O（n * n * n）,复杂度太高，所以考虑创建一个hash表来降低时间复杂度，但是这个算法会遇到一个问题如下：
当输入为[[-1,0,1,0]时，输出的结果可能是[-1,0,1],[-1,1,0]，这样结果是重复的，我暂时想到进行遍历比较，相同就删除，但是这样好像还是有点麻烦，于是上网查了一个比较好的思路，是用双指针遍历做的，思路是这样（引用）：

首先对数组从小到大排序，从一个数开始遍历，若该数大于0，后面的数不可能与其相加和为0，所以跳过；否则该数可能是满足要求的第一个数，这样可以转化为求后面数组中两数之和为该数的相反数的问题。定义两个指针一前一后，若找到两数之和满足条件则加入到解集中；若大于和则后指针向前移动，反之则前指针向后移动，直到前指针大于等于后指针。这样遍历第一个数直到数组的倒数第3位。注意再求和过程中首先判断该数字是否与前面数字重复，保证解集中没有重复解。

 vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() < 3)
            return res;
        vector<int> v;
        sort(nums.begin(), nums.end());
        int sum = -1;
        for(int i = 0; i < nums.size() - 2; i++){
            if(nums[i] <= 0){
                v.push_back(nums[i]);
                if(sum == 0 - nums[i]){
                    v.pop_back();
                    continue;
                }
                sum = 0 - nums[i];
                int f = i + 1, l = nums.size() - 1;
                int di = nums[f] - 1;
                while(f < l){
                    if(nums[f] + nums[l] == sum){
                        if(di != nums[f]){
                            v.push_back(nums[f]);
                            v.push_back(nums[l]);
                            res.push_back(v);
                            v.pop_back();
                            v.pop_back();
                            di = nums[f];
                        }
                        f++;l--;
                    }
                    else if(nums[f] + nums[l] < sum)
                        f++;
                    else if(nums[f] + nums[l] > sum)
                        l--;
                }
                v.pop_back();
            }
        }
        return res;
    }
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

下面是我的代码：

   vector<vector<int>> threeSum(vector<int>& nums) {
    	int min = nums[0], max = nums[0];
    	int size = nums.size();
    	vector<int> temp;
    	vector<vector<int>> res;
    	for(int i = 1; i < size; i++)
    		{
    			if(min > nums[i]) min = nums[i];
    			if(max < nums[i]) max = nums[i];
    		}
    	for(int i = 0; i < size; i++)
    		nums[i] -= min;
        int *hash;
        int zero = min * 3;
        max -= min;
        hash = (int*)malloc((max + 1) * sizeof(int));
        for(int i = 0; i < max + 1; i++)
    		hash[i] = 0;
    	for(int i = 0; i < size; i++)
    		hash[nums[i]]++;
    	for(int i = 0; i < size; i++)
    	{
    		for(int j = i + 1; j < size; j++)
    		{
    			hash[nums[i]]--;
    			hash[nums[j]]--;
    			if(hash[zero - nums[i] - nums[j]])
    			{
    				temp.push_back(nums[i] + min);
    				temp.push_back(nums[j] + min);
    				temp.push_back(- nums[i] - nums[j] - min * 2);
    				hash[nums[i]]--;
    			    hash[nums[j]]--;
    			    hash[zero - nums[i] - nums[j]]--;
    			}
    			res.push_back(temp);
    			hash[nums[i]]++;
    			hash[nums[j]]++;
    		}
    	}
    	return res;  
    }
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

矩阵置零

Question：
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]
示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]
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

进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

Solution：
直接的解决方案就是遍历，使用O（mn）的额外空间，但是这显然很蠢，至于使用O（n + m）的额外空间，我觉得应该是给每一行每一列都设置一个标记，如果遍历的时候发现某一行/列有0，就给标记置false，随后再遍历一次，把false的行和列都置0。
常数空间的解决方案：
既然要常数空间的话，想了一下，可以直接拿原矩阵的第一行和第一列，然后用常数空间来存储第一行和第二行是不是应该置0。

 void setZeroes(vector<vector<int>>& matrix) {
    	int firstrow = 1, firstcol = 1;
    	for(int i = 0; i < matrix.size(); i++)
        	if(matrix[i][0] == 0) firstcol = 0;
        for(int i = 0; i < matrix[0].size(); i++)
        	if(matrix[0][i] == 0) firstrow = 0;
        for(int i = 1; i < matrix.size(); i++)
        {
        	for(int j = 1; j < matrix[0].size(); j++)
        	{
        		if(matrix[i][j] == 0)
        		{
        			matrix[0][j] = 0;
        			matrix[i][0] = 0;
        		}
        	}
        }
       for(int i = 1; i < matrix.size(); i++)
        {
        	for(int j = 1; j < matrix[0].size(); j++)
        	{
        		if(matrix[0][j] == 0||matrix[i][0] == 0)
        		{
        			matrix[i][j] = 0;
        		}
        	}
        }
        if(firstcol == 0) 
        {
        	for(int i = 0; i < matrix.size(); i++)
                   matrix[i][0] = 0;
        }
        if(firstrow == 0) 
        {
        	for(int i = 0; i < matrix[0].size(); i++)
                   matrix[0][i] = 0;
        }

    }
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

字谜分组

Question：
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
1
2
3
4
5
6
7
8
9
10
11
12

Solution：
c++中string类的find（）函数和erase（）函数在这里被使用：

string中find()返回值是字母在母串中的位置（下标记录），如果没有找到，那么会返回一个特别的标记npos。（返回值可以看成是一个int型的数）
erase()三种用法：
（1）erase(pos,n); 删除从pos开始的n个字符，比如erase(0,1)就是删除第一个字符
（2）erase(position);删除position处的一个字符(position是个string类型的迭代器)
（3）erase(first,last);删除从first到last之间的字符（first和last都是迭代器）

我用了简单的比较+遍历的方法，代码如下：

bool Compare(string s1,string s2)
    {
    	if(s1.size()!= s2.size())return false;
    	int pos;
    	for(int i = 0; i < s1.size(); i++)
    	{
    		pos = s2.find(s1[i]);
    		if(pos == s2.npos) return false;
    		s2.erase(pos,1);
    	}
    	return true; 
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        string str;
        for(int k = 0; k < strs.size(); k++)
        {
        	str = strs[k];
            int i;
        	for(i = 0; i < res.size(); i++)
            {
        	  if(Compare(str,res[i][0]))
        	  {
        		  res[i].push_back(str);
        		  break;
        	  }
            }
            if(i == res.size())
            {
                vector<string> temp;
                temp.push_back(str);
                res.push_back(temp);
            }
        }
        return res;
    }
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

很不幸，最后一组数据超时了，上网查了一下， 这道题适合用hashmap来坐，hashmap的键值是排序后的一个string，value是最后要存储的字符串，正好我对map不熟悉，正好熟悉一下map，练练手~

vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        if(strs.empty()) return res;
        map<string,vector<string>> m;
        for(int i=0;i<strs.size();++i)
        {
            string temp=strs[i];
            sort(temp.begin(),temp.end());
            m[temp].push_back(strs[i]);
        }
        map<string,vector<string>>::iterator it;
        for(it = m.begin(); it != m.end(); it++)
        {
            res.push_back(it->second);
        }
        return res;
    }	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

无重复字符的最长子串

Question：
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

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

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

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
1
2
3
4
5
6
7
8
9
10
11
12
13
14

请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

Solution：
解法一（暴力）：

 int lengthOfLongestSubstring(string s) {
    	string suzy;
    	int max = 1,beg = 0,end = 0;
    	suzy = (char*)malloc(s.length() * typeof(char));
    	for(int i = 0; i < s.length(); i++)
    	{
    		suzy.append(1,s[i]);
    		int j = i + 1;
    	    while(suzy.find(j) != suzy.npos)
    	    {
    			suzy.append(s[j]);
    			j++;
    	    }
    		if(suzy.length() > max)
    		{
    			max = suzy.length();
    			end = j;
    		}
    		suzy.erase();
    		if(s.length() < max + i ) break;
    	}
        return max;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法二：hashmap

int lengthOfLongestSubstring(string s) {
    	map<char,int> m;
    	for(int i = 0; i < s.length(); i++)
    	{
    		m.insert(map<char,int>::value_type (s[i],0));
    	}
    	int res = 0, left = 0;
    	for(int i = 0; i < s.length(); i++)
    	{
    		if(m[s[i]] == 0 || m[s[i]] < left)
    		{
    			res = max(res, i - left + 1);
    		}
    		else
    		{
    			left = m[s[i]];
    		}
    		m[s[i]] = i + 1;
    	}
    	return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

最长回文子串

Question：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：

例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：
输入: "cbbd"
输出: "bb"
1
2
3
4
5
6
7
8

Solution：
这道题之前算法课的时候好像有看到过，应该是用动态规划来做的，设dp[i][j]为判断i与j之间的子串是否为回文串，分析后列出状态转移方程：
$$dp[i][j]=dp[i+1][j-1]\&\&str[i]==str[j]$$
根据这个转移方程，试着写出动态规划解决的方案：

string longestPalindrome(string s) {
    	int n = s.size();
        if(n == 0) return s.substr(0,0);
    	int max = 1, start = 0;
        bool dp[n][n];
        memset(dp, 0, sizeof(dp));
    	for(int j = 0; j < n; j++)
    	{
    		for(int i = 0; i <= j; i++)
    		{
    			if(s[i] == s[j])
    			{
    				if(j - i < 2) dp[i][j] = 1;
    			    else dp[i][j] = dp[i + 1][j - 1];
    			}
    			if(j - i + 1 > max && dp[i][j])
    			{
    				max = j - i + 1;
    				start = i;
    			}
    		}
    	}
    	return s.substr(start, max);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

动态规划其实理解的还不是很好，贴一段知乎上的话，帮助理解：

每个阶段只有一个状态->递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。

递增的三元子序列

Question：
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:

如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1， 使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。 说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。

示例 1:

输入: [1,2,3,4,5]
输出: true
示例 2:

输入: [5,4,3,2,1]
输出: false
1
2
3
4
5
6
7
8

Solution：
用动态规划的话，时间复杂度应该是O（n * n），不符合题目要求，那么考虑维护一个ready变量，这个变量是数组当前第二小的元素，这个第二小是怎么的出来的呢？只有数组前有比它更小的数才能被认定为第二小，那么只要之后出现比它大的，就直接可以认定存在递增的三元子序列，这个思路非常巧妙，我也是看了网上的思路才想出来：

bool increasingTriplet(vector<int>& nums) {
        int n = nums.size();
    	if(n < 3) return false;
 	    int min = nums[0], ready = INT_MAX;
 	    for(int i = 0; i < nums.size(); i++)
 	    {
 	    	if(nums[i] > ready) return true;
 	    	if(nums[i] <= min) min = nums[i];
 	    	if(nums[i] > min && nums[i] <= ready) ready = nums[i];
 	    }
 	    return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12

写在后面

中级的题目果然更难了一点，继续加油呀！