滴滴笔试编程IP地址题

<?php
$stdin = fopen('php://stdin','r');
$count = trim(fgets($stdin));
//var_dump($count);die();

for($i=1;$i<$count;$i++){
    $input[] = trim(fgets($stdin));
}
$inputBackup = $input;
//var_dump($input);
foreach($input as &$v){
    list($add,$num[]) = explode('/',$v);
    $add = explode('.',$add);
    foreach($add as &$_v){
        $_v = decbin($_v);
        $_v = str_pad($_v,8,"0",STR_PAD_LEFT);
    }
    $address[] = implode('',$add);
}

$j = 0;
foreach($address as $k => $v){
    ${'array'.$j}['value'] = substr($v,0,$num[$k]);
    ${'array'.$j}['key'] = $k;
    $j++;
}
$j--;
for($n=0;$n<=$j;$n++){
    for($m=0;$m<=$j;$m++){
        if($m != $n){
            if($num[$n] <= $num[$m]){
                $tmp = (substr(${'array'.$m}['value'],0,$num[$n]));
                if($tmp == ${'array'.$n}['value']){
                    unset(${'array'.$m});
                }
            }else{
                $tmp = (substr(${'array'.$n}['value'],0,$num[$m]));
                if($tmp == ${'array'.$m}['value']){
                    unset(${'array'.$n});
                }
            }
        }
    }
}

for($n=0;$n<=$j;$n++){
    if(isset(${'array'.$n})){
        $keys[] = ${'array'.$n}['key'];
    }
}

foreach($inputBackup as $k => $v){
    if(!in_array($k,$keys)){
        unset($inputBackup[$k]);
    }
}

$counting = count($inputBackup);
print($counting.'<br>');
foreach($inputBackup as $k => $v){
    print($v.'<br>');
}
?>

最后出来结果和测试用例比莫名其妙少了一组TuT 感觉就这样和AC擦肩而过了
6
192.168.0.0/16
172.50.137.225/32
202.139.219.192/32
192.183.125.71/32
201.45.111.138/32
172.24.0.0/17

#滴滴#

全部评论

推荐最新楼层

ALfheimSAO

Ohio State University Java

我用trie树做的第一题是用dp 做的

点赞回复分享

发布于 2017-10-09 22:33

我是个菜

南安普顿大学 C++

我是把ip地址转成32位的二进制，然后XOR，看到比较短的那个掩码的位数是不是都是0，但是只过了60多，不知道为什么。 #include <iostream> #include <cstdio> #include <map> #include <string> #include <sstream> #include <vector> #include <set> #include <bitset> using namespace std; ostringstream ostr; struct ip_addr { bitset<32> s1,s2,s3,s4; unsigned int l; bitset<32> bin; }; int main(){ int n= 0; cin >> n; vector<ip_addr> ips; vector<string> ipstring; set<int> idx; for(int i = 0; i < n; i++){ ip_addr ip; unsigned int s1,s2,s3,s4,l; scanf("%d.%d.%d.%d/%d",&s1,&s2,&s3,&s4,&ip.l); ip.s1 = bitset<32>(s1); ip.s2 = bitset<32>(s2); ip.s3 = bitset<32>(s3); ip.s4 = bitset<32>(s4); ip.bin = ((ip.s1<<8 | ip.s2)<<8 | ip.s3)<<8 | ip.s4; ips.push_back(ip); bool flag =false; for(auto j:idx){ ip_addr tmp = ips[j]; unsigned int tmp_l = tmp.l; bool current_wider = tmp.l>ip.l; unsigned int len = current_wider?ip.l:tmp.l; string compare="00000000000000000000000000000000"; string _xor = (tmp.bin^ip.bin).to_string(); if(compare.substr(0,len) == _xor.substr(0,len)){ if(current_wider){ idx.erase(j); } else{ flag = true; } } } if(flag){ continue; } idx.insert(i); } cout<<idx.size()<<endl; for(auto j:idx){ ip_addr ip = ips[j]; cout<<ip.s1.to_ulong()<<'.'<<ip.s2.to_ulong()<<'.'<<ip.s3.to_ulong()<<'.'<<ip.s4.to_ulong()<<'/'<<ip.l<<endl; } return 0; }

点赞回复分享

发布于 2017-10-09 22:27

流星幻象

北京邮电大学 Java

import java.util.*; public class Main{ public static void main(String[] args) throws Exception{ Scanner in = new Scanner(System.in); int k = in.nextInt(); String[] cidr = new String[k]; for(int i = 0; i < k; i++){ cidr[i] = in.next(); } String[] temp = new String[k]; for(int i = 0; i < k; i++){ temp[i] = ""; } for(int i = 0; i < k; i++){ String[] arr = cidr[i].split("/"); String[] arr2 = arr[0].split("\\."); for(int j = 0; j < arr2.length; j++){ temp[i]+=String.format("%08d",Integer.parseInt(Integer.toBinaryString(Integer.parseInt(arr2[j])))); } temp[i] = temp[i].substring(0, Integer.parseInt(arr[1])); } boolean[] flag = new boolean[k]; int count = k; for(int i = 0; i < k-1; i++){ for(int j = i+1; j < k; j++){ if(flag[i]==true){ break; } if(temp[i].indexOf(temp[j])==0){ flag[i] = true; count--; } if(temp[j].indexOf(temp[i])==0){ flag[j] = true; count--; } } } System.out.println(count); for(int i = 0; i < k; i++){ if(!flag[i]){ System.out.println(cidr[i]); } } } }

滴滴笔试编程IP地址题

全站热榜

创作者周榜