Ստեղնաշարի տող Leetcode լուծում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Մաթեմատիկական աշխատանքներ
ալգորիթմները կոդավորում Հեշինգ հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions String

Խնդիրի հայտարարություն  

Այս խնդրում մեզ տրվում է ան դասավորություն լարերի. Մենք պետք է գտնենք, թե տրված զանգվածի որ տողերն են պատկանում ցանկացած նույն շարքում Qwerty ստեղնաշար, ինչպես ցույց է տրված ստորև:

Ստեղնաշարի տող Leetcode լուծում

Ենթադրում ենք, որ զանգվածը պարունակում է անգլերեն տառերի տողեր:

Օրինակ

String_Array = {"Anand" , "Soni" , "Ashfak" , "Turipo"}
Ashfaq Turipo
String_Array = {"qaz" , "wsx" , "edc"}
No words found

Մոտեցում (Hashing)  

Մոտեցումը բավականին պարզ է: Մենք կարող ենք hash բոլոր ցուցանիշները նրանց տողերին և ստուգել, ​​որ զանգվածի յուրաքանչյուր տողի յուրաքանչյուր նիշ ունի նույն արժեքը: Բայց նախ պետք է hash ունենանք բոլոր 26 նիշերի համար, որպեսզի նախապատրասման ենթարկենք hashing մասը: Դրա հիման վրա մենք կարող ենք դրանք զանգվածում պահել և վերադարձնել:

Ալգորիթմ

  1. Ստեղծեք HashMap տող և զանգված արդյունք արդյունքային տողերը պահելու համար
  2. Նախաձեռնեք բուլյան փոփոխական նույն_լարը = ճիշտ է տողերի վրա ստուգումներ իրականացնել
  3. Հաշեք բոլոր հերոսներին իրենց շարքերում
  4. Rayանգվածի յուրաքանչյուր տողի համար.
    • սահմանել same_row = true
    • Յուրաքանչյուր կերպարի համար chr զանգվածում ՝ սկսած երկրորդ.
      • Եթե rowId [chr] հավասար չէ rowId [առաջին_ բնույթ]:
        • սահմանել same_row = false և անցնել հաջորդ տողին
    • Եթե ​​same_row == true:
      • Հրել այն դեպի արդյունք
  5. Վերադառնալ արդյունք

Keyboard Row Leetcode լուծման իրականացում

C ++ ծրագիր

#include <bits/stdc++.h>
using namespace std;

vector <string> findWords(vector <string> &words)
{
    unordered_map <char , int> rowId;

    string temp = "qwertyuiopQWERTYUIOP";
    for(char &i : temp)
        rowId[i] = 1;

    temp = "asdfghjklASDFGHJKL";
    for(char &i : temp)
        rowId[i] = 2;

    temp = "zxcvbnmZXCVBNM";
    for(char &i : temp)
        rowId[i] = 3;

    bool same_row;

    vector <string> result;
    for(string &word : words)
    {
        same_row = true;
        for(int i = 1 ; i < word.size() ; i++)
        {
            if(rowId[word[i]] != rowId[word[0]])
            {
                same_row = false;
                break;
            }
        }
        if(same_row)
            result.push_back(word);
    }
    return result;
}

int main()
{
    vector <string> words = {"Anand" , "Soni" , "Ashfak" , "Turipo"};
    vector <string> result = findWords(words);
    for(string &word : result)
        cout << word << " ";
    return 0;
}

Java ծրագիր

import java.util.*;

class keyboard_row
{
    public static void main(String args[])
    {
        String[] words = {"Anand" , "Soni" , "Ashfak" , "Turipo"};
        String result[] = findWords(words);
        for(String word : result)
            System.out.print(word + " ");
    }

    static String[] findWords(String[] words)
    {
        HashMap <Character , Integer> rowId = new HashMap <>();

        String temp = "qwertyuiopQWERTYUIOP";
        for(char i : temp.toCharArray())
            rowId.put(i , 1);

        temp = "asdfghjklASDFGHJKL";
        for(char i : temp.toCharArray())
            rowId.put(i , 2);

        temp = "zxcvbnmZXCVBNM";
        for(char i : temp.toCharArray())
            rowId.put(i , 3);

        boolean same_row;

        List <String> result_list = new ArrayList<String>();


        for(String word : words)
        {
            same_row = true;
            for(int i = 1 ; i < word.length() ; i++)
            {
                if(rowId.get(word.charAt(i)) != rowId.get(word.charAt(0)))
                {
                    same_row = false;
                    break;
                }
            }
            if(same_row)
                    result_list.add(word);
        }

        String[] result = new String[result_list.size()];
        for(int i = 0 ; i < result.length ; i++)
            result[i] = result_list.get(i);

        return result;
    }
}
Ashfak Turipo

Ստեղնաշարի տողի տողերի լուծման բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) երբ մենք անցնում ենք զանգվածի յուրաքանչյուր տողի յուրաքանչյուր նիշի միջով: N = բոլոր տողերի երկարությունների գումար:

Տես նաեւ,
Հռոմեական Leetcode Solution- ի ամբողջ թիվ

Տիեզերական բարդություն

O (1), քանի որ մենք հիշողության մեջ անընդհատ տարածություն ենք պահում ՝ անկախ հիշողությունից: