发表于

描述
给一个字符串，然后你重新组合，求组成回文数的最大字符数目。

思路
利用map数据结构保存每个字符出现的次数，显然偶数可以直接加2。为奇数的话，需要判断这个奇数是否大于1，大于1的话需要加上cnt(奇数)-1。又因为奇数可以放在中间，所以有奇数的话可以在最终的结果上再加上1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> chmap;
        for (auto ch : s) {
            chmap[ch]++;
        }
        int sum = 0;
        bool single = false;
        for (auto iter : chmap) {
            if (iter.second & 1) {
                single = true;
                sum += iter.second - 1;
            }
            else {    sum += iter.second;    }
        }
        if (single) { sum++; }
        return sum;
    }
};

参考资料
题目链接

发表于

标准库 < climits >

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define PATH_MAX    259    //定义路径的字符串最大长度

//定义字符类型的范围
#define CHAR_BIT    8      //单字符的bit数
#define MB_LEN_MAX  2      //宽字符最长字符数
#define SCHAR_MIN   (-128) //有符号char类型数的最小值
#define SCHAR_MAX   127    //有符号char类型数的最大值
#define UCHAR_MAX   255    //无符号char类型的最大值

//整数值范围
#define INT_MAX     2147483647
#define INT_MIN     (-INT_MAX-1)
#define UINT_MAX    0xffffffff

#define SHRT_MAX    32767
#define SHRT_MIN    (-SHRT_MAX-1)
#define USHRT_MAX   0xffff

#define LONG_MAX    2147483647L
#define LONG_MIN    (-LONG_MAX-1)
#define ULONG_MAX   0xffffffffUL

发表于

描述
给一个数组nums，分成m份，求每一种分法每一份的最大值的最小值。

有点绕，感觉又是组合爆炸。参考这篇文章后，得到了一些启发。将这个题转换成查找问题，不要被最小值迷惑，我们就求最大值，然后向下逼近。最大值的范围在单个数字最大值和总和之间，从总和开始向下枚举计算。要求这个最大值大于所有的子数组，m则为失败的次数条件，显然m越大，这个最大值可以更加的小，失败数目超过m后显然就不成立了，于是题目就解决了。

下面这个解法会超时，时间复杂度为O(N^2)，可以改进为二分查找。

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
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int left = INT_MIN;
        int right = 0;
        for (auto n : nums) {
            if (left < n) { left = n; }
            right += n;
        }
        int result = right;
        for (int i = right; i >= left; i--) {
            int cnt = 1;
            int subsum=0;
            bool done = false;
            for (auto n : nums) {
                subsum += n;
                if (subsum > i) {
                    cnt++;
                    subsum = n;
                    if (cnt > m) {
                        done = true;
                        break;
                    }
                }
            }
            if (done == false) { result = i; }
            else { break; }
        }
        return result;
    }
};

参考资料
题目链接

