问题传送门：https://leetcode.cn/problems/gas-station/description/



常规思路是暴力解法，以每一个点作为起点检索，在路上如果某一个点的油箱容量为负，说明到不了， 直接break到下一个点，直到所有的点都被遍历过。**思路是没问题，就是会超时。**

```C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int length = gas.size();
        vector<int> result(length, 0);
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                int index = (i + j) % length;
                result[i] += gas[index] - cost[index];
                if (result[i] < 0) {
                    break;
                }
            }
            if (result[i] >= 0) {
                return i;
            }
        }
        return -1;
    }
};
```

换一种思维方式：

- 相关变量：`total_tank`。如果从0到n点，它所有的油箱总所得，和所有的油箱总支出的差值是负数，那么说明油量不能够支持完成环形遍历，需要返回-1。如果为正数，则一定存在符合条件的点。题目另外也规定了**该点只有一个**。
- 相关变量：`curr_tank`。这个值用于模拟当前油箱的剩余油量，当它小于0的时候，说明当前的点无法到达。
- 相关变量：`start_station`。这个值用于记录当前的起点，并与`i`进行运行模拟。

算法思想是：
1. 初始化各个值，将起点设定为0.
2. `total_tank`记录总的油量数据。
3. `curr_tank`用于记录从`start_station`到`i`的过程中，油箱油量的变化。如果它变为负数，则证明：从`start_station`到`i-1`中的这个区间内的任意一点，都不能到达点`i`。
> 原因很简单：从`start_station`到它的下一站，是有可能有大于0的余油的；但是如果从`start_station+1`开始往`i`走，那么起始油量一定是0。有余油都跑不到`i`，更别提从0开始了。所以中间的所有点会被直接忽略掉。
4. 再次将起始点`start_station`记录为`i+1`，并将`curr_tank`置空，以重新模拟。
5. 最终判定，如果`total_tank`不为负数，说明存在点能够完成，并且最后一定是`start_station`符合条件。如果为负数，返回`-1`。

```C++
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total_tank = 0;
        int curr_tank = 0;
        int start_station = 0;
        
        for (int i = 0; i < gas.size(); i++) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            if (curr_tank < 0) {
                // Set Next Station as Start
                // Reset tank info
                start_station = i + 1;
                curr_tank = 0;
            }
        }
        
        return total_tank >= 0 ? start_station : -1;
    }
};
```

Leetcode 134. 加油站

COMP9517 Week 3 Feature Representation Part 2

COMP9517 Week 3 Feature Representation Part 1

COMP9517 Week 2 Image Processing Part 1

第一周的第二节课，讲述了CPP的一些基本用法。



# auto关键字

auto关键字允许编译器静态分析推断该类型，而不需要显式声明。

```cpp
int main()
{
    auto i = 0; // i is an int
    auto j = 8.5; // j is a double
    auto k = false; // k is a bool
    (void)i;
    (void)j;
    (void)k;
}
```

# const关键字

- const表示了无法被修改的一个变量
- 除非你知道它会被修改，不然任何变量都应当是const的
- 书写的规范是，const写在类型关键字的右侧

```cpp
int main()
{
    // `int` for integers.
    auto const meaning_of_life = 42;

    // `double` for rational numbers.
    auto const six_feet_in_metres = 1.8288;

    (void)meaning_of_life;
    (void)six_feet_in_metres;

    // meaning_of_life++; // COMPILE ERROR HERE
}
```

使用const关键字有以下几个原因：

- 更清晰的代码(你可以知道一个函数的只读权限)
- 不可变的对象更易被推理
- 编译器可以为不可变对象做优化
- 不可变对象在多线程环境中更有优势

# 类型转换

## 隐式类型转换

```cpp
#include <catch2/catch.hpp>

TEST_CASE()
{
    auto const i = 0;
    {
        auto d = 0.0;
        REQUIRE(d == 0.0);

        d = i; // Silent conversion from int to double
        CHECK(d == 42.0);
        CHECK(d != 41);
    }
}
```

当将int类型的i赋值给double类型的d时，发生了隐式类型转换。i的值为0，在赋值过程中被转换为double类型的0.0。

