用PHP从一个数组和给定的模式中获取最近的序列结果。

问题描述 投票:0回答:1

我正试图使用既定的序列从字母中获取年和月。我知道这个序列是基于以下字母的。

$letters = array('B','C','D','F','G','H','J','K','L','M','N','P','R','S','T','V','W','X','Y','Z');

从0000BBB开始,到了9999就变成了BBC,BBD等。所以在这种情况下,我不需要数字,只需要字母,因为我有一个最后注册的序列列表,每年和每月都是这样的。

$plates = array(
            array('2018','KHF','KHX','KJV','KKN','KLM','KML','KNK','KPD','KPR','KPT','----','----'),
            array('2017','JWN','JXF','JYB','JYT','JZP','KBM','KCH','KCV','KDK','KFB','KFV','KGN'),
            array('2016','JLN','JMF','JMY','JNR','JPK','JRG','JRZ','JSL','JTB','JTR','JVH','JVZ'),
            array('2015','JCK','JCY','JDR','JFG','JFW','JGP','JHJ','JHT','JJH','JJW','JKK','JKZ'),
            array('2014','HVN','HVZ','HWM','HXB','HXN','HYD','HTY','HZB','HZL','HZZ','JBL','JBY'),
            array('2013','HNT','HPC','HPN','HPY','HRK','HRX','HSK','HSR','HSZ','HTK','HTV','HVF'),
            array('2012','HJC','HJM','HKB','HKL','HKX','HLK','HLW','HMD','HML','HMT','HNC','HNK'),
            array('2011','HBP','HCB','HCR','HDC','HDR','HFF','HFT','HGC','HGM','HGX','HHH','HHT'),
            array('2010','GTC','GTS','GVM','GWC','GWV','GXP','GYD','GYM','GYX','GZJ','GZT','HBG'),
            array('2009','GKS','GLC','GLP','GMC','GMN','GNF','GNY','GPJ','GPW','GRM','GSC','GSR'),
            array('2008','FZR','GBN','GCK','GDH','GFC','GFY','GGV','GHG','GHT','GJJ','GJV','GKH'),
            array('2007','FKY','FLV','FNB','FNZ','FRC','FSJ','FTP','FVJ','FWC','FXB','FXY','FYY'),
            array('2006','DVW','DWT','DXZ','DYY','FBC','FCJ','FDP','FFK','FGF','FHD','FJD','FKC'),
            array('2005','DFZ','DGX','DHZ','DKB','DLD','DMJ','DNP','DPK','DRG','DSC','DTB','DVB'),
            array('2004','CRV','CSS','CTT','CVR','CWR','CXT','CYY','CZP','DBJ','DCH','DDG','DFF'),
            array('2003','CDV','CFM','CGJ','CHF','CJC','CKB','CLD','CLV','CMM','CNK','CPF','CRC'),
            array('2002','BSL','BTF','BTZ','BVW','BWT','BXP','BYP','BZF','BZV','CBP','CCH','CDC'),
            array('2001','BFJ','BGF','BHG','BJC','BKB','BLC','BMF','BMW','BNL','BPG','BRB','BRT'),
            array('2000','---','---','---','---','---','---','---','---','BBJ','BCD','BCY','BDR')
        );

这意味着数组索引0是年,1到12是月。我试图找到一个匹配的,但后来意识到我不能搜索精确的值,需要寻找基于字母的最近的值。

如果有谁能指导我正确的方向,最好的方法是什么,我将深表感激。

到目前为止,这是一个测试,但这将只是返回一个精确的匹配,我将不得不搜索任何可能的字母,如 KHW 作为一个例子,它将必须与以下数值最接近 KHX

foreach ($plates as $key => $val) {                        
            $search = array_search('KHX', $plates[$key]);            
            if($search){
                echo $search."\n";
                echo $plates[$key][0];
                break;
            }
        }        
php arrays compare sequence string-comparison
1个回答
1
投票

你可以用二进制搜索用O(log n)来解决。但更直接的解法,你可以用O(n).你可以用下面的算法计算每个字之间的差别。

<?php

function strToInt($str)
{
    $result = 0;
    for ($i = 0; $i < strlen($str); $i++) {
        $result = $result * 100 + ord($str[$i]);
    }

    return $result;
}

