LeetCode Hot 100(一)C++版

文書ディレクトリ

1. 2つの合計

2. 2つの合計

3. 重複文字なしの最上位列

4.2つの秩序配列の中位数

を探します
LeetCode Top 100問題解
1.両数の和
整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.
入力ごとに1つの答えしか対応しないと仮定できます.しかし、この配列の同じ要素を繰り返し利用することはできません.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/two-sum/
配列中の同じ元素を再利用できないと前後の元素加算の方法で目標が存在するか否かを判断できないことを考慮して、相反してtargetからnumsの中のある元素を減算してから、残りの元素の中で差分値と同じ元素を探して下標に戻り、いずれも異なると空のvectorに戻り、このような時間の複雑さはO(n^2)で、資料を見て私はこれが巧みな暴力法であるべきで、タイムアウトはありませんが、効率的ではありません

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		vector<int> res;
		if (nums.size() == 0)
			return res;

		int oth = 0;
		for (int i = 0; i < nums.size(); i++)
		{
			oth = target - nums[i];
			res.push_back(i);
			for (int j = i + 1; j < nums.size(); j++)
			{
				if (oth == nums[j])
				{
					res.push_back(j);
					return res;
				}
			}
			res.clear();
		}
        return res;
	}
};

線形の時間的複雑さで問題を解決するには、時間を空間的に変換し、HashMapで要素と座標のマッピング関係を構築することを考慮する必要があります.HashMapは定数レベルの検索効率です.これにより、配列を巡回し、targetで巡回した要素を減算して別の数値を得、HashMapで数値を検索します.しかし、見つかった数字が最初の数字であるかどうかを判断することに注意しなければなりません.そうすれば、私の上のコードの裏のループを省くことができます.

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		unordered_map<int, int> np;
		vector<int> res;

		for (int i = 0; i < nums.size(); i++)
		{
			np[nums[i]] = i;
		}

		for (int i = 0; i < nums.size(); i++)
		{
			int tmp = target - nums[i];
			if (np.count(tmp) && np[tmp] != i)
			{
				res.push_back(i);
				res.push_back(np[tmp]);
                break;
			}
		}

		return res;

	}
};

2つのforループを1つに統合してコードを貼り付ける大物もいます

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); ++i) {
            if (m.count(target - nums[i])) {
                return {i, m[target - nums[i]]};
            }
            m[nums[i]] = i;
            
        }
        return {};
    }
};

2.両数加算
2つの非負の整数を表すために、2つの非空のチェーンテーブルが与えられる.ここで、それぞれのビット数は逆順序で格納され、各ノードには1桁の数字しか格納されません.
この2つの数を加算すると、新しいチェーンテーブルが返され、合計が表示されます.
数値0以外の2つの数は0で始まると仮定できます.
例:入力:(2->4->3)+(5->6->4)出力:7->0->8理由:342+465=807
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/add-two-numbers
新しいチェーンテーブルを作成し、入力した2つのチェーンテーブルから加算要素を取得し、carryを設定してキャリー情報を記録します.最低ビットはチェーンテーブルの先頭にあるので、チェーンテーブルを遍歴しながら直接加算することができます.チェーンテーブルは空である可能性がありますので、現在のノード値を取るときは、空であれば0を取り、そうでなければノード値を取ります.2つのノード値を加算し、キャリーキャリーも加算します.次にcarryを更新し、sum/10に直接接続し、sum%10を値として新しいノードを確立し、prevの後ろに接続し、prevを次のノードに移動します.その後、2つのノードを更新し、存在する場合は次の位置を指します.ループ終了後、最上位のキャリー問題は最後に特殊に処理し、carryが1の場合、値が1のノードを再構築します.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode dum(-1);
		int carry = 0;
		ListNode *prev = &dum;
		for (ListNode* pa = l1, *pb = l2; pa != nullptr || pb != nullptr;
			pa = pa == nullptr ? nullptr : pa->next,
			pb = pb == nullptr ? nullptr : pb->next,
			prev = prev->next)
		{
			const int ai = pa == nullptr ? 0 : pa->val;
			const int bi = pb == nullptr ? 0 : pb->val;
			const int value = (ai + bi + carry) % 10;
			carry = (ai + bi + carry) / 10;
			prev->next = new ListNode(value);
		}
		if (carry > 0)
			prev->next = new ListNode(carry);

		return dum.next;
	}
};

3.重複文字のない長男列
文字列を指定すると、重複文字が含まれていない長男の列の長さを見つけてください.
例1:入力:「abcabcbb」出力:3説明:重複文字のない長男列が「abc」であるため、その長さは3である.例2:
入力:「bbbbb」出力:1解釈:重複文字のない長男列は「b」であるため、その長さは1である.例3:
入力:「pwwkew」出力:3解釈:重複文字のない長男列は「wke」であるため、その長さは3である.あなたの答えはサブストリングの長さでなければなりません.「pwke」はサブストリングであり、サブストリングではありません.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

class Solution {
public:
	int lengthOfLongestSubstring(string s) {
		const int ASC = 256;
		int last[ASC];//           
		int start = 0;//           

		fill(last, last+ASC, -1);
		int maxlen = 0;
		for (int i = 0; i < s.size(); i++)
		{
				if (last[s[i]] >= start)
				{
                    //s[i]   
					maxlen = max(i - start, maxlen);
					start = last[s[i]] + 1;
				}
				last[s[i]] = i;
		}

		return max((int)s.size() - start, maxlen);//    
	}
};

