笔试强训之每日一题(九)

字符串压缩

题目链接

题目描述

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例1:

输入："aabcccccaaa"
输出："a2b1c5a3"

示例2:

输入："abbccd"
输出："abbccd"
解释：“abbccd"压缩后为"a1b2c2d1”，比原字符串长度更长。

题目思路

通过遍历字符串，当S[i] != S[i+1]时，首先将S[i]放到ret中，然后把连续相等的数字转换成字符串，将该字符串放到ret中，最后将count设置为1，当S[i] == S[i+1]时，count++，count用来记录连续的个数。

题目代码

class Solution {
public:
    string compressString(string S) 
    {
        string ret;
        int count = 1;
        for(int i = 0;i<S.size();i++)
        {
            if(S[i] != S[i+1])
            {
                ret += S[i];
                //把数字转换成字符串
                //123->"123"
                string temp = to_string(count);
                //char temp = '0'+count;
                ret+=temp;
                count = 1;
            }
            else
            {
                count++;
            }
        }
        if(ret.size()>=S.size())
            return S;
        else
            return ret;
    }
};

配对交换

题目链接

题目描述

配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。

示例1:

输入：num = 2（或者0b10）
输出 1 (或者 0b01)

示例2:

输入：num = 3
输出：3

题目思路

交换某个整数的奇数位和偶数位，只需要将偶数位右移一位就变成了奇数位，将奇数位左移一位就变成了偶数位。用一个变量odd将偶数位全为1奇数位全是0的二进制数保存起来，num&odd得偶数位是num的偶数位，奇数位都为0，用一个变量even将偶数位全为0奇数位全是1的二进制数保存起来，num&even得奇数位是num的奇数位，偶数位都为0，odd和even相加得奇数位和偶数位互换后得值。

题目代码

class Solution {
public:
    int exchangeBits(int num) {
        //1011 -> 0111
        //奇数位：0 1
        //偶数位：1 1
        //用两个变量odd和even保存奇数位和偶数位：
        //偶数位右移一位变成奇数位，奇数位左移一位变成偶数位：0010,0101 0111
        
        //1、先保存奇数位和偶数位
        int odd = 0b10101010101010101010101010101010;//ood&num相当于将偶数位保存起来了
        int even = 0b01010101010101010101010101010101;//even&num相当于将奇数位保存起来了
        odd &= num;//偶数位是num的偶数位，奇数位都为0
        even &= num;//奇数位是num的奇数位，偶数位都为0
        return (odd>>1)+(even<<1);
    }
};