关于leetcode:LeetCode经典题篇一

本系列次要记录 LeetCode 经典算法题的解题记录以及从看到题目到解出答案，最终多思维拓展的的过程。仅作为题目记录以及解题思路探讨（心愿大家能够一起沟通解题思路），以管中窥豹的形式学习算法！

目前理解并浏览过的书籍举荐 漫画算法、数据结构

注：贴出来的代码为了不便，一个思路中可能多个逻辑解法，如需复制运行留神正文阐明

回文数

题目形容：

题意拆解:

判断一串数字是否是回文数，返回boolean值

• 回文数(回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。)

思路一：遍历顺叙判断是否和原始值完全一致

var isPalindrome = function(x) {  if (x < 0) return false;  // 思路一：正序和顺叙的值是完全一致的则是回文  // 这里可利用遍历、顺叙、等数组/字符串的原生办法  // 利用 reverse （76-80ms）  x = x.toString();  let reverse_x = x.split("").reverse().join("");  return x === reverse_x;  // 遍历 (60-84ms)  x = x.toString().split("");  let reverse_x = '';  for (let i = 0; i < x.length; i++) {    const ele = x[i];    reverse_x = ele + reverse_x;  }  return reverse_x === x.join('');};

思路二：基于数字个性的进制替换 既然是数字能够利用进制替换（60-92ms）

// 思路二：既然是数字能够利用进制替换（60-92ms）var isPalindrome = function(x) {  let reverse_x = 0;  for (let i = x; i >= 1; i = Math.floor(i / 10)){    reverse_x = reverse_x * 10 + (i % 10);  }  return reverse_x === x;  // 既然是回文那么我只遍历一半呢  let reverse_x = 0;  let center_index,    minVal = 1;  let x_leng = x.toString().length;  center_index = Math.ceil(x_leng / 2);  minVal = Math.pow(10, center_index);  for (let i = x; i >= minVal; i = Math.floor(i / 10)) {    reverse_x = reverse_x * 10 + (i % 10);  }  return reverse_x === Math.floor(x / minVal);  // 利用 which 替换for  if (x < 0) return false;  let temp = x;  let res = 0;  while (x) {    res = res * 10 + (x % 10);    x = Math.floor(x / 10);  }  return res == temp;};

此处回文的只是数字利用数字位替换，判断连个位数知否相等；既然是回文那么咱们只遍历个别数字判断遍历的前半部分和未解决的后半局部是否统一即可

合并K个升序链表

题目形容：

题意拆解:

将多个升序链表合并成一个升序链表

思路一：利用数组的遍历的形式

//链表节点实例function ListNode(val, next) {     this.val = (val===undefined ? 0 : val)    this.next = (next===undefined ? null : next)}var mergeKLists = function(lists) {  // 思路一：利用数组的解决形式（不举荐）  // 亮点：代码简介  return lists.reduce((p, n) => {        while (n) {            p.push(n), n = n.next        }        return p    },[]).sort((a, b) => a.val - b.val).reduceRight((p, n) => (n.next = p, p = n, p), null)  // 亮点: 条理清晰  // 1. 想将链表解决成一维数组，  // 2. 将数组进行排序  // 3. 最初将排序后的数组转换成链表  let arr = []  lists.forEach((ele) => {    function deepLinkedList(list) {      arr.push(list.val);      if(list.next){        deepLinkedList(list.next);      }    }    deepLinkedList(ele)  });  arr.sort()  let arr_list = {};  function deepList(arr,map) {    map["val"] = arr[0];    arr.shift(1);    map["next"] = arr.length?{}:null;    if(arr.length){      deepList(arr, map["next"]);    }  }  deepList(arr, arr_list);  return arr_list;};

思路二：链表两两合并

function ListNode(val, next) {     this.val = (val===undefined ? 0 : val)    this.next = (next===undefined ? null : next)}var mergeKLists = function(lists) {  // 思路二：应用数据结构链表思路：新建一个空白链表以及一个挪动的指针指向将要操作的节点上  // 两两合并  let ans = null;  for (let i = 0; i < lists.length; i++) {    ans = mergeTwoList(ans, lists[i]);  }  return ans;  function mergeTwoList(pHead1, pHead2) {    let newList = new ListNode();    let cur = newList;    while (pHead1 !== null && pHead2 !== null) {      // 找出更小筛入队列中      if(pHead1.val < pHead2.val) {        cur.next = pHead1        pHead1 = pHead1.next      } else {        cur.next = pHead2        pHead2 = pHead2.next      }      cur = cur.next;    }    cur.next = pHead1 || pHead2;    // console.log(newList,cur);    return newList.next;  }};

测试用例：

let data = mergeKLists([   { val: 1, next: { val: 4, next: { val: 5, next: null } } },   { val: 1, next: { val: 3, next: { val: 4, next: null } } },   { val: 2, next: { val: 6, next: null } },]);

K 个一组翻转链表

题目形容：

题意拆解:

将一个链表按n未一组顺叙后返回，如果残余链表或总链表有余n位时保持原状

思路一：利用链表转数组，数组转链表的暴力形式

var reverseKGroup = function(head, k) {  if (!k) return;  // 思路一：利用链表转数组，数组转链表的暴力形式  let arr = [];  let len = 0;  let index = 0;  function deepLinkedList(list) {    ++len;    if (!arr[index]) arr[index] = [];    arr[index].push(list.val);    if (len === k) {      len = 0;      index += 1;    }    if (list.next) {      deepLinkedList(list.next);    }  }  // 将链表按序转成二维数组  deepLinkedList(head);  // 翻转数组并整平  arr = arr.map((item) => {    if (item.length >= k) {      return item.reverse();    }    return item;  });  arr = [].concat.apply([], arr);  // 数组在转换成链表  let arr_list = {};  function deepList(arr,map) {    map["val"] = arr[0];    arr.shift(1);    map["next"] = arr.length?{}:null;    if(arr.length){      deepList(arr, map["next"]);    }  }  deepList(arr, arr_list);  return arr_list;};

思路一：利用链表转数组，数组转链表的暴力形式

var reverseKGroup = function(head, k) {  if (!k) return;  // 思路一：利用链表转数组，数组转链表的暴力形式  // let arr = [];  // let len = 0;  // let index = 0;  // function deepLinkedList(list) {  //   ++len;  //   if (!arr[index]) arr[index] = [];  //   arr[index].push(list.val);  //   if (len === k) {  //     len = 0;  //     index += 1;  //   }  //   if (list.next) {  //     deepLinkedList(list.next);  //   }  // }  // // 将链表按序转成二维数组  // deepLinkedList(head);  // // 翻转数组并整平  // arr = arr.map((item) => {  //   if (item.length >= k) {  //     return item.reverse();  //   }  //   return item;  // });  // arr = [].concat.apply([], arr);  // // 数组在转换成链表  // let arr_list = {};  // function deepList(arr,map) {  //   map["val"] = arr[0];  //   arr.shift(1);  //   map["next"] = arr.length?{}:null;  //   if(arr.length){  //     deepList(arr, map["next"]);  //   }  // }  // deepList(arr, arr_list);  // return arr_list;  // 思路二：对链表进行操作  const hair = new ListNode();  hair.next = head;  let pre = hair;  while (head) {    let tail = pre;    // 如果分组的值大于整个链长则间接将链返回    for (let i = 0; i < k; ++i) {        tail = tail.next; // 从 0 开始        if (!tail) {            return hair.next;        }    }    const nex = tail.next; // 把除去以后组的残余链表保留    console.log("顺叙前", head, tail);    [head, tail] = myReverse(head, tail);    // 把子链表从新接回原链表    console.log("顺叙后", head, tail, JSON.stringify(pre));    pre.next = head;    tail.next = nex;    console.log(JSON.stringify(pre), nex, tail);    pre = tail;    head = tail.next;  }  console.log("后果:", hair.next === head, head, JSON.stringify(hair));  return hair.next;};

思路二：链表分组并翻转

var reverseKGroup = function(head, k) {  if (!k) return;   // 思路二：对链表进行操作  const hair = new ListNode();  hair.next = head;  let pre = hair;  while (head) {    let tail = pre;    // 如果分组的值大于整个链长则间接将链返回    for (let i = 0; i < k; ++i) {        tail = tail.next; // 从 0 开始        if (!tail) {            return hair.next;        }    }    const nex = tail.next; // 把除去以后组的残余链表保留    console.log("顺叙前", head, tail);    [head, tail] = myReverse(head, tail);    // 把子链表从新接回原链表    console.log("顺叙后", head, tail, JSON.stringify(pre));    pre.next = head;    tail.next = nex;    console.log(JSON.stringify(pre), nex, tail);    pre = tail;    head = tail.next;  }  console.log("后果:", hair.next === head, head, JSON.stringify(hair));  return hair.next;};

测试用例

reverseKGroup({ val: 1, next: { val: 2, next: { val: 3, next: { val: 4, next: null } } } },2);

挪动零

题目形容：

题意拆解:

将数组中的0数组挪动到最右侧，其余非零数字程序不变但向前补位

思路一: 操作原数组笼罩批改，记录零的个数并置零，工夫复杂度增多

var moveZeroes = function(nums) {  // 要求: 要求只能原数组操作  // 思路一: 操作原数组笼罩批改，记录零的个数并置零，工夫复杂度增多  var k = 0;  for (let i = 0; i < nums.length; i++) {    if (nums[i] != 0){      nums[k++] = nums[i];    }  }  for (let j = k; j < nums.length; j++){    nums[j] = 0;  }};

思路二：双指针思路(冒泡的思路)

var moveZeroes = function(nums) {  // 要求: 要求只能原数组操作  // 思路二：双指针思路(冒泡的思路)  // 以 0 作为入口 两次循环  for (let i = 0; i < nums.length; i++) {    const ele = nums[i];    if(ele === 0){      for (let j = i+1; j < nums.length; j++) {        const ele2 = nums[j];        if (ele2 !== 0) {          nums[i] = ele2;          nums[j] = ele;          break;        }      }    }  }  // 以不等于 0 作为入口；一次循环，并增加一个计数器  let j = 0;  for (let i = 0; i < nums.length; i++) {    //以后元素!=0，就把其替换到右边，等于0的替换到左边    if (nums[i] != 0) {      let tmp = nums[i]; // 长期存下来      nums[i] = nums[j];      nums[j++] = tmp;    }  }  // 思考一下，如果按下面的思路以等于 0 作为判断根据并只遍历一遍呢？}

测试用例

课程表 IV

题目形容：

题意拆解:

提供一个长度的数字并有一份各个数字之间关联关系的映射，判断一组关系是否合乎

思路一: 暴力递归 递归遍历找出各个课程的父课程 会超时! 换了两种遍历路径还是都会超时

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {  if (!prerequisites.length) {    return queries.map(() => {      return false;    });  }  // 思路一: 递归遍历找出各个课程的父课程 会超时! 换了两种遍历路径还是都会超时  let allQueries = [];  // prerequisites =  prerequisites.sort((a,b)=>{  //   return a[0] - b[0]  // })  // prerequisites.forEach((ele,index) => {  //   allQueries.push(ele);  //   let curPreVal = ele[0];  //   let curNextVal = ele[1]    function deep(curVal,oldVal,idx) {      if (curVal < numCourses) {        // 这里做个小优化如果吧二维数组的第一个数组排序那每次递归遍历只须要从以后索引的下一个来即可        for (let i = 0; i < prerequisites.length; i++) {          const [j,k] = prerequisites[i];           if (j === curVal) {             allQueries.push([oldVal===null?curVal:oldVal, k]);             deep(k, oldVal===null?curVal:oldVal, i);           }        }        // prerequisites.forEach(([j,k]) => {        //   if (j === curVal) {        //     allQueries.push([curPreVal, k]);        //     deep(k);        //   }        // });      }    }    // deep(curNextVal,index);    for (let n = numCourses-1; n >= 0; n--) {      deep(n,null,0);    }  // });  // console.log(allQueries);  return queries.map(([i, j]) => {    return allQueries.some((item) => {      return JSON.stringify(item) === JSON.stringify([i, j]);    });  });};

这个尽管暴力然而也是个别同学能第一工夫想到的计划，将各个映射关系通过递归遍历的形式全副收集，在将指标判断数据进行比拟

floyed算法 奇妙利用最短门路弗洛伊德算法来解决

var checkIfPrerequisite = function(numCourses, prerequisites, queries) {  if (!prerequisites.length) {    return queries.map(() => {      return false;    });  }  // 思路二: floyed算法  let dp = [];  for (let i = 0; i < numCourses; i++) {    dp[i] = new Array(numCourses).fill(false);  }  // console.log(dp);  prerequisites.forEach(([i, j]) => (dp[i][j] = true));  // console.log(dp);  for (let k = 0; k < numCourses; k++) {    for (let i = 0; i < numCourses; i++) {      for (let j = 0; j < numCourses; j++) {        if((dp[i][k] && dp[k][j])){          // console.log(k, i, j);        }        dp[i][j] = dp[i][j] || (dp[i][k] && dp[k][j]);      }    }  }  return queries.map(([i, j]) => dp[i][j]);};

测试用例:

// console.log(//   checkIfPrerequisite(//     5,//     [//       [3, 4],//       [0, 1],//       [1, 2],//       [2, 3],//     ],//     [//       [0, 4],//       [4, 0],//       [1, 3],//       [3, 0],//     ]//   )// );

未完待续~

始终在路上的程序员ymc!