# 华为诺亚方舟实验室-CodingTest

## Huawei - CodingTest

#### 01 - 编程题01

A为一个十进制整数，k位，k<100。求B使得B为大于A的最小整数，且A各位的和等于B各位的和。请给出函数实现，测试例，并说明解题思路。

***

**思路**：

首先，以暴力算法扫描的话时间复杂度过大，我们根据规律可以发现：

* 从A的倒数第二位开始，从后向前搜索，直到找到一个符合条件的位数`A[i]`，使其满足如下条件：
  * `A[i]`不等于9并且`A[i]`之后的所有位不全为`0`

这样，我们将满足以上要求的数据，按一下的策略进行修改：

* `A[i]`加1, 计算后面的所有位数之和记作`sum`， 并从最后一位向前，将位数和减去`9`并改为`9`
* 如果剩余无法补`9`则继续改为`sum` 若为0则补`0` 直到修改到`A[i]`

此外 还会有不满足以上要求的数字，则我们在开头先补上一个`1`，再按我们的规律进行修改；

**测试样例及对拍代码**：

对拍代码即暴力解 时间复杂度高 以此来验证代码的正确性;

**对拍代码（matcher.cpp)**：

```cpp
/*
 * @Description: 
 * @Versions: 
 * @Author: Vernon Cui
 * @Github: https://github.com/vernon97
 * @Date: 2021-03-26 18:48:04
 * @LastEditors: Vernon Cui
 * @LastEditTime: 2021-03-22 21:23:26
 * @FilePath: /Projects/matcher.cpp
 */

#include <cstdlib>
#include <ctime>
#include <iostream>
const int N = 100;
const std::string bf = "../bf.cpp";
const std::string algo = "../Example.cpp";

/*
封装一下 `system`，支持 ctrl + c 退出整个对拍程序
*/
int mySystem(const char* command) {
    int result = system(command);
    if (WIFEXITED(result)) {
        // printf("Exited normally with status %d\n", WEXITSTATUS(result));
    } else if (WIFSIGNALED(result)) {
        printf("Exited with signal %d\n", WTERMSIG(result));
        exit(1);
    } else {
        printf("Not sure how we exited.\n");
    }
    return result;
}

int main() {
    mySystem("g++ ../random.cpp -o random.out");
    mySystem(
        ("g++ -std=c++11 -o bf.out " + bf).c_str());
    mySystem(
        ("g++ -std=c++11 -o algo.out " + algo).c_str());
    for (int T = 1; T <= N; T++) {
        // 生成随机数据
        mySystem("./random.out > data.in");
        // 记录运行的 CPU 时间
        double st = clock();
        // 暴力解法输出正确答案
        mySystem("./bf.out < data.in > data.ans");
        double ed = clock();
        // 优化解法输出待检查答案
        mySystem("./algo.out < data.in > data.out");
        // return 0;
        if (mySystem("diff data.out data.ans")) {
            puts("\033[1;31mWrong Answer\033[0m");
            puts("\033[1;31m-----错误数据-------\033[0m");
            printf("输入: \n");
            mySystem("cat data.in");
            return -1;
        } else {
            printf("\033[1;32mAccepted\033[0m, 测试点 #%d, 用时 %.01f\n", T, ed - st);
        }
    }
    return 0;
}
```

**随机测试样例生成代码（random.cpp)**:

