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

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

文章目录

字符串压缩

题目链接

题目描述

字符串压缩。利用字符重复出现的次数,编写一种方法,实现基本的字符串压缩功能。比如,字符串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);
    }
};
上一篇:MATALB 用户界面设计工具


下一篇:2020 ICPC Shanghai Site