update week01 assignment-2

SpongeMa · SpongeMa · commit 5631c6f02b6a · 2020-06-15T13:46:36.000+08:00
diff --git a/Week01/1-twoSum.js b/Week01/1-twoSum.js
diff --git a/Week01/66-plusOne.js b/Week01/66-plusOne.js
@@ -0,0 +1,88 @@
+/*
+ * @lc app=leetcode.cn id=66 lang=javascript
+ *
+ * [66] 加一
+ */
+
+// @lc code=start
+/**
+ * @param {number[]} digits
+ * @return {number[]}
+ */
+
+/**@sponge
+ * 解法一：
+ * 一开始的想法但是发现Number数据类型整数位超过16位，超过的部分会全部置0
+ * 参考@gatsby-23，将Number数据类型改为ES10基本类型BigInt可以表示任意大的整数
+ * 
+ * 1.已知传入参数必定为数值型数组
+ * 2.将参数转换为字符型（Array.prototype.join()）
+ * 3.由字符型变为BigInt型（BigInt构造函数)）
+ * 4.进行专属于BigInt类型的数学计算
+ * 5.计算结果再次变为字符型（String构造函数）
+ * 6.将字符型数值变更为数组（String.prototype.split()）
+ * 
+ * runtime: 72ms beats46.22%
+ * memory usage: 33.3MB beats 100%
+ */
+var plusOne = function(digits) {
+  let num = BigInt(digits.join(''));
+  // BigInt基本类型进行数学操作时，需要在数字字面量后加个n
+  let string = String(num + 1n);
+  let ary = string.split('');
+
+  return ary.map(str => Number(str));
+};
+
+/**@sponge 
+ *  解法二：
+ *  1.当末位为9的情况：末位为9需要进位所以当前值置0，
+ *   继续往前看有没有需要进位的数，没有则前一位+1并return
+ *  2.当末位不为9的情况：直接将末位+1并return
+ *  3.当数组里的数都为9的情况：由于遍历的每个数都为9，所以全部置0，
+ *   然后跳出循环，在数组开头插入1并return
+ *  时间复杂度：O(n)
+ *  runtime: 72ms beats46.22%
+ *  memory usage: 32.7MB beats 100%
+ */
+var plusOne = function (digits) {
+  let len = digits.length;
+  
+  for (let i = len - 1; i >= 0; i--) {
+    if(digits[i] == 9)
+      digits[i] = 0;
+    else {
+      digits[i]++;
+      return digits;
+    }
+  }
+  //数组都为9的情况
+  digits.unshift(1)
+  return digits;
+};
+
+/**@other  
+ *  解法三：余数法，类似的解法
+ *  1.末位+1，将当前值置为余数，根据余数看是否需要进位：
+ *    1-余数为0的情况：余数为0说明当前值为10,所以当前值为余数0
+ *    2-余数不为0的情况：直接return
+ *  2.当数组里的数都为9的情况：由于遍历的每个数都为9，所以遍历的每一位余数都为0
+ *    最后会跳出循环往下执行，将数组长度+1，每个数置0，第一位置1并return
+ *  时间复杂度：O(n)
+ *  runtime: 56ms beats98.1%
+ *  memory usage: 32.4MB beats 100%
+ */
+var plusOne = function(digits) {
+  const len = digits.length;
+  for(let i = len - 1; i >= 0; i--) {
+      digits[i]++;
+      digits[i] %= 10;
+      if(digits[i]!=0)
+          return digits;
+  }
+  digits = [...Array(len + 1)].map(_=>0);;
+  digits[0] = 1;
+  return digits;
+};
+
+// @lc code=end
diff --git a/Week01/88-mergeTwoArray.js b/Week01/88-mergeTwoArray.js
@@ -0,0 +1,66 @@
+/*
+ * @lc app=leetcode.cn id=88 lang=javascript
+ *
+ * [88] 合并两个有序数组
+ */
+
+// @lc code=start
+/**
+ * @param {number[]} nums1
+ * @param {number} m
+ * @param {number[]} nums2
+ * @param {number} n
+ * @return {void} Do not return anything, modify nums1 in-place instead.
+ */
+
+
+ /**@sponge
+  * 解法一：双指针
+  * runtime:76ms,beats 34.25%
+  * memory usage:32.9MB,beats 100%
+  */
+var merge = function(nums1, m, nums2, n) {
+  let len = nums1.length;
+  nums1.splice(m,len-m);
+  console.log(nums1)
+  let j=0;
+  let lastIndex=0;
+  while(j<n){
+    let cur =nums2[j];
+    for(let i =lastIndex;i<nums1.length;i++ ){
+      console.log('j:',j,'cur:',cur,'i:',i,'nums1[i]:',nums1[i])
+      if(cur<nums1[i]){
+        nums1.splice(i,0,cur);
+        lastIndex = i+1;
+        break;
+      }else if( cur==nums1[i]){
+        nums1.splice(i+1,0,cur);
+        lastIndex = i+2;
+        break;
+      }
+      if(cur>nums1[i]&&i==nums1.length-1){
+        nums1.push(cur);
+        lastIndex = nums1.length-1;
+        break;
+      }
+        
+    }
+    j++;
+  }
+
+};
+
+/**@sponge
+ * 解法二：先concat->sort
+ * 注意：需要考虑如果sort参数缺省的话，排序会按照数据的第一位的unicode码来排序
+ * runtime:72ms,beats 54.29%
+ * memory usage:33.2MB,beats 100%
+ */
+var merge = function(nums1, m, nums2, n) {
+  let len = nums1.length;
+  nums1.splice(m,len-m,...nums2);
+  nums1.sort((a,b)=>a-b);
+};
+
+// @lc code=end
+
