Parity rearrangement of linked list

Parity rearrangement of NC133 linked list

• Use a cnt counter

• When the node is the odd node, it will be inserted into the odd linked list

• When the node is the even node, it will be inserted into the even linked list

• Finally, point the next of the tail pointer of the odd chain to the header node of the even chain

• Don't forget to cut off unnecessary relationships in the middle. For example, the next of the tail pointer of the even list points to null. Otherwise, when the number of nodes in the list is odd, the tail pointer of the even list will point to the last node of the odd list, resulting in falling into a ring and problems.

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly
 *
 * 
 * @param head ListNode class 
 * @return ListNode class
 */
function oddEvenList( head ) {
    if(!head || !head.next) return head
    let p = head
    let oddHead = null
    let evenHead = null
    let oddRear, evenRear
    let cnt = 1
    while(p){
        if(cnt%2 == 1){
            if(oddHead == null){
                oddHead = p
                oddRear = p
            }else{
                oddRear.next = p
                oddRear = p
            }
        }else{
            if(evenHead == null){
                evenHead = p
                evenRear = p
            }else{
                evenRear.next = p
                evenRear = p
            }
        }
        cnt ++
        p = p.next
    }
    evenRear.next = null
    oddRear.next = evenHead
    
    return oddHead;
}
module.exports = {
    oddEvenList : oddEvenList
};

Maximum path sum in binary tree

Maximum path sum in NC6 binary tree

• Depth first traversal, post root traversal
• Traverse to the left and right nodes of the leaf node, null returns 0
• The return value of the current node means the maximum path including the current node. There are three types:
  • Start directly from the current node
  • From the left subtree of the current node to the current node
  • From the right subtree of the current node to the current node
  • Take the maximum of the above three
• leftPath is the maximum path of the left subtree
• rightPath is the maximum path of the right subtree
• nowPath represents the current maximum path. If the maximum paths of the left and right subtrees are greater than 0, they can be accumulated
• Then compare and update with ans, and maintain that ans is the largest path in the current path while traversing. When traversing is completed, ans is the largest path in the whole tree.

/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */

/**
  * 
  * @param root TreeNode class 
  * @return int integer
  */
function maxPathSum( root ) {
    let ans = -10000
    function dfs(node){
        if(!node) return 0;
        let leftPath = dfs(node.left)
        let rightPath = dfs(node.right)
        let nowPath = node.val
        if(leftPath > 0) nowPath += leftPath
        if(rightPath > 0) nowPath += rightPath
        ans = Math.max(ans , nowPath)
        return Math.max(node.val , node.val + Math.max(leftPath , rightPath))
    }
    dfs(root)
    return ans
}
module.exports = {
    maxPathSum : maxPathSum
};

Symmetric binary tree

NC16 symmetric binary tree

• The current tree is empty or has only one node, which is symmetrical

• Number of traversals using auxiliary queue hierarchy

• You only need to judge whether the nodes of each layer are symmetrical. If not, false is returned directly

• If the traversal of layers ends successfully and each layer is symmetrical, return true

• It should be noted that to consider the status of empty nodes, you can set a node with val of - 1 to fill in the position of empty nodes. If the left and right children of leaf nodes are empty, it will not be considered.

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function isSymmetrical(pRoot)
{
    if(!pRoot || !pRoot.left&&!pRoot.right) return true
    function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
    }
    let queue = [pRoot]
    while(queue.length != 0){
        let len = queue.length
        while(len --){
            let font = queue.shift()
            if(!font.left&&!font.right){
                
            }else{
                if(font.left) queue.push(font.left)
                else queue.push(new TreeNode(-1))
                if(font.right) queue.push(font.right)
                else queue.push(new TreeNode(-1))
            }
            
        }
        
        for(let i = 0 ; i < Math.floor(queue.length/2) ; i ++){
            if(queue[i].val != queue[queue.length - 1 - i].val){
                return false
            }
        }
        
    }
    return true
}
module.exports = {
    isSymmetrical : isSymmetrical
};

bracket-generating

NC26 bracket generation

• This question is a bit similar to the arrangement and combination of high school
  • It is equivalent to five left parentheses with four empty positions in the middle
  • We can select several positions i(1~4) from the four empty positions and put the right parentheses
  • The remaining (n - i) right parentheses can be placed directly at the end
• Set ans as the final returned result array, and each array for each arrangement
• Set left and right to indicate the current number of left and right parentheses
• If left == n, it means that we have finished arranging. We just need to splice the remaining right parentheses at the end, convert them to string type through the join method, and then add the ans array
• It should be noted here that the array in js is also an object, so when splicing the remaining right parentheses, it is best to copy the depth of each array to the result array for further operation to facilitate subsequent backtracking
• Another note is that the current position can be placed only when right < left is true. Such a sequence of parentheses is valid

/**
  * 
  * @param n int integer 
  * @return string One dimensional array of strings
  */
function generateParenthesis( n ) {
    let ans = []
    let each = []
    function dfs(left , right){
        if(left == n){
            let k = n*2 - each.length
            let result = [...each]
            while(k--){
                result.push(')')
            }
            
            ans.push(result.join(''))
            return;
        }
        if(right < left){
            each.push(')')
            dfs(left , right + 1)
            each.pop()
        }
        each.push('(')
        dfs(left + 1 , right)
        each.pop()
    }
    dfs(0 , 0)
    return ans;
}
module.exports = {
    generateParenthesis : generateParenthesis
};

Rotate matrix clockwise

NC18 clockwise rotation matrix

• Through observation, we can know that 90 ° clockwise rotation is to change the original row i to the penultimate column i

• We can use an auxiliary array tmp to do this

• Time complexity On2, space complexity On2

/**
 * The class name, method name and parameter name in the code have been specified. Do not modify them. Just return the value specified by the method directly
 *
 * 
 * @param mat int Integer two-dimensional array 
 * @param n int integer 
 * @return int Integer two-dimensional array
 */
function rotateMatrix( mat ,  n ) {
    let tmp = []
    let k = n
    while(k--){
        tmp.push([])
    }
    for(let i = n - 1 ; i >= 0 ; i--){
        for(let j = 0 ; j < n ; j++){
            tmp[j].push(mat[i][j])
        }
    }
    return tmp
}
module.exports = {
    rotateMatrix : rotateMatrix
};