JavaScript盲点记录----(二)

文章目录

最近在练习JavaScript题目时发现有些实现自己立即并不能想出来，而且有些常见的方法的用法理解是有错误的如parseInt，所以记录一下。这是第二篇，定要温故而知新 。^_^

1. 动态规划求最长子序列。
   思想:
   动态规划步骤：

   描述最优解的结构
   递归定义最优解的值
   按自底向上的方式计算最优解的值
   由计算出的结果构造一个最优解

   对于LCS：

   if i=0 或者 j=0 c[i][j] = 0
   if i,j>0 且 xi=yj c[i][j] = c[i-1,j-1]+1
   if i,j>0 且 xi!=yj c[i][j] =max(c[i-1,j],c[i,j-1])

   代码:

   const UP = 0;
   const LEFT_UP = 1;
   function LCS(str1, str2) {
   
       var l1 = str1.length
       var l2 = str2.length
       var c = [], b = []
       for (var i = 0; i <= l1; i++) {
           b[i] = []
           c[i] = []
           c[i][0] = 0
       }
       for (var j = 0; j <= l2; j++) {
           c[0][j] = 0
       }
       for (var i = 1; i <= l1; i++) {
           for (var j = 1; j <= l2; j++) {
               if (str1[i - 1] === str2[j - 1]) {  // 注意取值
                   c[i][j] = c[i - 1][j - 1] + 1
                   b[i][j] = LEFT_UP
               } else if (c[i - 1][j] >= c[i][j - 1]) {
                   c[i][j] = c[i - 1][j]
                   b[i][j] = UP
               } else {
                   c[i][j] = c[i][j - 1]
               }
           }
       }
       return {
           c: c,
           b: b
       };
   }
   function printLCS(b, str1, i, j) {
       if (i == 0 || j == 0) {
           return
       }
       if (b[i][j] == LEFT_UP) {
           printLCS(b, str1, i - 1, j - 1)
           console.log(str1[i - 1])
       } else if (b[i][j] == UP) {
           printLCS(b, str1, i - 1, j)
       } else {
           printLCS(b, str1, i, j - 1)
       }
   }

   分析:
   LCS 时间复杂度是O(mn)， printLCS 时间复杂度是O(m+n)

   变种题目：给定一个字符串S,可以从中删除一些字符，使得剩下的串是一个回文串，如何删除才能使得回文串最长呢？

2. 在一个数的编码中，若任意两个相邻的代码只有一位二进制不同，则这种编码为格雷码，给定一个整数n,请返回n位的格雷码，顺序从0 开始
   思想：
   递归： n4位格雷码是由n-1 位格雷码 生成的。 如n=2 时，格雷码是[00,01,11,10], n=3时，是对n=2 的格雷码首位添加‘0’或‘1’，添加1后应逆序

   代码：

   function createGray(n) {
       var result = [];
       if (n == 1) {
           result = ["0", "1"]
           return result
       }
       var last_result = createGray(n - 1)
       var temp = []
       for (var i = 0; i < last_result.length; i++) {
           temp.unshift('1' + last_result[i])
           result[i] = '0' + last_result[i]
       }
       result =  result.concat(temp)
       return result
   
   }

3. 反转一个DOM元素的所有子节点的顺序

   function reverseChildNodes(node){
       var frag = node.ownerDocument.createDocumentFragment()
       while(node.lastChild){
         frag.appendChild(node.lastChild)
       }
       node.appendChild(frag)
   }

   appendChild()方法不只是可以向document的某节点插入一个手动创建的节点，还可以将document中已经存在的节点移动到所需的插入位置
   DocumentFragments是一些DOM节点，他们不是DOM树的一部分。 通常使用的场景是创建一个文档片段，然后将创建的DOM元素插入到文档片段中，最后把文档片段插入到DOM树中，在DOM树中，文档片段会被替换成它所有的子元素

4. 日期格式转换
   方法一：

   function formatDate(t, str) {
       var obj = {
           yyyy: t.getFullYear(),
           yy: ("" + t.getFullYear()).slice(-2),
           M: t.getMonth() + 1,
           MM: ("0" + (t.getMonth() + 1)).slice(-2),
           d: t.getDate(),
           dd: ("0" + t.getDate()).slice(-2),
           H: t.getHours(),
           HH: ("0" + t.getHours()).slice(-2),
           h: t.getHours() % 12,
           hh: ("0" + t.getHours() % 12).slice(-2),
           m: t.getMinutes(),
           mm: ("0" + t.getMinutes()).slice(-2),
           s: t.getSeconds(),
           ss: ("0" + t.getSeconds()).slice(-2),
           w: ['日', '一', '二', '三', '四', '五', '六'][t.getDay()]
       };
       return str.replace(/([a-z]+)/ig, function ($1) {
           return obj[$1]
       });
   }
   var result = formatDate(new Date(1409894060000), 'yyyy-MM-dd HH:mm:ss 星期w');

   关于 new Date()

   var date = new Date();// Sun Mar 19 2017 16:00:45 GMT+0800 (中国标准时间)
   var date1 = new Date(0); // Thu Jan 01 1970 08:00:00 GMT+0800 (中国标准时间)
   var date2 = new Date(3000); // Thu Jan 01 1970 08:00:03 GMT+0800 (中国标准时间)
   var date3 = new Date(1409894060000);// Fri Sep 05 2014 13:14:20 GMT+0800 (中国标准时间)
   var date4 = new Date('Aug 9, 1995');// Wed Aug 09 1995 00:00:00 GMT+0800 (中国标准时间)
   var date5 = new Date(1995,11,17);//Sun Dec 17 1995 00:00:00 GMT+0800 (中国标准时间)
   // 看见没。。。返回的格式都是一样的。
   // 在Date原型上有一些方法，getXX 或者 setXX

   方法二：

   function formatDate(date, fmt) {
       if (/(y+)/.test(fmt)) {
           fmt = fmt.replace(RegExp.$1, (date.getFullYear()) + '').substr(4 - RegExp.$1.length)
       }
       let o = {
           'M+': date.getMonth() + 1,
           'd+': date.getDate(),
           'h+': date.getHours(),
           'm+': date.getMinutes(),
           's+': date.getSeconds()
       }
       for (let k in o) {
           if (new RegExp(`(${k})`).test(fmt)) {
               let str = o[k] + ''
               fmt = fmt.replace(RegExp.$1, (RegExp.$1.length === 1) ? str : padLeftZero(str))
           }
       }
       return fmt
   }
   
   function padLeftZero(str) {
       return ('00' + str).substr(str.length)
   }