php算法實(shí)現(xiàn)（一）

xcc3641 發(fā)布于2019-06-28 18:40 / 2659人閱讀

摘要：記錄所有算法相關(guān)知識。寫算法時(shí)，可以先寫，這樣比較容易把握和思考。以下算法都可以直接跑。冒泡算法這種形式比較簡便易讀快速排序。

記錄所有算法相關(guān)知識。寫算法時(shí)，可以先寫test case，這樣比較容易把握和思考。
以下算法都可以直接跑。
1.冒泡算法

     $arr[$j]) {
                    //這種形式比較簡便易讀
                    list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]);
                }
            }
        }
        return $arr;
    }

2.快速排序。簡單思路，隨機(jī)挑選一個(gè)數(shù)組中的值，以它為標(biāo)準(zhǔn)，小于他的放在她的左邊，大于他的放在他的右邊。之后遞歸，最后所有的值都會排列好。


3.從兩個(gè)數(shù)組中找出相同的數(shù)
 $arr2[$index2]) {
            $index2++;
        } else {
            $container[] = $arr1[$index1];
            //放入container之后，不要忘記增加index
            $index1++;
            $index2++;
        }
    }
    return array_unique($container);
}
4.重寫shuffle函數(shù)，打亂一個(gè)數(shù)組

5.分離字母和數(shù)字。一個(gè)string中有字母數(shù)字，分離并用：分割

6.約瑟夫環(huán)問題
相關(guān)題目：一群猴子排成一圈，按1,2,…,n依次編號。然后從第1只開始數(shù)，數(shù)到第m只,把它踢出圈，從它后面再開始數(shù)， 再數(shù)到第m只，在把它踢出去…，如此不停的進(jìn)行下去， 直到最后只剩下一只猴子為止，那只猴子就叫做大王。要求編程模擬此過程，輸入m、n, 輸出最后那個(gè)大王的編號。
 1) {
        for ($i=0;$i<$n-1;$i++) {
            $pop = array_shift($roundTable);
            array_push($roundTable, $pop);
        }
        array_shift($roundTable);
    }
    return $roundTable[0];
}
7.二分法
 $index) {
            $right = $mid - 1;
        } else if ($arr[$mid] < $index) {
            $left = $mid + 1;
        } else {
            return $mid;
        }
    }
    return -1;
}
8.找出一組數(shù)中連續(xù)的最大和
= 0) {
            if ($maxSum < $currentSum) 
                $maxSum = $currentSum;
            $currentSum += $arr[$i];
        } else {
            $currentSum = $arr[$i];
        }
    }
    return $maxSum;
}
9.3sum. 排序好的數(shù)列，復(fù)雜度n^2。如果沒有排列好，可以先用sort
left，所以不用擔(dān)心i,left,right相等
        while ($right > $left) {
            $sum = $arr[$left] + $arr[$i] + $arr[$right];
            if ($sum < 0) {
                $left++;
            } else if ($sum > 0) {
                $right--;
            } else {
                $set = array($arr[$left], $arr[$i], $arr[$right]);
                $result[] = $set;
                //不要忘記++，否則死循環(huán)
                $left++;
                $right--;
            }
        }
    }
    return $result;
}