C++剣指Offerシリーズ(1)——チェーンテーブルの最後からK番目のノード(JZ 14)奇数が偶数の前に位置するように配列を調整する(JZ 13)

剣指Offerシリーズ(1)

1. チェーンテーブルの最後からK番目のノード

2. 奇数が偶数の前に位置するように配列を調整する

1.チェーンテーブルの最後からK番目のノード
タイトル:チェーンテーブルを入力し、チェーンテーブルの最後からk番目のノードを出力します.従来の考え方は簡単で,チェーンテーブル長n,n−k+1を統計し,順次下にシフトすればよいが,より簡単な高速法がある.

は、ポインタ1とポインタ2を先頭に向けて初期化し、ポインタ2をk−1 k−1個の位置に前方に移動させる.

は、ポインタ2が最後のノード

に達するまで、ポインタ1とポインタ2を同時に後方に移動する.

このときポインタ1は、最後からk番目のノードを指す.

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
     
public:
    ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
     
        if(k==0||pListHead == NULL)return NULL; //    ，pListHead    
        ListNode* tmp = pListHead;
        ListNode* tmp2 = pListHead;
        for(unsigned int i =0 ;i<k-1;i++){
         //    k-1 
          if(tmp2->next != NULL)    //  k    ，        
                tmp2 = tmp2->next;
            else
            {
     
                return NULL;
            }
        }
        while(tmp2->next!=NULL){
         //        ，     k   
            tmp2 = tmp2->next;
            tmp = tmp->next;
        }
        return tmp;
        
        
    }
};

この問題はもともと難しくなくて、主に2つのとても弱い知恵の誤りがあって、またチェーンテーブルが空であることを考慮しなければならなくて、あるいはkがチェーンテーブルの長さより大きい情況を考慮しなければならなくて、とても長い時間DEBUGを浪費して、本当にこの2つの特殊な条件をいじってこの問題に対してどんな意義があるとは思いません.
2.奇数が偶数より前になるように配列を調整する
この問題は私が考えているのは知恵の弱いアルゴリズムで、別のvectorを設定します

class Solution {
     
public:
    void reOrderArray(vector<int> &array) {
     
      vector<int> tmp = array;
      int len =0;
      for(int i = 0; i< array.size();i++){
     
        if(array[i]&1 !=0){
     
            tmp[len] = array[i];
            len++;
        }
      }
        for(int i = 0; i< array.size();i++){
     
        if(array[i]%2 ==0){
     
            tmp[len] = array[i];
            len++;
        }
      }
        array  = tmp;
    }
};

もう一つの方法は、スペースを別に設けないことです.偶然ではありません.

class Solution {
     
public:
  void reOrderArray(vector<int> &array) {
     
      int i = 0;
      for (int j=0; j<array.size(); ++j) {
     
          if (array[j]&1) {
     
              int tmp = array[j];
              for (int k=j-1; k>=i; --k) {
     
                  array[k+1] = array[k];
              }
              array[i++] = tmp;
          }
      }
  }
};

この問題は比較的簡単だ