0703学习 agile Posted on Jul 3 2023 面试 leetcode学习 - 剑指 Offer 05. 替换空格 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 ```C# public string ReplaceSpace(string s) { var sb = new StringBuilder(); foreach (var t in s) { if (t == ' ') { sb.Append("%20"); } else { sb.Append(t); } } return sb.ToString(); } ``` --- - 剑指 Offer 58 - II. 左旋转字符串 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。 ```C# public string ReverseLeftWords(string s, int n) { var sb = new StringBuilder(); for (int i = n; i < n + s.Length; i++) { sb.Append(s[i % s.Length]); } return sb.ToString(); } ``` --- - 剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 --- ```C# public int FindRepeatNumber(int[] nums) { for (var i = 0; i < nums.Length; i++) { var t = nums[i]; var index = i; while (t != index) { nums[index] = nums[t]; if (nums[index] == t) { return t; } nums[t] = t; t = nums[index]; } } return -1; } ``` --- - 剑指 Offer 53 - I. 在排序数组中查找数字 I 统计一个数字在排序数组中出现的次数。nums 是一个非递减数组 --- ```C# private int __FindTarget(int[] nums, int target) { var left = 0; var right = nums.Length - 1; while (left <= right) { var mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else { return mid; } } return -1; } private int __FindMinTarget(int[] nums, int target, int targetIndex) { var index = targetIndex - 1; while (index >= 0) { var minTarget = nums[index]; if (minTarget < target) { break; } index--; } return index; } private int __FindMaxTarget(int[] nums, int target, int targetIndex) { var index = targetIndex + 1; while (index < nums.Length) { var minTarget = nums[index]; if (minTarget > target) { break; } index++; } return index; } public int Search(int[] nums, int target) { var targetIndex = __FindTarget(nums, target); if (targetIndex == -1) { return 0; } var left = __FindMinTarget(nums, target, targetIndex); var right = __FindMaxTarget(nums, target, targetIndex); return right - left - 1; } // 以下优化基于：查找完右边界 right == i后，则nums[j]指向最右边的target(诺存在) public int Search2(int[] nums, int target) { return __Help(nums, target) - __Help(nums, target - 1); } private int __Help(int[] nums, int target) { var left = 0; int right = nums.Length - 1; while (left <= right) { var mid = left + (right - left) / 2; if (nums[mid] <= target) { left = mid + 1; } else { right = mid - 1; } } return left; } ``` - 剑指 Offer 53 - II. 0～n-1 中缺失的数字 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 --- 二分法 ```C# // 左闭右开时，当left = right时，[left, right）是无意义的 public int MissingNumber2(int[] nums) { int left = 0, right = nums.Length; //区间为：左闭右开 while (left < right) { int m = left + (right - left) / 2; if (nums[m] == m) left = m + 1; else right = m; } return left; } //左闭右闭时，当left = right时，[left, right]是有意义的 public int MissingNumber(int[] nums) { var left = 0; var right = nums.Length - 1; while (left <= right) { var mid = left + (right - left) / 2; if (nums[mid] == mid) { left = mid + 1; } else { right = mid - 1; } } return left; } ``` ---- (异或)XOR 是 exclusive OR 的缩写。英语的 exclusive 意思是 "专有的，独有的"，可以理解为 XOR 是更单纯的 OR 运算。 我们知道，OR 运算的运算子有两种情况，计算结果为`true`。 （1）一个为 true，另一个为 false; （2）两个都为 true。 上面两种情况，有时候需要明确区分，所以引入了 XOR。 XOR 排除了第二种情况，只有第一种情况（一个运算子为`true`，另一个为`false`）才会返回 true，所以可以看成是更单纯的 OR 运算。也就是说， **XOR 主要用来判断两个值是否不同。** XOR 一般使用插入符号（caret）`^`表示。如果约定`0` 为 false，`1` 为 true，那么 XOR 的运算真值表如下。 > ``` > 0 ^ 0 = 0 > 0 ^ 1 = 1 > 1 ^ 0 = 1 > 1 ^ 1 = 0 > > > ``` 二、运算定律 ------ XOR 运算有以下的运算定律。由于非常简单，这里就省略证明了。 （1）**一个值与自身的运算，总是为 false。** > ``` > x ^ x = 0 > > > ``` （2）**一个值与 0 的运算，总是等于其本身。** > ``` > x ^ 0 = x > > > ``` （3）**可交换性** > ``` > x ^ y = y ^ x > > > ``` （4）**结合性** > ``` > x ^ (y ^ z) = (x ^ y) ^ z > > > ``` 三、应用 ---- 根据上面的这些运算定律，可以得到异或运算的很多重要应用。 ### 3.1 简化计算 多个值的异或运算，可以根据运算定律进行简化。 > ``` > a ^ b ^ c ^ a ^ b > = a ^ a ^ b ^ b ^ c > = 0 ^ 0 ^ c > = c > > > ``` ### 3.2 交换值 两个变量连续进行三次异或运算，可以互相交换值。 假设两个变量是`x`和`y`，各自的值是`a`和`b`。下面就是`x`和`y`进行三次异或运算，注释部分是每次运算后两个变量的值。 > ``` > x = x ^ yy = x ^ yx = x ^ y > > ``` 这是两个变量交换值的最快方法，不需要任何额外的空间。 ### 3.3 加密 异或运算可以用于加密。 第一步，明文（text）与密钥（key）进行异或运算，可以得到密文（cipherText）。 > ``` > text ^ key = cipherText > > > ``` 第二步，密文与密钥再次进行异或运算，就可以还原成明文。 > ``` > cipherText ^ key = text > > > ``` 原理很简单，如果明文是 x，密钥是 y，那么 x 连续与 y 进行两次异或运算，得到自身。 > ``` > (x ^ y) ^ y > = x ^ (y ^ y) > = x ^ 0 > = x > > > ``` ### 3.4 数据备份 异或运算可以用于数据备份。 文件 x 和文件 y 进行异或运算，产生一个备份文件 z。 > ``` > x ^ y = z > > > ``` 以后，无论是文件 x 或文件 y 损坏，只要不是两个原始文件同时损坏，就能根据另一个文件和备份文件，进行还原。 > ``` > x ^ z > = x ^ (x ^ y) > = (x ^ x) ^ y > = 0 ^ y > = y > > > ``` 上面的例子是 y 损坏，x 和 z 进行异或运算，就能得到 y。 四、一道面试题 ------- 一些面试的算法题，也能使用异或运算快速求解。 请看下面这道题。 > 一个数组包含 n-1 个成员，这些成员是 1 到 n 之间的整数，且没有重复，请找出缺少的那个数字。 最快的解答方法，就是把所有数组成员（A[0] 一直到 A[n-2]）与 1 到 n 的整数全部放在一起，进行异或运算。 > ``` > A[0] ^ A[1] ^ ... ^ A[n-2] ^ 1 ^ 2 ^ ... ^ n > > > ``` 上面这个式子中，每个数组成员都会出现两次，相同的值进行异或运算就会得到 0。只有缺少的那个数字出现一次，所以最后得到的就是这个值。 你可能想到了，加法也可以解这道题。 > ``` > 1 + 2 + ... + n - A[0] - A[1] - ... - A[n-2] > > > ``` 但是，加法的速度没有异或运算快，而且需要额外的空间。如果数字比较大，还有溢出的可能。 下面是一道类似的题目，大家可以作为练习。 > 一个数组包含 n+1 个成员，这些成员是 1 到 n 之间的整数。只有一个成员出现了两次，其他成员都只出现一次，请找出重复出现的那个数字。 ------ ```C# // 我们知道异或具有交换律 // 只需要把所有的数字都异或一遍，最终的结果就是我们要求的那个数字 public int MissingNumber3(int[] nums) { if (nums.Length <= 0) { return 0; } int xor = 0; for (int i = 0; i < nums.Length; i++) xor = xor ^ nums[i] ^ (i + 1); //0 到 length 之间总共有length + 1位数 //但是nums[]的下标为0，length - 1 //i的实际下标应该为 1，length +1 return xor; } ``` 0630学习 0704学习