题意

以字符串的形式给一个二进制数，对这个二进制数循环右移$kk$k位，求右移结果的十进制的值。

二进制位数小于等于$6363$63

方法

模拟

按照题意，我们操作字符串k次，每次移动一位，63次后得到了目标的二进制表示的字符串

再对二进制字符串进行转化成10进制，需要注意的是这里是long long 不是int

代码

class Solution {
public:
    /**
     * 位移后二进制串的十进制值
     * @param str string字符串 二进制字符串
     * @param k int整型 循环位移次数
     * @return long长整型
     */
    long long rotateRight(string str, int k) {
        for(int i = 0;i<k;i++){
            char ch = str[str.length()-1];
            str = ch+str;
            str.pop_back();
        }
        long long res = 0;
        for(int i = 0;i<str.length();i++){
            res*=2;
            res+= str[i]-'0';
        }
        return res;
    }
};

复杂度分析

时间复杂度:

我们首先操作字符串k次, 每次将字符串最后一位移动到最前，时间复杂度为 $O\left(k\right)O(k)$O(k)

然后是进制转换，对每一位进行操作一次所以复杂度是$O\left(len\right(str\left)\right)O(len(str))$O(len(str)),综上 总时间时间复杂度为$O(k+len(str\left)\right)O(k+len(str))$O(k+len(str))

空间复杂度: 只用了常数大小的额外空间来记录结果和做for循环,所以空间复杂度为$O\left(1\right)O(1)$O(1)

抽象优化

如果我们需要算$11$1到$nn$n的和，我们并不需要循环从$11$1到$nn$n,而是可以直接求和公式,同样，虽然说题目描述是循环右移，那么可以看一下当前位置与实际位置的区别，从意义上完成一个等效的操作，而不去实际操作它

以样例数据为例

这样的位置可以用取模汇总成一个表达式

令 $f\left(i\right)=\left(len\right(str)+i-k)modlen\left(str\right)f(i)=\; (len(str)+i-k)\backslash bmod\; len(str)$f(i)=(len(str)+i−k)modlen(str), $f\left(实际位置\right)=当前位置f(实际位置)=当前位置$f(实际位置)=当前位置

因此原来的进制转换是s[0 ~ len(str)-1],现在变成s[f(0) ~ f(len(str)-1)]

代码

class Solution {
public:
    /**
     * 位移后二进制串的十进制值
     * @param str string字符串 二进制字符串
     * @param k int整型 循环位移次数
     * @return long长整型
     */
    long long rotateRight(string str, int k) {
        long long res = 0;
        for(int i = 0;i<str.length();i++){
            res*=2;
            res+= str[((int)str.length()-k+i)%str.length()]-'0';
        }
        return res;
    }
};

复杂度分析

时间复杂度: 我们省去了字符串的操作步骤，直接转换，每一位一次运算，以时间复杂度是$O\left(len\right(str\left)\right)O(len(str))$O(len(str))

空间复杂度: 只用了常数大小的额外空间来记录结果和做for循环,所以空间复杂度为$O\left(1\right)O(1)$O(1)