`

发表于

普通法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxSum_w1(int a[],int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int tempsum = 0;
        for (int j = i; j < n;j++) {
            //add i to j
            tempsum += a[j];
            if (tempsum > sum) {
                sum = tempsum;
            }
        }
    }
    return sum;
}

分治法

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
    if (left == right) { return a[left]; }
    if (right - left + 1 == 2) {
        int maxelement = std::max(a[left], a[right]);
        return std::max(maxelement, a[left] + a[right]);
    }
    int result_left = recursion(a, n, left, (right+left)/2 );
    int result_right = recursion(a, n, (right + left) / 2 + 1, right);

    int mix_left = a[left + (right - left) / 2];
    int mix_right = a[left + (right - left) / 2 + 1];

    int temp = 0;
    for (int i = left + (right-left)/2; i >= left; i--) {
        temp += a[i];
        if (temp > mix_left) { mix_left = temp; }
    }

    temp = 0;
    for (int i = left + (right - left) / 2+1; i <= right; i++) {
        temp += a[i];
        if (temp > mix_right) { mix_right = temp; }
    }

    int max_temp = std::max(result_left, result_right);

    return std::max(mix_left + mix_right, max_temp);
}

int maxSum_w3(int a[], int n) {
    return   recursion(a, n, 0, n -1);
}

动态规划法

1
2
3
4
5
6
7
8
9
10
11
int maxSum_w2(int a[], int n) {
    if (n <= 1) { return -1000; }
    int all=a[n-1];
    int result=a[n-1];
    if (n <= 2) { return result; }
    for (int i = n - 2; i >= 0; i--) {
        all = std::max(a[i], a[i] + all);
        result = std::max(result, all);
    }
    return result;
}

其中动态规划是时间复杂度最低的，而且代码也较短。相对而言分治法可能会产生更多的bug。

note:可以建立三个cpp文件，包含一个共同的头文件申明，然后主函数只要包含头文件就可以了，这样就不需要写多个main函数那么麻烦了。

发表于

描述
一个求余判断的题目

note:std::to_string(21) 将int转化为string类型，不是21+’0’。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> result;
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                result.push_back("FizzBuzz");
            }
            else if (i % 3 == 0) {
                result.push_back("Fizz");
            }
            else if (i % 5 == 0) {
                result.push_back("Buzz");
            }
            else {
                //string num = "";
                //num += char(i + '0');
                result.push_back(std::to_string(i));
            }
        }
        return result;
    }
};

参考资料
原题链接

发表于

描述
寻找等差数列的个数

样例

1
2
输入: [1,2,3,4]
输出: 3 有[1,2,3],[2,3,4]以及[1,2,3,4]

我的解法
注意到每次多加一个数字后，增加的等差数列个数与当前等差数列的长度有关。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        if (A.size() < 3) { return 0; }
        int gap = A[1]-A[0];
        int len = 2;
        int sum = 0;
        for (int i = 2; i < A.size(); i++) {
            int tempgap = A[i] - A[i-1] ;
            if (tempgap == gap) {
                len++;
                sum += len - 2;
            }
            else {
                len = 2;
                gap = tempgap;
            }
        }
        return sum;
    }
};

其他解法
关键在于对每增加一个长度后对等差数列个数的影响。

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
class Solution {
public:
    int sum1toN(int n) {
        return n * (n + 1) / 2;
    }

    int numberOfArithmeticSlices(vector<int>& A) {
        if (A.size() < 3) { return 0; }
        int gap = A[1] - A[0];
        int len = 0;
        int sum = 0;
        for (int i = 2; i < A.size(); i++) {
            int tempgap = A[i] - A[i - 1];
            if (tempgap == gap) {
                len++;
            }
            else {
                sum += sum1toN(len);
                len = 0;
                gap = tempgap;
            }
        }
        return len=0?sum:sum+sum1toN(len);
    }
};

参考资料
原题链接

发表于

辗转相除

1
2
3
int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a%b);
}

另一种方法
需要实现大整数类，其中大整数可以用string或者数组保存。

1
2
3
4
5
int gcd2(BigInt a, BigInt b) {
    if (a < b) { return gcd2(b, a); }
    if (b == 0) { return  a; }
    else {    return gcd2(a - b, b);    }
}

发表于

描述
返回第三大的数

样例

1
2
输入: [1,2,2,3]
输出: 1

思路
<(￣︶￣)↗[GO!],这个题目好简单啊!排序完，再调用一下unique就ok了。然而效率是硬伤。

我的解法

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int thirdMax(vector<int>& nums) {
        sort(nums.begin(), nums.end(),greater<int>());
        if (nums.size() < 3) { return nums[0]; }
        auto uend = unique(nums.begin(), nums.end());
        if (uend - nums.begin() < 3) { return nums[0]; }
        return nums[2];
    }
};

另一个解法

set的运用，消除重复值
set与vector的区别:首先，vector是序列式容器而set是关联式容器。set包含0个或多个不重复不排序的元素。也就是说set能够保证它里面所有的元素都是不重复的。另外对set容器进行插入时可以指定插入位置或者不指定插入位置。如insert(v.begin(),1),也可以直接用insert(1)。
set默认从小到大排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int thirdMax(vector<int> & nums) {
        set<int> numsets;
        for (int n : nums) {
            numsets.insert(n);
            if (numsets.size() > 3) {
                numsets.erase(numsets.begin());
            }
        }
        return numsets.size() >= 3 ?  *numsets.begin() : *numsets.rbegin();
    }
};

参考资料
原题

发表于

描述:
输入一个整数，将其转化为16进制。若为负数，则取它的补码进行运算。

输入输出样例
样例1

输入: 26
输出: 1a

样例2

输入: -1
输出: ffffffff

解题思路
将这个数对16求余，之后除以16，依次从低位转换。

note:负数的补码处理可以采用 unsigned int x = num 和 x /= 16处理。 也可以采用 num = ~(-num)+1 加上 x >> 4 处理，int 是32位的，每次移动 4 位，一共可以移动 8 次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string toHex(int num) {
        if (num == 0) { return "0"; }
        unsigned int x = num;
        //int x = num > 0 ? num : ~(-num) + 1;

        string res = "";
        do {
            int ret = x % 16;
            x /= 16;
            if (ret < 10) { res = to_string(ret) + res; }
            else { res = char('a'+ret%10)+res; }
        } while (x);
        return res;
    }
};

参考资料
原题

发表于

描述
将两个字符相加，两个字符代表大整数，有5100多位，不能用int表示。

我的解法

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    string addStrings(string num1, string num2) {
        int len1 = num1.size();
        int len2 = num2.size();
        int maxlen = len1 > len2 ? len1 : len2;
        string str_sum ="";
        int overflow = 0;
        for (int i = 0; i < maxlen; i++) {
            int sumtemp = 0;
            //common partion
            if (i < len1 && i < len2) {
                sumtemp = (num1[len1 - i - 1]-'0') + (num2[len2 - i - 1] -'0');
                if (overflow == 1) {
                    sumtemp ++;
                    overflow = 0;
                }
                if (sumtemp >= 10) {
                    overflow = 1;
                    sumtemp -= 10;
                }
            }
            else if (len1 > len2) {
                sumtemp = num1[len1-i-1]-'0';
                if (overflow == 1) {
                    overflow = 0;
                    sumtemp++;
                }
                if (sumtemp >= 10) {
                    sumtemp -= 10;
                    overflow = 1;
                }
            }
            else if (len1 < len2) {
                sumtemp = num2[len2 - i-1]-'0';
                if (overflow == 1) {
                    overflow = 0;
                    sumtemp++;
                }
                if (sumtemp >= 10) {
                    sumtemp -= 10;
                    overflow = 1;
                }
            }
            str_sum=to_string(sumtemp)+str_sum;
        }
        if (overflow == 1) { str_sum= "1" + str_sum; }
        return str_sum;
    }
};

更佳的解法
引用值得学习，overflow的产生值得学习，求余的方式值得学习，采用short和long值得学习。
参考链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string addStrings(string num1, string num2) {
        string & longstr = (num1.size() > num2.size()) ? num1:num2;
        string & shortstr = (num1.size() <= num2.size()) ? num1:num2;
        string result = "";
        int overflow = 0;
        for (int i = longstr.size() - 1,  j = shortstr.size() - 1; i >= 0; i--, j--) {
            int tempsum = 0;
            if (j >= 0) {
                tempsum = longstr[i] - '0' + shortstr[j] - '0'+ overflow;
            }
            else {
                tempsum = longstr[i] - '0' + overflow;
            }
            overflow = tempsum / 10;
            result = char(tempsum % 10+'0') + result;
        }
        if (overflow) {
            result = '1' + result;
        }
        return result;
    }
};

参考资料
原题链接