CHECK(d == 42.0)：由于i的值为0，因此在隐式转换后d的值也应该是0.0，而不是42.0。这一行断言会失败。

同样的，CHECK(d != 41);这一行断言也会失败，因为d的值是0.0，与41不相等。

## 显式类型转换

```cpp
#include <catch2/catch.hpp>

TEST_CASE()
{
    auto const i = 0;
    {
        // Preferred over implicit, since your intention is clear
        auto const d = static_cast<double>(i);
        CHECK(d == 42.0);
        CHECK(d != 41);
    }
}
```

# 函数

## 定义

两种定义法都可以，更推荐使用现代语法。

```cpp
#include <iostream>

auto main() -> int
{
    // put "Hello world\n" to the character output
    std::cout << "Hello, world!\n";
}
```
```cpp
#include <iostream>

int main() {
  // put "Hello world\n" to the character output
  std::cout << "Hello, world!\n";
}
```

## 参数

- 默认参数：函数可以使用默认参数，如果函数调用时没有指定实际参数，则使用默认参数。
- 默认值的位置：默认值用于函数调用中未指定的尾部参数，这意味着参数的顺序很重要。

```cpp
#include <string>

std::string rgb(short r = 0, short g = 0, short b = 0)
{
    (void)r;
    (void)g;
    (void)b;
    return "";
}

int main()
{
    rgb(); // rgb(0, 0, 0);
    rgb(100); // Rgb(100, 0, 0);
    rgb(100, 200); // Rgb(100, 200, 0)
    // rgb(100, , 200);   // error
}
```

## 重载

函数重载是指在同一作用域内，具有相同函数名但参数不同的一组函数。这种技术可以使代码更容易编写和理解。

注意：

- 函数匹配错误：函数匹配中的错误会在编译时被发现。
- 忽略返回类型：在函数匹配过程中，返回类型被忽略，仅根据参数进行匹配。

建议：

- 在编写代码时，建议仅创建简单的函数的重载

```cpp
#include <catch2/catch.hpp>

auto square(int const x) -> int
{
    return x * x;
}

auto square(double const x) -> double
{
    return x * x;
}

TEST_CASE()
{

    CHECK(square(2) == 4);
    CHECK(square(2.0) == 4.0);
    CHECK(square(2.0) != 4);
}
```

# 引用

- 我们可以像在C语言中那样在C++中使用指针，但通常我们不希望这样做。
- 引用是另一个对象的别名：你可以像使用原始对象一样使用引用。

相似点：

- 都是指向另一个对象。

不同点：

- 不需要使用->来访问元素，直接使用.即可。
- 不能为null。
- 一旦设置了引用，就不能更改其指向的对象。

```cpp
#include <catch2/catch.hpp>

TEST_CASE()
{
    auto i = 1;
    auto& j = i;
    j = 3;

    CHECK(i == 3);
}
```

## 常量引用

常量引用意味着你不能通过该引用修改对象。

但是，对象本身仍然可以被修改，只是不能通过这个常量引用进行修改。

```cpp
#include <iostream>

int main()
{
    auto i = 1;
    auto const& ref = i;
    std::cout << ref << '\n';
    i++; // This is fine
    std::cout << ref << '\n';
    // ref++; // This is not allowed

    auto const j = 1;
    auto const& jref = j; // this is allowed
    // auto& ref = j; // not allowed
    std::cout << jref << "\n";
}
```

# 函数参数传递方法

## 值传递

实际参数的值被复制到用于存储形式参数的内存中，在函数调用/执行期间使用。

这意味着在函数内部对参数的任何修改不会影响函数外部的实际参数。

```cpp
#include <iostream>

auto swap(int x, int y) -> void
{
    auto const tmp = x;
    x = y;
    y = tmp;
}

auto main() -> int
{
    auto i = 1;
    auto j = 2;
    std::cout << i << ' ' << j << '\n'; // prints 1 2
    swap(i, j);
    std::cout << i << ' ' << j << '\n'; // prints 1 2... not swapped?
}
```

## 引用传递

