Diagonal Traverse LeetCode ဖြေရှင်းချက်

ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Apple DoorDash Facebook က Google Microsoft က ရော်ဘင်ဟုဒ် ဗီဇာ
Goldmann Sachsviews 87

စနစ်ဒီဇိုင်းအင်တာဗျူးမေးခွန်းများ ပြင်ဆင်ရန် နည်းလမ်းမှန်ကို သိရန် အလွန်ခက်ခဲသည် ။ ယခု ဝယ်ယူပြီးနောက် Amazon၊ Microsoft နှင့် Adobe တို့၏ ဒီဇိုင်းအဝိုင်းများကို ဖောက်ထွင်းနိုင်ပါပြီ။ ဒီစာအုပ်. နေ့စဉ်ပြန်လည်သုံးသပ်ပါ။ ဒီဇိုင်းမေးခွန်း ပြီးတော့ ဒီဇိုင်းအဝိုင်းကို ဖောက်နိုင်မယ်လို့ ကတိပေးပါတယ်။

ပြProbleနာဖော်ပြချက်

Diagonal Traverse LeetCode ဖြေရှင်းချက် - တစ်ခုပေးထားသည်။ m x n matrix matပြန်လာ ထောင့်ဖြတ်အစီအစဥ်ဖြင့် array ၏ဒြပ်စင်အားလုံး၏ array တစ်ခု.

Diagonal Traverse LeetCode ဖြေရှင်းချက်တွယ်အပ်

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

ရှင်းလင်းချက်

NxM matrix တစ်ခု၏ ထောင့်ဖြတ်အညွှန်းကိန်းများကို သုံးသပ်ကြည့်ပါ။ ဥပမာအနေနဲ့ 4×4 matrix ကို သုံးကြည့်ရအောင်။

(0, 0) (0, 1) (0, 2) (0, 3)

(1, 0) (1, 1) (1, 2) (1, 3)

(2, 0) (2, 1) (2, 2) (2, 3)

(3, 0) (3, 1) (3, 2) (3, 3)

ပထမထောင့်ဖြတ်သည် (0, 0). ဒုတိယကတော့ (0, 1), (1, 0)တတိယအချက်က (2, 0), (1, 1), (0, 2), etc

အတန်း၏ပေါင်းလဒ်ကို ရှင်းရှင်းလင်းလင်း သိရပါမည်။ i နှင့် ကော်လံ j ထောင့်ဖြတ်အညွှန်းကိန်း (ထောင့်ဖြတ်ဂဏန်း – 1) နှင့် ညီမျှသည်။ ဥပမာ - ဒုတိယထောင့်ဖြတ် (အညွှန်းကိန်း 1) အတွက် ဖြစ်နိုင်သောအတွဲများ (i, j) ပေါင်းရန် 1ဆိုလိုသည်မှာ i + j = 1 2nd ထောင့်ဖြတ်အတွက်။ အများဆုံး ထောင့်ဖြတ် index သည်ရိုးရှင်းပါသည်။ ((N-1) + (M-1)) = N + M - 2

ထို့ကြောင့် ပြဿနာကိုဖြေရှင်းရန် ကျွန်ုပ်တို့သည် ဖြစ်နိုင်ချေရှိသော ထောင့်ဖြတ်အညွှန်းကိန်းများအားလုံးကို ရိုးရှင်းစွာ ထပ်လောင်းရန်လိုသည် (၎င်းကို ဆိုလိုသည်။ s) နှင့် ဖြစ်နိုင်သောအတွဲများ (i၊ j) စသည်တို့ကို ရှာပါ။ i + j = s. ကိုယ့်ကိုကိုယ် အလေးထားရမယ့် တစ်ခုတည်းသောအချက်က အမိန့်ပါ။ ထောင့်ဖြတ်အညွှန်းသည် ပင်လား သို့မဟုတ် ထူးဆန်းသလားကို ကြည့်ခြင်းဖြင့် မှာယူမှုကို ကျွန်ုပ်တို့ ရှာဖွေနိုင်သည်။ ထောင့်ဖြတ်အညွှန်းသည်ပင်လျှင် ကျွန်ုပ်တို့သည် ပထမအတွဲဖြစ်လိုပါသည်။ (s, 0) ပထမအတွဲကို လိုချင်တဲ့အခါ ထူးဆန်းနေတဲ့အခါ (0, s)နှင့် ကျွန်ုပ်တို့သည် i/j ကို 1 အလိုက် လျှော့ သို့မဟုတ် တိုးသည်။

ကုဒ်

Diagonal Traversal အတွက် C++ ကုဒ်

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if(matrix.empty()) return {};
        
        const int N = matrix.size();
        const int M = matrix[0].size();
        
        vector<int> res;
        for(int s = 0; s <= N + M - 2; ++s)
        {
            // for all i + j = s
            for(int x = 0; x <= s; ++x) 
            {
                int i = x;
                int j = s - i;
                if(s % 2 == 0) swap(i, j);

                if(i >= N || j >= M) continue;
                
                res.push_back(matrix[i][j]);
            }
        }
        
        return res;
    }
};

Diagonal Traversal အတွက် Java ကုဒ်

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        HashMap<Integer,List<Integer>> map=new HashMap<>();
        for (int i=0;i<mat.length;i++) {
            for(int j=0;j<mat[i].length;j++) {
                int key=i+j;
                if(map.containsKey(key)) map.get(key).add(mat[i][j]);
                else {
                    map.put(key,new ArrayList<Integer>());
                    map.get(key).add(mat[i][j]);
                     }
            }
        }
        int curr=0;
        int index=0;
        boolean check=false;
        int[] ans=new int[mat.length*mat[0].length];
        while (true) {
            if(!map.containsKey(curr)) break;
            List<Integer> a=map.get(curr);
            if(check) {
                for(int i=0;i<a.size();i++) {
                    ans[index++]=a.get(i);
                }
                check=!check;
            }
            else {
                for(int i=a.size()-1;i>=0;i--) {
                    ans[index++]=a.get(i);
                }
                check=!check;
            }
            curr++;
        }
        return ans;
    }
}

Diagonal Traversal အတွက် Python ကုဒ်

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        result = [ ]
        dd = collections.defaultdict(list)
        if not matrix: return result
        # Step 1: Numbers are grouped by the diagonals.
        # Numbers in same diagonal have same value of row+col
        for i in range(0, len(matrix)):
            for j in range(0, len(matrix[0])):
                dd[i+j+1].append(matrix[i][j]) # starting indices from 1, hence i+j+1.
        # Step 2: Place diagonals in the result list.
        # But remember to reverse numbers in odd diagonals.
        for k in sorted(dd.keys()):
            if k%2==1: dd[k].reverse()
            result += dd[k]
        return result

Diagonal Traverse LeetCode ဖြေရှင်းချက်အတွက် ရှုပ်ထွေးမှု ခွဲခြမ်းစိတ်ဖြာခြင်း။

အချိန်ရှုပ်ထွေး

အို (n ^ ၂)

အာကာသရှုပ်ထွေးမှု

အို (n ^ ၂)

Crack System Design အင်တာဗျူးများ
Translate »