LeetCode //2675. Array of Objects to Matrix (Day 19 of LC JavaScript Challenge)

这篇具有很好参考价值的文章主要介绍了LeetCode //2675. Array of Objects to Matrix (Day 19 of LC JavaScript Challenge)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

2675. Array of Objects to Matrix

Write a function that converts an array of objects arr into a matrix m.

arr is an array of objects or arrays. Each item in the array can be deeply nested with child arrays and child objects. It can also contain numbers, strings, booleans, and null values.

The first row m should be the column names. If there is no nesting, the column names are the unique keys within the objects. If there is nesting, the column names are the respective paths in the object separated by “.”.

Each of the remaining rows corresponds to an object in arr. Each value in the matrix corresponds to a value in an object. If a given object doesn’t contain a value for a given column, the cell should contain an empty string “”.

The colums in the matrix should be in lexographically ascending order.

 

Example 1:

Input:
arr = [
{“b”: 1, “a”: 2},
{“b”: 3, “a”: 4}
]
Output:
[
[“a”, “b”],
[2, 1],
[4, 3]
]
Explanation:
There are two unique column names in the two objects: “a” and “b”.
“a” corresponds with [2, 4].
“b” coresponds with [1, 3].

Example 2:

Input:
arr = [
{“a”: 1, “b”: 2},
{“c”: 3, “d”: 4},
{}
]
Output:
[
[“a”, “b”, “c”, “d”],
[1, 2, “”, “”],
[“”, “”, 3, 4],
[“”, “”, “”, “”]
]
Explanation:
There are 4 unique column names: “a”, “b”, “c”, “d”.
The first object has values associated with “a” and “b”.
The second object has values associated with “c” and “d”.
The third object has no keys, so it is just a row of empty strings.

Example 3:

Input:
arr = [
{“a”: {“b”: 1, “c”: 2}},
{“a”: {“b”: 3, “d”: 4}}
]
Output:
[
[“a.b”, “a.c”, “a.d”],
[1, 2, “”],
[3, “”, 4]
]
Explanation:
In this example, the objects are nested. The keys represent the full path to each value separated by periods.
There are three paths: “a.b”, “a.c”, “a.d”.

Example 4:

Input:
arr = [
[{“a”: null}],
[{“b”: true}],
[{“c”: “x”}]
]
Output:
[
[“0.a”, “0.b”, “0.c”],
[null, “”, “”],
[“”, true, “”],
[“”, “”, “x”]
]
Explanation:
Arrays are also considered objects with their keys being their indices.
Each array has one element so the keys are “0.a”, “0.b”, and “0.c”.

Example 5:

Input:
arr = [
{},
{},
{},
]
Output:
[
[],
[],
[],
[]
]
Explanation:
There are no keys so every row is an empty array.

Constraints:
  • 1 <= arr.length <= 1000
  • unique keys <= 1000

From: LeetCode
Link: 2675. Array of Objects to Matrix
文章来源地址https://www.toymoban.com/news/detail-455961.html


Solution:

Ideas:
The JavaScript function jsonToMatrix() aims to convert an array of JavaScript objects (possibly nested) into a 2-dimensional matrix. It uses depth-first search (DFS) to traverse the nested objects, creating a unique set of keys and a map for each object in the input array.
Here’s the step-by-step idea behind this function:
1. Initialize empty maps and key set: For each object in the input array, an empty map is created. These maps will store keys and corresponding values for each object. An empty set is also created to store unique keys.
2. Iterative DFS on each object: For each object in the array, an iterative DFS is performed. The DFS uses a stack to keep track of the current state. It starts with the entire object, pushes each key into the stack, and recursively pushes nested keys if a value is an object or array.
3. Populate maps and key set: In the DFS, each time it encounters a key-value pair, it adds the key to the current path (represented as curr.join(‘.’)), and if the value isn’t an object or array, it sets this path and corresponding value in the map of the current object (lookup.set(curr.join(‘.’), u[v])). It also adds this key to the set of unique keys (keys_set.add(k)).
4. Construct the matrix: After populating the maps and key set, it constructs the matrix. The first row is filled with the sorted unique keys. For each subsequent row corresponding to an object, it checks if the object has a value for each key (column) and adds it to the row, or adds an empty string if there’s no value.
In this way, the function transforms an array of possibly nested objects into a matrix, where each row corresponds to an object, each column corresponds to a unique key, and each cell contains the value of the corresponding key for the corresponding object, or an empty string if the key doesn’t exist in the object. The keys are sorted in lexicographic order.
Note: The time complexity is O(l * mlogm + m * n) and the space complexity is O(l * m + m * n), where l is the maximum depth of the nested objects, m is the number of unique keys, and n is the number of objects in the array.
Code:
/**
 * @param {Array} arr
 * @return {Matrix}
 */