```cpp
/*
 * @Description: 
 * @Versions: 
 * @Author: Vernon Cui
 * @Github: https://github.com/vernon97
 * @Date: 2021-03-22 20:49:05
 * @LastEditors: Vernon Cui
 * @LastEditTime: 2021-03-29 19:12:58
 * @FilePath: /Projects/random.cpp
 */

#include <iostream>
#include <cstdlib>
#include <string>
#include <sstream>
#include <time.h>
#include "sys/timeb.h"

using namespace std;

int main()
{
    struct timeb timeSeed;
    ftime(&timeSeed);
    srand(timeSeed.time * 1000 + timeSeed.millitm);  // milli time
    // 产生[a,b)的随机数，可以使用 (rand() % (b-a))+a;
    // 产生[a,b]的随机数，可以使用 (rand() % (b-a+1))+a;
    // 产生(a,b]的随机数，可以使用 (rand() % (b-a))+a+1;
    int n = (rand() % (21 - 1 + 1)) + 1; // 避免前导零
    stringstream ss;
    ss << (rand() % (10 - 0 + 1)) + 1;
    for(int i = 0; i < n; i++)
        ss << (rand() % (10 - 0 + 1)) + 0;
    cout << ss.str() << endl;
    return 0;
}
```

**暴力算法（bf.cpp)**:

```cpp
/*
 * @Description: 
 * @Versions: 
 * @Author: Vernon Cui
 * @Github: https://github.com/vernon97
 * @Date: 2021-03-22 20:48:38
 * @LastEditors: Vernon Cui
 * @LastEditTime: 2021-03-29 18:54:47
 * @FilePath: /Projects/bf.cpp
 */
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
using ULL = unsigned long long;
const int N = 20;

int n;
int fact[N];

int sumA(ULL A)
{
    int sum = 0;
    while(A)
    {
        sum += A % 10;
        A /= 10;
    }
    return sum;
}
ULL findB(ULL A)
{
    for(ULL i = A + 1; i < ULLONG_MAX; i++)
        if(sumA(i) == sumA(A)) return i;
}
int main()
{
    ULL A;
    cin >> A;
    cout << findB(A) << endl;
    return 0;
}
```

**代码（Example.cpp)**：

```cpp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

vector<int> num;
string tmp;

int main() {
    stringstream ss;
    cin >> tmp;
    // 1. 高精度按位存
    for (int i = 0; i < tmp.size(); i++)
    {
        num.push_back(tmp[i] - '0');
    }

    if (num.size() == 1)
    {
        std::cout << num[0] + 9;
        return 0;
    }
    // 2. 倒序查找
    int r = num.size() - 1;
    int curSum = 0;
    
    while (curSum == 0 || num[r] == 9)
    {
        if (r == -1) break;
        r--;
        curSum += num[r + 1];
    }
    // 3. 处理输出
    if (r >= 0) {
        for (int i = 0; i < r; i++) 
            ss << num[i];
        ss << num[r] + 1;

        curSum--;
        int nine_num = static_cast<int>(curSum) / 9;
        int num_mod = curSum % 9;
        for (int i = r; i < num.size() - 1 - nine_num - 1; i++)
            ss << 0;
        ss << num_mod;
        for (int i = 0; i < nine_num; i++) 
            ss<< 9;
    } else 
    {
        ss << "1";
        curSum--;
        int nine_num = static_cast<int>(curSum) / 9;
        int num_mod = curSum % 9;
        r = 0;
        for (int i = r; i < static_cast<int>(num.size()) - nine_num - 1; i++)
            ss << 0;
        ss << num_mod;
        for (int i = 0; i < nine_num; i++)
            ss << 9;
    }
    cout << ss.str() << endl;
    return 0;
}
```

***

**测试样例：**

以下测试样例为自动生成, 分别为A和B

```
1023950553073
1023950553082
Accepted, 测试点 #1, 用时 491.0
11410238899918
11410238899927
Accepted, 测试点 #2, 用时 502.0
16099
16189
Accepted, 测试点 #3, 用时 628.0
27617
27626
Accepted, 测试点 #4, 用时 488.0
2021071096708
2021071096717
Accepted, 测试点 #5, 用时 722.0
50893
50929
Accepted, 测试点 #6, 用时 614.0
```

#### 02 - 编程题02

已知有如下二维离散点：（3.1,1）（4,1.9）（4,4）（6,2.1）（9,7）（9.6,3）（11,2）（12.2,4）（14,2）（18,6），提取其中近似在一条直线上的离散点集群（要求该集群要包含最多的离散点，集群中点到集群对应直线的距离小于0.3）。输出该离散点集群以及对应的直线（以两点表示），给出函数实现，输出结果并说明解题思路（避免使用封装好的库算法）

