2018-07-14

693. 交替位二进制数

题目描述

给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

示例 1:

输入: 5
输出: True
解释:
5的二进制数是: 101
示例 2:

输入: 7
输出: False
解释:
7的二进制数是: 111
示例 3:

输入: 11
输出: False
解释:
11的二进制数是: 1011
示例 4:

输入: 10
输出: True
解释:
10的二进制数是: 1010

思路

转换成二进制，判断即可

代码

class Solution {
public:
    bool hasAlternatingBits(int n) {
        
        vector<int> tmp;
        while(n)
        {
            tmp.push_back(n%2);
            n/=2;
        }
        
        for(int i=0;i<tmp.size()-1;i++)
        {
            if(tmp[i]==tmp[i+1])
                return false;
        }
        return true;
        
    }
};

561. 数组拆分 I

题目描述

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:

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

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:

n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].

思路

通过定义，我们可以看出，本题要求的就是排好序之后，偶数位元素之和<_>,嘻嘻

代码

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int ret = 0;
        for(int i = 0;i<nums.size()-1;i+=2)
        {
            ret += nums[i];
        }
        return ret;
        
    }
};

371. 两整数之和

题目描述

不使用运算符 + 和-，计算两整数a 、b之和。

示例：
若 a = 1 ，b = 2，返回 3。

思路

知道这个题是用二进制做，但是没找出规律，看了网上的解答，思路如下：

1、输入 a，b 
2、按照位把ab相加，不考虑进位，结果是 a xor b，即1+1 =0 0+0 = 0 1+0=1，进位的请看下面 
3、计算ab的进位的话，只有二者同为1才进位，因此进位可以标示为 (a and b) << 1 ，注意因为是进位，所以需要向左移动1位 
4、于是a+b可以看成 （a xor b）+ （(a and b) << 1），这时候如果 (a and b) << 1 不为0，就递归调用这个方式吧，因为（a xor b）+ （(a and b) << 1） 也有可能进位，所以我们需要不断的处理进位。

代码

class Solution {
public:
    int getSum(int a, int b) {
        int result = a ^ b; // 按位加
        int carray = (a & b) << 1; // 计算进位
        if(carray!=0) return  getSum(result,carray); //判断进位与处理
        return result;
    }
};

412. Fizz Buzz

题目描述

写一个程序，输出从 1 到 n 数字的字符串表示。

1. 如果 n 是3的倍数，输出“Fizz”；

2. 如果 n 是5的倍数，输出“Buzz”；

3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

示例：

n = 15,

返回:
[
"1",
"2",
"Fizz",
"4",
"Buzz",
"Fizz",
"7",
"8",
"Fizz",
"Buzz",
"11",
"Fizz",
"13",
"14",
"FizzBuzz"
]

思路

这个题的难点在于int转换为string，幸亏，C++11已经有全局函数支持这个了LOL（to_string）

代码

class Solution {
public:
    vector<string> fizzBuzz(int n) {
       vector<string> ret;
        for(int i = 1;i<=n;i++)
        {
            if(i%3==0&&i%5==0)
                ret.push_back("FizzBuzz");
            else if(i%3==0)
                ret.push_back("Fizz");
            else if(i%5==0)
                ret.push_back("Buzz");
            else
                ret.push_back(to_string(i));
        }
        return ret;
        
    }
};