var jsonToMatrix = function(arr) {
    let row = new Array(arr.length).fill(null).map(() => new Map());  
    let keys_set = new Set();  
    arr.forEach((x, i) => {
        const iter_dfs = (u, lookup) => {  
            let stk = [[1, u, undefined]];  
            let curr = []  
            while (stk.length) {  
                const [step, u, v] = stk.pop();  
                if (step === 1) {  
                    for (const v in u) {  
                        stk.push([3, u, v]);  
                        stk.push([2, u, v]);  
                    }  
                } else if (step === 2) {  
                    curr.push(v);  
                    if (!(u[v] !== null && (typeof u[v] === 'object' || Array.isArray(u[v])))) {  
                        lookup.set(curr.join('.'), u[v]);  
                    } else {  
                        stk.push([1, u[v], null])  
                    }  
                } else if (step === 3) {  
                    curr.pop(); 
                }
            }
        }
        iter_dfs(x, row[i]); 
        for (const [k, _] of row[i].entries()) {  
            keys_set.add(k);
        }
    });  
    let result = [Array.from(keys_set).sort()];  
    for (let i = 0; i < row.length; ++i) {  
        result.push([])
        for (let j = 0; j < result[0].length; ++j) {  
            result[i+1].push(row[i].has(result[0][j]) ? row[i].get(result[0][j]) : '');
        }
    }
    return result
};

到了这里,关于LeetCode //2675. Array of Objects to Matrix (Day 19 of LC JavaScript Challenge)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • numpy 邻接矩阵转稀疏矩阵 array to scipy csr_matrix

    也就是说,一个dense的numpy矩阵,如何转换成scipy包里面的sparse的csr矩阵看代码: 输出: print(csr_a.toarray()) print(csr_a.tocoo())

    2024年02月12日
    浏览(47)
  • LeetCode --- 1929. Concatenation of Array 解题报告

    Given an integer array  nums  of length  n , you want to create an array  ans  of length  2n  where  ans[i] == nums[i]  and  ans[i + n] == nums[i]  for  0 = i n  ( 0-indexed ). Specifically,  ans  is the  concatenation  of two  nums  arrays. Return  the array  ans . Example 1: Example 2:

    2024年02月09日
    浏览(46)
  • LeetCode 2475. Number of Unequal Triplets in Array【数组,排序,哈希表】简单

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月09日
    浏览(43)
  • LeetCode 2496. Maximum Value of a String in an Array【字符串,数组】简单

    本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,

    2024年02月11日
    浏览(57)
  • day19【LeetCode力扣】160.相交链表

    1.题目描述 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交**:** 题目数据 保证 整个链式结构中不存在环。 注意 ,函数返回结果后,链表必须 保持其原始结构

    2024年01月18日
    浏览(37)
  • 力扣python刷题day04|LeetCode24、19、160、142

    题目 来源:24:两两交换链表中的节点 建议使用虚拟头结点,这样会方便很多,要不然每次针对头结点(没有前一个指针指向头结点),还要单独处理。 接下来就是交换相邻两个元素了,此时一定要画图,不画图,操作多个指针很容易乱,而且要操作的先后顺序 方法: 题目

    2024年02月16日
    浏览(36)
  • LeetCode //C - 19. Remove Nth Node From End of List

    Given the head of a linked list, remove the n t h n^{th} n t h node from the end of the list and return its head.   Example 1: Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1] Constraints: The number of nodes in the list is sz. 1 = sz = 30 0 = Node.val = 100 1

    2024年02月10日
    浏览(37)
  • LeetCode2111. Minimum Operations to Make the Array K-Increasing——动态规划

    You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k. The array arr is called K-increasing if arr[i-k] = arr[i] holds for every index i, where k = i = n-1. For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because: arr[0] = arr[2] (4 = 5) arr[1] = arr[3] (1 = 2) arr[2] = arr[4] (5 = 6) arr[3] = arr[5]

    2024年03月09日
    浏览(41)
  • 【每日一题】Leetcode - 19. Remove Nth Node From End of List

    Leetcode - 19. Remove Nth Node From End of List Drawing on the method of finding midpoints in linked lists, use quick slow pointer Finding midpoints in linked lists nothing

    2024年02月12日
    浏览(50)
  • 【LeetCode 算法】Minimum Operations to Halve Array Sum 将数组和减半的最少操作次数-Greedy

    给你一个正整数数组 nums 。每一次操作中,你可以从 nums 中选择 任意 一个数并将它 减小 到 恰好 一半 。(注意,在后续操作中你可以对减半过的数继续执行操作) 请你返回将 nums 数组和 至少 减少一半 的 最少 操作数。 1 = n u m s . l e n g t h = 1 0 5 1 = n u m s [ i ] = 1 0 7 1 = num

    2024年02月15日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包