JavaScript算法题

本是古典何须时尚 2022-05-09 18:04 148阅读 0赞

**1. 给定一串数据将其转化为树形结构**

// 数据：
     let arr = [
            {
                id: 1,
                name: 'js',
                parent:'前端'
            },
            {
                id: 2,
                name: '前端'
            },
            {
                id: 3,
                name: 'react',
                parent:'js'
            },
            {
                id: 4,
                name: 'jquery',
                parent:'js'
            },
            {
                id: 5,
                name: 'css3',
                parent:'css'
            },
            {
                id: 6,
                name: 'css',
                parent:'前端'
            }
        ];

// 方法一：非递归
    <script>
        function findChild(arr, root) {
          var data = {}
          for (var i in arr) {
            data[arr[i].name] = arr[i]
          }
          for (var j in data) {
            if (data[j].parent) { // 该数据具有parent
              if (!data[data[j].parent].child) {
                data[data[j].parent].child = []
              }
              data[data[j].parent].child.push(data[j])
            } else {
              var res = Object.assign({}, data[j])
            }
          }
          return res
        }
        function findRoot(arr) {
          for (var i in arr) {
            if (!arr[i].parent) {
              return arr[i]
            }
          }
        }
        var root = findRoot(arr)
        console.log(findChild(arr))
      </script>
    
    // 方法二： 递归
    <script>
        function findChild(arr, parent) {
          var child = []
          for (var i in arr) {
            if (arr[i].parent && arr[i].parent === parent.name) {
              child.push(arr[i])
            }
          }
          if (child.length > 0) {
            parent.child = child
            for (var i in child) {
              findChild(arr, child[i])
            }
          }
        }
        function findRoot(arr) {
          for (var i in arr) {
            if (!arr[i].parent) {
              return arr[i]
            }
          }
        }
        var root = findRoot(arr);
        var obj = Object.assign({}, root);
        findChild(arr, obj)
        console.log(obj)
    </script>

**2. 对一个数组进行随机排序？**

var arr = [1,2,3,4,5,6,7,8,9,10];
    arr.sort(function(){
      return Math.random() - 0.5;
    })
    console.log(arr);

**3. 求一段字符串中的最长回文字符串？**

方法一：

思路：

1.  提供一个函数用于判断一个字符串是否是回文字符串。
2.  使用for循环，从第一个位置开始不断向后取字符直至最后，每取一次便判断其是否为回文字符串，然后从第二个位置开始不断向后取字符，依次类推。

方法二：

思路:

1.  只使用一层for循环遍历，先获取单个字符，设置指针i，j指向该字符，判断该字符左侧（i - 1）和右侧（j + 1）是否相等，如果相等，继续递减i，递增j判断。
2.  需要处理形如 ‘aab’ 这样的字符串，应该返回 ‘aa’ ，而不是 ‘a’

**4. 数组的排序？**

// 快速排序
    <script>
        var arr = [10, 33, 44, 4, 12, 15, 0];
        function quickSort(arr) {
          if (arr.length <= 1) {
            return arr
          }
          var index = Math.floor(arr.length - 1 / 2)
          var val = arr.splice(index,1) // 删除中间值
          var left = []
          var right = []
          for (var i = 0; i <= arr.length - 1; i++) {
            if (arr[i] < val) {
              left.push(arr[i])
            } else {
              right.push(arr[i])
            }
          }
          return quickSort(left).concat(val, quickSort(right))
        }
        console.log(quickSort(arr)) // [0, 4, 10, 12, 15, 33, 44]
    </script>
      
    // 冒泡排序
    <script>
        var arr = [10, 33, 44, 4, 12, 15, 0];
        function sort(arr) { // 每相邻的两个元素比较，大的沉底
          for (var i = 0; i < arr.length - 1; i++) { // 控制比较的次数
            for (var j = 0; j < arr.length - 1 - i; j++) {
              if (arr[j] > arr[j + 1]) {
                var temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
              }
            }
          }
          return arr
        }
        console.log(sort(arr)) // [0, 4, 10, 12, 15, 33, 44]
    </script>
      
    // 选择排序
    <script>
        var arr = [10, 33, 44, 4, 12, 15, 0];
        function sort(arr) { // 每一个元素和后面的所有元素比较，小的元素上浮
          for (var i = 0; i < arr.length - 1; i++) {
            for (var j =  i + 1; j < arr.length - 1; j++) {
              if (arr[i] > arr[j]) {
                var temp = arr[j]
                arr[j] = arr[i]
                arr[i] = temp
              }
            }
          }
          return arr
        }
        console.log(sort(arr)) // [0, 4, 10, 12, 15, 33, 44]
    </script>

