刷题笔记～

发表于

到现在为止，刷了pat乙级75道， pat甲级82道，leetcode44道，感觉有点盲目，就开个博客，记录一下刷题过程中遇到比较好的题目和写法.

leercode

字符相同的子字符串

Group Anagrams
本题要求将字母一样的单词分到一起。思路是，把每个单词排序(这样所有字母一样的单词的结果都相同),把这个排序后的单词作为索引，储存原先的单词，这样就分好了类。
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string> > res ; 
        map<string,vector<string> > tmp ; 
        for(auto str: strs) {  
            string temp = str ;  
            sort(temp.begin(), temp.end()) ;  
            tmp[temp].push_back(str) ;  
        }  
        for (auto item: tmp ){
            res.push_back(item.second) ; 
        } 
        return res ; 
    }
};

值得一提的是sort能用于字符串的排序。
c++11之后，for和auto可以用于更简便的迭代和遍历.

类似的题还有 242. Valid Anagram 其中一种解题思路就是，将2个字符串以同一种方式排序，排序后如果相等的话，就证明这2个字符串中的字符相同。

还有438. Find All Anagrams in a String 在一个字符串中，找到所有与目标字符中所有字符相等的所有子字符串，这题用之前那种排序的算法会超时。
解题代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> res , tmp1(256) , tmp2(256) ;
        for ( auto i : p )
            tmp1[i]++ ; 
        int len1 = s.length() , len2 = p.length() ; 
        for ( int i = 0 ; i <len1 ; i++ ){
            tmp2[s[i]]++ ; 
            if ( i >= len2 ) tmp2[s[i-len2]]-- ; 
            if  ( tmp1 == tmp2 )
                res.push_back(i-len2+1) ; 
        } 
        return res ; 
    }
};

维持2个辅助向量，tmp1中储存目标字符串中的字符，用遍历字符串的方法把维持一个与目标字符串长度相同的子字符串，tmp2储存其中的字符信息，如果tmp1和tmp2相同，就代表找到一个。

寻找所有可行路径

62. Unique Paths , 63. Unique Paths II 和 64. Minimum Path Sum 这3道题的中心思想是从 (0,0) 到（i,j) 的 所有路径总数是与（0，0）到（i-1,j)的路径总数和(0,0)到(i,j-1)的路径总数相关。
代码如下：
062 ：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int> > way (m, vector<int> (n,1) ) ; 
        for ( int i = 1 ; i < m ; i++ ) {
            for ( int j = 1 ; j < n ; j++ ) {
                way[i][j] = way[i-1][j] + way[i][j-1] ; 
            }
        }
        return way[m-1][n-1] ; 
    }
};

063: 

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
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obs) {
        int m = obs.size() , n = obs[0].size() , i , j , k ; 
        if ( m == 1 && n == 1 && obs[0][0] == 0 )
            return  1 ; 
        vector<vector<int> > way (m, vector<int> (n,0)) ; 
        if  ( obs[0][0] == 0 )
            way[0][0] = 1 ; 
        for ( i = 1 ; i < n ; i++ ){
            if ( way[0][i-1] == 1 && obs[0][i] == 0 && obs[0][i-1] == 0 ) {
                way[0][i] = 1 ; 
            }
        } 
        for ( i = 1 ; i < m ; i++ ) {
            if ( way[i-1][0] == 1 && obs[i][0] == 0 && obs[i-1][0] == 0 ) { 
                way[i][0] = 1 ; 
            }
        } 
        for ( i = 1 ; i < m ; i++ ) {
            for ( j = 1 ; j < n ; j++ ) {
                if ( obs[i-1][j] == 0 && obs[i][j] == 0 ) {
                    way[i][j] += way[i-1][j] ; 
                }
                if ( obs[i][j-1] == 0 && obs[i][j] == 0 ) { 
                    way[i][j] += way[i][j-1] ; 
                }
            }
        }
        return way[m-1][n-1] ; 
    }
};

064： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) { 
        int m = grid.size() , n = grid[0].size() , i , j , k ; 
        vector<vector<int> > res (m,vector<int> (n,0)) ; 
        res[0][0] = grid[0][0] ; 
        for ( i = 1 ; i < m ; i ++ ) 
            res[i][0] = res[i-1][0] + grid[i][0] ; 
        for ( i = 1 ; i < n ; i ++ )
            res[0][i] = res[0][i-1] + grid[0][i] ; 
        for ( i = 1 ; i < m ; i++ ){
            for ( j = 1 ; j < n ; j++ ){ 
                k = min(res[i-1][j],res[i][j-1]) ;
                res[i][j] = k + grid[i][j] ; 
            }
        }
        return res[m-1][n-1] ; 
    }
};

其中需要注意的问题是res二维向量的初始化问题，根据题目的情景设计。