内容简介:例:在统计一个字符串中字幕出现的次数时,我们就可以把这些字母当做数组下标,在遍历的时候,如果字母A遍历到,则arr['a']就可以加1了。法一:利用对象的key值不重复
1、巧用数组下标
例:在统计一个字符串中字幕出现的次数时,我们就可以把这些字母当做数组下标,在遍历的时候,如果字母A遍历到,则arr['a']就可以加1了。
法一:利用对象的key值不重复
var str = 'hajshdjldjf'; function count(str){ var obj = {}; for(var i = 0; i < str.length; i++){ if(obj[str[i]]){ obj[str[i]]++; }else{ obj[str[i]] = 1; } } console.log(obj); return obj; } count(str);复制代码
法二:利用数组的下标
var str = 'hajshdjldjf'; function count(str){ var arr = []; for(var i = 0; i < str.length; i++){ if(arr[str[i]]){ arr[str[i]]++; }else{ arr[str[i]] = 1; } } } count(str);复制代码
其实这两种方法的思想是一致的。
例:给你n个无序的int整型数组arr,并且这些整数的取值范围都在0-20之间,要你在 O(n) 的时间复杂度中把这 n 个数按照从小到大的顺序打印出来。
对于这道题,如果你是先把这 n 个数先排序,再打印,是不可能O(n)的时间打印出来的。但是数值范围在 0-20。我们就可以巧用数组下标了。把对应的数值作为数组下标,如果这个数出现过,则对应的数组加1。
利用对象:
var arr = [1,2,3,4,5,4,5,6,6,7,6,9,17,16,15,14,12,11]; //常规解法 利用对象的key值不能重复去计算次数 //res去记录数字出现的顺序 function fn(arr){ arr.sort(function(a,b){ return a - b; }); var res = []; var resdetail = []; for(var i = 0; i < arr.length; i++){ if(res.length === 0 || res[res.length-1] !== arr[i]){ res.push(arr[i]); var obj = { key:arr[i], value:1 }; resdetail.push(obj); }else{ resdetail[resdetail.length-1].value++; } } console.log(resdetail); return resdetail; } fn(arr);复制代码
利用数组下标
var arr = [1,2,3,4,5,4,5,6,6,7,6,9,17,16,15,14,12,11]; //利用数组下标 时间复杂度为O(n) function fn(arr){ var temp = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]; for(var i = 0; i < arr.length; i++){ temp[arr[i]]++; } for(var j = 0; j < 21; j++){ for(var k = 0; k < temp[j]; k++){ console.log(j); } } } fn(arr);复制代码
2、巧用取余
有时候我们在遍历数组的时候,会进行越界判断,如果下标差不多要越界了,我们就把它置为0重新遍历。特别是在一些环形的数组中,例如用数组实现的队列。往往会写出这样的代码:
for (int i = 0; i < N; i++) { if (pos < N) { //没有越界 // 使用数组arr[pos] else { pos = 0;//置为0再使用数组 //使用arr[pos] } pos++; } }复制代码
实际上我们可以通过取余的方法来简化代码
for (int i = 0; i < N; i++) { //使用数组arr[pos] (我们假设刚开始的时候pos < N) pos = (pos + 1) % N; }复制代码
3、巧用双指针
对于双指针,在做关于单链表的题是特别有用,比如“判断单链表是否有环”、“如何一次遍历就找到链表中间位置节点”、“单链表中倒数第 k 个节点”等问题。对于这种问题,我们就可以使用双指针了,会方便很多。
(1)判断单链表中是否有环
我们可以设置一个快指针和一个慢指针,慢的一次移动一个节点,快的一次移动两个节点。如果存在环,快指针会在第二次遍历时和慢指针相遇。
(2)如何一次遍历就找到链表中间位置节点
一样是设置一个快指针和慢指针。慢的一次移动一个节点,快的一次移动两个。当快指针遍历完成时,慢指针刚好到达中点。
(3)单链表中倒数第 k 个节点
设置两个指针,其中一个指针先移动k-1步,从第k步开始,两个指针以相同的速度移动。当那个先移动的指针遍历完成时,第二个指针指向的位置即倒数第k个位置。
4、巧用位移
有时候我们在进行除数或乘数运算的时候,例如n / 2,n / 4, n / 8这些运算的时候,我们就可以用移位的方法来运算了,这样会快很多。
例如:
n / 2 等价于 n >> 1
n / 4 等价于 n >> 2
n / 8 等价于 n >> 3。
这样通过移位的运算在执行速度上是会比较快的,也可以显的你很厉害的样子,哈哈。
还有一些 &(与)、|(或)的运算,也可以加快运算的速度。例如判断一个数是否是奇数,你可能会这样做
if(n % 2 == 1){ dosomething(); }复制代码
不过我们用 与或运算 的话会快很多。例如判断是否是奇数,我们就可以把n和1相与了,如果结果为1,则是奇数,否则就不会。即
if(n & 1 == 1){ dosomething(); )复制代码
5、设置哨兵位
在链表的相关问题中,我们经常会设置一个头指针,而且这个头指针是不存任何有效数据的,只是为了操作方便,这个头指针我们就可以称之为 哨兵位 了。
例如我们要删除头第一个节点是时候,如果没有设置一个哨兵位,那么在操作上,它会与删除第二个节点的操作有所不同。但是我们设置了哨兵,那么删除第一个节点和删除第二个节点那么在操作上就一样了,不用做额外的判断。当然,插入节点的时候也一样。
有时候我们在操作数组的时候,也是可以设置一个哨兵的,把arr[0]作为哨兵。例如,要判断两个相邻的元素是否相等时,设置了哨兵就不怕越界等问题了,可以直接arr[i] == arr[i-1]?了。不用怕i = 0时出现越界。
6、与递归相关的一些优化
(1)对于可以递归的问题考虑状态保存。
当我们使用递归来解决一个问题时,很容易产生重复去算同一个子问题,这个时候我们要考虑状态保存以防止重复计算。
例:斐波那契数列
function fn(n){ if(n <= 2){ return 1; }else{ return fn(n-1) + fn(n-2); } } console.log(fn(10));复制代码
不过对于可以使用递归解决的问题,我们一定要 考虑是否有很多重复计算 。显然对于 f(n) = f(n-1) + f(n-2) 的递归,是有很多重复计算的。如
就有很多重复计算了。这个时候我们要考虑 状态保存 。并且可以自底向上。
function fn(n){ var res = []; res[0] = 1; res[1] = 1; for(var i = 2; i < n; i++){ res[i] = res[i-1] + res[i-2]; } console.log(res[n-1]); return res[n-1]; } fn(10);复制代码
进一步优化:使用两个变量。
function fn(n){ var a = 1; var b = 1; for(var i = 3; i <= n; i++){ a = a + b; b = a - b; } return a; } fn(10);复制代码
以上所述就是小编给大家介绍的《一些常用的算法技巧》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。