242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example, s = “anagram”, t = “nagaram”, return true. s = “rat”, t = “car”, return false.

Note: You may assume the string contains only lowercase alphabets.

非常经典的变位词问题,此题降低了难度,因为只要求判断小写字母组成的变位词,那么方法无外乎就是sort和hash-table。

通过观察,我们发现互为变位词的两个词中每个字母出现次数一定是相同的,所以最基本的思路是用两个哈希表来存字母和次数的键值对,代码如下:

/*solution 1,52ms*/
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.empty()&&t.empty())
            return true;
        if(s.size()!=t.size())
            return false;
        unordered_map<char,int> hash;
        unordered_map<char,int> hash2;
        bool flag=false;
        for(int i=0;i<s.size();i++)
            hash[s[i]]++;
        for(int i=0;i<t.size();i++)
            hash2[t[i]]++;
        for(int i=0;i<s.size();i++){
            if(hash[s[i]]==hash2[s[i]])
                flag=true;
            else
                return false;
        }
        return flag;
    }
};

最初的代码不是很好,因为对于两个空字符串的情况需要单独进行判断,运行时间较长,而且用了两个哈希表,不够优雅,所以我开始考虑如何优化。

既然每个字母出现次数相同,那么我们可以只用一个哈希表:

  • 当s中的字母被储存在哈希表中时,其对应的值+1;
  • 当t中的字母被储存在哈希表中时,其对应的值-1;

代码如下:

/*solution2 36ms*/
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size())
            return false;
        unordered_map<char,int> hash;
        for(int i=0;i<s.size();i++){
            hash[s[i]]++;
            hash[t[i]]--;
        }
        for(auto pos:hash)
            if(pos.second!=0)
                return false;
        return true;
    }
};

这次只用了36ms,减少一个哈希表的使用可以换来效率上的很大的提升,那么,还能不能继续优化呢?

我们知道,哈希表的作用在于完成以O(1)为时间复杂度的查找操作,不过这道题中我们更多的是在使用哈希表中的键值对关系,而不是需要频繁的查找操作,所以,针对这道题,我们可以用一个数组来替换掉哈希表,代码如下:

/*solution 3,use array instead of hash-table,12ms*/
class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size()!=t.size())
            return false;
        int count[26]={0};
        for(int i=0;i<s.size();i++){
            count[s[i]-'a']++;
            count[t[i]-'a']--;
        }
        for(int pos:count)
            if(pos!=0)
                return false;
        return true;
    }
};

只用了12ms,效率已经比较高了。

当然,最简单的方法就是排序后进行比较,非常简单,不再赘述了。

204. Count Primes

Description:

Count the number of prime numbers less than a non-negative number, n.

给出一个非负整数n,要求返回比n小的素数的个数

看起来非常容易,只需要写一个判断素数的函数isPrime()函数,然后对从2~n的数字进行判断就可以了,但是如果有这么简单,这道题也就不会作为面试题进行考察了。因为这个O(n^2)的算法会被OJ判为超时,即使你已经考虑了循环条件是:i<sqrt(n),而不是i<n

考虑到统计个数的复杂度基本没有降低的希望,所以我们在判断素数这个函数上做优化。

因为之前学过的判断素数的算法只是在循环条件上做优化,所以最多也只能将时间复杂度降低到O(n^1.5),所以我们需要一种新的判断素数的思路。

我们要AC这道题,就必须使用sieve of Eratosthenes算法,中文名是埃拉托斯特尼筛法,不要被它的名字吓到,原理很简单,就是从2开始,将每个素数的各个倍数,标记成合数。下面这张图可以帮助理解

image

按步骤对算法的运行状况进行分析:

首先列出2以后的所有序列: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 标出序列中的第一个质数,也就是2,序列变成: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 将剩下序列中,划掉2的倍数,序列变成: 2 3 5 7 9 11 13 15 17 19 21 23 25 如果现在这个序列中最大数小于最后一个标出的素数的平方,那么剩下的序列中所有的数都是质数,否则回到第二步。

