常见算法题

数组转树

�定义一个 convert 函数，将以下数组转换为树结构。
�

interface IArrayItem {
  id: number
  name: string
  parentId: number
}
interface ITreeNode {
  id: number
  name: string
  children?: ITreeNode[]
}
function convert(arr: IArrayItem[]): ITreeNode | null {
  // 用于 id 和 treeNode 的映射
  const idToTreeNode: Map<number, ITreeNode> = new Map()
  let root = null
  arr.forEach(item => {
    const { id, name, parentId } = item
    // 定义 tree node 并加入 map
    const treeNode: ITreeNode = { id, name }
    idToTreeNode.set(id, treeNode)
    // 找到 parentNode 并加入到它的 children
    const parentNode = idToTreeNode.get(parentId)
    if (parentNode) {
      if (parentNode.children == null) parentNode.children = []
      parentNode.children.push(treeNode)
    }
    // 找到根节点
    if (parentId === 0) root = treeNode
  })
  return root
}
const arr = [
  { id: 1, name: '部门A', parentId: 0 }, // 0 代表顶级节点，无父节点
  { id: 2, name: '部门B', parentId: 1 },
  { id: 3, name: '部门C', parentId: 1 },
  { id: 4, name: '部门D', parentId: 2 },
  { id: 5, name: '部门E', parentId: 2 },
  { id: 6, name: '部门F', parentId: 3 },
]
const tree = convert(arr)
console.info(tree)

树转数组

思路

• 遍历树节点（广度优先）
• 讲树节点转为Array Item,push到数组
• 根据父子关系，找到Array Item的parentld ```typescript interface IArrayItem { id: number name: string parentId: number }

interface ITreeNode { id: number name: string children?: ITreeNode[] }

function convert1(root: ITreeNode): IArrayItem[] { // Map const nodeToParent: Map = new Map()

const arr: IArrayItem[] = []
// 广度优先遍历，queue
const queue: ITreeNode[] = []
queue.unshift(root) // 根节点 入队
while (queue.length > 0) {
    const curNode = queue.pop() // 出队
    if (curNode == null) break
    const { id, name, children = [] } = curNode
    // 创建数组 item 并 push
    const parentNode = nodeToParent.get(curNode)
    const parentId = parentNode?.id || 0
    const item = { id, name, parentId }
    arr.push(item)
    // 子节点入队
    children.forEach(child => {
        // 映射 parent
        nodeToParent.set(child, curNode)
        // 入队
        queue.unshift(child)
    })
}
return arr

}

const obj = { id: 1, name: ‘部门A’, children: [ { id: 2, name: ‘部门B’, children: [ { id: 4, name: ‘部门D’ }, { id: 5, name: ‘部门E’ } ] }, { id: 3, name: ‘部门C’, children: [ { id: 6, name: ‘部门F’ } ] } ] } const arr1 = convert1(obj) console.info(arr1)

<a name="kG8VU"></a>
## [两数之和](https://leetcode-cn.com/problems/two-sum/)
- 使用 map
```javascript
var twoSum = function(nums, target) {
    // 暴力遍历
    // for(let i = 0, len = nums.length; i<len-1; i++) {
    //     for(let j = i+1; j < len; j++) {
    //         if(nums[i] + nums[j] == target){
    //             return [i, j]
    //         }
    //     }
    // }
    // return null;
    let map = new Map();
    for(let i = 0, len = nums.length; i < len; i++) {
        if(map.has(target-nums[i])) {
            return [map.get(target-nums[i]), i];
        } else {
            map.set(nums[i], i)
        }
    }
    return null
};

三数之和

var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        // 因为数组已经排序完，如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(nums[i] > 0) break; 
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L<R && nums[L] == nums[L+1]) L++; // 去重
                while (L<R && nums[R] == nums[R-1]) R--; // 去重
                L++;
                R--;
            }
            else if (sum < 0) L++;
            else if (sum > 0) R--;
        }
    }        
    return ans;
};

最长回文子串

• 如果子串只有一个字母，那么该子串就是最短的回文字符串；

