下午自己用C++写的FB恐龙题

自己下午闲着没事干写了一下恐龙题，可直接在coderpad上运行
恐龙题是啥，就是下面这个：

divide array to two equal sun和恐龙题 (Leetcode)
Dataset1
恐龙名字， 恐龙腿长， 恐龙食性（食草，食肉，两者皆吃，这个是无关feature)

Dataset2
恐龙名字， 恐龙某个feature(...

Dataset2
恐龙名字， 恐龙某个feature(暂名d1), Stance(两只脚，四只脚等）

要求，选出stance是两只脚走路的恐龙，计算出他们的速度，并根据速度排序，然后从快到慢输出名字。.

速度是根据腿长以及d1来算出来的。

看上述要求，很明显先扫dataset2, 写一个class，然后放到map里。 最后处理第一个dataset， 算出speed,放到heap中。输出。


#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <unordered_map>
#include <queue>
#include <cmath>
using namespace std;

/*
dinosaurs question

You will be supplied with two data files in CSV format. The first file contains
statistics about various dinosaurs. The second file contains additional data.

Given the following formula,

speed = ((STRIDE_LENGTH / LEG_LENGTH) - 1) * SQRT(LEG_LENGTH * g)
Where g = 9.8 m/s^2 (gravitational constant)
(normal code)
Write a program to read in the data files from disk, it must then print the names
of only the bipedal dinosaurs from fastest to slowest. Do not print any other information.

$ cat dataset1.csv
NAME,LEG_LENGTH,DIET
Hadrosaurus,1.2,herbivore
Struthiomimus,0.92,omnivore
Velociraptor,1.0,carnivore
Triceratops,0.87,herbivore
Euoplocephalus,1.6,herbivore
Stegosaurus,1.40,herbivore
Tyrannosaurus Rex,2.5,carnivore

$ cat dataset2.csv
NAME,STRIDE_LENGTH,STANCE
Euoplocephalus,1.87,quadrupedal
Stegosaurus,1.90,quadrupedal
Tyrannosaurus Rex,5.76,bipedal
Hadrosaurus,1.4,bipedal
Deinonychus,1.21,bipedal
Struthiomimus,1.34,bipedal
Velociraptor,2.72,bipedal
*/
class dinosaurs {
public:
  
/*** calculate speed  
speed = ((STRIDE_LENGTH / LEG_LENGTH) - 1) * SQRT(LEG_LENGTH * g)***/
  
  float speed(float leg_length, float stride_length) {
    return (stride_length / leg_length - 1) * sqrt(leg_length * 9.8);
  }
  
  vector <string> read_line(string s) {
    vector <string> m;
    s.push_back(',');
    string t;
    for(int i = 0; i < (int)s.size(); ++i) {
      if (s[i] == ',') {
        m.push_back(t);
        t.clear();
      }
      else t += s[i];
    }
    return m;
  }
  vector <string> calculate(vector <string> file1, vector <string> file2) {
    map <string, float> m2;
    for (int i = 0; i < (int)file2.size(); ++i) {
      vector <string> tmp = read_line(file2[i]);
      if (tmp[2] == "bipedal") m2[tmp[0]] = stof(tmp[1]);
    }
    map <string, float> m;
    for (int i = 0; i < (int)file1.size(); ++i) {
      vector <string> tmp = read_line(file1[i]);
      if (m2.count(tmp[0])) m[tmp[0]] = speed(m2[tmp[0]], stof(tmp[1]));
    }
    priority_queue <pair <float, string>> q;
    for (auto it : m) {
      q.push({it.second, it.first});
    }
    vector <string> res;
    while (!q.empty()) {
      auto t = q.top(); q.pop();
      res.push_back(t.second);
    }
    return res;
  }
};
int main () {
  vector <string> file1 = { "NAME,LEG_LENGTH,DIET",
                  "Hadrosaurus,1.2,herbivore",
                  "Struthiomimus,0.92,omnivore",
                  "Velociraptor,1.0,carnivore",
                  "Triceratops,0.87,herbivore",
                  "Euoplocephalus,1.6,herbivore",
                  "Stegosaurus,1.40,herbivore",
                  "Tyrannosaurus Rex,2.5,carnivore"};
  vector <string> file2 = {"NAME,STRIDE_LENGTH,STANCE",
                  "Euoplocephalus,1.87,quadrupedal",
                  "Stegosaurus,1.90,quadrupedal",
                  "Tyrannosaurus Rex,5.76,bipedal",
                  "Hadrosaurus,1.4,bipedal",
                  "Deinonychus,1.21,bipedal",
                  "Struthiomimus,1.34,bipedal",
                  "Velociraptor,2.72,bipedal"  
                 };
  dinosaurs d;
  vector <string> res = d.calculate(file1, file2);
  cout <<"The names of only the bipedal dinosaurs from fastest to slowest is:" <<endl;
  for (auto it : res)
    cout << it << endl;
  return 0;
}

小弟寫了一下java版  有錯請指教

import java.util.*;
import java.io.*;

class Dino
{
        String name;
        //String stance;
        double vel;
        double stride;
        double leg;
       
        Dino(String in_name, double in_stride)
        {
                name = in_name;
                stride = in_stride;
        }
}

public class dinosaur {
       
        public static void main(String[] arg)
        {               
                Map<String, Dino> map = new HashMap<>();
                // put file in the "project folder"
                List<String> data1= parseFile(new File("dataset1.csv"));
                List<String> data2= parseFile(new File("dataset2.csv"));
                PriorityQueue<Dino> Q = new PriorityQueue<>(new Comparator<Dino>()
                { public int compare(Dino a, Dino b)
                  {
                         return (a.vel - b.vel)<0?1:-1;
                  }
                });
               
                for(String s2 : data2)
                {
                        String[] dino = s2.split(",");
                        if(dino[2].equals("bipedal"))
                        {
                                Dino d = new Dino(dino[0], Double.parseDouble(dino[1]));
                                map.put(dino[0], d);
                        }
                }
               
                for(String s1 : data1)
                {
                        String[] dino = s1.split(",");
                        if(map.containsKey(dino[0]))
                        {
                                double leg = Double.parseDouble(dino[1]);
                                Dino d = map.get(dino[0]);
                                d.vel = (d.stride/leg-1)*Math.sqrt(leg*9.8);
                                Q.offer(d);
                        }
                }
               
                while(!Q.isEmpty())
                {
                        Dino d = Q.poll();
                        System.out.println(d.name + "  "  + d.vel);
                }
        }
       
        static List<String> parseFile(File f)
        {
                List<String> list = new LinkedList<>();
                try
                {
                        Scanner input = new Scanner(f);
                        while(input.hasNextLine())
                                list.add(input.nextLine());
                }
                catch(FileNotFoundException e)
                {
                        e.printStackTrace();
                }
                return list;
        }
}

面试题： 从多个html文件中替换其中的email。我知道这个题其实最简单的是用正则表达式。如果非要c++程序实现的话，其实就是实现一个文件中字符串替换的函数。
此题的点在于导入文件到vector。寻找字符串，找到后替换，然后再写回文件。以下贴出本人写的可编译运行的代码。

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

class Solution{
public:
        string replace_str(string &s, string &nat, string &rep) {
                while (true) {
                        int pos = s.find(nat);
                        if (pos == (int) string::npos) break;
                        s.replace(pos, (int) nat.size(), rep);
                }
                return s;
        }
};

int main (int argc, char ** argv) {
        if (argc != 4) {
                cout <<"Invalid!" << endl;
                exit(0);
        }
       ifstream s(argv[1]);
        if (!s) {
                cout << "Does not exit" << endl;
                exit(1);
        }
        string nat = argv[2];
        string rep = argv[3];
        Solution b;
        vector <string> in;
        string out;
        while (getline(s, out)) {
                out = b.replace_str(out, nat, rep);
                in.push_back(out);
        }
        ofstream r(argv[1]);
        for (int i = 0 ; i < (int)in.size(); ++i) {
                r <<  in[i] + '\n';
        }
        return 0;
}

自己又改进了一下，可直接读取csv文件到vector，然后处理vector。另外，如果处理ifstream 一定要#include <fstream>

class dinosaurs {
public:

vector <string> dump_file(ifstream &s) {
   vector <string> res;
   string out;
   while (getline(s, out)) {
      res.push_back(out);
      out.clear();
   }
   return res;
}


/*** calculate speed
speed = ((STRIDE_LENGTH / LEG_LENGTH) - 1) * SQRT(LEG_LENGTH * g)***/

  float speed(float leg_length, float stride_length) {
    return (stride_length / leg_length - 1) * sqrt(leg_length * 9.8);
  }

  vector <string> read_line(string s) {
    vector <string> m;
    s.push_back(',');
    string t;
    for(int i = 0; i < (int)s.size(); ++i) {
      if (s[i] == ',') {
        m.push_back(t);
        t.clear();
      }
      else t += s[i];
    }
    return m;
  }
  vector <string> calculate(vector <string> file1, vector <string> file2) {
    map <string, float> m2;
    for (int i = 0; i < (int)file2.size(); ++i) {
      vector <string> tmp = read_line(file2[i]);
      if (tmp[2] == "bipedal") m2[tmp[0]] = stof(tmp[1]);
    }
    map <string, float> m;
    for (int i = 0; i < (int)file1.size(); ++i) {
      vector <string> tmp = read_line(file1[i]);
      if (m2.count(tmp[0])) m[tmp[0]] = speed(m2[tmp[0]], stof(tmp[1]));
    }
    priority_queue <pair <float, string>> q;
    for (auto it : m) {
      q.push({it.second, it.first});
    }
    vector <string> res;
    while (!q.empty()) {
      auto t = q.top(); q.pop();
      res.push_back(t.second);
    }
    return res;
  }
};
int main () {
  dinosaurs d;
  ifstream s1("file1.csv");
  ifstream s2("file2.csv");
  vector <string> file1 = d.dump_file(s1);
  vector <string> file2 = d.dump_file(s2);
  vector <string> res = d.calculate(file1, file2);
  cout <<"The names of only the bipedal dinosaurs from fastest to slowest is:" <<endl;
  for (auto it : res)
    cout << it << endl;
  return 0;
}

就不直接新开贴了。贴一下 Goat to Latin

原题是这样要求的：

Goat to Latin  is a made-up language based off of English, sort of like Pig Latin.
(normal code)
The rules of Goat Latin are as follows:
1. If a word begins with a consonant (i.e. not a vowel), remove the first
    letter and append it to the end, then add 'ma'.
    For example, the word 'goat' becomes 'oatgma'.
2. If a word begins with a vowel (a, e, i, o, or u), append 'ma' to the end of the word.
    For example, the word 'I' becomes 'Ima'.
3. Add one letter "a" to the end of each word per its word index in the
    sentence, starting with 1. That is, the first word gets "a" added to the
    end, the second word gets "aa" added to the end, the third word in the
    sentence gets "aaa" added to the end, and so on.

Write a function that, given a string of words making up one sentence, returns
that sentence in Goat Latin. For example:

  string_to_goat_latin('I speak Goat Latin')

would return: 'Imaa peaksmaaa oatGmaaaa atinLmaaaaa'

其实很简单，就是按照要求来就行了。如果遇到元音(aeiou注意还有其大写)字母开头，直接串尾加ma 然后再加index数量的a
如果是辅音字母把头去掉，加到尾部，然后再直接加ma和index数量的a。 index为该词的拆分成vector之后的序号。

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <sstream>
#include <unordered_set>

using namespace std;
class Solution {
public:
        vector <string> str_to_vec(string &s) {
                vector <string> res;
                istringstream in(s);
                string word;
                while (in >> word) {
                        res.push_back(word);
                }
                return res;
        }
        string string_to_goat_latin(string s) {
                vector <string> res = str_to_vec(s);
                for (int i = 0; i < (int) res.size(); ++i) {
                        if(ref.count(res[i][0])) res[i] += "ma";
                        else res[i] = res[i].substr(1) + res[i].substr(0, 1) + "ma";
                        string b;
                        for (int j = 0; j <= i; ++j) {
                                b += 'a';
                        }
                        res[i] += b;
                }
                string ans;
                for (int i = 0; i < (int)res.size(); ++i) {
                        ans += res[i] + ' ';
                }
                ans.pop_back();
                return ans;
        }
private:
        const unordered_set <char> ref = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
};

int main() {
        string s = "I speak Goat Latin";
        Solution m;
        cout << "The coverted Latin is:" << endl;
        cout << m.string_to_goat_latin(s) << endl;
        return 0;
}

Battleship题

一个N*N的grid, 里面battleship是一个横着或者竖着的一条线（三个格子）， 要找到battleship的坐标 可以每次隔3个格子 按行扫、按列扫，输出坐标需要输出battleship的三个格子的各自坐标...

实在一个square里面找battership的位置，battership会连续占据三个的位置，或是横着或是竖着。 里面会有一个给定函数来判断给定位置是不是有船，最后要求输出battership占据三个位置的坐标。
Battleship game: write a function that finds a ship and return its coordinates.

思路: 首先判断前后左右，如果是有船，就添加。其次再扫描3 * 3 格，找到所有的坐标

参照 http://www.1point3acres.com/bbs/thread-318820-1-1.html

写的c++实现

您好！
本帖隐藏的内容需要积分高于 10 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 10 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

面试题： 用C++ 实现 tail -n file (没考虑大文件，等到时候写一个大文件的版本)

#include <iostream>
#include <fstream>
#include <string>
#include <stack>

using namespace std;

class showtail {
public:
        void tail(ifstream &tmp, int count) {
                stack <string> res;
                string out;
                while (getline(tmp, out)) {
                        res.push(out);
                }
                while (!res.empty() && count > 0) {
                        string t = res.top();
                        res.pop();
                        cout << t << '\n';
                        count--;
                }
        }

};

int main(int argc, char **argv) {
         if(argc != 3){
          cout <<"Usage:Please enter the value like ./tail -n file" <<endl;
          exit(0);
        }
        string n1 = argv[1];
        if (n1[0] != '-' || n1[1] < '0' || n1[1] > '9') {
                cout <<"Invalided line number, Please enter a valid number" << endl;
                exit(1);
        }
        string n2 = argv[2];
        ifstream ss(argv[2]);
        if (!ss) {
                cout << "Could not open a file, the target file does not exist" <<endl;
                exit(2);
        }
        int n = stoi(n1.substr(1));
        showtail m;
        m.tail(ss, n);
        return 0;
}

厉害啊。。。。。。。

friendlybo 发表于 2018-3-10 23:49
Battleship题

一个N*N的grid, 里面battleship是一个横着或者竖着的一条线（三个格子）， 要找到battles ...

这个是不是只要往右或者往下数就够了? 从上到下，从左到右遍历的话，往上或者往左数重复了。DFS？