序文

誰も読んでくれないので、自己啓発的な書き方をします。

JZ11 2進数の1の数

問題

整数を入力し、その数の 32 ビット 2 進表現における 1 の数を出力します。負の数は補数として表現されます。

解き方

ところで、10進数から2進数への変換方法を復習しておきましょう：

parseInt(n).toString(2)

この質問も、最初はかなり困惑して、後で高い人の指摘を読んで、少し理解することができ、一種の競争の数を再生する感じを持っています。

1100マイナス1～1011。

1を引くと、右端の1から始まるすべてのビットが反転することがわかります。

この時点で、元の整数和から1を引くと、1100&1011=1000という和演算ができます。

つまり、整数から1を引いて元の整数で演算すると、整数の右端の1が0になります。

整数の2進数は、そのような演算の数と同じ数の1を持ちます。

function NumberOf1(n)
{
 // write code here
 var count = 0;
 while(n)
 {
 n = n & (n-1);
 count++;
 }
 return count;
 
}

JZ12 整数のべき乗

問題

double型の浮動小数点数baseとint型の整数指数が与えられた場合、baseの指数べき乗を求めます。

基数と指数が同時に0にならないようにします。

ソリューション

ソリューション1

pow関数の簡単な実装

 /**
 * @return {number}
 */
 function Power(base, exponent) {
 // write code here
 if (exponent === 0) {
 return 1;
 } else if (exponent === 1) {
 return base;
 }
 let ret = base;
 if (exponent > 0) {
 for (let i = 1; i < exponent; i++) {
 ret *= base;
 }
 return ret;
 } else {
 for (let i = 1; i < Math.abs(exponent); i++) {
 ret *= base;
 }
 return 1 / ret;
 }
 }

解答2

最新のES6演算子**の適用

function Power(base, exponent)
{
 // write code here
 return base**exponent;
}

JZ13 奇数が偶数の前に来るように配列を並べ替える方法

問題

整数の配列を入力し、その配列のすべての奇数が配列の前半に、すべての偶数が配列の後半に来るように、また、奇数と奇数、偶数と偶数の相対位置が変わらないように、配列の数字を並べ替える関数を実装します。

ソリューション1

2つのアレイを開いて記録

function reOrderArray(array)
{
 let oddArray = [];
 let evenArray = [];
 for(let i = 0; i < array.length; i++)
 {
 if(array[i]%2 === 0){
 evenArray.push(array[i]);
 }else{
 oddArray.push(array[i]);
 }
 }
 return oddArray.concat(evenArray);
}

解答2

これは特殊な条件判定に相当する挿入ソートです。奇数ならそれを最初に挿入し、残りの数字を後ろに動かします。

function reOrderArray2(array) {
 let k = 0;
 for(let i = 0; i < array.length; i++)
 {
 let tmp = array[i];
 if(tmp & 1){// 
 for(let j = i - 1; j >= k; j--)//すでにソートされた
 {
 array[j+1] = array[j];
 }
 array[k++] = tmp;
 }
 }
 return array;
}
console.log(reOrderArray2([1,2,3,4,5,6]))

JZ14 チェーンテーブルの最後からk番目のノード

問題

連鎖表を入力し、連鎖表の最後のk番目のノードを出力します。

解き方

高速ポインタと低速ポインタはk個離れているので、高速ポインタが終端に到達したとき、低速ポインタの位置はkの逆数になります。

function FindKthToTail(head, k) {
 if (!head || k < 1) return null;
 let slowptr = head;
 let fastptr = head;
 let count = 0;
 while (fastptr != null && count < k) {
 count++;
 fastptr = fastptr.next;
 }
 if (count < k) return null;//kこれは連鎖表の長さ以上かかる
 while (fastptr != null) {
 fastptr = fastptr.next;
 slowptr = slowptr.next;
 }
 return slowptr;
}

JZ15 倒立チェーンテーブル

問題

連鎖表を入力し、連鎖表を反転させ、新しい連鎖表のヘッダを出力します。

解

基本的な考え方として、現在のポインタ.next.nextを保存し、現在のポインタ.nextを現在のポインタにポイントし、次に前進します。

function ReverseList(pHead) {
 // write code here
 if (!pHead) return null;
 if (!pHead.next) return pHead;
 let p1 = pHead;
 let p2 = pHead.next;
 p1.next = null;
 let temp;
 while (p2 != null) {
 temp = p2.next;
 p2.next = p1;
 p1 = p2;
 p2 = temp;
 }
 return p1;
}