4.2つの整列配列の中央値を探す
mとnのサイズの2つの秩序配列nums 1とnums 2が与えられる.この2つの秩序配列の中位数を見つけ,アルゴリズムの時間的複雑さをO(log(m+n))とすることを要求してください.nums 1とnums 2が同時に空にならないと仮定できます.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/median-of-two-sorted-arrays
例1:nums 1=[1,3]nums 2=[2]では中位数は2.0
例2:nums 1=[1,2]nums 2=[3,4]では中位数は(2+3)/2=2.5
  本題の目的は2つの秩序配列の中の中位数を探し出すことであり,同時に時間複雑度をO(log(m+n))に制限することであり,まず中位数の概念を明確にする:ある秩序配列の長さが奇数であれば,中位数は最も中間の数であり,数組長度が偶数であれば,中位数は最も中間の2つの数の平均値である.2つの秩序配列についても同様に適用され、例えば、2つの秩序配列の長さがそれぞれmとn、m+nのパリティが不確定であるとして、私たちはそれぞれ(m+n+1) / 2番目と(m+n+2)/2番目を探して、それからその平均値を求めて中位数を得ることができ、m+nが奇数であれば、(m+n+1) / 2と(m+n+2)/2の値は等しく、その平均値はそれ自体である.次に、時間の複雑さはO(log(m+n))であることを考慮する必要があるため、この時間の複雑さを超えるすべての操作を避ける必要がある.例えば、2つの配列を結合して操作する.コピー配列など;株はこの時間から複雑度が二分法であるため,二つの配列間で二分ルックアップ法をどのように使用するかを考慮する必要がある.  は、2つの秩序配列の中でk番目の要素を検索する関数を定義し、iとjを使用して配列nums 1とnums 2の開始位置をマークします.まず、2つの配列の特殊な状況を考慮します.ある配列の開始位置が配列の長さ以上である場合、そのすべての数字が淘汰されたことを説明し、別の配列で検索します.K=1の場合、nums 1とnums 2の開始位置iとjの数字を比較する必要があります.次に,一般的な状況を考慮すると,Kはnums 1とnums 2でそれぞれK/2番目の要素を検索する二分法を用いて二分する.配列長が不定であるため、配列にK/2番目の数字が存在するか否かを考慮し、存在すると取り出す必要があり、存在しなければ整形最大値を付与する(nums 1またはnums 2でK/2個の小さい数字を先に除外するため、判断の根拠はmidVal 1とmidVal 2のどちらが小さいかを見ることであり、ある配列の長さがK/2未満では淘汰できないため、対応するidVal値を整形最大値とし、排除されないことを保証する).また,両配列にK/2番目の要素が存在しない場合,この問題では不可能であることを考慮する必要がある.Kは任意に与えられたものではなく,m+nの中間値であるため,必ず1つの配列がK/2番目の数字が存在する.これで、2つの配列のK/2番目の小さい数字midVal 1とmidVal 2の大きさを比較し、nums 1のK/2番目の数字が小さい場合、nums 1の前のK/2要素を排除し、nums 1の開始位置iをK/2と同時にKを後退させ、再帰を呼び出す.

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(), left = (m + n + 1) / 2, right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    } 
      int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k)     			   {
        if (i >= nums1.size()) return nums2[j + k - 1];
        if (j >= nums2.size()) return nums1[i + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int midVal1 = (i + k / 2 - 1 < nums1.size()) ? nums1[i + k / 2 - 1] : INT_MAX;
        int midVal2 = (j + k / 2 - 1 < nums2.size()) ? nums2[j + k / 2 - 1] : INT_MAX;
        if (midVal1 < midVal2) {
            return findKth(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return findKth(nums1, i, nums2, j + k / 2, k - k / 2);
        }
    }
};

 問題要求の時間的複雑さの要求を越えて、新しい配列を用いて処理することを考慮し、開始位置変数を使用しないようにしますが、コピー配列の操作は時間的複雑さを増加させ、制限を超える可能性があります.同じように特殊な状況を先に考慮します:配列が空であるかどうか;K=1の場合の検索.2つの配列のK/2番目の座標iとjを取り出し、K/2番目の要素がないことを避けるために、毎回配列長と比較し、小さい値を取り出します.

class Solution {
public:
	int findKth(vector<int> nums1, vector<int> nums2, int k)
	{
		if (nums1.empty())
			return nums2[k - 1];

		if (nums2.empty())
			return nums1[k - 1];

		if (k == 1)
		{
			return min(nums1[0], nums2[0]);
		}

		int i = min((int)nums1.size(), k / 2);
		int j = min((int)nums2.size(), k / 2);

		if (nums1[i - 1] > nums2[j - 1])
		{
			return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j);
		}
		else
		{
			return findKth(vector<int>(nums1.begin() + i, nums1.end()),nums2, k - i);
		}
		return 0;
	}

	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();

		return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0;
	}
};

この問題は反復形式の二分探索法も用いることができる.

class Solution {
public:
	double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
		int m = nums1.size(), n = nums2.size();

		if (m < n) 
			return findMedianSortedArrays(nums2, nums1);
		if (n == 0) 
			return ((double)nums1[(m - 1) / 2] + (double)nums1[m / 2]) / 2.0;
		int left = 0, right = n * 2;
		
		while (left <= right) 
		{
			int mid2 = (left + right) / 2;
			int mid1 = m + n - mid2;

			double L1 = mid1 == 0 ? INT_MIN : nums1[(mid1 - 1) / 2];
			double L2 = mid2 == 0 ? INT_MIN : nums2[(mid2 - 1) / 2];
			double R1 = mid1 == m * 2 ? INT_MAX : nums1[mid1 / 2];
			double R2 = mid2 == n * 2 ? INT_MAX : nums2[mid2 / 2];

			if (L1 > R2) 
				left = mid2 + 1;
			else if 
				(L2 > R1) right = mid2 - 1;
			else 
				return (max(L1, L2) + min(R1, R2)) / 2;
		}
		return -1;
	}
};