<
查看: 1926| 回复: 3
收起左侧

[数组] 求问今天的daily challenge, 为啥我的TLE???

ChrisSun1996 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   223
95%
5%
12

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x

LEETCODE Code1424. Diagonal Traverse II


这题其实不难,主要是要知道colIndex+rowIndex = constant. 但是楼主首先,loop over first col, then loop last col.  time complexity should be O(N) 因为每个element只访问一遍。我看答案是用hashmap。但是我感觉总的tc应该是一样的。为啥我的过不了??转码选手轻喷,抱着学习的心态发帖。。。。




class Solution {
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        List<Integer> ans = new ArrayList<>();
        int m = nums.size();
        int maxCol = 0;
        for (int i = 0; i<m; i++) {
            int indexSum = i;
            maxCol = Math.max(maxCol, nums.get(i).size());
            for (int row = i; row >= 0; row--) {
                int col = indexSum - row;
                if (col<nums.get(row).size()) {
                    ans.add(nums.get(row).get(col));
                }
            }
        }
        for (int j = 1; j<maxCol; j++) {
            int indexSum = m-1+j;
            for (int row = m-1; row>=0; row--) {
                int col = indexSum - row;
                if (col < nums.get(row).size()) {
                    ans.add(nums.get(row).get(col));
                }
            }
        }
        int size = ans.size();
        int[] res = new int[size];
        for (int i = 0; i<size; i++) {
            res[i] = ans.get(i);
        }
   
        return res;
    }
}

评分

参与人数 1大米 +2 收起 理由
14417335 + 2 给你点个赞!

查看全部评分


上一篇:时间非常不方便,周赛372
下一篇:2944. Minimum Number of Coins for Fruits 咋做?
mc2 2023-11-23 05:57:17 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   329
98%
2%
8
maxCol 可以很大。所以会tle

你可以看看solution里的bfs解法

评分

参与人数 1大米 +1 收起 理由
14417335 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

 楼主| ChrisSun1996 2023-11-23 07:15:23 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   223
95%
5%
12
mc2 发表于 2023-11-22 13:57
maxCol 可以很大。所以会tle

你可以看看solution里的bfs解法

这不就是周赛大神吗。欢迎大神莅临指导。
回复

使用道具 举报

vincent_great 2023-11-26 08:59:29 | 显示全部楼层
本楼:   👍  0
0%
0%
0   👎
全局:   250
97%
3%
9
本帖最后由 vincent_great 于 2023-11-26 01:02 编辑
  1. def findDiagonalOrder(self, grid):
  2.      m = len(grid)
  3.      n = max(len(r) for r in grid)
  4.      ans = [[] for _ in range(m+n)]
  5.      for i in range(len(grid)):
  6.           for j in range(len(grid[i])):
  7.                ans[i+j].append(grid[i][j])
  8.     return [r[i] for r in ans for i in range(len(r)-1, -1, -1)]
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

Advertisement
>
快速回复 返回顶部 返回列表