题目(67)动态口令

题目链接：动态口令

某公司门禁密码使用动态口令技术。初始密码为字符串 password，密码更新均遵循以下步骤：

设定一个正整数目标值 target
将 password 前 target 个字符按原顺序移动至字符串末尾
请返回更新后的密码字符串。

• 示例 1：
  输入: password = “s3cur1tyC0d3”, target = 4
  输出: “r1tyC0d3s3cu”

• 示例 2：
  输入: password = “lrloseumgh”, target = 6
  输出: “umghlrlose”

提示：
1 <= target < password.length <= 10000

---

解题思路

1. 写一个reverse 函数用于反转字符串中指定范围的字符。它接受一个指向字符数组的指针 p1，以及两个整型参数 pos1 和 pos2，分别表示反转范围的起始位置和结束位置。
2. 在函数内部，使用一个临时变量 tmp 进行字符交换的操作，通过循环，不断将 pos1 和 pos2 所指向的字符进行交换，直到 pos1 不再小于 pos2。

总的来说就是:通过循环遍历，将字符串中指定范围内的字符实现反转。

在dynamicPassword函数中调用 reverse 函数来对密码进行反转操作:

1. 首先对整个密码字符串进行反转
2. 然后是从 0 到 len - target - 1 的部分反转
3. 最后是从 len - target 到末尾的部分反转
4. 最终将经过处理后的密码字符串返回

代码

void reverse(char *p1,int pos1,int pos2) {
    int tmp = 0;
    while(pos1 < pos2) {
        tmp = p1[pos1];
        p1[pos1] = p1[pos2];
        p1[pos2] = tmp;
        ++pos1;
        --pos2;
    }
}

char* dynamicPassword(char* password, int target) {
	//求字符串长度
    int len = strlen(password);
    //避免target过大导致重复左旋
    target = target % len;
    reverse(password, 0, len - 1);
    reverse(password, 0, len - target - 1);
    reverse(password, len - target, len - 1);
    return password;
}

---

题目(68)解码异或后的数组

题目链接：解码异或后的数组

未知 整数数组 arr 由 n 个非负整数组成。

经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。

给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。

请解码返回原数组 arr 。可以证明答案存在并且是唯一的。

• 示例 1：
  输入：encoded = [1,2,3], first = 1
  输出：[1,0,2,1]
  解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

• 示例 2：
  输入：encoded = [6,2,7,3], first = 4
  输出：[4,2,0,7,4]

提示：
2 <= n <= 104
encoded.length == n - 1
0 <= encoded[i] <= 105
0 <= first <= 105

---

解题思路

做这道题要知道 n ^ m ^ n = m
题目说 encoded[i] = arr[i] ^ arr[i + 1] ,在等号两边同时按位异或arr[i] ,我们就得到了arr[i] ^ encoded[i] = arr[i] ^ arr[i + 1] ^ arr[i] , 它等价于 arr[i] ^ encoded[i] = arr[i + 1] ,即 arr[i + 1] = arr[i] ^ encoded[i]

以下是详细介绍

1. 首先动态分配一个大小为 (encodedSize + 1) 的整型数组 arr ,用于存储解码后的数组。
2. 将给定的 first 存入 arr[0]。
3. 然后使用一个循环遍历数组 encoded，对每个元素进行解码操作：encoded[i] ^ arr[i]，并将结果存入 arr[i + 1] 中。
4. 最后将解码后数组的大小更新为 encodedSize + 1，并返回解码后的数组 arr。

按位异或的一些基本知识:

n ^ n = 0
n ^ 0 = n
消除：n ^m ^n = m
交换律：n ^ m = m ^ n
结合律：n ^ m ^ z = n ^ (m ^ z)

代码

int* decode(int* encoded, int encodedSize, int first, int* returnSize) {
    int *arr = (int*)malloc(sizeof(int)*(encodedSize + 1));
    arr[0] = first;

    for(int i = 0; i < encodedSize; i++) {
        arr[i + 1] = encoded[i] ^ arr[i];
    }

    *returnSize = encodedSize + 1;

    return arr;
}

---

---