Leetcode/AlgoExpert 解题笔记 – Array 篇 (1)
嗨大家好，这系列的文章主要是想纪录我在写 Leetcode / AlgoExpert 的题目时的一些所思所想，跟大家分享之余也做个笔记，方便日後需要的时候可以回顾。
因为是第一篇，所以先牛刀小试一下，这则文章里的题目都是跟 Array 有关的题目，难度基本上都是 Leetcode easy 的 level。另外，在这系列的文章里面将会使用 Java 作为实作的程序语言。
那就废话不多说，让我们开始吧！
Squares of a Sorted Array
题目
给定一个 int[] nums，里面元素为 non-decreasing 排列，需回传一个 array 以 non-decreasing 排列平方後的元素。
Example
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Brute Force
最暴力的解法就是，我们先迭代 nums 得出平方後的 array（以范例来说就是 [16, 1, 0, 9, 100]，然後再 sort 这个 array。
但是这样 time compleity 会取决你用的 sorting method，可见下表。
但不管使用哪种 sorting algorithm，time complexity 都没有比 好。
Improvement
要有比较好的 performance，我们必须要利用题目给的线索，那就是 non-decreasing。input 跟 output 都要是 non-decreasing order，但我们不能直接把 output 照 input 的顺序排，因为有的负数平方过後会比正数的平方来得大。
但是我们可以注意到一件事，正数与正数之间或是负数与负数之间，在平方过後的顺序是会一致的。如果把正数跟负数拆开，两边都按照顺序排列，每次都从两者中挑出比较大的那个放入目标，然後继续看下一个，如此两两一组去看，最後就可以排出来了。
这麽说有点模糊，想像成两组人，两组都按身高从高排到低。一开始看两边最高的人谁高，假设第一排的人比较高，就把他叫去第三排当第一个，然後再接着比第一排第二高的人跟第二排最高的人谁高，高的就叫他离开原本那排去第三排接着排队，以此类推直到所有人都排到第三排为止。
所以其实我们要做的就是让正数自己一排，负数也一排，要怎麽做？我们就让负数从 array 的头开始，然後让正数从 array 的尾巴开始，两两比较他们的「绝对值」，谁比较大就把它平方，然後塞到要 return 的 array 的最尾巴。接着，如果是头的数被移掉，头就往右边一格；反之，如果是尾巴被移掉，就往左边一格。
你可能想，如果头在往右移的过程中，指到的数字变成正的；或是尾巴在往左移的过程中，指到的数字变成负的怎麽办？其实不影响，因为头如果变成指到正数，代表剩下的都是正数，所以尾巴指的数字接下来一定都比头指到的大，也就是说头接下来都不会移动了，反之亦然。我们只要重复这个操作到头跟尾巴指到同一个数字即可。
而整个过程我们只有迭代 input array 一次，而且每次的操作都是 constant time，所以总 time complexity 为 。
Implementation
class Solution {
public int[] sortedSquares(int[] nums) {
int start = 0;
int end = nums.length-1;
int inserting = nums.length-1;
int[] sorted = new int[nums.length];
while (start != end) {
int startValue = nums[start] * nums[start];
int endValue = nums[end] * nums[end];
if (startValue > endValue) {
sorted[inserting] = startValue;
start += 1;
} else {
sorted[inserting] = endValue;
end -= 1;
}
inserting -= 1;
}
sorted[inserting] = nums[start] * nums[start];
return sorted;
}
}
Duplicate Zeros
题目
给定一个固定长度 array int[] nums，将 array 里面出现的每个 0 复制一次，并把所有元素往右移。如果超过 array 长度，则丢弃那些溢出的元素。
不可以另外建立新的 array 回传，必须修改原有的 array（in-place operation）。
Example
Input: [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
观察
这题因为不能额外建立新的 array 去储存，所以我们只能去修改原本的 array。可是麻烦的是我们必须要 duplicate 0，这会导致接在 0 後面的元素被盖掉。
要解决这问题，我们就要用变数去记住稍後会被盖掉的元素，可是当 0 很多个或是连续出现好几个的时候，我们就要提前去记住接下来很多个会被盖掉的元素，逻辑会很复杂，也没办法预预测你必须要保留多少个会被盖掉的变数，如此就要用 array-like 的资料结构去记，那就失去不能使用新的 array 这个限制的意义了。
Brute Force
我们可以观察到，一定是後面的元素会被前面的挤掉，不会是前面被後面挤掉，因为整个 array 是往右 shift 的。
我们也可以发现，只要有一个 0 出现，那就代表从 array 的尾巴会有一个元素被挤掉。所以，我们就从 array 的头开始出发，每遇到一个 0，我们就把从这个 0 以後的所有元素往右一格，直到最後一个元素就行。
Implementation
class Solution() {
public void duplicateZeros(int[] arr) {
if (arr == null || arr.length == 0) return;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
for (int j = arr.length-1; j > i; j--) {
arr[j] = arr[j-1]; // 把每个元素都往右移
}
i++; // 跳过被 duplicate 的 0，从原本 array 下一个元素继续
}
}
}
}
但是这个解法的 time complexity(in worst case) 会是 ，可以看到我们的 for loop 包了两层，这个解法的迭代过程有点类似 bubble sort。
较好的解法
我们可以先透过扫描一次 array 去知道，从第几个元素开始，後面的元素都会因为溢出而不会被写到 array 里。然後，从这个位置开始往 array 的头回推，遇到 0 的话就填入两个 0，不是 0 的话就填入该元素就好。
下面是示意图
因为我们已经算过到第几个元素会是储存的界限，所以你会看到，留下来的 array 中有几个 0，就应该是这个留下来的 array 的长度跟初始 array 长度的差。（e.g. [1,0,2,3,0,4] 长度为 6，有两个 0，6+2 刚好会是初始 array [1,0,2,3,0,4,5,0] 的长度。
我们就从 4 开始往回，从初始 array 的最後一个往回塞，遇到 0 就连续填两个 0；遇到其他的就填入当下遇到的数字。
Implementation
class Solution() {
public void duplicateZeros(int[] arr) {
int lastValidIndex = 0; // 纪录最後不会溢出的元素 index
int count = 0; // 纪录是否已经超出 array 长度
while (true) {
if (arr[lastValidIndex] == 0) {
count += 2; // 如果是 0，要占两格
} else {
count += 1;
}
// 若前面元素占掉的空间已经超过 array 长度，就跳出，否则继续往下算
if (count < arr.length) {
lastValidIndex += 1;
} else {
break;
}
}
// 如果 count 超出长度，代表最後一个是 0，而且这个 0 所产生的 duplicate 溢出，不会重复。
// 把最後一个填入 0，而且把有效的 index 往左一格
int insertingIndex = arr.length-1;
if (count > arr.length) {
arr[arr.length-1] = 0;
insertingIndex -= 1;
lastValidIndex -= 1;
}
for (int i = lastValidIndex; i >= 0; i--) {
if (arr[i] == 0) { // 0 -> 填入两个 0，下一个填入的 index 往左两格
arr[insertingIndex] = 0;
arr[insertingIndex-1] = 0;
insertingIndex -= 2;
} else { // 非 0 -> 填入该元素，下一个填入的 index 往左一格
arr[insertingIndex] = arr[i];
insertingIndex -= 1;
}
}
}
}
Merge Sorted Array
题目
给定 int[] nums1、int[] nums2，其中 nums1 含有 m 个元素，nums2 含有 n 个元素，两者皆为 sorted (in asecnding order)。
将两者合并成一个 sorted array (in ascending order)，必须将 nums2 合并到 nums1 中，不可建立新的 array，extra memory space 只能为 。
另外，nums1 的长度为 m+n，但只有前 m 个元素为有值的元素，後面的 n 个为 0，不代表数字 0，而是空值的意思。
Examples
Input:
nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]
Output: [1,2,2,3,5,6]
Brute Force
每次从 nums2 取出一个元素（称 b），从 nums1 的头开始迭代，找到 b 对应插入的位置後，将後面的 nums1 元素全部往右一格。
接着，继续迭代下一个 nums2 元素，从插入上一个 nums2 元素的位置继续往下比对，找到要插入的位置後，一样把该位置後面的所有 nums1 元素往右移一格。如此反覆操作直到 nums2 元素全部迭代完。
trick
每次插入 nums2 元素时，可以检查是不是插在当下最後面了，如果是的话，就代表这个 nums2 的元素已经比所有 nums1 元素来得大。因此接下来就直接把剩下的 nums2 元素从这个位置往後依序排放即可。
不过这个解法并不好，有以下两个原因
- 我们要迭代每个
nums2的元素，在处理每一个nums2的元素，又要先迭代nums1的所有元素，找到插入位置後，又要把此位置後的元素全部往右移，因此又要再迭代一次。这样三层包下来，time complexity会是。
- 逻辑不好写，要设置往右移的起点跟终点，没写好的话可能会遇到 index out of bounds 的问题。
较好的解法
我们要怎麽 improve 上面的解法呢？答案就是我们从 後面 开始比较，不要从前面。
因为 nums1 前 m 个元素跟 nums2 前 n 个元素都是从小排到大，而且 nums1 後 n 个 entry 都是空的，所以我们就从 nums1 的第 m 个还有 nums2 的第 n 个开始比大小，谁比较大谁就去从 nums1 的最後面插入 nums1。接着，拿下一个元素往下，如此两两比较到 nums1 或 nums2 的第一个元素已经被放到後面为止。
Implementation
class Solution() {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - 1; // nums1 从第 m 个开始比
int index2 = n - 1; // nums2 从第 n 个开始比
int inserting = m + n - 1; // 从 nums1 的最後面开始 insert
while (true) {
if (index1 < 0) { // 如果 nums1 的 m 个全部被取完
// 剩下的都是 nums2，把 nums2 剩下的放到 nums1 最前面
for (int i = index2; i >= 0; i--) {
nums1[i] = nums2[i];
}
break;
}
if (index2 < 0) { // 如果 nums2 的 n 个全部被取完
// 剩下的都是 nums1，不用动
break;
}
// 两者皆尚未取完
int val1 = nums1[index1];
int val2 = nums2[index2];
if (val1 > val2) { // nums1 的比较大
nums1[inserting] = val1;
index1 -= 1; // 指到 nums1 下一个元素
} else { // nums2 的比较大
nums1[inserting] = val2;
index2 -= 1; // 指到 nums2 下一个元素
}
inserting -= 1; // 插入的位置往左移一格
}
}
}
Remove Element
题目
给定一个 int[] nums 和一个 int val，计算nums 中不等於 val 的个数有几个（假设为 N），并且修改 nums，让其前 N 个元素是那些不等於 val 的元素（顺序不重要）。
此题必须要修改原有的 nums，不可额外建立新的 array 或其他 data structures，extra space memory 为 。
Examples
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3] (不用考虑这五个元素排列顺序)
较差的解法
假设 val 在 nums 里面有 m 个，array size 为 n，那麽我们要做的就是把其他元素放在 array 的前 n-m 个。
一个较差的解法就是一样分别从头尾两端去检查，因为我们要把等於 val 的元素往後送，所以只要检查到前面的元素是 val 而且後面的元素是 val 时，我们就把两者互换，并且两个指标都往中间继续靠拢。
然後，如果上面条件不成立，那就还要看两个条件。如果前面指标指到的元素是 val，那就不能继续往後跳，要等後面的指标指到不是 val 的元素时要互换，如果前面指到的元素不是 val，那就继续往後跳。 而後面的指标则相反，指到不是 val 的元素时要停下来，否则继续往前。
Implementation
class Solution {
public int removeElement(int[] nums, int val) {
if (nums.length == 0) return 0;
int start = 0;
int end = nums.length - 1;
while (start < end) {
if (nums[start] == val && nums[end] != val) {
nums[start] = nums[end];
nums[end] = val;
end -= 1;
}
if (nums[end] == val) {
end -= 1;
}
if (nums[start] != val && start < end) {
start += 1;
}
}
if (nums[end] == val) {
return end;
} else {
return end+1;
}
}
}
但是可以看到，这个解法写起来有点麻烦，而且需要去考虑 start 跟 end 的关系，像是 nums 里面只有一个或零个元素时，没有处理好就可能会出现 index out of bound。
Read/Write Pointer (Fast-Slow Pointer)
我们可以使用一样使用两个指标来解这题，只不过这次我们让两者都从 array 的最前面开始，我们取名为 read、write。所谓 Read/Write 是指一个指标用於读取、一个用於写入，读取的会比写入跑得快，当条件符合的时候，会把读取指标指到的元素 copy 给写入指标的元素。
如果 read 指到的元素不是 val，那就把值 assign 给 read 所在的那格，并且两者都往後一格；如果 read 指到的元素是 val，那就不动，继续往下。
这个解法乍听下来不知道为什麽可以 work，但其实很简单，我们让 read 从 nums 第一格往後，就是会迭代每一个元素。而当它指到的元素不是 val 时，就会把这个值往前塞，总共会塞几次？答案是 n-m 次，因为总共有 n 个元素，其中有 m 个等於 val，所以不等於 val 的就是 n-m。而 write 一开始也是指到 nums 第一格（index 为 0），而它只有在 read 指到的元素不是 val 时才会将指到的该格往下，总共会进行 n-m 次，所以会将 nums 前 n-m 格换成不是 val 的元素，而且不会有重复的问题，因为 read 只会指到每个元素一次。
Implementation
class Solution {
public int removeElement(int[] nums, int val) {
int pointer1, pointer2;
pointer1 = pointer2 = 0;
while (pointer2 < nums.length) {
if (nums[pointer2] != val) {
nums[pointer1] = nums[pointer2];
pointer1++;
pointer2++;
} else {
pointer2++;
}
}
return pointer1;
}
}
这个解法不仅 performance 来得好一点，更重要的是大大地提升了阅读性。
:::info
此题与 Remove Duplicates from Sorted Array 非常相似，可以互相参考。
:::
Replace Elements with Greatest Element on Right Side
题目
给定一 int[] arr，将每个元素替换成该元素右边所有元素中最大值，最後一个元素则替换成 -1。
不可建立新的 array，extra space complexity 为 。
Examples
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Brute Force
要将每个元素替换成右边最大的元素，那就迭代每个元素，则该元素被迭代的时候，再用一层 for loop 去迭代该元素「右边的所有元素」（0 -> 1,2,3,4,5 / 1 -> 2,3,4,5 ...）。
在迭代右边所有元素的过程中，记下出现的最大值，然後把该元素替换成最大值，如此重复到 array 倒数第二个元素就行，因为最後一个没有右边的元素，直接替换成 -1。
虽然简单明了，但是可以想见，这个解法的 time complexity 不会好，因为它叠了两层的 for loop，time complexity 会是 ，是一个 brute force 的解法。
Implementation
class Solution {
public int[] replaceElements(int[] arr) {
int max;
for (int i = 0; i < arr.length-1; i++) {
max = arr[i+1];
for (int j = i+2; j < arr.length; j++) {
if (arr[j] > max) {
max = arr[j];
}
}
arr[i] = max;
}
arr[arr.length-1] = -1;
return arr;
}
}
较好的解法
有没有办法只迭代一次 array 我们就可以完成这项任务呢？是可以的！我们只要从 array 的末端开始就办得到。
可以看到，从前面开始的话我们会遇到一个问题，假设我们第一次迭代整个 array 找到最大值，但我们不能把这个最大值应用到所有人身上，因为随着往右走的过程中，会越过这个成为最大值的元素，接下来这些元素其右边所有元素的最大值就不是整个 array 的最大值了，所以我们又要重新去找。
但是如果从末端开始就没有这个问题，我们再从末端找回尾端的过程中一直纪录最大值，到了该元素时，就直接把该元素替换成目前的最大值就行了。不过我们要注意，这个元素是不是大於最大值，如果是的话，就要把最大值替换成这个元素，最大值替换成元素，元素替换成最大值，不是会互相覆盖吗？没错，要做这种 swapping 的话就必须要有一个额外的变数来暂存其中ㄧ者。
Implementation
class Solution {
public int[] replaceElements(int[] arr) {
// initialize maximum to the last entry
int max = arr[arr.length-1];
// replace last entry with -1
arr[arr.length-1] = -1;
int temp;
// iterate the array from the end
for (int i = arr.length-2; i > -1; i--) {
// store current iterating entry to temp
temp = arr[i];
// assign maximum to the current iterating entry
arr[i] = max;
// compare temp with maximum to decide new maximum
if (temp > max) {
max = temp;
}
}
return arr;
}
}
只迭代了一次 array，time complexity 瞬间从 掉到
，Leetcode 的 runtime 则从 143ms 直接掉到 1ms。
Sort Array By Parity
题目
给定一个 int[] A，里面的每个元素都为 non-negative integers，回传一个 array，里面所有偶数 elements 必须排列在所有奇数 elements 前面。（不用考虑偶数与偶数间、奇数与奇数间的顺序）
Examples
Input: [3,1,2,4]
Output: [2,4,1,3] / [2,4,3,1] [4,2,1,3] / [4,2,3,1]
O(N) for both Time & Space
因为这个题目是要求回传一个 array，没有规定不能用新的 array，所以是可以建立新的 array。
我们可以建立一个新的 array int[] B，长度与 A 相同。接着我们可以 loop through A，遇到奇数的时候放到 B 的尾端，并且把尾端往左一格；遇到偶数的时候放到 B 的头端，并且把头端往右一格，直到迭代完 A 的所有元素。
虽然这个解法的 time complexity 为 ，但是 space complexity 也为
。
较好的解法
前面讲了这麽多题现在应该也猜到，较好的解法就是要用 in-place operation，将 time complexity 维持在 的同时也将 space complexity 降为
。
而应该也不难猜到，我们要使用的技巧就是前面遇到烂的 two-pointer technique。
而这题我们将两个 pointer 分别从 array 的头与尾开始，我们的目标是要将偶数全部放到前面、奇数全部放到後面。所以也就是说，从前面开始的 pointer 遇到奇数时，应该要把它往後丢、从後面开始的 pointer 遇到偶数时，应该要把它往前丢。
所以当这两个条件都成立的时候，我们就把两者位置互换，让奇数去後面、後数去前面。那如果只有一个条件成立呢？那就是让条件不成立的那个 pointer 继续往中间移动，直到两个条件成立。什麽时候会停？当两个 pointer 交会的时候就停下来。
Implementation
class Solution {
public int[] sortArrayByParity(int[] A) {
int start = 0; // 从前面开始的 pointer
int end = A.length-1; // 从後面开始的 pointer
int temp; // 用於 swapping
while (start < end) { // 当两者还没交会，继续往中间找
// 两个条件都成立，互换，并且都往中间移动一格
if (A[end] % 2 == 0 && A[start] % 2 == 1) {
temp = A[end];
A[end] = A[start];
A[start] = temp;
start += 1;
end -= 1;
} else {
// 後面的不是偶数，往下（中间）一格找
if (A[end] % 2 == 1) {
end -= 1;
}
// 前面的不是奇数，往下（中间）一格找
if (A[start] % 2 == 0) {
start += 1;
}
}
}
return A;
}
}
>>: Day 26 - 当AI有了常识之後, 超越人类? -GAN(2)
D-28-dotnet cli ? build ? run
产生了专案之後 昨天经由大头的代领小光终於完成建置环境，并且也产生了他人生中第一个专案，虽然最後在H...
资产分类准则（asset classification guideline）
分类方案适用於整个组织。RD负责人定义一个是不合适的。此外，由於发布了资产分类准则，这意味着分类方...
Base64
即使HTTP基本身份验证确实使用Base64来编码用户ID和密码，HTTP仍以明文形式传输编码，并依...
那些被忽略但很好用的 Web API / 结语
Web API -- Application Programming Interface for ...
Day 21 | 3D蛇走迷宫AR游戏开发Part2 -角色蛇移动
昨天的文章已把场景与平面侦测做好，今天要继续说明角色蛇的移动 目录 移动机制说明 变数宣告 介面按钮...