本例中,因为25大于2的平方,我们返回第二步: 剩下的序列中第一个质数是3,将主序列中3的倍数划出,主序列变成: 2 4 5 7 8 10 11 13 14 16 17 19 20 22 23 25 我们得到的质数有:2,3 25仍然大于3的平方,所以我们还要返回第二步: 现在序列中第一个质数是5,同样将序列中5的倍数划出,主序列成了: 2 3 5 7 11 13 17 19 23。 我们得到的质数有:2 3 5 。 因为25等于5的平方,跳出循环. 结论:去掉红色的数字,2到25之间的质数是:2 3 5 7 11 13 17 19 23。

class Solution {
public:
    int countPrimes(int n) {
        int count=0;
        bool isprime[n];
        for(int i=0;i<n;i++)
            isprime[i]=true;
        for(int i=2;i<sqrt(n);i++){
            if(isprime[i]){
                for(int j=2;j*i<n;j++)
                    isprime[j*i]=false;
            }
        }
        for(int i=2;i<n;i++){
            if(isprime[i]==true)
                count++;
        }
        return count;
    }
};

这个算法的时间复杂度为 O(n log log n),数学上的证明请见维基百科(太复杂了),由于申请额外空间,所以空间复杂度为O(n)

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note: You may assume k is always valid, 1 ≤ k ≤ n2.

这道题给我们一个二维数组,二维数组的行和列按升序排列,要求找出第k小的元素,k的范围是1 ≤ k ≤ n2.

对于寻找数组中第k小的元素,最经典的方法是使用堆这种数据结构,我们首先要建立一个大顶堆,然后让把数组中的元素依次插入堆中,当堆中元素数目超过k时,就删除堆顶元素,直到所有元素都遍历完后,返回堆顶元素的值即可。

这种方法根据大顶堆的性质很容易想到,时间复杂度为O(n^2 * logk),k是堆的大小,效率太低,而且没有用上题目中元素按行按列递增的性质。

代码如下:

/*solution 1,use heap,144ms,O(n^2 *  logk),k is the size of heap*/
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<int> heap;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                heap.emplace(matrix[i][j]);
                if(heap.size()>k)
                    heap.pop();
            }
        }
        return heap.top();
    }
};

于是考虑能不能用二分查找对算法进行优化,考虑到元素按行按列递增,那么左上角必然是最小元素,右下角必然是最大元素,那么我们计算最小与最大的均值作为二分查找中的mid,假设mid就是我们的数组中第k小的元素,然后以mid元素为准,使用upper_bound()函数来统计每行中小于mid元素的个数,这个个数与k作比较,有两种情况:

  1. 大于或等于k,说明选择的mid太大,需要调整到左半区,则high=mid-1;
  2. 小于k,说明我们选定的mid太小,需要调整到右半区,则low=mid+1;

那么最后要返回的元素是什么?因为猜想的解不一定在数组中,所以要不断的收缩直到找到在数组中的元素为止。

时间复杂度为O(nlogn),运行时间56ms,代码如下:

/*solution 2,use binary-search,O(nlogn),56ms*/
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int low=matrix[0][0],n=matrix.size(),high=matrix[n-1][n-1],cnt=0,mid=low+((high-low)>>1);
        while(low<=high){
            mid=low+((high-low)>>1);
            cnt=0;
            for(int i=0;i<matrix.size();i++)
                cnt=cnt+upper_bound(matrix[i].begin(),matrix[i].end(),mid)-matrix[i].begin();
            if(cnt<k)
                low=mid+1;
            else
                high=mid-1;
        }
        return low;
    }
};

74.Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

首先是最容易想到的解法,对这个m*n阶的矩阵进行遍历,时间复杂度为O(m*n),Leetcode给出的运行时间最快为12ms,最慢为20ms,性能不够稳定,代码如下:

/*solution1 
Traverse the 2D matrix*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()||matrix[0].empty())
            return false;
        int i=0,j=0;
        int row=matrix.size(),col=matrix[0].size();
        for(i=0;i<row;i++)
            for(j=0;j<col;j++)
                if(matrix[i][j]==target)
                    return true;
        return false;
    }
};

下面开始对算法进行优化:

既然是查找,而且元素又按照一定的顺序进行排列,那就要考虑二分算法,我们发现每一行的元素都是有序的,那么对每一行进行遍历,每一行内部使用二分查找,时间复杂度为O(mlogn),见代码:

/*solution2
use binary-search in rows*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()||matrix[0].empty())
            return false;
        int row=matrix.size(),i=0;
        int low=0,size=matrix[0].size(),high=size-1,mid=0;
        for(i=0;i<row;i++){
            low=0;
            high=size-1;
            while(low<=high){
                mid=low+(high-low)/2;
                if(matrix[i][mid]==target)
                    return true;
                if(matrix[i][mid]<target)
                    low=mid+1;
                else
                    high=mid-1;
            }
        }
        return false;
    }
};

提交之后发现这个算法与最快的算法还有一定差距,于是继续思考如何优化。

上面的算法是对每行进行二分查找,既然都能想到对行进行二分查找,那为何不先用二分锁定所在行,之后用二分锁定所在列,这样时间复杂度是O(log m+log n),比刚才的两个算法时间性能上有了很大的提升。代码如下:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()||matrix[0].empty())
            return false;
        int low=0,size=matrix.size(),high=size-1,mid=0;
        while(low<=high){
            mid=low+(high-low)/2;
            if(matrix[mid][0]==target)
                return true;
            if(matrix[mid][0]>target)
                high=mid-1;
            else
                low=mid+1;
        }
        int row=high;
        
        if(row<0)
            return false;
        low=0;
        high=matrix[0].size()-1;
        mid=0;
        while(low<=high){
            mid=low+(high-low)/2;
            if(matrix[row][mid]==target)
                return true;
            if(matrix[row][mid]>target)
                high=mid-1;
            else
                low=mid+1;
        }
        return false;
    }
};

66.Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

一个数组代表了一个数字,现在要将这个数字+1,然后将结果以数组的形式返回。这道题看似简单,但实际处理的时候还是会有很多问题,首先,要维护一个进位,难点在于要处理好如果出现了连续进位的情况。我的思路请见代码:

/*solution1*/
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int i=0,size=digits.size(),carry=1;
        for(i=size-1;i>=0;i--){
            int digit=(digits[i]+carry)%10;
            carry=(digits[i]+carry)/10;
            digits[i]=digit;
            if(carry==0)
                return digits;
        }
        vector<int> res(size+1,0);
        res[0]=1;
        return res;
    }
};

第一版代码很重要,可以说是这类问题的一个通解,carry的初始值随题目所需要加上的值相等,在这道题中当然就是1了。进入循环之后,首先要计算的是末位+1之后对10取模的值,这是加法计算的原则,之后carry的值被更新为’'’carry=(digits[i]+carry)/10;’’‘,如果其大于0,则说明需要进位,因为int类型是向下取整的,需要进位,则向左移动一位,将进位值加到这一位上,以相同的方法继续判断是否需要进位;如果不需要进位则carry==0,直接返回即可。还有一种情况,就是循环结束后发现还是需要进位,例如999这种情况,那么就需要申请一个长度比原来大1 的vector,因为是+1,所以只有可能得到以1开头之后全为0的值,所以很好处理,看代码就好了。

之后看了一下讨论区,发现这道题还有一种钻空子的解法,只适用于plus one的情况,如果不是plus one而是plus two之类的情况就不能用这种方法了。

思路是从最后一位开始判断,如果这一位是9,将其赋值为0,如果不是9,则将其+1并返回;循环结束后如果还没有返回(也就是全为9的情况),那么将其首位赋值为1,调用push_back方法追加一个0即可,代码也十分优雅,请看代码:

/*solution2*/
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int i=0,size=digits.size();
        for(i=size-1;i>=0;i--){
            if(digits[i]==9)
                digits[i]=0;
            else{
                digits[i]++;
                return digits;
            }
        }
        digits[0]=1;
        digits.push_back(0);
        return digits;
    }
};