• 对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如：对于回文字符串“ababa”，我们把首尾两个字母去除后，剩下的子串一定也是回文串。

  暴力破解

  
  

  中心扩散法

  https://leetcode-cn.com/problems/longest-palindromic-substring/solution/by-smooth-b-5rej/
  https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

  var longestPalindrome = function(s) {
    let left, right, nowMax, len = s.length, maxLength = 0, maxStart;
    for(let i = 0; i < len; i++) {
        left = i - 1;
        right = i + 1;
        nowMax = 1; // 当前区间最大长度重置为 1
        // 从中心 i 出发，往左找到第一个不同的，即开始找可能会不满足题意的回文子串，并准备判断
        while(left >= 0 && s[left] === s[i]) {
            left--;
            nowMax++;
        }
        // 从中心 i 出发，往右找到第一个不同的，即开始找可能会不满足题意的回文子串，并准备判断
        while(right < len && s[right] === s[i]) {
            right++;
            nowMax++;
        }
        // 开始左右指针各往外遍历，寻找到第一个不符合回文串的位置
        while(left >= 0 && right < len && s[left] === s[right]) {
            left--;
            right++;
            nowMax += 2;
        }
        // 遍历结束，看看此时子串是否最大
        if(nowMax > maxLength) {
            maxLength = nowMax;
            maxStart = left;
        }
    }
  
    return s.substring(maxStart + 1, maxStart + 1 + maxLength);
  };
  

动态规划

https://leetcode-cn.com/problems/longest-palindromic-substring/solution/shi-pin-tu-jie-dong-tai-gui-hua-zui-chang-hui-wen-/

解题思路：

• 已知单个字母就是一个回文子串，那么我们可以从两个字符开始判断，如：“ababc”，我们依次比较 “ab”、“ba”、“ab”、“bc”，判断是否存在回文字符串，并记录每个子串的结果（什么结果？每个子串开始下标和结束下标位置对应的结果——是否为回文字符串：true/false。怎么记录？用二维数组），接着开始依次比较三个字符串”abc“、”bab“、”abc“ 并记录结果，最后依次比较四个字符串 ”abab“、”babc“并记录结果。这期间每次比较完子串后，如果当前子串是回文字符串时，会去判断当前子串的长度是否大于当前记录的最大子串长度，如果大于的话就会覆盖最大值。

  1、获取不同长度的子串

  ```javascript function longestPalindrome(str) { const len = str.length; if (len < 2) {

    return str;
  

  } for (let childStrLen = 2; childStrLen <= len; childStrLen++) {

    for (let l = 0; l < len; l++) {
        let r = childStrLen + l - 1;
        // 一旦子串的结束位置等于/超过字符串长度，就终止本轮比较
        if (r >= len) {
            break;
        }
        console.log("childStr", str.substring(l, r + 1));
    }
  

  } }

console.log(‘result’, longestPalindrome(“babadab”));

// childStr ba // childStr ab // childStr ba // childStr ad // childStr da // childStr ab // childStr bab // childStr aba // childStr bad // childStr ada // childStr dab // childStr baba // childStr abad // childStr bada // childStr adab // childStr babad // childStr abada // childStr badab // childStr babada // childStr abadab // childStr babadab

<a name="DUCn4"></a>
#### 2、创建二维数组并赋默认值
```javascript
function longestPalindrome(str) {
    const len = str.length;
    if (len < 2) {
        return str;
    }

    // 创建二维数组并赋默认值
    let twoDimensionalArr = Array.from(new Array(len), () => new Array(len).fill(false));
    // 单个字母是回文字符串，所以直接设置为 true
    twoDimensionalArr.forEach((it, i) => twoDimensionalArr[i][i] = true);

    for (let childStrLen = 2; childStrLen <= len; childStrLen++) {
        for (let l = 0; l < len; l++) {
            let r = childStrLen + l - 1;
            // 一旦子串的结束位置等于/超过字符串长度，就终止本轮比较
            if (r >= len) {
                break;
            }
        }
    }
}

console.log('result', longestPalindrome("babadab"));

