• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

算法总结(一)

admin

11月 28, 2021

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 };

View Code

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 };

View Code

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 }

View Code

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 }

View Code

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 };

View Code

FIGHTING

发表评论

您的电子邮箱地址不会被公开。