leetcode 191：统计1的个数；5 最长回文串；54，59 蛇形矩阵

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int k=0;   //统计次数
        while(n>0){
            n &= (n-1);   //每次消掉一个1
            k++;   //统计消掉1的次数
        }
        return k;  
    }
};

解法：从下标为0开始，到下标为s的长度减1，对于每个字符都要计算

1）以这个字符为中心的回文串的长度（奇数串）；

2）以这个字符和下个字符为中心的回文串的长度（偶数串）。

注意：既要统计回文串为奇数时，又要统计回文串为偶数时，故要循环两次分开统计。

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        int maxlen = 1;
        int start = 0;
        
            //aba
            for(int i=0; i<len; i++){
                int j = i-1;
                int k = i+1;
                while(j>=0 && k<len && s[j]==s[k]){
                    if(k-j+1 > maxlen){
                        maxlen = k-j+1;
                        start = j;
                    }
                    j--;
                    k++;
                }
            } 
            //abba
            for(int i=0; i<len; i++){
                int j = i;
                int k = i+1;
                while(j>=0 && k<len && s[j]==s[k]){
                    if(k-j+1 > maxlen){
                        maxlen = k-j+1;
                        start = j;
                    }
                    j--;
                    k++;
                }
            } 
        
        return s.substr(start, maxlen);
    }
};

string longestPalindrome(string s) {
        
        int len = s.length();
        if(len == 0) return "";
        string res = s.substr(0,1);
        
        for(int i=0;i<=len-2;++i){
            
            string temp = mid_to_side(s,i,i);
            if(temp.length() > res.length()) //回文串为奇
                res = temp;
            temp = mid_to_side(s,i,i+1);
            if(temp.length() > res.length()) //回文串为偶
                res = temp;
        
        }
        
        return res;
        
        
    }；
    
    
    string mid_to_side(string s, int left, int right){
        
        while(left >= 0 && right <= s.length()-1 && s[left] == s[right]){
            
            --left;
            ++right;
        }
        return s.substr(left+1, right-left-1);
    }

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        string res = s.substr(0,1);
        
        for(int i=0; i<len; i++){
            //aba
            string temp = palin(s,i-1,i+1);
            if(temp.size()> res.size())
                res = temp;
                
            //abba
            temp = palin(s,i,i+1);
            if(temp.size()> res.size())
                res = temp;
            } 
            
        return res;
    }
    
    string palin(string s, int j, int k){
        int maxlen = 1;
        int start = 0;
        while(j>=0 && k<s.size() && s[j]==s[k]){
            if(k-j+1 > maxlen){
                maxlen = k-j+1;
                start = j;
            }
                j--;
                k++;
        }
        return s.substr(start, maxlen);
    }
};

leetcode 191：统计1的个数；5 最长回文串；54，59 蛇形矩阵

我把重复的代码写成一个函数调用之后更慢了==

leetcode 191：统计1的个数；5 最长回文串；54，59 蛇形矩阵

求 n! 中0的个数。

思路：计算0的个数，也就是计算10的个数，即计算包含的2和5组成的pair的个数，因为5的个数比2少，所以2和5组成的pair的个数由5的个数决定。

观察15! = 有3个5(来自其中的5, 10, 15)，所以计算15/5=3就可以。

25! = 有6个5(有5个5来自其中的5, 10, 15, 20, 25，另外还有1个5来自25=(5*5)的另外一个5），

所以要循环计算n/5，直到商为0。

class Solution {
public:
    int trailingZeroes(int n) {
        int result = 0, k = 0;
        while(n>0){
            k = n/5;   //统计 n! 是5的几幂次
            result += k;
            n = k;
        }
        return result;
    }
};

螺旋矩阵：

leetcode 191：统计1的个数；5 最长回文串；54，59 蛇形矩阵

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return {};
        
        int m = matrix.size();  //行数
        int n = matrix[0].size();   //列数
        
        vector<int> res;
        int up = 0, down = m-1, left = 0, right = n-1;
        while(true){
            for(int j = left; j<=right;j++)
                res.push_back(matrix[up][j]);
            
            if(++up > down) break;
            
            for(int j = up; j<=down; j++)
                res.push_back(matrix[j][right]);
            
            if(--right < left) break;
            
            for(int j = right; j>= left; j--)
                res.push_back(matrix[down][j]);
            
            if(--down < up) break;
            
            for(int j = down; j >= up; j--)
                res.push_back(matrix[j][left]);
            
            if(++left>right) break;
        }
        return res;
    }
};

leetcode 191：统计1的个数；5 最长回文串；54，59 蛇形矩阵

注意下需要设置一个val变量，它的取值是不断递增的。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int left = 0, right = n-1, top = 0, down = n-1, val = 1;
        vector<vector<int>> res(n, vector<int> (n,0));   //初始化res为n个vector<int>的对象，每个又包含n个0
        while(true){
            for(int j = left; j<=right; j++)
                res[top][j] = val++;
            if(++top > down) break;
            
            for(int j = top; j<=down; j++)
                res[j][right] = val++;
            if(--right < left) break;
            
            for(int j = right; j>=left; j--)
                res[down][j] = val++;
            if(--down < top) break;
            
            for(int j = down; j>=top; j--)
                res[j][left] = val++;
            if(++left > right) break;
            
        }
        return res;
    }
};

leetcode 191：统计1的个数；5 最长回文串；54，59 蛇形矩阵

相关推荐