LeetCode开心刷题二十六天——49.Group Anagrams50. Pow(x, n)

蔚落 2021-10-26 15:12 87阅读 0赞

49. Group Anagrams

Medium

1824116FavoriteShare

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
    Output:
    [
      ["ate","eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]
    bonus：
    1.join function usage:

str = "-";
    seq = ("a", "b", "c"); # 字符串序列
    print str.join( seq );

result:
    a-b-c

class Solution:
        def groupAnagrams(self, strs):
            res = {}
            for item in strs:
                k = ''.join(sorted(item))  # 字符串排序
                print("k")
                print(k)
                print("sorted")
                print(sorted(item))
                if k not in res:  # 判断是否存在
                    res[k] = []
                res[k].append(item)  # 相同字符串放到同一个字典 k中
            return [res[x] for x in res]  # 输出结果
    
    
    if __name__ == '__main__':
        strs = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
        solu = Solution()
        print(solu.groupAnagrams(strs))

C++ version Analyse:

This time appears some small problem such as forget iterator,new variable during two-dimension vector loop forget to define.

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<map>
    #include<algorithm>
    using namespace std;
    class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            //map get value
            map<string,vector<string>> temp;
            vector<vector<string>> res;
            //middle handle
            for(int i=0;i<strs.size();i++)
            {
                string str=strs[i];
                sort(str.begin(),str.end());
                if(temp.find(str)==temp.end())
                {
                    vector<string> tmp1={};
                    temp[str]=tmp1;
                }
                temp[str].push_back(strs[i]);
    //            cout<<str<<endl;
    
            }
    
            //Assign the second value of the map to the vector.
            for(map<string,vector<string>>::iterator it=temp.begin();it!=temp.end();it++)
            {
                //pushback is a function it need a variable to get the value it output by.push_back
                res.push_back((*it).second);
            }
            return res;
        }
    };
    
    int main()
    {
        Solution s;
        vector<string> strs={
         "eat", "tea", "tan", "ate", "nat", "bat"};
        vector<vector<string>> res;
        res=s.groupAnagrams(strs);
        //cout<<res<<endl;
        //output result
        for(vector<vector<string>>::iterator ite=res.begin();ite!=res.end();ite++)
        {
    
            //whenever use a new variable remember to define variables
            vector<string> tmp_vec=*ite;
            //iterator variable must add ::iterator
            for(vector<string>::iterator it=tmp_vec.begin();it!=tmp_vec.end();it++)
            {
                cout<<*it<<" ";
            }
            cout<<endl;
        }
        return 0;
    }

Special Attention the two-dimensional loop way,please don't check next time:

for(vector<vector<string>>::iterator ite=res.begin();ite!=res.end();ite++)
        {
    
            //whenever use a new variable remember to define variables
            vector<string> tmp_vec=*ite;
            //iterator variable must add ::iterator
            for(vector<string>::iterator it=tmp_vec.begin();it!=tmp_vec.end();it++)
            {
                cout<<*it<<" ";
            }
            cout<<endl;
        }

50. Pow(x, n)

Medium

9002214FavoriteShare

Implement [pow(*x*, *n*)][pow_x_n], which calculates *x* raised to the power *n* (xn).

Example 1:

Input: 2.00000, 10
    Output: 1024.00000

Example 2:

Input: 2.10000, 3
    Output: 9.26100

Example 3:

Input: 2.00000, -2
    Output: 0.25000
    Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

*  \-100.0 < *x* < 100.0

*n* is a 32-bit signed integer, within the range \[−231, 231 − 1\]

Method Idea：

Use recursion to finish this problem logn,divide the solution into first juge the minus or positive,then only if index=0 return 1,other situation multiply x or divide into small parts

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<algorithm>
    using namespace std;
    class Solution {
    public:
        double myPow(double x, int n) {
            return n>=0?myPowImp(x,n):1.0/myPowImp(x,n);}
    private:
        double myPowImp(double x,int n){
            if(n==0)  return 1;
            return myPowImp(x*x,n/2)*(n%2?x:1);
        }
    };
    int main()
    {
        Solution s;
        double x=2.00000;
        int n=10;
        double res=s.myPow(x,n);
        cout<<res<<endl;
        return 0;
    }

Python version has the same idea:
    Bonus:
    　　1.recursive itself should add self.myPow(x,n-1) use self to add the function name
    　　2.three special version,if minus,let minus to x-->1/x,change n-->-n
    　　3.judge whether n%2 to x*x,n/2 or (x,n-1)*x

class Solution(object):
        def myPow(self, x, n):
            if n==0:
                return 1
            if n<0:
                x=1/x
                n=-n
            if n%2:
                return x*self.myPow(x,n-1)
            return self.myPow(x*x,n/2)
    
    solu=Solution()
    x=2
    n=10
    print(solu.myPow(x,n))

转载于:https://www.cnblogs.com/Marigolci/p/11252171.html

[pow_x_n]: http://www.cplusplus.com/reference/valarray/pow/