**5. 找出给定字符串中出现次数最多的字符？**

**6. JS实现斐波那契数列？**

数列：1，1，2，3，5，8，13，21…  
给定f(1) = 1， f(2) = 1，之后每项值等于前两项之和，求f(n)？

**7. 给定一个数，求其阶乘？**

**8. 求一个数组中最大值和最小值之差？**

var arr = [10, 5, 11, 7, 8, 9]
    var max = Math.max(...arr) // 或使用Math.max.apply(null, arr)
    var min = Math.min(...arr)
    console.log(max - min) // 6

附：apply方法中传入null或undefined时执行的JS对象是window对象。

**9. 判断一个字符串在另一个字符串中的位置（不使用字符串的任何方法）？**

**10. JavaScript实现数组的快速排序？**

/**
    快速排序思路：
    1. 定义初始start和end,i和j,start为数组首位，end为数组末位，i初始化为数组首位，j初始化为数组末位。
    2. 将arr[start]作为比较的基数，定义key=arr[start]，从右向左找比key大的数，满足则j--,不满足时说明arr[j] < key,保证互换位置后key右侧的值均大于key。
    3.同理，从左向右找比key小的数,满足则i++，不满足时说明arr[i] > key,保证互换位置后key左侧的值均小于key。
    4.对当前key左侧和右侧的数据分别重复上述过程。
    */
    
    var arr = [12, 11, 13, 4, 5, 7, 18, 33, 99]
    function quickSort(arr, start, end) {
      var i = start
      var j = end
      var key = arr[start]
      while(i < j) {
        while(i < j && arr[j] >= key) {
          j--
        }
        if (arr[j] <= key) {
          var temp = arr[j]
          arr[j] = arr[i]
          arr[i] = temp
        }
        while(i < j && arr[i] <= key) {
          i++
        }
        if (arr[i] >= key) {
          var temp = arr[i]
          arr[i] = arr[j]
          arr[j] = temp
        }
      }
      if (i > start) {
        quickSort(arr, start, i - 1)
      }
      if (j < end) {
        quickSort(arr, j + 1, end)
      }
    }
    quickSort(arr, 0, arr.length - 1)
    console.log(arr)

**11. 使用快速排序查找数组中位数（奇数）？**

**12. 求f(2)(3)(4)…的值？**

运算规则：res = 2 + 3 + 4 + … （使用柯里化）

详见：[https://segmentfault.com/a/1190000008263193][https_segmentfault.com_a_1190000008263193]

// 方法一：
    function add(a){
        var sum = 0;
        sum += a;     
        return function temp(b) {   
            if (arguments.length === 0) {
                return sum;
            } else {
                sum= sum+ b;
                return temp;
            }
        }
    }
    add(2)(3)(4)(5)(); //14
    
    // 方法二：（匿名函数）
    function add() {
      var _args = [];
      return function(){ 
        if(arguments.length === 0) { 
          return _args.reduce(function(a,b) {
            return a + b;
          });
        }
        [].push.apply(_args, [].slice.call(arguments));
        return arguments.callee;
      }
    }
    var sum = add();
    sum(2,3)(4)(5)(); //14
        
    // 方法三：
    function add(a) {
        var sum = 0;  
            sum += a;     
        var temp = function(b) {
            if(arguments.length===0){
                return sum;
            } else {
                sum = sum+ b;
                return temp;
            }
        }
        temp.toString = temp.valueOf = function() {
            return sum; 
        } 
        return temp;
    }
    add(2)(3)(4)(5)(); //14

**13. 使用递归获取指定的省市区的value值？**

var localData = [
        {
          value: 3,
          label: '河北',
          children: [{
            value: 3,
            label: '石家庄市',
            children: [{
              value: 37,
              label: '长安区'
            },
            {
              value: 38,
              label: '桥东区'
            }]
          }]
        },{
          value: 111,
          label: '上海',
          children: [{
            value: 222,
            label: '闵行区'
          }]
        }]
      function findChild (data, list, res = []) {
        let info = list.shift()
        if (!info) return res
        let dataInfo = data.find(item => item.label === info)
        res.push(dataInfo.value)
        return dataInfo.children ? findChild(dataInfo.children, list, res) : res
      }
      console.log(findChild(localData, ['河北', '石家庄市', '桥东区'])) // [3, 3, 38]
      console.log(findChild(localData, ['上海', '闵行区'])) // [111, 222]

[https_segmentfault.com_a_1190000008263193]: https://segmentfault.com/a/1190000008263193