精华内容
下载资源
问答
  • 循环移位

    2017-12-11 20:28:00
    今天面试,被考一道循环移位的算法问题:有一数组,N个元素,循环移动K个元素,要求算法时间复杂度为O(N)。 当时,还真被难住了。回来后,查查资料,才发现,这真是个操蛋的题啊。 特此记录下来,供有需要事...

    今天面试,被考一道循环移位的算法问题:有一数组,N个元素,循环移动K个元素,要求算法时间复杂度为O(N)。

     

    当时,还真被难住了。回来后,查查资料,才发现,这真是个操蛋的题啊。

     

    特此记录下来,供有需要事使用

     

    ——————————————————————————————————————————————————-

    #include <stdio.h>

    #include <stdlib.h>

     

    char arr[5] = {'0', '1', '2', '3', '4'};

     

    void shift(int left, char* arr, int N, int K)

    {

        K = K%N;

        int vbit = 0==left?N-K:K;

        int *sp = (int*)malloc(vbit*sizeof(char));

        int i = 0, s = 0;

        for(; i<vbit; i++)

        {

            sp[i] = arr[i];

        }

        for(; i<N; i++, s++)

        {

            arr[s] = arr[i];

        }

        for(i=0; s<N;i++,s++)

        {

            arr[s] = sp[i];

        }

     free(sp);

    }

     

    void reverse(char* arr, int start, int end)

    {

        for(; start<end; start++,end--)

        {

            int s = arr[end];

            arr[end] = arr[start];

            arr[start] = s;

        }

    }

     

    void shift_effi(int left, char* arr, int N, int K)

    {

        K = K%N;

        int vbit = 0==left?N-K:K;

        reverse(arr, 0, vbit-1);

        reverse(arr, vbit, N-1);

        reverse(arr, 0, N-1);

    }

     

    void main()

    {

       

        printf("source:\n");

        for(int i=0; i<5; i++)

        {

            printf("%c", arr[i]);

        }

     

        printf("\n");

     

        printf("left shift 2 unit\n");

        shift(1, arr, 5, 2);

        for(int i=0; i<5; i++)

        {

            printf("%c", arr[i]);

        }

     

        printf("\n");

     

        printf("right shift 4 unit\n");

        shift(0, arr, 5, 4);

        for(int i=0; i<5; i++)

        {

            printf("%c", arr[i]);

        }

        printf("\n");

     

        shift(0, arr, 5, 3);

        printf("source:\n");

        for(int i=0; i<5; i++)

        {

            printf("%c", arr[i]);

        }

       

        printf("\n");

     

        printf("left shift 2 unit\n");

        shift_effi(1, arr, 5, 2);

        for(int i=0; i<5; i++)

        {

            printf("%c", arr[i]);

        }

     

        printf("\n");

     

        printf("right shift 4 unit\n");

        shift_effi(0, arr, 5, 4);

        for(int i=0; i<5; i++)

        {

            printf("%c", arr[i]);

        }

        printf("\n");

     

    }

    //result

    # ./LeftRightShift
    source:
    01234
    left shift 2 unit
    23401
    right shift 4 unit
    34012
    source:
    01234
    left shift 2 unit
    23401
    right shift 4 unit
    34012

    其中,shift_effi就是时间复杂度为N,空间复杂度为1的算法要求。

    Finally:

    作为工程师,被要求现场作法,有时候还真是头疼,毕竟,工程师还不等同于数学家。

    转载于:https://www.cnblogs.com/woodzcl/p/8024891.html

    展开全文
  • 在这里,我为循环反转和循环移位编写了简单的函数代码。
  • 循环移位补码.rar

    2021-02-06 17:02:50
    输入一个左边界数值(下记作a),一个右边界数值(下记作b),选择结果类型,如果选择循环移位,输入循环移位数值(正数右移,负数左移),针对 [a, b]区间内的每个数值n,先将十进制变成二进制,按照指定数值(正数...
  • 循环移位算法

    2020-04-04 13:51:00
    目录循环移位法数组循环移位方法一:取模法方法二:时间换空间方法三:空间换时间三次翻转法字符串移位暴力法用空间换时间取模法链表循环移位 循环移位法 参考文章:内容连接。文章主要从数组,字符串,链表三种情况...

    循环移位法

    参考文章:内容连接。文章主要从数组,字符串,链表三种情况下,介绍循环移位的具体实现。这里只梳理一下文章脉络。

    数组循环移位

    方法一:取模法

    这个方法在 Leetcode 189 中已经用过了,作者这里考虑了两种新情况:

    • 如果移位位数 K 是数组长度 len(s) 的倍数的话,那么就不用移位了;
    • 如果 K 是负数,就是往相反方向(向左移)

    方法二:时间换空间

    如果要解决上面的问题,那我们便一次一次的考虑,总共移动 K 次。这样时间复杂度变成了 O(N*K),最大可达 O(N^2)。

    方法三:空间换时间

    就是将数组长度变成原来的两倍,拼在一起。这在 leetcode-189 也有相关的描述。

    三次翻转法

    所谓“翻转”,比如[0,N],就是把 0 和 N 交换位置,1和(N-1)交换位置……。算法描述:

    • 先把[0, n - k - 1]翻转
    • 然后把[n - k, n - 1]翻转
    • 最后把[0, n - 1]翻转

    这个算法其实很好证明。我们用箭头代表方向:

    • 初始数组为 A->B | C->D
    • 经过前两次反转后变成了 B<-A | D<-C
    • 最后整体翻转,C->D | A->B
    • 翻转看箭头的方向就好了,这是自己想的比较直观的证明。实现翻转的代码描述为:
    while (start < end) {
        t = list[start];
        list[start] = list[end];
        list[end] = t;
        start++;
        end--;
    }
    

    字符串移位

    这里给出的例题为检查是否包含的问题。直观解法是每移动一次就判断一次,那么需要判断 len(s) 次。

    暴力法

    就是上面最直观的方法。实现思路是:已知 S1 和 S2,每次都把 S1 左移一位,用指针 P1 和 P2 开始对两个字符串开始检查;每左移一次,两个指针就循环检查一次。

    用空间换时间

    拼接两个 S1 字符串,然后用两个指针开始对于新的 S1 和 S2 进行检查。

    取模法

    取模法实际上是对于空间换时间算法的取巧。我们假设 S1 后面还有一个 S1,实际上是用取模的方法实现的。

    链表循环移位

    源于 leetcode-61,难度中等。这里便不再展开了。

    展开全文
  • 循环移位密码

    2016-05-17 09:44:53
    java实现循环移位密码 将明文中字字母数字用R位后的字母数字进行替换
  • 大家知道,大家用MCU写程序的时候,只有移位的语句,没有循环移位的语句。那么如何实现循环移位呢,详见下述。
  • 介绍了数组循环移位操作实例,有需要的朋友可以参考一下
  • 循环移位:循环左移和循环右移

    万次阅读 多人点赞 2018-04-30 15:35:46
    换句话说,循环移位就是将移出的低位放到该数的高位(循环右移)或把移出的高位放到该数的低位(循环左移),左移,和右移动都是对整数进行的操作,在Win32控制台应用程序中,整形占4Byte节32bit。 &nbsp; &...

           循环移位就是把数值变成二进制,然后循环移动的过程;换句话说,循环移位就是将移出的低位放到该数的高位(循环右移)或把移出的高位放到该数的低位(循环左移),左移,和右移动都是对整数进行的操作,在Win32控制台应用程序中,整形占4Byte节32bit。


           循环左移的过程:
    这里写图片描述
           循环左移的过程可以分为3步:
    1. 将x左端的n位先移动到y的低n位中,x>>(32-n);
    2. 将x左移n位,其右面低位补0,x<<n;
    3. 进行按位或运算(x >> (32 - n) | (x << n));


           循环右移的过程:

    这里写图片描述
           循环右移的过程可以分为3步:
    1. 将x的左端的低n位先移动到y的高n位中x<<(32-n)
    2. 将x右移n位,其左面高n位补0x>>n;
    3.进行按位或操作(x << (32 - n) | (x >> n));


            假如将一个无符号的数据val,长度为N,需要循环移动n位。可以利用下面的公式:
            循环左移:(val >> (N - n) | (val << n))
            循环右移:(val << (32 - n) | (val >> n))


           C语言实现循环移位:循环移位是对二进制序列进行操作,所以实现循环移位先需要将需要移位的数转换为二进制序列,然后按照上面描述的步骤进行移位,最后将移位后的二进制序列打印出来;

    源代码

    #include <stdio.h>
    #include <Windows.h>
    
    //将一个十进制数转换为二进制
    void  trans_binary(unsigned int  val)
    {
        int a[32];
        int i = 0;
        for(i=0;i<=31;i++)
        { 
            a[i] = val % 2;
            val /= 2;
        }
        //倒序输出,每输出8位,输出一个空格
        for (int j = 31,k = 1; j >= 0; j--,k++)
        {
            printf("%d", a[j]);
            if (k % 8 == 0)
            {
                printf(" ");
            }
        }
        printf("\n");
    }
    
    //循环左移
    
    void left_move(unsigned val, int n)
    {
        unsigned int z;
        printf("需要移位的二进制序列为:\n");
        trans_binary(val);
        z = (val >> (32 - n) | (val << n));
        printf("移位后:\n");
        trans_binary(z);
    }
    
    void right_move(unsigned val, int n)
    {
        unsigned int z;
        printf("需要移位的二进制序列为:\n");
        trans_binary(val);
        z =  (val << (32 - n) | (val >> n));
        printf("移位后:\n");
        trans_binary(z);
    }
    
    int main()
    {
        int num = 0;
        int n = 0;
        int select = 0;
        printf("请输入要移位的数和移动位数:\n");
        scanf("%d%d", &num, &n);
        printf("请输入选择:(-1-:左移 -2-:右移 -0-:退出):\n");
        scanf("%d", &select);
        switch (select)
        {
        case 1:left_move(num, n);
            printf("\n");
            break;
        case 2:right_move(num, n);
            break;
        case 0:exit(0);
            break;
        default:
            printf("输入有误!\n");
            break;
        }
        system("pause");
        return 0;
    }

    运行结果

    这里写图片描述

            为了更直观的显示结果,选取了一个比较大的数1234567891,移动位数:8,移动方式:循环左移;根据循环左移的方法,先取出高8(移动的位数)位,移动到底8位(右移24位),然后将其余位数依此左移8位,结果与运行结果一致。

    展开全文
  • MATLAB循环移位

    2021-04-10 08:58:17
    matlab循环移位操作 需求,拿到了两个以时间为变量函数,形状差不多但是有时间差,为了比对主要信号区间的差异,需要对齐,便想到了circshift的操作,这个函数感觉做相关,循环卷积这种操作,应该是非常顺手的,...

    matlab循环移位操作

    需求,拿到了两个以时间为变量函数,形状差不多但是有时间差,为了比对主要信号区间的差异,需要对齐,便想到了circshift的操作,这个函数感觉做相关,循环卷积这种操作,应该是非常顺手的,记录一下

    1.circshift用法极其简单

    Y = circshift(A,K)

    如果指定第几个维度循环位移: Y = circshift(A,K,dim)

    K是标量,就对第一维循环位移,K是矩阵,就分别对应的维度循环位移
    正数代表下、右方向移位,负数代表左、上方向移位

    2.举例

    % 产生数据------------------------------------
    a =
    
         1     2     3
         4     5     6
         7     8     9
    % 向下移位------------------------------------
    >> circshift(a,1)
    ans =
    
         7     8     9
         1     2     3
         4     5     6
    
    >> circshift(a,[1,1])
    % 向下移位,同时向右移位------------------------
    ans =
    
         9     7     8
         3     1     2
         6     4     5
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,107
精华内容 1,642
关键字:

循环移位