KelvinMao

26.Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

删除已排序数组中的重复元素，要求常数级的空间复杂度，并返回最后的数组长度。 思路就是遍历，直接看代码吧：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        if(nums.size()<2)
            return 1;
        int i=0,new_len=1;
        for(i=1;i<nums.size();i++){
            if(nums[i]!=nums[i-1]){
                nums[new_len]=nums[i];
                new_len++;
            }
        }
        return new_len;
    }
};
KelvinMao

18.4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

给出n个元素的数组S，寻找是否存在四个数组中的元素a,b,c,d且a+b+c+d=target，如果有，寻找出所有这样的不重复的四元组。

这道题如果有一个数是确定的，那么就转化为了3Sum问题，思路完全相同，代码上稍作改动即可

solution1 用时92ms

  • [ TODO To be faster]
/*solution 1*/
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>>res;
        int left=0,mid1=0,mid2=0,right=0,tmp_mid2=0,tmp_right=0,tmp_mid1=0,tmp_left=0;
        int size=nums.size();
        sort(nums.begin(),nums.end());
        if(size<4)
            return res;
        for(left=0;left<size-3;left++){
            int tmp_left=target-nums[left];
            /*去除left造成的重复*/
			if(left > 0 && nums[left] == nums[left-1])
                continue;
            for(mid1=left+1;mid1<size-2;mid1++){
                int tmp=tmp_left-nums[mid1];
                mid2=mid1+1;
                right=size-1;
                /*去除mid1造成的重复*/
				if(mid1 > left+1 && nums[mid1] == nums[mid1-1])
                    continue;
                while(mid2<right){
                    if(nums[mid2]+nums[right]==tmp){
                        tmp_mid2=nums[mid2];
                        tmp_right=nums[right];
                        vector<int>quadruplets(4,0);
                        quadruplets[0]=nums[left];
                        quadruplets[1]=nums[mid1];
                        quadruplets[2]=nums[mid2];
                        quadruplets[3]=nums[right];
                        res.push_back(quadruplets);
                        while(mid2 < right && nums[++mid2] == tmp_mid2);/*去除mid2造成的重复*/
                        while(mid2 < right && nums[--right] == tmp_right);
                    }
                    else if(nums[mid2]+nums[right]<tmp)
                        mid2++;
                    else
                        right--;
                }
            }
        }
        return res;
    }
};
KelvinMao

179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

给出一个数组，要求用数组中的数字来组成一个新数字，并且这个新数字是所有可能中最大的一个。

这道题如果可以对数组中的数字进行调整，那么就很简单了，对大于等于10的数字进行分割，之后将分割后得到的各位数字加入数组，小于10的数字也加入这个数组，之后将数组从大到小排序，转化成字符串即可。

然而这道题并不允许我们调整字符串，所以我们得转换思路。

问题的关键在于如何比较任意两个数字的大小:

  1. 如果是两个个位数，则直接比较即可。
  2. 如果其中有一个超过10的数字，比如23和9，则在这道题的逻辑中，应该是9>23
  3. 如果某个数的前半部分和另一个数完全相同，则看该数剩下的那部分和另一个数的大小关系，如6532和65比较时，65是大于6532的，因为65大于32。
  4. …………

由此可见，如果要细分各种情况，会十分复杂，所以在参阅了讨论区之后我得到了这样一种思路。

要判断任意两个数的大小关系，可以将其转换为字符串之后，对其进行正反两次拼接，比较获得的两个字符串的大小关系即可，本题中用到的比较函数的代码如下:

bool compTwoString(string& s1,string& s2){
        return s1+s2>s2+s1;
}

这个函数会作为参数被传给sort函数，但现在有一个问题，如果就这样对compTwoString进行定义的话，编译器会报错，提示invalid use of non-static member function，这是什么原因呢？

因为我们使用的std::sort()函数是一个全局函数，而我们定义的比较函数是一个非静态成员函数，非静态成员函数是依赖于具体对象的，所以我们无法在全局函数中调用非静态成员函数，那么我们在声明函数时就需要将其声明为静态函数或者全局函数。

静态成员函数是不依赖于具体对象的，无需创建任何实例就可以调用，但同时静态成员函数是不可以调用非静态成员的。

另外，有一个corner case,就是如果排序后第一个数是0，则直接返回0，因为后面的数只有可能是0了。

解决了这个问题，我们就很容易写出代码了:

class Solution {
private:
    static bool compTwoString(string& s1,string& s2){
        return s1+s2>s2+s1;
    }
public:
    string largestNumber(vector<int>& nums) {
        if(nums.empty())
            return {};
        vector<string> tmp;
        string res;
        for(int num:nums)
            tmp.push_back(to_string(num));
        sort(tmp.begin(),tmp.end(),compTwoString);
        for(string s:tmp)
            res+=s;
        return res[0]=='0'?"0":res;
    }
};

一道值得反复研究的习题，被归类在Sort中，但除了需要我们利用库函数中的排序，还需要我们另辟蹊径，自定义比较函数，这个拼接字符串的思路值得反复思考。

知识共享许可协议
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。

KelvinMao

15.3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: (Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c))The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

从数组中计算出和与给定值相等的元素组成的新数组，以数组形式返回。Leetcode上的题目似乎有变化，原先还有一个条件是返回的数组中元素必须以升序排列。

最笨的方法就是三重循环，O(n^3)的时间复杂度，想想都可怕。

再来分析题目要求:

  1. 以数组形式返回
  2. 返回结果不能重复
  3. 返回结果以升序排列

以上我们用一大堆if语句都可以完成，不过如果数组在最初是有序的，问题就简化了许多。声明left,mid,right作为待返回数组的三个数的下标，其中left最小，right最大。

那么三个数之和等于0，只要确定一个数，不就转化为2Sum问题了吗？所以我们需要一层外循环

for(left=0;left<size&&nums[left]<=0;left++)

之后mid和right两个指针从两边向中间扫描，发现符合条件的进行记录

while(mid<right){
                if(nums[mid]+nums[right]==tmp){
                    int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
                    vector<int>triplet(3,0);
                    triplet[0]=nums[left];
                    triplet[1]=nums[mid];
                    triplet[2]=nums[right];
                    res.push_back(triplet);
                }
                else if(nums[mid]+nums[right]<tmp)
                    mid++;
                else
                    right--;
            }

这样，似乎我们的算法可以解决这个问题了，然而还需要处理重复的问题。于是修改代码如下:

for(left=0;left<size&&nums[left]<=0;left++){
            tmp=0-nums[left];
            mid=left+1;
            right=size-1;
            while(mid<right){
                if(nums[mid]+nums[right]==tmp){
                    int tmp_left=nums[left],tmp_right=nums[right],tmp_mid=nums[mid];
                    vector<int>triplet(3,0);
                    triplet[0]=nums[left];
                    triplet[1]=nums[mid];
                    triplet[2]=nums[right];
                    res.push_back(triplet);
                    while(mid<right&&nums[++mid]==tmp_mid);/*防止mid造成重复*/
                    while(mid<right&&nums[--right]==tmp_right);/*防止right造成重复*/
                }
                else if(nums[mid]+nums[right]<tmp)
                    mid++;
                else
                    right--;
            }
            while(left+1<size&&nums[left]==nums[left+1])/*防止*/
                left++;
        }

问题就得到了解决。

KelvinMao

389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

给出两个字符串s和t，仅含有小写字母

字符串t是由s中任意插入一个字母构成的，现在要求我们找出这个加入的字母。

题目要求不高，就是简单的应用哈希表的性质，因为字符集的规模很小，所以我们用一个长度为26的int数组来模拟哈希表即可，代码如下:

/*solution1,use a vector to compute the frequency,4ms*/ 
class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> word(26,0);
        for(int i=0;i<s.size();i++)
            word[s[i]-'a']++;
        for(int i=0;i<t.size();i++){
            int tmp=word[t[i]-'a']--;
            if(tmp==0)
                return t[i];
        }
        return 'a';
    }
};

第一版代码用数组对字符和其出现次数做了一个映射，思路并不复杂。

在查看了讨论区之后，我发现了一个更好的思路，之前我们在解决single number这个问题时，用了位运算的方法，也就是让每个数字相互进行异或XOR运算，最后剩下的一定是出现次数为1的元素，那么这个题实际上也可以让两个字符串中的字符做异或运算，代码如下:

/*solution2,use bit manipulation，4ms*/
class Solution {
public:
    char findTheDifference(string s, string t) {
        char tmp=0;
        for(char a:s)
            tmp^=a;
        for(char b:t)
            tmp^=b;
        return tmp;
    }
};

Stefan大神提出了一行代码解决问题的方案，运用了accumulate方法，思路上和第二种方法相同,代码如下:

/*solution 3,one-line version of solution2*/
class Solution {
public:
    char findTheDifference(string s, string t) {
        return accumulate(begin(s), end(s += t), 0, bit_xor<int>());
    }
};

知识共享许可协议
本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。