点击刷新
1、合并两个有序数组，时间复杂度为O(n)
思路：两个指针，从零开始，比较两个数组里面的指针，每次把两者之中最小的放到结果数组中来。
const getOrderList = (list1, list2) => { let newList = []; let i = 0; let j = 0; while (i < list1.length && j < list2.length) { if (list1[i] <= list2[j]) { newList.push(list1[i]); i++; } else { newList.push(list2[j]); j++; } } if (i === list1.length) { newList = newList.concat(list2.slice(j)); } if (j === list2.length) { newList = newList.concat(list1.slice(i)); } return newList; };
2、判断一个单词是否回文
思路：
1、把字符串翻转之后，看是否等于原来的字符
const isRecerseValue = (value = '') => { let newValue = '' let i = value.length-1 while(i>=0) { newValue +=value[i] i--; } return newValue === value } console.log(isRecerseValue('aba'))
2、用首尾两个指针，向中间扫描字符串，如果两指针指向的字符都一样， 这字符串就是一个回文。
const isRecerseValue = (value = '') => { let i = 0; let j = value.length - 1; while (i < j) { if (value[i] !== value[j]) { return false; } i++; j--; } return true; };
3、求一个数组中的两数之和为target，输出两个数的index
1、暴力计算,
const target2element = (list = [], target) => { for (let i = 0; i < list.length-1; i++){ for (let j = i + 1; j < list.length; j++){ if(list[i]+list[j] === target){ return [i,j] } } } return [] }
2、使用hash表，把数组 的index，value生成 hash，对于一个list[i],判断target-list[i]是否在map中
const target2element = (list = [], target) => { const hashMap = new Map(); for (let i = 0; i < list.length; i++) { if (hashMap.has(target - list[i])) { return [i, hashMap.get(target - list[i])]; } hashMap.set(list[i], i); } };
4、给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a ，b ，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
思路：排序一下（解决不重复的问题），然后固定一个数之后，用双指针夹逼的原则。
补充：如果不规定重复，那么可以用3中的相似的手法
const sum2tree = (list = [], target) => { const result = []; if (list.length < 3) { return result; } list.sort((a, b) => a - b); for (let i = 0; i < list.length - 2; i++) { if (list[i] > 0) { break; } let left = i++; let right = list.length - 1; // 双指针夹逼 while (left < right) { const sum = list[i] + list[left++] + list[right++]; if (sum === 0) { // push 了之后防止还有重复的。 while (list[left] === list[left - 1]) { left++; } while (list[right] === list[right + 1]) { right++; } } else if (sum > 0) { right--; } else { left++; } } } };
© 著作权归作者所有
举报
发表评论
0/200
