Q19 回文解碼
現(xiàn)在有一個(gè)字符串，你要對(duì)這個(gè)字符串進(jìn)行 n 次操作，每次操作給出兩個(gè)數(shù)字：(p, l) 表示當(dāng)前字符串中從下標(biāo)為 p 的字符開(kāi)始的長(zhǎng)度為 l 的一個(gè)子串。你要將這個(gè)子串左右翻轉(zhuǎn)后插在這個(gè)子串原來(lái)位置的正后方，求最后得到的字符串是什么。字符串的下標(biāo)是從 0 開(kāi)始的，你可以從樣例中得到更多信息。輸入描述:
每組測(cè)試用例僅包含一組數(shù)據(jù)，每組數(shù)據(jù)第一行為原字符串，長(zhǎng)度不超過(guò) 10 ，僅包含大小寫(xiě)字符與數(shù)字。接下來(lái)會(huì)有一個(gè)數(shù)字 n 表示有 n 個(gè)操作，再接下來(lái)有 n 行，每行兩個(gè)整數(shù)，表示每次操作的(p , l)。保證輸入的操作一定合法，最后得到的字符串長(zhǎng)度不超過(guò) 1000。
輸出描述:
輸出一個(gè)字符串代表最后得到的字符串。
輸入例子:
ab
2
0 2
1 3
輸出例子:
abbaabb
??????? function reversecion(input){
??????????? var arr = input.split('\n')
??????????? var str=arr[0],
??????????????? num=arr[1]
??????????? for(var i=0;i<num;i++){
??????????????? var arrtemp = arr[i+2]
??????????????? var start=arrtemp.split(' ')
??????????????? var startnum = + start[0]
??????????????? var endnum = + start[1]
??????????????? var temp=str.substr(startnum,endnum)
??????????????? str=str.substr(0,startnum+endnum)+temp.split("").reverse().join("") +str.substr(startnum+endnum)
??????????? }
??????????? return str;
??????? }
??????? var input = "ab\n2\n0 2\n1 3"
??????? console.log(reversecion(input)) //abbaabb
??????? var input1= "abc\n2\n0 2\n1 2"
??????? console.log(reversecion(input1))??? //abbbbac
substring()
substr()
slice()
slice()
第一個(gè)參數(shù)代表開(kāi)始位置,第二個(gè)參數(shù)代表結(jié)束位置的下一個(gè)位置,截取出來(lái)的字符串的長(zhǎng)度為第二個(gè)參數(shù)與第一個(gè)參數(shù)之間的差;若參數(shù)值為負(fù)數(shù),則將該值加上字符串長(zhǎng)度后轉(zhuǎn)為正值;若第一個(gè)參數(shù)等于大于第二個(gè)參數(shù),則返回空字符串.
substring()
第一個(gè)參數(shù)代表開(kāi)始位置,第二個(gè)參數(shù)代表結(jié)束位置的下一個(gè)位置;若參數(shù)值為負(fù)數(shù),則將該值轉(zhuǎn)為0;兩個(gè)參數(shù)中,取較小值作為開(kāi)始位置,截取出來(lái)的字符串的長(zhǎng)度為較大值與較小值之間的差.
substr()
第一個(gè)參數(shù)代表開(kāi)始位置,第二個(gè)參數(shù)代表截取的長(zhǎng)度
Q20 你作為一名出道的歌手終于要出自己的第一份專輯了，你計(jì)劃收錄 n 首歌而且每首歌的長(zhǎng)度都是 s 秒，每首歌必須完整地收錄于一張 CD 當(dāng)中。每張 CD 的容量長(zhǎng)度都是 L 秒，而且你至少得保證同一張 CD 內(nèi)相鄰兩首歌中間至少要隔 1 秒。為了辟邪，你決定任意一張 CD 內(nèi)的歌數(shù)不能被 13 這個(gè)數(shù)字整除，那么請(qǐng)問(wèn)你出這張專輯至少需要多少?gòu)?CD ?
輸入描述:
每組測(cè)試用例僅包含一組數(shù)據(jù)，每組數(shù)據(jù)第一行為三個(gè)正整數(shù) n, s, L。 保證 n ≤ 100 , s ≤ L ≤ 10000
輸出描述:
輸出一個(gè)整數(shù)代表你至少需要的 CD 數(shù)量。
輸入例子:
7 2 6
輸出例子:
4
??????? function getNum(n,s,l){
??????????? var maxPerCD =? parseInt((l+1) / (s+1));
??????????? var num= 0;
??????????? if(maxPerCD>n){
??????????????? if(n%13==0){
??????????????????? return 2
??????????????? }else{
??????????????????? return 1
??????????????? }
??????????? }
??????????? if(maxPerCD%13==0){
??????????????? maxPerCD--;
??????????? }
??????????? if(n%maxPerCD==0){
??????????????? return n/maxPerCD
??????????? }else{
??????????????? if(n%maxPerCD%13==0&&(n%maxPerCD==maxPerCD-1)){ //如果余數(shù)可被13整除，并且余數(shù)等于每張CD最多歌數(shù)-1，
????????????????? // 這時(shí)候余數(shù)不能單獨(dú)一張CD，也不能再?gòu)钠渌鸆D挪一張，只能再加一張CD
??????????????????? return parseInt(n/maxPerCD)+2
??????????????? }else{
??????????????????? return parseInt(n/maxPerCD)+1
??????????????? }
??????????? }
??????? }
??????? console.log(getNum(7,2,6))? //4
??????? console.log(getNum(28,30,400))? //3
Q21 從一個(gè)數(shù)組中找出與給定數(shù)字最接近的元素。例如，數(shù)組[1,23,24,14,31,45,11,18,54,47,75,99,65]，給定值70，輸出75.
??????? var arr = [1,23,24,14,31,45,11,18,54,47,75,99,65];
??????? var n = 70;
??????? function findNear(arr,n){
????????? var returnNum,cha,temp;
????????? for(var i=0;i<arr.length;i++){
??????????? temp = Math.abs(arr[i]-n)
??????????? if(!cha||cha>temp){
????????????? cha = temp
????????????? returnNum = arr[i]
??????????? }
????????? }
????????? return returnNum
??????? }
??????? console.log(findNear(arr,n))
Q22 倒序打印鏈表的值，列如
node = {
??????????? val:1,
??????????? next:{
??????????????? val:2,
??????????????? next:{
??????????????????? val:3,
??????????????????? next:{
??????????????????????? val:4
??????????????????? }
??????????????? }
??????????? }
??????? }
輸出 4 3 2 1
并且不能用web存儲(chǔ)，比如不能使用臨時(shí)變量 var temp = XXX
面試今日頭條被問(wèn)到了這個(gè)問(wèn)題，當(dāng)時(shí)沒(méi)想上來(lái)。
??????? var node = {
??????????? val:1,
??????????? next:{
??????????????? val:2,
??????????????? next:{
??????????????????? val:3,
??????????????????? next:{
??????????????????????? val:4
??????????????????? }
??????????????? }
??????????? }
??????? }
??????? function reverseFun(node){
??????????? if(!node){
??????????????? return
??????????? }else{
??????????????? reverseFun(node.next)
??????????????? console.log(node.val)
??????????? }
??????? }
??????? reverseFun(node);
Q23 從一個(gè)有序數(shù)組中找出兩個(gè)元素之和等于給定值得元素角標(biāo)的集合，只能使用單次遍歷，例如，從數(shù)組 [1,2,5,7,9,12,15,18]中找出兩個(gè)和為19的元素的集合，輸出[0,7] [3,5]。
??????? var arr = [1,2,5,7,9,12,15,18]
??????? var s= 19
??????? function fun(arr,s){
??????????? var len = arr.length
??????????? var i=0,j=len-1
??????????? while(i<j){
??????????????? if((arr[i]+arr[j])<s){
??????????????????? i++
??????????????? }else if((arr[i]+arr[j])>s){
??????????????????? j--
??????????????? }else{
??????????????????? var res = [i,j]
??????????????????? console.log(res)
??????????????????? i++
??????????????????? j--
??????????????? }
??????????? }
??????? }
??????? fun(arr,s)
//[0, 7]? [3, 5]
Q24 求二叉樹(shù)中和值為n的路徑
題目描述:
輸入一顆二叉樹(shù)和一個(gè)整數(shù)，打印出二叉樹(shù)中結(jié)點(diǎn)值的和為輸入整數(shù)的所有路徑。路徑定義為從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的結(jié)點(diǎn)形成一條路徑。
思路
前序遍歷二叉樹(shù)，每次更新當(dāng)前路徑的和curtSum；
判斷當(dāng)前結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)，以及curtSum是否等于expectNumber。如果是，把當(dāng)前路徑保存在res結(jié)果中；
若不符合條件，則彈出此結(jié)點(diǎn)。
實(shí)現(xiàn)代碼
??????? var tree = {
??????????? "val": 0,
??????????? "left": {
??????????????? "val": 1,
??????????????? "left": {
??????????????????? "val": 3,
??????????????????? "left": {
??????????????????????? "val": 7,
??????????????????????? "left": {
??????????????????????????? "val": 11,
??????????????????????? }
??????????????????? },
??????????????????? "right": {
??????????????????????? "val": 8,
??????????????????????? "left": {
??????????????????????????? "val": 12,
??????????????????????? }
??????????????????? }
??????????????? },
??????????????? "right": {
??????????????????? "val": 4,
??????????????????? "left": {
??????????????????????? "val": 9,
??????????????????? }
??????????????? }
??????????? },
??????????? "right": {
??????????????? "val": 2,
??????????????? "left": {
??????????????????? "val": 5,
??????????????? },
??????????????? "right": {
??????????????????? "val": 6,
??????????????????? "right": {
??????????????????????? "val": 10,
??????????????????? }
??????????????? }
??????????? }
??????? }
??????? function FindPath(root, expectNumber) {
??????????? var result = [];
??????????? if (root === null) {
??????????????? return result;
??????????? }
??????????? dfsFind(root, expectNumber, [], 0, result);
??????????? return result;
??????? }
??????? function dfsFind(root, expectNumber, path, currentSum, result) {
??????????? currentSum += root.val;
??????????? path.push(root.val);
??????????? if (currentSum == expectNumber && root.left == null && root.right == null) {
??????????????? result.push(path.slice(0));
??????????? }
??????????? if (root.left != null) {
??????????????? dfsFind(root.left, expectNumber, path, currentSum, result);
??????????? }
??????????? if (root.right != null) {
??????????????? dfsFind(root.right, expectNumber, path, currentSum, result);
??????????? }
??????????? path.pop();
??????? }
??????? console.log(FindPath(tree,18)) // [0, 2, 6, 10]
Q25 有一個(gè)數(shù)組和一個(gè)給定的值，從數(shù)組中選擇任意數(shù)，可以重復(fù)選擇，使其和為給定的值，求所需數(shù)最少的一組數(shù)。例如：數(shù)組[2,3,6,7] 常數(shù)7，[2,2,3] [7]兩種組合的和值為7，所以需要數(shù)最少的組合是[7]。
??????? var res = []
??????? function combinationSum(candidates,target){
????????? helper(candidates,target,[],0)
????????? var minNum = res[0].length,temp=0
????????? for(var i=1;i<res.length;i++){
??????????? if(res[i].length<minNum){
????????????? minNum= res[i].length
????????????? temp = i
??????????? }
????????? }
????????? console.log('所有符合條件的組合為：',res)
????????? console.log('最小個(gè)數(shù)為：', minNum)
????????? console.log('最小個(gè)數(shù)的組合為：', res[temp])
??????? }
??????? function helper(candidates,target,list,index){
??????????? if(target == 0){
????????????? res.push(list.slice())
??????????? }
??????????? for(var i=index;i<candidates.length;i++){
??????????????? if(candidates[i] <= target){
????????????????? list.push(candidates[i])
????????????????? helper(candidates,target-candidates[i], list, i)
????????????????? list.pop()
??????????????? }
??????????? }
??????? }
??????? combinationSum([1,3,4],6)
Q26 合并兩個(gè)降序排列的數(shù)組，使合并之后數(shù)組仍然降序排列，要求時(shí)間復(fù)雜度低。例如：[100,97,92,89,80,76] [96,93,88,72,71,66,55] 合并后為[100,97,96,93,92,89,88,80,76,72,71,66,55]
??????? var arr1 = [100,97,94,88,84,80,79,77,73,68,65,62,57,55,52,49,46,44]
??????? var arr2 = [96,93,90,89,85,78,74,69,63,59,57,56,52,48,46,33]
??????? function mergeFun(arr1,arr2){
????????? var i=0,j=0;
????????? var res = []
????????? while(i<arr1.length && j<arr2.length){
??????????? if(arr1[i] > arr2[j]){
????????????? res.push(arr1[i++])
??????????? }else if(arr1[i] == arr2[j]){
????????????? res.push(arr1[i++])
????????????? j++;
??????????? }else{
????????????? res.push(arr2[j++])
??????????? }
????????? }
????????? while(i<arr1.length){
??????????? res.push(arr1[i++])
????????? }
????????? while (j< arr2.length){
??????????? res.push(arr2[j++])
????????? }
????????? return res
??????? }
??????? console.log(mergeFun(arr1,arr2))
Q27 輸出楊輝三角第m行n列的值，m、n從0開(kāi)始。
我們很容易想到用遞歸的方法實(shí)現(xiàn)，如下：
??????? function triangle1(m,n){
??????????? if(n==0||m==n){
??????????????? return 1
??????????? }
??????????? return (triangle1(m-1,n)||0) + (triangle1(m-1,n-1)||0)
??????? }
??????? console.log(triangle1(6,3))
遞歸的方法在計(jì)算較小的數(shù)時(shí)沒(méi)問(wèn)題，但是計(jì)算較大的數(shù)時(shí)就容易超時(shí)。
下面用數(shù)組的方法實(shí)現(xiàn)一下：
??????? function triangle(m,n){
??????????? var arr = [[1]]
??????????? for(var i=1;i<m;i++){
??????????????? arr[i] = []
??????????????? for(var j=0;j<=i;j++){
??????????????????? arr[i][j]= (arr[i-1][j-1] || 0) + (arr[i-1][j] || 0)
??????????????? }
??????????? }
??????????? return arr
??????? }
??????? console.log(triangle(64,30))
Q28 給定一個(gè)整數(shù)數(shù)組 arr ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。
例如，輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
動(dòng)態(tài)規(guī)劃法——O(N)
設(shè)sum[i]為以第i個(gè)元素結(jié)尾且和最大的連續(xù)子數(shù)組。假設(shè)對(duì)于元素i，所有以它前面的元素結(jié)尾的子數(shù)組的長(zhǎng)度都已經(jīng)求得，那么以第i個(gè)元素結(jié)尾且和最大的連續(xù)子數(shù)組實(shí)際上，要么是以第i-1個(gè)元素結(jié)尾且和最大的連續(xù)子數(shù)組加上這個(gè)元素，要么是只包含第i個(gè)元素，即sum[i]
= max(sum[i-1] + a[i], a[i])?？梢酝ㄟ^(guò)判斷sum[i-1] + a[i]是否大于a[i]來(lái)做選擇，而這實(shí)際上等價(jià)于判斷sum[i-1]是否大于0。由于每次運(yùn)算只需要前一次的結(jié)果，因此并不需要像普通的動(dòng)態(tài)規(guī)劃那樣保留之前所有的計(jì)算結(jié)果，只需要保留上一次的即可，因此算法的時(shí)間和空間復(fù)雜度都很小
??? var arr = [2,4,-3,5,-1,3,-2,-6,-5,6]
??? function maxSubArray(arr){
????? var sum = arr[0],
????????? n = arr[0]; //當(dāng)前循環(huán)最大和值
????? for(var i=1;i<arr.length;i++){
??????? if(n>0){
????????? n += arr[i]
??????? }else{
????????? n = arr[i]
??????? }
??????? if(n>sum){
????????? sum = n
??????? }
????? }
????? return sum
??? }
??? console.log(maxSubArray(arr))
Q29 無(wú)重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度
無(wú)重復(fù)字符的最長(zhǎng)子串
給定一個(gè)字符串，找出不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。
示例：
給定 "abcabcbbefdxvbnmkjtgfsd" ，沒(méi)有重復(fù)字符的最長(zhǎng)子串是"fdxvbnmkjtg"，那么長(zhǎng)度就是12。
給定 "bbbbb" ，最長(zhǎng)的子串就是 "b"，長(zhǎng)度是1。
給定 "pwwkew"，最長(zhǎng)子串是"wke"，長(zhǎng)度是3。請(qǐng)注意答案必須是一個(gè)子串，"pwke"是 子序列 而不是子串。
思路分析：
對(duì)字符串進(jìn)行遍歷，使用String.prototype.indexOf()實(shí)時(shí)獲取遍歷過(guò)程中的無(wú)重復(fù)子串并存放于str，并保存當(dāng)前狀態(tài)最長(zhǎng)無(wú)重復(fù)子串的長(zhǎng)度為res，當(dāng)遍歷結(jié)束時(shí)，res的值即為無(wú)重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。
??????? function longSubString(str){
??????????? var res =0,
??????????????? currentStr = '',
??????????????? len = str.length
??????????? for(var i=0;i<len;i++){
??????????????? var char = str.charAt(i);
??????????????? var index = currentStr.indexOf(char)
??????????????? if(index==-1){
??????????????????? currentStr += char
??????????????????? res = res< currentStr.length? currentStr.length: res
??????????????? }else{
??????????????????? currentStr = currentStr.substring(index+1) + char
??????????????? }
??????????? }
??????????? return res
??????? }
??????? console.log(longSubString('abcabcbbefdxvbnmkjtgfsd'))
Q30 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.
說(shuō)明：
給定的 n 保證是有效的。
進(jìn)階：
你能嘗試使用一趟掃描實(shí)現(xiàn)嗎？
思路:
這道題要用雙指針來(lái)實(shí)現(xiàn)。先用first指針前進(jìn)n，然后讓second從head開(kāi)始和first一起前進(jìn)，直到first到了末尾，此時(shí)second的下一個(gè)節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)。（另外，若first一開(kāi)始前進(jìn)n就已經(jīng)不在鏈表中了，說(shuō)明要?jiǎng)h除的節(jié)點(diǎn)正是head節(jié)點(diǎn)，那么直接返回head的下一個(gè)節(jié)點(diǎn)接口。）
/**
* Definition for singly-linked list.
* function ListNode(val) {
*???? this.val = val;
*???? this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
? let first = head, second = head;
? while (n > 0) {
??? first = first.next
??? n--
? }
? if (!first) return head.next;???? // 刪除的是頭節(jié)點(diǎn)
? while (first.next) {
??? first = first.next;
??? second = second.next;
? }
? second.next = second.next.next;
? return head
}
Q31 寫(xiě)一個(gè)函數(shù)獲取兩個(gè)日期之間所有日期，放在對(duì)象里。
例如：getAllDate('2018/09/10','2019/03/04')
輸出：
??? {
??????? 2018:{
??????????? 9:[12,13,14,...30],
??????????? 10:[...],
??????????? 11:[...],
??????????? 12:[...]
??????? },
??????? 2019:{
??????????? 1:[...],
??????????? 2:[...],
??????????? 3:[1,2,3]
??????? }
??? }
??????? function getAllDate(startDate,endDate){
??????????? let startTime = new Date(startDate),
??????????????? endTime = new Date(endDate)
??????????? let arr = []
??????????? let dateObj = {}
??????????? while(startTime<endTime){
??????????????? let year = startTime.getFullYear()
??????????????? let month = startTime.getMonth()
??????????????? let day = startTime.getDate()
??????????????? arr.push(year +'/'+month +'/'+day)
??????????????? startTime.setDate(startTime.getDate() +1)
??????????? }
??????????? for(let i=0;i<arr.length;i++){
??????????????? let temp = arr[i].split('/')
??????????????? let year = parseInt(temp[0]),
??????????????????? month = parseInt(temp[1]) +1,
??????????????????? day = parseInt(temp[2])
??????????????? if(!dateObj[year]){
??????????????????? dateObj[year] = {}
??????????????? }
??????????????? if(!dateObj[year][month]){
??????????????????? dateObj[year][month] = []
??????????????? }
??????????????? dateObj[year][month].push(day)
??????????? }
??????????? return dateObj
??????? }
??????? console.log(getAllDate('2018/09/10','2019/03/04'))
Q32 給定一個(gè)字符串，形如：'a=12,b=23,c=k1,d=2s,k=$'，請(qǐng)寫(xiě)一個(gè)find方法，給定左側(cè)值，找到右側(cè)值，例如：find('a')，打?。骸?2’。
??? var str = 'a=12,b=23,c=k1,d=2s,k=$'
??? function find(param){
??????? var arr= str.split(',')
??????? var obj={}
??????? for(var i=0;i<arr.length;i++){
??????????? obj[arr[i].split('=')[0]] = arr[i].split('=')[1]
??????? }
??????? console.log(obj[param])
??? }
??? find('k')
Q33 給定一個(gè)字符串，找出無(wú)重復(fù)字母的最長(zhǎng)子串。
這個(gè)題和29題類似
??? function func(str){
??????? var subStr = ''
??????? var arr = []
??????? var maxLen = 0
??????? var maxIndex=0
??????? var subMaxStr = ''
??????? for(var i=0;i<str.length;i++){
??????????? if(subStr.indexOf(str.charAt(i))===-1){
??????????????? subStr+=str.charAt(i)
??????????? }else{
??????????????? arr.push(subStr)
??????????????? subStr = subStr.split(str.charAt(i))[1]+str.charAt(i)
??????????? }
??????? }
??????? maxLen = arr[0].length
??????? subMaxStr = arr[0]
??????? for(var j=1;j<arr.length;j++){
??????????? if(arr[j].length>maxLen){
??????????????? maxLen =? arr[j].length
??????????????? maxIndex = j
??????????????? subMaxStr = arr[j]
??????????? }
??????? }
??????? console.log(subMaxStr)
??? }
??? func('zxcvbngfdvfeeewdfrgthfqwertyuiokjhofd')
??? func('zxcvbngfeefd')
方法二
??????? function getSubString(str){
??????????? let longSub = '',len=str.length,currentStr='',max=0
??????????? for(let i=0;i<len;i++){
??????????????? let char = str.charAt(i)
??????????????? if(currentStr.indexOf(char)==-1){
??????????????????? currentStr+=char
??????????????????? if(max<currentStr.length){
??????????????????????? max = currentStr.length
??????????????????????? longSub = currentStr
??????????????????? }
??????????????? }else{
??????????????????? currentStr = currentStr.substring(currentStr.indexOf(char)+1)+char
??????????????? }
??????????? }
??????????? return longSub
??????? }
??????? console.log(getSubString('zxcvbngfdvfeeewdfrgthfqwertyuiokjhofd'))
??????? console.log(getSubString('zxcvbngfeefd'))
Q34 給一個(gè)obj，要求實(shí)現(xiàn)一個(gè)console.tree(obj)，在控制臺(tái)以縮進(jìn)的形式打印這個(gè)值的樹(shù)狀結(jié)構(gòu)（不要打印原型鏈中的方法名稱），例如：
var obj = {'x':1,'y':{'z':2,'b':4,'c':{'d':5}},'a':3}
打?。?/p>
??? console.__proto__.tree = function(json){
??????? var i=0
??????? var str = ''
??????? var fun= function(json){
??????????? for(var key in json){
??????????????? if(json.hasOwnProperty(key)){
??????????????????? if(typeof json[key] ==='object'){
??????????????????????? str+='\t'.repeat(i)+ '|---'+key+'\n'
??????????????????????? i++
??????????????????????? fun(json[key])
??????????????????????? i--
??????????????????? }else{
??????????????????????? str+= '\t'.repeat(i)+ '|---'+key+':'+json[key] +'\n'
??????????????????? }
??????????????? }
??????????? }
??????? }
??????? fun(json)
??????? console.log(str)
??? }
??? var json = {'x':1,'y':{'z':2,'b':4,'c':{'d':5}},'a':3}
??? console.tree(json)
Q35 有一組不同高度的臺(tái)階，有一個(gè)整數(shù)數(shù)組表示，數(shù)組中每個(gè)數(shù)是臺(tái)階的高度，當(dāng)開(kāi)始下雨了（雨水足夠多）臺(tái)階之間的水坑會(huì)積水多少呢？如下圖，可以表示為數(shù)組[0,1,0,2,1,0,1,3,2,1,2,1]，返回積水量6。
方法一
先在這個(gè)數(shù)組中找到最大值，然后從左右兩邊遍歷。以左邊為例，只要當(dāng)前的數(shù)字比下一個(gè)數(shù)字大，那么這個(gè)數(shù)字的右邊就可以存水，按照這個(gè)思路去分析就可以了，右邊的也是一樣的道理。
代碼如下：
let maxIndex=0,max = arr[0]
for(let i=1;i<arr.length;i++){
??? if(arr[i]>max){
??????? max=arr[i]
??????? maxIndex = i
??? }
}
let sum = 0,leftMax=arr[0],rightMax=arr[arr.length-1]
for(let i=1;i<maxIndex;i++){
??? if(arr[i]<leftMax){
??????? sum += (leftMax-arr[i])
??? }else{
??????? leftMax = arr[i]
??? }
}
for(let j = arr.length-1;j>maxIndex;j--){
??? if(arr[j]<rightMax){
??????? sum += (rightMax - arr[j])
??? }else{
??????? rightMax = arr[j]
??? }
}
console.log(sum)
方法二
這個(gè)原理和方法一一樣，只需一次遍歷，相對(duì)方法一略微難理解。
let leftM = arr[0],rightM = arr[arr.length-1],leftIndex = 0,rightIndex = arr.length-1,volumn=0
while (leftIndex < rightIndex) {
??? if(leftM < rightM){
??????? leftIndex++
??????? if(arr[leftIndex]>leftM){
??????????? leftM = arr[leftIndex]
??????? }else{
??????????? volumn += (leftM-arr[leftIndex])
??????? }
??? }else{
??????? rightIndex--
??????? if(arr[rightIndex]>rightM){
??????????? rightM = arr[rightIndex]
??????? }else{
??????????? volumn += (rightM - arr[rightIndex])
??????? }
??? }
}
console.log(volumn)
Q36 替換字符串中所有指定的子字符串。
例如：替換‘a(chǎn)sssdfgghhjsssertyu’中‘sss’
方法一：
str.replace(/需要替換的字符串/g，"新字符串")
'asssdfgghhjsssertyu'.replace(/sss/g,'123')
這種形式要替換的字符串沒(méi)法用參數(shù)，可以用
??????? var str = 'asssdfgghhjsssertyu'
??????? function replacer(str,str1,str2){
??????????? return str.replace(new RegExp(str1,'g'),str2)
??????? }
??????? console.log(replacer(str,'sss',12))
方法二
??????? var str = 'asssdfgghhjsssertyu'
??????? function replacer(str,str1,str2){
??????????? var arg = str.split(str1)
??????????? return arg.join(str2)
??????? }
?????? console.log(replacer(str,'sss',12))
Q 37 給定一個(gè)字符串，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引。如果不存在，則返回 -1。
案例:
s = "leetcode"
返回 0.
s = "loveleetcode",
返回 2.
解法一? ： 有點(diǎn)暴力，主要思路為拋出本身后，利用indexOf查詢查找是否存在重復(fù)值，不存在則直接返回當(dāng)前索引
/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function(s) {
??? var len = s.length;
??? for(var i=0;i<len;i++){
??????? var str? = s,
??????? test = str.split('');
??????? test.splice(i,1);
??????? var sub = test.indexOf(s[i]);
??????? if(sub === -1) return i;
??? }
??? return -1;
};
方法二
方法一用到了indexOf ,所以時(shí)間復(fù)雜度也達(dá)到了O（n^2）,
則想到了利用哈希來(lái)存儲(chǔ)重復(fù)的次數(shù)，在循環(huán)字符串查找哈希中值為1的這個(gè)字符，第一次遇到則返回，這樣循環(huán)次數(shù)相對(duì)減少時(shí)間復(fù)雜度也降到了O（n）
/**
* @param {string} s
* @return {number}
*/
var firstUniqChar = function(s) {
??? var len = s.length,
??????? haxi = {};
??? for(var i=0;i<len;i++){
??????? var sub = haxi[s[i]];
??????? if(sub){
??????????? haxi[s[i]] = ++sub;
??????? }else{
??????????? haxi[s[i]] = 1;
??????? }
??? }
???? for(var i=0;i<len;i++){
??????? if(haxi[s[i]] === 1) {
??????????? return i
??????? }
??? }
??? return -1;
};
Q 38 實(shí)現(xiàn)一個(gè)函數(shù) find(obj, str)，滿足:
如
??????? var obj = {a:{b:{c:1}}};
??????? var obj2 = {d:{e:{f:2}}}
??????? find(obj, 'a.b.c') //返回1
find(obj, 'a.d.c') //返回undefined?
??????? find(obj2, 'd')??? //返回{e:{f:2}}
??????? find(obj2, 'd.e.f') //返回2
??? function find(obj,str){
??????? var arrStr = str.split('.')
??????? var newObj = obj
??????? for(var i=0;i<arrStr.length;i++){
??????????? var temp = newObj[arrStr[i]]
??????????? if(temp){
??????????????? newObj = temp
??????????? }else{
??????????????? return undefined
??????????? }
??????? }
??????? return newObj
??? }
??? var obj = {a:{b:{c:1}}};
??? var obj2 = {d:{e:{f:2}}}
??? console.log(find(obj, 'a.b.c')) //返回1
console.log(find(obj, 'a.d.c')) //返回undefined?
??? console.log(find(obj2, 'd'))?? //返回{e:{f:2}}
??? console.log(find(obj2, 'd.e.f')) //返回2
Q39 把數(shù)值轉(zhuǎn)化為貨幣形式，并保留兩位小數(shù)。
例如：輸入1234567.891，輸出1,234,567.89
??? function int2str (num){
??????? let newNum = num.toFixed(2)
??????? let arr = newNum.toString().split('.')
??????? let strLeft = arr[0],strRight = arr[1]
??????? let str = strLeft.split('').reverse()
??????? for(let i=0;i<str.length;i++){
??????????? if((i+1)%4 === 0){
??????????????? str.splice(i,0,',')
??????????? }
??????? }
??????? str.reverse()
??????? let reg = str.join('') + '.' + strRight
??????? return reg
??? }
??? console.log(int2str(1234567.891))
Q40 JS寫(xiě)一個(gè)方法，傳入一個(gè)數(shù)組，返回該數(shù)組的層深(維度)
如：var arr = [1,[2,3,[4,[5,6,7]],11],[8]]
??? function fo(arr,len){
??????? var flag = false
??????? var arr1= []
??????? for(var i=0;i<arr.length;i++){
??????????? if(!!arr[i].length){
??????????????? for(var j=0;j<arr[i].length;j++){
??????????????????? arr1.push(arr[i][j])
??????????????? }
??????????????? flag = true
??????????? }
??????? }
??????? if(flag){
??????????? len++
??????????? return fo(arr1,len)
??????? }else{
??????????? return len
??????? }
??? }
??? var arr = [1,[2,3,[4,[5,6,7]],11],[8]]
??? console.log(fo(arr,1))
作者：指尖跳動(dòng)
鏈接：https://www.jianshu.com/p/2f38ac50c63a
來(lái)源：簡(jiǎn)書(shū)
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
