प्रौद्योगिकी साझेदारी

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

सामग्रीसूची

विषयः १ : दीर्घतमः सामान्यः उपसर्गः

प्रश्नः २ : दीर्घतमः पालिन्ड्रोम उपतारः

विषयः ३ : द्विचक्रीययोगः

प्रश्नः ४ : तारानाम् गुणनम्

---

विषयः प्रथमः : १.दीर्घतमः सामान्यः उपसर्गः

स्ट्रिंग्-समूहे दीर्घतमं सामान्यं उपसर्गं अन्वेष्टुं फंक्शन् लिखन्तु

यदि सामान्यः उपसर्गः नास्ति तर्हि रिक्तं स्ट्रिंग् प्रत्यागच्छति""

उदाहरणम् १ : १.

输入：strs = ["flower","flow","flight"]
输出："fl"

उदाहरणम् २ : १.

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

संकेत:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i]केवलं लघु-आङ्ग्ल-अक्षराणि सन्ति

---

समाधानम् १ : युग्मरूपेण तुलना

प्रथमं समाधानं युग्मरूपेण तुलनारणनीतिः प्रथमयोः तारयोः तुलनां कृत्वा प्रथमयोः तारयोः सामान्यपूर्वपदस्य तुलनां तृतीयतारया सह कुर्वन्तु

कोडः अधोलिखितरूपेण दर्शयतु:

class Solution 
{
public:
    string findCommon(string& s1, string& s2)
    {
        int i = 0;
        //i有可能会出现越界的情况，所以i小于s1s2长度时再循环判断
        while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])
            i++;
        return s1.substr(0, i);
    }
 
    string longestCommonPrefix(vector<string>& strs) 
    {
        int n = strs.size();
        //same字符串就是存储最长公共前缀的字符串
        string same = strs[0];
        for(int i = 1; i < n; i++)
            same = findCommon(same, strs[i]);
        return same;
    }
};

---

समाधानम् २ : एकीकृततुलना

एकीकृततुलना इत्यस्य अर्थः अस्ति यत् सर्वेषां तारानाम् एकदा एव समानस्थानस्य तुलना कृत्वा यावत् भिन्नाः वर्णाः न दृश्यन्ते तावत् स्थानानि समानानि सन्ति वा इति निर्धारयितुं शक्यते ।

अत्र सीमातः बहिः स्थितिः भविष्यति यदि सीमातः बहिः स्थितिः अस्ति तर्हि कश्चन तारः समाप्तः इति अर्थः, ततः तुलना समाप्तुं शक्यते ।

कोडः अधोलिखितरूपेण दर्शयतु:

class Solution 
{
public:
    string longestCommonPrefix(vector<string>& strs) 
    {
        int i = 0;
        //以第一个字符串为基准，与其他所有字符串做比较
        for(i = 0; i < strs[0].size(); i++)
        {
            //ch表示第一个字符串当前循环到的字符
            char ch = strs[0][i];
            //循环strs中其余的字符串，其余字符串的i位置字符与ch做比较
            for(int j = 1; j < strs.size(); j++)
            {  
                //如果i大于当前字符串的长度，说明当前字符串已经没有元素了
                if(i > strs[j].size() || strs[j][i] != ch)
                    return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

---

विषयः २ : १.दीर्घतमः पालिन्ड्रोम उपतारः

एकं तारं ददातुs,ऊर्ध्वं गच्छतुsदीर्घतमः पलिण्ड्रोम उपतारः in

उदाहरणम् १ : १.

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

उदाहरणम् २ : १.

输入：s = "cbbd"
输出："bb"

---

साधारणः ब्रूट् फोर्स् गणना एल्गोरिदम् द्वौ सूचकौ सेट् करोति, एकः i एकः j च, j इत्यस्य निश्चयं करोति, प्रत्येकं j इत्यस्य स्थानान्तरणं कृत्वा, इदं निर्धारयितुं आवश्यकं यत् i तथा j इत्येतयोः मध्ये स्ट्रिंग् एकः palindrome उपस्ट्रिंग् अस्ति वा इति । j चाल्यते entire violent enumeration time जटिलता अतीव उच्चा अस्ति, O(N^3) यावत् भवति ।

समाधानम् : केन्द्रविस्तार एल्गोरिदम्

केन्द्रविस्तार-अल्गोरिदम् अस्ति : १.

1एकं केन्द्रबिन्दुं स्थापयतु
2केन्द्रबिन्दुतः आरभ्य उभयतः विस्तारं कुर्वन्तु (विषमसमदीर्घताद्वयं विचारणीयम्)

अर्थात् प्रत्येकं समये एकः केन्द्रीयबिन्दुः i नियतः भवति, तथा च प्रत्येकं समये तस्य विस्तारः i इत्यस्य वामभागे दक्षिणे च भवति यत् एषः पलिण्ड्रोम-तारः अस्ति वा इति निर्धारयितुं शक्यते i इत्यस्य भ्रमणस्य एल्गोरिदम् इत्यस्य समयजटिलता O(N) अस्ति, तथा नेस्टेड् दिशा i इत्यस्य वामदक्षिणयोः भवति विस्तारेण समयजटिलता अपि O(N) भवति, अतः अन्ते O(N^2) भवति, यत् उपरि उल्लिखितस्य हिंसकसमाधानस्य अपेक्षया बहु अधिकं अनुकूलितं भवति .

यत् ज्ञातव्यं तत् केन्द्रविस्तार-अल्गोरिदमस्य द्वितीयः बिन्दुः विषम-सम-सङ्ख्याः विचारणीयाः, यतः विषम-सङ्ख्याः वाम-दक्षिण-सूचकान् i-स्थानात् वाम-दक्षिणयोः कृते चालयन्ति, यदा तु सम-सङ्ख्याः आवश्यकाः भवन्ति वामः i स्थाने भवितुं दक्षिणं च i + 1. स्थाने भवितुं, ततः वामदक्षिणयोः गमनम्

ज्ञातव्यं यत् कोड् मध्ये दीर्घता दक्षिण - वाम - 1 अस्ति, यतः यदि वर्तमान वाम-दक्षिणयोः समानं तत्त्वं दर्शयति तर्हि भवद्भिः वाम--, दक्षिण++ परिवर्तनं कर्तव्यं यदि ते समानाः न सन्ति तर्हि लूप् तः बहिः गच्छन्तु , अतः palindrome तारानाम् अपेक्षया अधिकं वाम-दक्षिणौ स्तः, अतः दीर्घता दक्षिणतः - वामतः - 1. विस्तरेण कृते अधोलिखितं चित्रं पश्यन्तु ।

यथा उपरि चित्रे दर्शितं, वामः दक्षिणः च लूप्तः निर्गन्तुं वर्तमानबिन्दुं प्रति सूचयति, अतः palindrome substring aa इत्यस्य दीर्घता अस्ति :
दक्षिण - वाम - 1 = 3 - 0 - 1 = 2

---

कोडः अधोलिखितरूपेण दर्शयतु:

class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        if(s.size() == 1) return s;
        int n = s.size(), begin = 0, size = 0;
        for(int i = 0; i < n; i++)
        {
            //先做奇数长度的扩展
            int left = i, right = i;
            //left和right符合条件，且指向元素相等再进入循环
            while(left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            //如果长度更大，更新begin与size
            if((right - left - 1) > size)
            {
                size = right - left - 1;
                begin = left + 1;
            }
            //再做偶数长度的扩展
            left = i, right = i + 1;
            //left和right符合条件，且指向元素相等再进入循环
            while(left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            //如果长度更大，更新begin与size
            if((right - left - 1) > size)
            {
                size = right - left - 1;
                begin = left + 1;
            }            
        }
        return s.substr(begin, size);
    }
};

---

विषयः तृतीयः : १.द्विचक्रीय योग

भवन्तं द्विचक्रीयतारद्वयं ददातुaतथाb, तेषां योगं द्विचक्रीयताररूपेण प्रत्यागच्छति ।

उदाहरणम् १ : १.

输入:a = "11", b = "1"
输出："100"

उदाहरणम् २ : १.

输入：a = "1010", b = "1011"
输出："10101"

---

अयं प्रश्नः उच्च-सटीक-संयोजनस्य गणना, अनुकरण-क्रियायाः, ऊर्ध्वाधर-गणना-प्रक्रियायाः अनुकरणस्य च विषये अस्ति ।

भवद्भिः क्रमशः द्वौ स्ट्रिंग् सूचयितुं cur1 तथा cur2 इति द्वौ सूचकौ सेट् कर्तव्यौ, ततः carry इत्यस्य प्रतिनिधित्वार्थं t चरं सेट् कर्तव्यम् ।

कोडः अधोलिखितरूपेण दर्शयतु:

class Solution 
{
public:
    string addBinary(string a, string b) 
    {
        //t表示相加后的进位
        int t = 0;
        string ret;
        int cur1 = a.size()-1, cur2 = b.size()-1;
        //cur1或cur2 >= 0表示字符串没遍历完，t>0表示还剩一个进位
        while(cur1 >= 0 || cur2 >= 0 || t)
        {
            if(cur1 >= 0) t += a[cur1--] - '0';  
            if(cur2 >= 0) t += b[cur2--] - '0';
            ret += to_string(t % 2);
            t /= 2;
        }
        //从后向前加的，刚好反过来了，需要逆置
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

---

विषयः चतुर्थः : १.तारगुणनम्

ताररूपेण प्रतिनिधितौ अऋणात्मकौ पूर्णाङ्कौ दत्तौnum1तथाnum2,निर्वतनम्num1तथाnum2, तेषां उत्पादः अपि ताररूपेण व्यक्तः भवति ।

सूचना:भवान् अन्तःनिर्मितस्य BigInteger पुस्तकालयस्य कस्यापि उपयोगं कर्तुं वा निवेशं प्रत्यक्षतया पूर्णाङ्के परिवर्तयितुं वा न शक्नोति ।

उदाहरणम् १ : १.

输入: num1 = "2", num2 = "3"
输出: "6"

उदाहरणम् २ : १.

输入: num1 = "123", num2 = "456"
输出: "56088"

---

समाधानम् १ : ऊर्ध्वाधरक्रियाणां अनुकरणं कुर्वन्तु

गणिते गुणनस्तम्भस्य ऊर्ध्वाधररूपम् अस्ति एषा एव चिन्तनीयः सरलतमः विधिः ।

यथा- १.

वयं तत् अवगन्तुं शक्नुमः यथा, निम्नलिखितस्य ४५६ इत्यस्य प्रत्येकं अङ्कं उपर्युक्तेन १२३ गुणितं भवति, ततः योजितं भवति, तत्र त्रयः विवरणाः सन्ति ।

1उच्चक्रमगुणनं 0 इत्यनेन पूरयितुं आवश्यकम्, यतः ७३८, ६१५ च योजयित्वा एकः बिट् दोषः भवति, यत् ७३८ + ६१५० इति अवगन्तुं शक्यते
2प्रक्रिया अग्रणी 0, १२३ × ० इत्यस्य स्थितिः भवितुम् अर्हति, अस्मिन् सति उत्तरं ००० भवति, तस्य प्रक्रियायाः आवश्यकता वर्तते ।
3गणनाफलक्रमे ध्यानं ददातु, यतो हि गणना विपरीतक्रमेण क्रियते, गुणनं च अन्तिमाङ्कात् गण्यते ।

परन्तु एषा पद्धतिः कोड् लिखितुं सुलभा नास्ति ।

समाधानं द्वितीयम् : समाधानं प्रथमं अनुकूलितं कुर्वन्तु

कैरी विना गुणनं कृत्वा योजयन्तु, ततः कैरी अन्तिमे चरणे संसाधितः भवति:

अर्थात् कियत् अपि गुणितं चेदपि वहनं न भविष्यति, अन्तिमसंयोजनानन्तरं वहनं च निर्वहति।

तथैव गणनां आरभ्य प्रथमं क्रमं विपर्यस्तं कुर्वन्तु यतः गुणनं द्वौ अङ्कौ भवितुम् अर्हति, तस्य स्थाने स्ट्रिंग् प्रतिनिधित्वस्य उपयोगः कर्तुं न शक्यते

क्रमस्य विपर्ययत्वात् १२३ अनुरूपं उपलिपिः २,१,०, ४५६ अनुरूपं उपलिपिः अपि २,१,० भवति

अतीव उपयोगी नियमः अस्ति यत् i तथा j इत्यनेन उपलिपिकृताः सङ्ख्याः गुणिताः भवन्ति, परिणामः च सरणीयाः i + jth स्थाने स्थापितः भवति

1 m + n - 1 (m तथा n द्वयोः गुणितसङ्ख्यायोः दीर्घतायाः अनुरूपं) एकं सरणी tmp परिभाषयन्तु ।
गुणितयोः सङ्ख्यायोः उपलिपिः क्रमशः i तथा j भवति, गणितं परिणामं च सरणीयाः i + j स्थाने स्थापितं भवति ।
2अन्तिम-संयोजनानन्तरं कैरी-प्रक्रियायाः आवश्यकता भवति
3प्रसंस्करण अग्रणी 0

कोडः अधोलिखितरूपेण दर्शयतु:

class Solution 
{
public:
    string multiply(string num1, string num2) 
    {
        //先逆序两个字符串
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        //定义一个数组tmp
        int m = num1.size(), n = num2.size();
        vector<int> tmp(m + n - 1);
        //无进位相乘然后相加
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
        //处理进位
        string ret;
        int t = 0, cur = 0;
        while(cur < m + n - 1 || t != 0)
        {
            if(cur < m + n - 1) t += tmp[cur++];
            ret += to_string(t % 10);
            t /= 10;
        }
        if(t) ret += to_string(t);
        //处理前置0
        while(ret.back() == '0' && ret.size() > 1) ret.pop_back();
        reverse(ret.begin(), ret.end());
 
        return ret;
    }
};

---

एतेन तारसम्बद्धाः प्रश्नाः समाप्ताः भवन्ति