1.两个链表相加
总的来说类似于数学运算，思路就是依次将链表的值取出，然后进行按位相加，必须的变量有一个进位，最后返回链表时需要一个节点，运算方法除了相加还需要进行取模取余，最后由于计算是从低位到高位，所以还需要取节点时进行头部插入。
代码如下。但使用特别特别长的链表时，有时会报超时，需继续优化（TODO）
1 // 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。 2 // 给定两个这种链表，请生成代表两个整数相加值的结果链表。 3 // 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。 4 5 // 超时——TODO 6 /* 7 * function ListNode(x){ 8 * this.val = x; 9 * this.next = null; 10 * } 11 */ 12 13 /** 14 * 15 * @param head1 ListNode类 16 * @param head2 ListNode类 17 * @return ListNode类 18 */ 19 function addInList( head1 , head2 ) { 20 var arr1 = [], 21 arr2 = [], 22 // sumArr = [], 23 sum = 0, 24 deg = 0, 25 len = 0 26 while(head1 != null || head2 != null) { 27 if (head1 != null) { 28 arr1.unshift(head1.val) 29 head1 = head1.next 30 } 31 if (head2 != null) { 32 arr2.unshift(head2.val) 33 head2 = head2.next 34 } 35 len++ 36 } 37 var p,p1=null 38 for (var i=0;i<len;i++) { 39 var _sum = (+(arr1[i]||0))+(+(arr2[i]||0))+deg 40 // sumArr.push(_sum%10) 41 deg = Math.floor(_sum/10) 42 p=new ListNode(_sum%10) 43 p.next = p1 44 p1 = p 45 } 46 if (deg > 0) { 47 // sumArr.push(deg) 48 p=new ListNode(deg) 49 p.next = p1 50 } 51 // for (var j=0;j<sumArr.length;j++) { 52 // p=new ListNode(sumArr[j]) 53 // p.next = p1 54 // p1 = p 55 // } 56 return p 57 } 58 module.exports = { 59 addInList : addInList 60 };
2.用2个栈实现队列
栈，先进后出，尾部进，尾部出，队列，先进先出，尾部进，头部出。
思路就是进的时候直接进，出的时候先判断一个栈是否空，空的话则全部将另一个栈入栈，非空则直接弹出顶部元素。题目多少比较混淆人。
1 // 用两个栈来实现一个队列，分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。 2 3 // 示例: 4 // 输入: 5 // ["PSH1","PSH2","POP","POP"] 6 // 返回: 7 // 1,2 8 // 解析: 9 // "PSH1":代表将1插入队列尾部 10 // "PSH2":代表将2插入队列尾部 11 // "POP“:代表删除一个元素，先进先出=>返回1 12 // "POP“:代表删除一个元素，先进先出=>返回2 13 14 var _quene1 = [] 15 var _quene2 = [] 16 function push(node) 17 { 18 _quene1.push(node) 19 } 20 function pop() 21 { 22 if (_quene2.length == 0) { 23 while(_quene1.length > 0) { 24 _quene2.push(_quene1.pop()) 25 } 26 } 27 return _quene2.pop() 28 } 29 module.exports = { 30 push : push, 31 pop : pop 32 };
3.翻转链表
思路很简单，就是简单的遍历然后翻转指针。
实际操作，首先是进行循环原链表，然后需要一个当前指针变量，还需要一个next节点变量，需要进行到下个节点时，将当前节点变成上个节点，因而一共需要3个变量。循环条件就是节点不为null。需要注意的是操作顺序是严格一步步进行的，因为如果顺序不对，节点会相互缠绕。而最后返回的，则是最后一个节点。而我们循环终止时，最后一个是null，因而再往前的一个节点就是我们要返回的变量。
1 /*function ListNode(x){ 2 this.val = x; 3 this.next = null; 4 }*/ 5 function ReverseList(pHead) 6 { 7 let cur = pHead 8 let pre = null 9 while (cur != null) { 10 let cnext = cur.next 11 cur.next = pre 12 pre = cur 13 cur = cnext 14 } 15 return pre 16 }
4.解析url参数
url的格式：协议://域名(:端口)/url路径?参数1=值1&参数2=值2#锚点id
相应的参数截取方法，则是先以?分割，再以#分割，来截取中间部分，再以&切割开不同键值对，最后以=区分键值。
1 function getUrlParam(sUrl, sKey) { 2 const urlMap = {} 3 try { 4 let urlMapAr = sUrl.split("?")[1].split("#")[0].split("&") 5 urlMapAr.forEach(e => { 6 let er = e.split("=") 7 if (urlMap[er[0]] === undefined) { 8 urlMap[er[0]] = er[1] 9 } else { 10 if (Array.isArray(urlMap[er[0]])) { 11 urlMap[er[0]].push(er[1]) 12 } else { 13 urlMap[er[0]] = [urlMap[er[0]], er[1]] 14 } 15 } 16 }) 17 } catch(e) {} 18 return sKey ? (urlMap[sKey] || "") : urlMap 19 }
5.青蛙跳（斐波那契数列-递归）
问题抽象为，一次只能加1或者2，要实现和为n，有多少种方法。
n为1时，只有1，n为2时，有2和1,1......。思路的关键点是，要想到达n，则先要到达n-1时最后一步是1，或者到达n-2最后一步是2（是1+1的和n-1重复），因而使用反向递归的方法可以解决。但是其实斐波那契数列在参数稍微大一点时就进行了大量的递归，效率方面有严重不足(10g内存到32就无法计算了)，可以考虑使用其他方法解决。（时间复杂度On方和On的关系）
1 // 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 2 function jumpFloor(number) {// On^2，递归 3 if (number > 2) { 4 return jumpFloor(number - 1) + jumpFloor(number - 2) 5 } else { 6 return number 7 } 8 } 9 10 function jumpFloor(num) {// On，for循环 11 if (num > 2) { 12 var num1 = 1; 13 var num2 = 1; 14 for (var i = 2; i < num; i++) { 15 num2 = num1 + num2; 16 num1 = num2 - num1; 17 } 18 return num1 + num2; 19 // 可以使用解构赋值简化 20 // [n1, n2] = [n2, n1 + n2] 21 // return n2// 确认没问题吧TODO 22 } else { 23 return num 24 } 25 } 26 27 const fb4 = function(){// 闭包（差了1——TODO），去除重复计算的递归 28 var mem = [0,1]; 29 var f = function(n){ 30 var res = mem[n]; 31 if(typeof res !== 'number'){ 32 mem[n] = f(n-1) + f(n-2); 33 res = mem[n]; 34 } 35 return res; 36 } 37 return f; 38 }(); 39 40 // 惰性序列？？TODO 41 42 // class Matrix 43 // { 44 // public: 45 // int n; 46 // int **m; 47 // Matrix(int num) 48 // { 49 // m=new int*[num]; 50 // for (int i=0; i<num; i++) { 51 // m[i]=new int[num]; 52 // } 53 // n=num; 54 // clear(); 55 // } 56 // void clear() 57 // { 58 // for (int i=0; i<n; ++i) { 59 // for (int j=0; j<n; ++j) { 60 // m[i][j]=0; 61 // } 62 // } 63 // } 64 // void unit() 65 // { 66 // clear(); 67 // for (int i=0; i<n; ++i) { 68 // m[i][i]=1; 69 // } 70 // } 71 // Matrix operator=(const Matrix mtx) 72 // { 73 // Matrix(mtx.n); 74 // for (int i=0; i<mtx.n; ++i) { 75 // for (int j=0; j<mtx.n; ++j) { 76 // m[i][j]=mtx.m[i][j]; 77 // } 78 // } 79 // return *this; 80 // } 81 // Matrix operator*(const Matrix &mtx) 82 // { 83 // Matrix result(mtx.n); 84 // result.clear(); 85 // for (int i=0; i<mtx.n; ++i) { 86 // for (int j=0; j<mtx.n; ++j) { 87 // for (int k=0; k<mtx.n; ++k) { 88 // result.m[i][j]+=m[i][k]*mtx.m[k][j]; 89 // } 90 // } 91 // } 92 // return result; 93 // } 94 // }; 95 // int main(int argc, const char * argv[]) { 96 // unsigned int num=2; 97 // Matrix first(num); 98 // first.m[0][0]=1; 99 // first.m[0][1]=1; 100 // first.m[1][0]=1; 101 // first.m[1][1]=0; 102 // int t; 103 // cin>>t; 104 // Matrix result(num); 105 // result.unit(); 106 // int n=t-2; 107 // while (n) { 108 // if (n%2) { 109 // result=result*first; 110 // } 111 // first=first*first; 112 // n=n/2; 113 // } 114 // cout<<(result.m[0][0]+result.m[0][1])<<endl; 115 // return 0; 116 // } 117 // TODO——改成js 118 119 module.exports = { 120 jumpFloor: jumpFloor 121 };