function find($searchStr)
{
    $plates = [
        ['2018','KHF','KHX','KJV','KKN','KLM','KML','KNK','KPD','KPR','KPT','----','----'],
        ['2017','JWN','JXF','JYB','JYT','JZP','KBM','KCH','KCV','KDK','KFB','KFV','KGN'],
        ['2016','JLN','JMF','JMY','JNR','JPK','JRG','JRZ','JSL','JTB','JTR','JVH','JVZ'],
        ['2015','JCK','JCY','JDR','JFG','JFW','JGP','JHJ','JHT','JJH','JJW','JKK','JKZ'],
        ['2014','HVN','HVZ','HWM','HXB','HXN','HYD','HTY','HZB','HZL','HZZ','JBL','JBY'],
        ['2013','HNT','HPC','HPN','HPY','HRK','HRX','HSK','HSR','HSZ','HTK','HTV','HVF'],
        ['2012','HJC','HJM','HKB','HKL','HKX','HLK','HLW','HMD','HML','HMT','HNC','HNK'],
        ['2011','HBP','HCB','HCR','HDC','HDR','HFF','HFT','HGC','HGM','HGX','HHH','HHT'],
        ['2010','GTC','GTS','GVM','GWC','GWV','GXP','GYD','GYM','GYX','GZJ','GZT','HBG'],
        ['2009','GKS','GLC','GLP','GMC','GMN','GNF','GNY','GPJ','GPW','GRM','GSC','GSR'],
        ['2008','FZR','GBN','GCK','GDH','GFC','GFY','GGV','GHG','GHT','GJJ','GJV','GKH'],
        ['2007','FKY','FLV','FNB','FNZ','FRC','FSJ','FTP','FVJ','FWC','FXB','FXY','FYY'],
        ['2006','DVW','DWT','DXZ','DYY','FBC','FCJ','FDP','FFK','FGF','FHD','FJD','FKC'],
        ['2005','DFZ','DGX','DHZ','DKB','DLD','DMJ','DNP','DPK','DRG','DSC','DTB','DVB'],
        ['2004','CRV','CSS','CTT','CVR','CWR','CXT','CYY','CZP','DBJ','DCH','DDG','DFF'],
        ['2003','CDV','CFM','CGJ','CHF','CJC','CKB','CLD','CLV','CMM','CNK','CPF','CRC'],
        ['2002','BSL','BTF','BTZ','BVW','BWT','BXP','BYP','BZF','BZV','CBP','CCH','CDC'],
        ['2001','BFJ','BGF','BHG','BJC','BKB','BLC','BMF','BMW','BNL','BPG','BRB','BRT'],
        ['2000','---','---','---','---','---','---','---','---','BBJ','BCD','BCY','BDR']
    ];

    $minYear = null;
    $minKey = null;
    $minDiff = strToInt('ZZZ');
    $searchInt = strToInt($searchStr);

    for ($i = 0; $i < count($plates); $i++) {
        for ($j = 1; $j < 13; $j++) {
            if(abs($searchInt - strToInt($plates[$i][$j])) < $minDiff) {
                $minDiff = abs($searchInt - strToInt($plates[$i][$j]));
                $minYear = $plates[$i][0];
                $minKey = $plates[$i][$j];
            }
        }
    }

    return [$minYear, $minKey];
}


print_r(find('KHW'));

1
投票

下面的代码绝不是优化过的,而是你解决问题的一个概念。

//Flatten out array (one dimension without years and ----)
$flatten = array();
foreach($plates as $platevalues) {
    foreach($platevalues as $pv) {        
        if ($pv != '---' && $pv != '----' && intval($pv) == 0) {
            //Create a string only if valid letters included in the $letters-array
            //This string is then added to the new array that is flattened out
            $pv2 = '';
            for($i=0;$i<strlen($pv);$i++) {
                $letter = substr($pv,$i,1);
                if (in_array($letter, $letters) !== false) {
                    $pv2 .= $letter;
                }
            }
            $flatten[] = $pv2;
        }
    }
}

//Do the search
$search = 'GWN';
$search_result = '';

//Create a new search string based on first found in flattened
//plates array (first G, then GW, then GWN)
for($i=0;$i<strlen($search);$i++) {
    foreach($flatten as $key=>$f) {
        if (substr($search,0,$i+1) == substr($f,0,$i+1)) {
            $search_result .= substr($search,$i,1);
            break;
        }
    }
}
/*
$search_result is: GW
*/

//Create a new array where all items that begins with GW are included
$result = [];
foreach($flatten as $key=>$item) {
    if (substr($search_result,0,strlen($search_result)) == 
    substr($item,0,strlen($search_result))) {
        $result[] = $item;   
    }
}
/*
$result =

array (size=2)
    0 => string 'GWC' (length=3)
    1 => string 'GWV' (length=3)
*/

//Create an array with total ASCII-value for each item 
//in the $result array above
$result_o = [];
foreach($result as $item) {
    $o = 0;
    for($i=0;$i<strlen($item);$i++) {
        $o += ord(substr($item,$i,1));
    }
   $result_o[]= $o;
}
/* 
$result_o = 

array (size=2)
    0 => int 225
    1 => int 244        
*/


//Get the total ASCII-value for the original search string
$search_o = 0;
for($i=0;$i<strlen($search);$i++) {
    $search_o += ord(substr($search,$i,1));
}
/*
$search_ o = 236
*/


//Find closest value in the $result_o (ASCII) - array compared (225,244)
//to the original $search_o ASCII value above (236)
$closest = 0;
$use_key = 0;
foreach($result_o as $key=>$item) {
    if ($closest == 0 || abs($search_o - $closest) > abs($item - $search_o)) {
        $closest = $item;
        $use_key = $key;
    }
}

/* 
$closest = 244 (it's closer to 236 than 225 is)
$use_key = 1
*/

为了得到你所拥有的结果。

/*
$result =

array (size=2)
    0 => string 'GWC' (length=3)
    1 => string 'GWV' (length=3)
*/

//This should print out GWV
echo 'result=' . $result[$use_key];
© www.soinside.com 2019 - 2024. All rights reserved.