形式参数仅作为实际参数的别名。每当方法/函数使用形式参数（用于读或写）时，它实际上是在使用实际参数。

优点：

减少内存开销
- 通过引用传递参数不会创建参数的副本，从而减少了内存的使用。这对于大型对象尤其重要。

提高性能
- 因为没有创建参数副本的开销，所以通过引用传递参数可以提高函数调用的性能。

修改原始数据
- 通过引用传递参数，函数可以直接修改实际参数的值，这对于需要在函数内部修改外部变量的情况非常有用。

```cpp
#include <iostream>

auto swap(int& x, int& y) -> void
{
    auto const tmp = x;
    x = y;
    y = tmp;
}

auto main() -> int
{
    auto i = 1;
    auto j = 2;
    std::cout << i << ' ' << j << '\n'; // 1 2
    swap(i, j);
    std::cout << i << ' ' << j << '\n'; // 2 1
}
```

## 性能比较

```cpp
/*auto by_value(std::string const sentence) -> char;
// takes ~153.67 ns
by_value(two_kb_string);

auto by_reference(std::string const& sentence) -> char;
// takes ~8.33 ns
by_reference(two_kb_string);

auto by_value(std::vector<std::string> const long_strings) -> char;
// takes ~2'920 ns
by_value(sixteen_two_kb_strings);

auto by_reference(std::vector<std::string> const& long_strings) -> char;
// takes ~13 ns
by_reference(sixteen_two_kb_strings);*/
```

# 声明与定义

声明：

- 声明使变量的类型和名称变得已知。
- 声明不分配存储空间，也不构造变量。
- 你可以通过声明调用函数，但必须在之后提供定义。

定义：

- 定义是一个声明，但它还做了额外的事情：
    - 变量定义分配存储空间并构造变量。
    - 类定义允许你创建类类型的变量。
    - 函数定义提供函数的实现。
- 每个变量或函数必须有且只有一个定义。

```cpp
#include <catch2/catch.hpp>

// 函数声明
void declared_fn(int arg);

// 类声明
class declared_type;

// 这个类是定义的，但不是所有的方法都被定义了。
class defined_type {
    int declared_member_fn(double);
    int defined_member_fn(int arg) { return arg; }
};

// 函数定义
int defined_fn(int arg)
{
    (void)arg;
    return 1;
}

TEST_CASE()
{
    int i;
    int const j = 1;
    auto vd = std::vector<double> {};
    (void)i;
    (void)j;
    (void)vd;
}
```

# 程序错误

一般有以下几种错误：

## 编译时错误 Compile-time Errors

编译时错误是在源代码编译过程中由编译器检测到的错误。常见的编译时错误包括：
- 语法错误
- 类型错误
- 声明/定义不匹配

## 链接时错误 Link-time Errors

链接时错误是在编译器生成目标文件后，由链接器在试图将多个目标文件链接成一个可执行文件时检测到的错误。常见的链接时错误包括：

- 未定义符号
- 重复定义

## 运行时错误 Run-time Errors

运行时错误是在程序运行过程中发生的错误。常见的运行时错误包括：

- 空指针引用
- 数组越界
- 除0错误

## 逻辑错误 Logic Errorss

逻辑错误是程序在运行时不会产生错误信息，但程序的输出结果不符合预期。这类错误通常是由于编程逻辑不正确引起的，需要通过调试和测试来发现和修正。

- 算法错误
- 错误的条件判断

# 文件io

```cpp
#include <fstream>
#include <iostream>

int main()
{
    // Below line only works C++17
    std::ofstream fout { "data.out" };
    if (auto in = std::ifstream { "data.in" }; in) { // attempts to open file, checks it was opened
        for (auto i = 0; in >> i;) { // reads in
            std::cout << i << '\n';
            fout << i;
        }
        if (in.bad()) {
            std::cerr << "unrecoverable error (e.g. disk disconnected?)\n";
        } else if (not in.eof()) {
            std::cerr << "bad input: didn't read an int\n";
        }
    } // closes file automatically <-- no need to close manually!
    else {
        std::cerr << "unable to read data.in\n";
    }
    fout.close();
}
```