Leetcode题解（十七）

48、Rotate Image

题目：

分析：题目意思很简单，就是将一个n*n的矩阵顺时针旋转90度。

这道题难度不大，按照旋转的过程走一遍即可。代码如下：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        vector<vector<int>> temp;
        const int size = matrix.size();
        
        temp.resize(size);
        int i,j,k;
        for(i=0;i<size;i++)
        {
            temp[i].resize(size);
        }
        k=size-1;
        for(i=0;i<size;i++)
        {
            for(j=0;j<size;j++)
            {
                temp[j][k] = matrix[i][j];//把一行赋值给temp的一列
            }
            k--;
        }
        matrix = temp;
    }
};

 ---------------------------------------------------------------------------分割线---------------------------------------------------------------------

49、Group Anagrams

题目：

分析：这道题目需要将给定的字符串进行分类。在算法课上，有一种比较经典的算法就是“指纹”算法，将每一个需要被分类的元素求指纹，指纹相同的归为一类。指纹算法中，需要注意的是，指纹相同的元素并不一定是满足要求的同一类元素，指纹不同的元素一定不是同一类元素。比如这道题目中，我可以把每一个字符串的字符相加，相加得到的结果作为字符串的指纹。对指纹相同的字符串，可以多次求指纹，求指纹的方法可以不同，如果每次求指纹得到的结果都一样，则可以认为这两个字符串是同一类，这种算法虽然不是确切算法，多次求指纹可以将误差减小到很小。

代码如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> temp;
        vector< vector<string> > res;
        
        const int size = strs.size();
        bool flag[size];
        memset(flag,size,sizeof(char));
        int mode,finger;
        for(int i=0;i<size;i++)
        {
            if(flag[i] == 0)
            {
                flag[i]=1;
                mode = FingerPrint(strs[i]);
                temp.clear();
                temp.push_back(strs[i]);
                for(int j=i+1;j<size;j++)
                {
                    finger = FingerPrint(strs[j]);
                    if(finger == mode)
                    {
                        if(isSame(strs[i],strs[j]))
                        {
                            temp.push_back(strs[j]);
                            flag[j]=1;
                        }
                            
                    }
                }
            }
            sort(temp.begin(),temp.end());
            res.push_back(temp);    
            
        }
        return res;
    }
    
    int FingerPrint(string str)
    {
        int total = 0;
        int i;
        for(i=0;i<str.length();i++)
        {
            total +=str[i];
        }
        return total;
    }
    bool isSame(string mode,string finger)
    {
        set<char> st1;
        set<char> st2;
        int i;
        for(i=0;i<mode.length();i++)
        {
            st1.insert(mode[i]);
        }
        for(i=0;i<finger.length();i++)
        {
            st2.insert(finger[i]);
        }
        return st1 == st2;
    }
};

提交时间超限了，说明算法复杂度太高，不能满足题目要求，需要进一步改进算法，优化算法。

在网上看了一下别人的解题思路，可以为每一类字符串建立一个hash表，key值为这一类字符串的字符按照字典顺序排列的字符串。

代码如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<string> temp;
        vector< vector<string> > res;
        
        map<string,vector<string>> myMap;
        const int size = strs.size();
        //sort(strs.begin(), strs.end());
        for(int i=0;i<size;i++)
        {
            myMap[getStr(strs[i])].push_back(strs[i]);
        }
        for(map<string, vector<string>>::iterator it =myMap.begin();it != myMap.end();it++)
        {
            sort(it->second.begin(),it->second.end());//如果事先已经对strs排序，这一步就不需要了
            res.push_back(it->second);
        }
        return res;
    }
    string getStr(string str)
    {
        sort(str.begin(),str.end());
        return str;
    }
};

 -------------------------------------------------------------------------分割线----------------------------------------------------------------------

50、Pow(x,n)

题目：

题目要求计算x的n次，也就是一个数学运行，只是需要考虑很多的边界问题。在网上找了一些有关幂运算的详解，链接http://blog.csdn.net/fengbingyang/article/details/12236121

这一篇博客对幂运算做了比较详细的说明，代码也很简单，在理解算法的基础上很容易的实现。