// 我们只需要看对角线右上方的值就行，因为 l 的不可能会比 r 大，所以不会用到对角线下方的值
// [
//     [true, false, false, false, false, false, false],
//     [false, true, false, false, false, false, false],
//     [false, false, true, false, false, false, false],
//     [false, false, false, true, false, false, false],
//     [false, false, false, false, true, false, false],
//     [false, false, false, false, false, true, false],
//     [false, false, false, false, false, false, true]
// ]

3、开始比较

function longestPalindrome(str) {
    const len = str.length;
    if (len < 2) {
        return str;
    }
    let maxLen = 1;
    let begin = 0;
    // 创建二维数组并赋默认值
    let twoDimensionalArr = Array.from(new Array(len), () => new Array(len).fill(false));
    // 单个字母是回文字符串，所以直接设置为 true
    twoDimensionalArr.forEach((it, i) => twoDimensionalArr[i][i] = true);
    for (let childStrLen = 2; childStrLen <= len; childStrLen++) {
          for (let l = 0; l < len; l++) {
            let r = childStrLen + l - 1;
            // 一旦子串的结束位置等于/超过字符串长度，就终止本轮比较
            if (r >= len) {
                break;
            }
            // 如果首尾字符不相等，那么当前子串肯定不是回文字符串
            if (str[l] !== str[r]) {
                twoDimensionalArr[l][r] = false;
            } else {
                // 特殊情况：如果当前子串长度为 2 并且首尾字符相等时，那么当前子串就是回文字符串，不需要去掉首尾两个字符，再判断中间内容是否为回文字符串
                if (childStrLen === 2) {
                    twoDimensionalArr[l][r] = true;
                } else {
                    // 如果首尾字符相等，那就去掉首尾两个字符，继续判断子串中间的内容是否为回文字符串
                    twoDimensionalArr[l][r] = twoDimensionalArr[l + 1][r - 1];
                }
            }
            if (twoDimensionalArr[l][r] && childStrLen > maxLen) {
                maxLen = childStrLen;
                begin = l;
            }
        }
    }
    // console.log(twoDimensionalArr);

    return str.substring(begin, begin + maxLen);
}

console.log('result', longestPalindrome("babadab"));

// 默认值
// [
//     [true, false, false, false, false, false, false],
//     [false, true, false, false, false, false, false],
//     [false, false, true, false, false, false, false],
//     [false, false, false, true, false, false, false],
//     [false, false, false, false, true, false, false],
//     [false, false, false, false, false, true, false],
//     [false, false, false, false, false, false, true]
// ]

// 最终的值
// [
//     [true, false, true, false, false, false, false], 
//     [false, true, false, true, false, false, false], 
//     [false, false, true, false, false, false, true], 
//     [false, false, false, true, false, true, false],
//     [false, false, false, false, true, false, false], 
//     [false, false, false, false, false, true, false], 
//     [false, false, false, false, false, false, true]
// ]

？？？疑问？？？

//  这里用 map 代替了二维数组，这个代码在 LeetCode 可以运行成功，但是一提交就会超时，目前不明所以
function longestPalindrome(str) {
    const len = str.length;
    if (len < 2) {
        return str;
    }
    let maxLen = 1;
    let begin = 0;
    let map = new Map();
    for (let i = 0; i < len; i++) {
        map.set(i + '-' + i, true)
    }
    for (let childStrLen = 2; childStrLen <= len; childStrLen++) {
        for (let l = 0; l < len; l++) {
            let r = childStrLen + l - 1;
            // 一旦子串的结束位置等于/超过字符串长度，就终止本轮比较
            if (r >= len) {
                break;
            }
            const key = l + '-' + r;
            if (str[l] !== str[r]) {
                map.set(key, false)
            } else {
                if (childStrLen === 2) {
                    map.set(key, true)
                } else {
                    const key2 = (l + 1) + '-' + (r - 1);
                    const val = map.get(key2);
                    map.set(key, val)
                }
            }
            if (map.get(key) && childStrLen > maxLen) {
                maxLen = childStrLen;
                begin = l;
            }
        }
    }
    console.log(map);
    return str.substring(begin, begin + maxLen);
}

console.log('result', longestPalindrome("babadab"));