***

本题的思路是采用RANSAC来拟合直线；

RANSAC做的一件事就是先随机的选取一对点，用这些点去计算出一个直线，然后用此模型去测试剩余的点，不断重复此过程，直到找到选取的这些数据点集达到了可以接受的程度为止，此时得到的模型便可认为是对数据点的最优模型构建。 **答案：**

```
-5.16x + 14.98y + 0.21 = 0
```

```cpp
#include <math.h>
#include <fstream>
#include <iostream>
#include <vector>
#include <random>
#include <string>
#include <time.h>
#include "sys/timeb.h"
using namespace std;

const float PI  = 3.1415926;
const float MAXD = 0.30;
string filePath = "/Users/vernon/question/question2/sample.in";

int n;
vector<float> x, y;
int max_cnt;

int getNumPoints(float x1, float y1, float x2, float y2) {
  float a, b, c, dist;
  a = y1 - y2;
  b = x2 - x1;
  c = y2 * x1 - x2 * y1;

  float ab = sqrt(a * a + b * b);
  int cnt = 0;
  for (int i = 0; i < n; i++) {
    dist = abs(a * x[i] + b * y[i] + c) / ab;
    if (dist < MAXD) cnt++;
  }
  return cnt;
}

int main() {
  FILE *fin = fopen(filePath.c_str(), "r");
  struct timeb timeSeed;
  ftime(&timeSeed);
  srand(timeSeed.time * 1000 + timeSeed.millitm);  // milli time
  n = 10;
  x.resize(n, 0);
  y.resize(n, 0);
  // 1. 读取每一个点的坐标
  for (int i = 0; i < n; i++)
  {
    float cur_x, cur_y;
    fscanf(fin, "%f %f", &cur_x, &cur_y);
    x[i] = cur_x;
    y[i] = cur_y;
  }

  vector<vector<float>> res_pairs;
  float x1, y1, x2, y2;
  int idx1, idx2, cnt;
  float r, theta;
  // 2. Ransac 迭代过程
  for (int i = 0; i < 100000; i++)
  {
    idx1 = random() % 10;
    do
      idx2 = random() % 10;
    while (idx2 == idx1);

    r = (random() % 300000) / 1000000.0;
    theta = (random() % 360000000) / 1000000.0;
    theta = theta * PI / 180.;
    x1 = x[idx1] + r * cos(theta);
    y1 = y[idx1] + r * sin(theta);

    r = (random() % 300000) / 1000000.0;
    theta = (random() % 361000000) / 1000000.0;
    theta = theta * PI / 180.0;
    x2 = x[idx2] + r * cos(theta);
    y2 = y[idx2] + r * sin(theta);
    cnt = getNumPoints(x1, y1, x2, y2);
    if (cnt > max_cnt) {
      max_cnt = cnt;
      res_pairs = {{x1, y1}, {x2, y2}};
    }
  }

  float a, b, c, dist;
  x1 = res_pairs[0][0];
  y1 = res_pairs[0][1];
  x2 = res_pairs[1][0];
  y2 = res_pairs[1][1];
  a = y1 - y2;
  b = x2 - x1;
  c = y2 * x1 - x2 * y1;
  
  // 输出最后的直线拟合方程
  string line = "直线拟合方程如下: %.2fx";
  if (b >= 0)
    line += " + %.2fy";
  else {
    line += " - %.2fy";
    b = -b;
  }
  if (c >= 0)
    line += " + %.2f";
  else {
    line += " - %.2f";
    c = -c;
  }
  line += " = 0\n";
  printf(line.c_str(), a, b, c);
  return 0;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://vernon97-io.gitbook.io/untitled/codingtests/hua-wei-nuo-ya-fang-zhou-shi-yan-shi-codingtest.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.