推荐一首歌
陌生人 丁倩倩 http://www.kugou.com/song/olx8n55.html?frombaidu?frombaidu#hash=972B9ED063EFD4588457E06F97F4FA5C&album_id=0
读
第七章字符串
总结
1: 字符串的全排列问题
- 字典表排列, 也是数字组合的排列
- 字符串也可以受用下标 123 代替, 那么等于我们直接对 123... 排序在连接在字符串上去了
- 一种实现方式如下
- <?php
- $arr = [1,2,3];
- function x($arr, $str) {
- $count = count($arr);
- if ($count == 1) {
- echo $str . $arr[0]."</br>";
- }
- else {
- for ($i=0; $i <$count; $i++) {
- list($arr[0],$arr[$i]) = [$arr[$i], $arr[0]];
- x(array_slice($arr, 1), $str . $arr[0]);
- }
- }
- }
- x($arr, '');
2: 字符串反转问题.
- 这里要注意的是, 如果是中文字符反转, 使用 $str[$i] 直接获取是不行的, 需要使用 mb_string 函数来操作
- -
- <?php
- $str = '一二三四五六七八九';
- function strrev1($str) {
- $count = strlen($str);
- $new_str = '';
- for ($i = $count - 1; $i>= 0 ; $i--) {
- $new_str .= mb_substr($str,$i,1,'utf-8');
- }
- echo $new_str;
- }
- strrev1($str);
3: 关于指定位置旋转字符串问题.
- 比如一个字符串为 abcdefg 需要从第三个字符开始旋转 得到的结果是 efgabcd
- 我们也可以像之前一样, 使用简单排序, 让 e 排到第一个, f 在排....
- 但是这样需要很大的时间复杂读, 这里介绍一种, 叫三步反转法
- 第一步 反转 abcd 成为 dcba
- 第二部 反转 efg 成为 gfe
- 第三部 连接 dcbagfe 整体反转, 得到字符串.
- -
- <?php
- $str = 'abcdefg';
- function strrev1($str, $target) {
- // 第一部分
- $left = mb_substr($str, 0, $target);
- $right = mb_substr($str, $target);
- for ($i = strlen($left) - 1; $i>= 0; $i--) {
- $new_left .= $left[$i];
- }
- for ($i = strlen($right) - 1; $i>= 0; $i--) {
- $new_right .= $right[$i];
- }
- $str = $new_left . $new_right;
- for ($i = strlen($str) - 1; $i>= 0; $i--) {
- $new_str .= $str[$i];
- }
- echo $new_str;
- }
- strrev1($str, 4);
4: 字符串回文问题
- 什么是回文, 就是正着读和反着读是一样的.
- 比如 abcba
- 那么如何判断是否是回文字符串呢
- 我们可以使用折半来判断
- 这里需要特别注意中轴的计算, 如果长度为 7, 那么下标为 [0-6], 中轴就为 3, 如果为 8, 下标 [0-7], 这里中轴应该选择 3.
- 中轴下标计算公式 (n - 1) / 2
- 7 个数, 中轴为 3,0 对应的就应该是 6,8 个数, 中轴为 3,0 对应的应该为 7
- 所以, 对应的计算公式为 n-1-k
- -
- <?php
- $str = '123-1-321';
- function strUtils($str) {
- $legth = strlen($str);
- $middle = floor(($legth-1) / 2);
- for ($i=0; $i <$middle; $i++) {
- if ($str[$i] != $str[$legth-1-$i]) {
- return false;
- }
- }
- return true;
- }
- var_dump(strUtils($str));
5: 查找最大回文字符串
- 寻找字符串中最长的回文字符串, 例如 abcdedc , 最大回文字符串为 cdedc
- 这里的最简单的办法也就是, 把每一个点都单做是中轴点, 来看最长的匹配
- 这里是我自己的想法, 找出最大回文的开始和结束, 最够同意输出字符串
- <?php
- $str = 'abcdedc';
- function strUtils($str) {
- $legth = strlen($str);
- // 最大回文开始
- $str_strart = 0;
- // 最大回文结束
- $str_end = 0;
- // 临时字段, 确认谁是相隔最大的回文
- $tmp = 0;
- // 遍历, 认为每个点都是中轴点
- for ($i=0; $i < $legth; $i++) {
- // 获取中轴点
- $middle = $i;
- if ($middle == 0 || $middle == $legth -1) continue;
- for ($k=0; $k < $middle; $k++) {
- if ($str[$i - $k] != $str[$i+ $k]) {
- break;
- }
- // 循环 - 找到差距最大的组
- else {
- // 回文开始和结束, 最大间隔
- if ((2 * $k)> $tmp) {
- $str_strart = $i - $k;
- $str_end = $i + $k;
- }
- }
- }
- }
- // 输出回文字符串
- for ($i = $str_strart; $i <= $str_end; $i++) {
- $result .= $str[$i];
- }
- if (strlen($result) <2) return false;
- return $result;
- }
- var_dump(strUtils($str));
6: 字符串包含问题
- 可以使用正常的遍历, 但是会导致时间度非常大 O(M * N)
- 这里使用 HashTable 做排序, 适合重复字符串不多的字符串
- -
- <?php
- $str1 = '123';
- $str2 = '123456789';
- function strExists($str1, $str2) {
- $str2_arrays = str_split($str2);
- // 建立 $str1 的 HashTable
- foreach ($str2_arrays as $key => $str2_array) {
- $HashTable[$str2_array] = $key;
- }
- for ($i=0; $i < strlen($str1); $i++) {
- $data = $HashTable[$str1[$i]];
- $exists[] = $data;
- }
- for ($k=0; $k < count($exists) - 1; $k++) {
- if (($exists[$k] + 1) != $exists[$k + 1]) {
- return false;
- }
- }
- return true;
- }
- var_dump(strExists($str1, $str2));
来源: http://www.bubuko.com/infodetail-2751324.html