leetcode -day8 Copy List with Random Pointer & Single Number I II

メーデーの間に何日か切れて、続きます...
1、

Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
分析:剣はofferの上の1つのテーマを指して、3つのステップに分けて行って、まず各チェーンテーブルのノードを複製してそれを各ノードに接続した後、第2のステップはランダムノードを指すポインタをコピーして、第3の部分はチェーンテーブルを分割します.
コードは次のとおりです.

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(head == NULL){
            return NULL;
        }
        cloneNodes(head);
        connectRandomNodes(head);
        return reconnectNodes(head);
    }
    void cloneNodes(RandomListNode *head){
        RandomListNode* pNode = head;
        while(pNode!=NULL){
            RandomListNode* pClonedNode = new RandomListNode(pNode->label);
            pClonedNode->next = pNode->next;
            pNode->next = pClonedNode;
            pNode = pClonedNode->next;
        }
    }
    void connectRandomNodes(RandomListNode *head){
        RandomListNode* pNode = head;
        while(pNode!=NULL){
            RandomListNode* pClonedNode = pNode->next;
            RandomListNode* pRandomNode = pNode->random;
            if(pRandomNode != NULL){
                pClonedNode->random = pRandomNode->next;
            }
            pNode = pClonedNode->next;
        }
    }
    RandomListNode* reconnectNodes(RandomListNode *head){
        RandomListNode* pNode = head;
        RandomListNode* pNextNode = pNode->next;
        RandomListNode* pClonedHead = pNode->next;
        while(pNode!=NULL && pNextNode!=NULL){
            pNode->next = pNextNode->next;
            pNode = pNextNode;
            pNextNode = pNextNode->next;
        }
        return pClonedHead;
    }
};

2、Single Number
Given an array of integers, every element appears twice except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
分析:配列の他に2回しか現れない数字が1回しか現れないのはよくある問題で、簡単で、すべての数字も、最後の結果は1回しか現れない数字です.
コードは次のとおりです.

class Solution {
public:
    int singleNumber(int A[], int n) {
        if(A==NULL || n<=0){
            return 0;
        }
        int result = A[0];
        for(int i=1;i<n;++i){
            result ^= A[i];
        }
        return result;
    }
};

3、Single Number II 
Given an array of integers, every element appears three times except for one. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
分析:1つの数字が1回現れる以外に残りの数字が3回現れて、2回の上ですでに計算したことがあって、3回はどのように0を得て、mod 3を考えて、きっとビット運算を通じて処理します.では、ビット演算はどのようにmod 3を得るのか、シミュレーションしかできません.
1回の出現を除くすべての整数に対して、そのバイナリ表現の1ビットあたりの出現回数は3の整数倍であり、これらすべての1をクリアし、残りは最終的な数である.
onesで現在計算されている変数まで記録し,バイナリ1には「1回」(mod 3以降の1)の数ビットが現れる.現在計算されている変数までtwosで記録すると,バイナリ1には「2回」(mod 3以降の2)の数ビットが現れる.onesとtwosのいずれかが同時に1である場合はバイナリ1が3回現れることを示し,この場合はクリアが必要である.すなわち
3進法計算をバイナリシミュレーションします.最終onesは最終結果を記録します.

class Solution {
public:
    int singleNumber(int A[], int n) {
        int ones = 0, twos = 0, threes = 0;
        for(int i = 0; i < n; i++)
        {
            threes = twos & A[i]; //            
            twos = twos | ones & A[i]; //                      
            ones = ones | A[i]; //     
            
            twos = twos & ~threes; //         ，             
            ones = ones & ~threes; //         ，             
        }
        return ones; //twos, threes    0.ones        
    }
};

4、Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
解析:1つの配列の中で2つの数を探して、それを目標値にして、循環遍歴の複雑度がO(n^2)の場合、先に並べ替えてから2ポインタ法で検索することができます.vectorのiteratorがrandom iteratorであることを考慮すると、持参したsortを使用してソートすることができるが、ソート後にvectorの要素の位置が変化し、題意に合致しない.次に、mapにデータを保存することを考慮し、キー値はvectorの数値、値はvectorのインデックス+1(出力インデックスは1から)とする.
注意mapを使用する場合はvectorの要素が重複するためmultimapを使用するべきであり、stlの赤黒ツリーのend()は空の値であるため、ダブルポインタの場合はテールポインタの付与に注意してください.このような複雑さはO(nlgn)である.
コードは次のとおりです.

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
		vector<int> resultVec;
		if(numbers.empty()){
			return resultVec;
		}
		multimap<int,int> numberMap;
		for(int i=0; i<numbers.size(); ++i){
			numberMap.insert(make_pair(numbers[i],i+1));
		}
		//sort(numbers.begin(),numbers.end());
		multimap<int,int>::iterator iter1 = numberMap.begin();
		multimap<int,int>::iterator iter2 = numberMap.end();
		--iter2;
		int sum = 0;
		while(iter1!=iter2){
			sum = iter1->first+iter2->first;
			if(sum == target){
				int index1 = iter1->second;
				int index2 = iter2->second;
				if(index1>index2){
					swap(index1,index2);
				}
				resultVec.push_back(index1);
				resultVec.push_back(index2);
				break;
			}else if(sum >target){
				--iter2;
			}else{
				++iter1;
			}
		}
		return resultVec;
	}
   
};