プログラミング問題のまとめ

は、2つのチェーンテーブルの第1の共通ノード位置

を見つける.

は、共通ノードが現れると、2つのチェーンテーブルの後続のすべてのノードが同じであり、チェーンテーブルの末尾が同じであることを認識することに重要である.

であるため、2つのチェーンテーブルにポインタを付与し、ポインタを用いて遍歴と比較を行う.

2 2 2つのチェーンテーブルが異なる場合、まず長いチェーンテーブルを短いチェーンテーブルと同じ長さに遍歴する.2つのポインタを並べて比較します.

例えば、a 1->a 2->c 1->c 2->c 3;//チェーンテーブル1 b 1->c 1->c 2->c 3;//チェーンテーブル2

左シフトの基本思想は、YX=(XT Y T)Tであるため、左シフトnビットは、前nビットの位置交換(第1ビットと第nビットの交換)、さらに(n+1)ビットを最後のビットの位置交換、好ましくは同から尾へ元素の位置交換に等しい.

for(int i=0,j=n-1;i<j;++i,--j)
      swap(str[i],str[j]);
for(int i=n,j=len-1;i<j;++i,--j)
      swap(str[i],str[j]);
for(int i=0,j=len-1;i<j;++i,--j)
      swap(str[i],str[j]);

同理,右シフトnビット:(総長len)

後nビット、互いに位置を交換する.(n番目と最後の交換)

残りの他の要素は互いに位置を交換する.(1位とlen-n位の交換)

は1位から最後の位まで互いに位置を交換する.(1位とlen位の交換)

文字列の文字をスペースから分離する鍵は、2つの変数、1つの移動、1つのタグが必要であることです.I am a student.|i,mは、スペースに遭遇するまでiを移動する.このとき(i-1)とmの間は文字である.

string ReverseSentence(string str) {
        int mark=0;
        int i;
        int len=str.size();
        if(len==0) return str;
        str+=' ';				//       ，            
        for(i=0;i<len+1;++i)	//      ，     1
        {
            if(str[i]==' ')
            {
                Reverse(str,i-1,mark);
                mark=i+1;
            }
        }
        str=str.substr(0,len);			//          
        for(int j=len-1,i=0;i<j;++i,--j)
            swap(str[i],str[j]);
        return str;
    }
    void Reverse(string &str,int i,int m)
    {

        while(m<i)
        {
            swap(str[m],str[i]);
            m++;
            i--;
        }
    }

一度現れるアルファベットを見つけて、2回現れるアルファベットを見つけて、n回現れるアルファベットを見つけます:基本思想:1つの配列を利用して各要素が何回現れたかを記録して、そして要求に従って出力します;

//   vector a;
int C[256]={0};
for(int i=0;i<a.size();++i)
{
	C[a[i]]=C[a[i]]+1; //        
}
for(int i=0;i<a.size();++i)
{
	if(C[a[i]]==1)	//             
		return a[i];
}

5.チェーンテーブルの中のリング:まず定理を言います:2つのポインタは1つのfast、1つのslowは同時に1つのチェーンテーブルの頭部から出発します;fastは1回2歩、slowは1回1歩、もしこのチェーンテーブルにリングがあれば、2つのポインタは必ずリング内で出会うこの時、そのうちの1つのポインタをチェーンテーブルの頭に再び指さすだけで、もう1つは変わらない(まだリング内)、今回2つのポインタは1回1歩、出会った場所は入口ノードです.
このリングの長さを探すにはfastとslowのステップ長を一定に保つだけで、両者が再び出会ったとき、slowが歩く総ステップ数はリングの長さです.

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead == NULL){
            return NULL;
        }
        ListNode* meetingnode = MeetingNode(pHead);
        if(meetingnode == NULL){
            return NULL;
        }
        ListNode* pNode1 = meetingnode;
        //         ，     
        ListNode* pNode2 = pHead;
        while(pNode1 != pNode2){
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }
        return pNode1;
    }
private:
    //       ，           
    ListNode* MeetingNode(ListNode* pHead){
        ListNode* pSlow = pHead->next;
        if(pSlow == NULL){
            return NULL;
        }
        ListNode* pFast = pSlow->next;
        while(pFast != NULL && pSlow != NULL){
            if(pFast == pSlow){
                return pFast;
            }
            pSlow = pSlow->next;
            pFast = pFast->next;
            if(pFast != NULL){
                pFast = pFast->next;
            }
        }
        return NULL;
    }
};

https://blog.csdn.net/weixin_38075257/article/details/87921436