算法题:找到它

发表于 2020-11-29 更新于 2025-06-12
本文字数： 3.1k 阅读时长 ≈ 3 分钟

算法题: 找到它

标题: 找到它

题描述

找到它是一个小游戏,你需要在一个矩阵中找到给定的单词。假定给定的单词是HELLOWORLD,在矩阵中只需要找到H->E->L->L->O->W->O->R->L->D连成的单词,就算通过。
注意区分英文字母大小写, 并且只能上下左右行走，不可以回头

输入描述

输入第一行包含两个整数rows,cols(0 < rows,cols < 21)分别表示矩阵的行数rows和列数cols.
第二行是一个长度不超过100的单词，在给定的矩阵中，整个单词只会出现一次，从第三行到第rows + 2行是包含大小写英文字母的长度为cols的字符矩阵

输出描述

如果能在矩阵中找到对应的单词, 输入所在对应单词第一个字母所在的行和列，否则输出NO

测试示例

输入:

5 5
HELLOWORLD
CPUCY
EKLQH
CHELL
LROWO
DGRBC

输出

3 2

解题思路

首先想到使用回溯法
遍历矩阵元素,找到单词第一个字母所在位置, 标记该位置被占用, 并从该位置开始检验是否能找到对应的单词,找到则返回行和列的索引
检验时, 依次检验当前位置的左上右下等位置的flag值,flag未标记时判断该位置的字母是否和目标单词当前索引的下一个位置的字母相等, 相等则标记该位置的flag为占用状态并以该位置进行下一轮递归检验, 直到单词下一个索引的字符变为’\0’，检验不通过时,将对应位置的flag回溯为false

示例代码


#include <vector>
#include <iostream>


struct Matrix {
    Matrix(int rows, int cols): m_rows(rows), m_flags(rows) {
        for(auto& row: m_rows) {
            row.resize(cols);
        }

        for(auto& row: m_flags) {
            row.resize(cols);
        }
    }

    bool find(const char *target, int& row, int& col) {


        for (auto i = 0; i < m_rows.size(); ++i) {
            for (auto j = 0; j < m_rows[i].size(); ++j) {
                if (m_rows[i][j] == *target) {
                    m_flags[i][j] = true;
                    if (check(target, i, j)) {
                        row = i;
                        col = j;
                        return true;
                    }
                    m_flags[i][j] = false;
                }
            }
        }


        return false;
    }

    bool check(const char *target, int row, int col) {

        if (target and *target != '\0' and target[1] != '\0') {

            if (0 < row and not m_flags[row - 1][col] and m_rows[row - 1][col] == target[1]) {
                m_flags[row - 1][col] = true;
                if (check(target + 1, row - 1, col)) {
                    return true;
                }
                m_flags[row - 1][col] = false;
            }

            if (0 < col and not m_flags[row][col - 1] and m_rows[row][col - 1] == target[1]) {
                m_flags[row][col - 1] = true;
                if (check(target + 1, row, col - 1)) {
                    return true;
                }
                m_flags[row][col - 1] = false;
            }

            if (row < m_rows.size() - 1 and not m_flags[row + 1][col] and m_rows[row + 1][col] == target[1]) {
                m_flags[row + 1][col] = true;
                if (check(target + 1, row + 1, col)) {
                    return true;
                }
                m_flags[row + 1][col] = false;
            }

            if (col < m_rows[row].size() - 1 and not m_flags[row][col + 1] and m_rows[row][col + 1] == target[1]) {
                m_flags[row ][col + 1] = true;
                if (check(target + 1, row, col + 1)) {
                    return true;
                }
                m_flags[row][col + 1] = false;
            }

            return false;

        }
        return true;
    }

    template<typename InputStream>
    InputStream& input(InputStream& in) {

        for(auto i = 0; i < m_rows.size(); ++i) {
            std::string line;
            in >> line;
            m_rows[i].assign(line.begin(), line.end());
        }

        return in;
    }


private:
    std::vector<std::vector<char>> m_rows;
    std::vector<std::vector<bool>> m_flags;
};

template<typename InputStream>
InputStream& operator>>(InputStream& in, Matrix& m) {
    return m.input(in);
}



int main() {

    int row, col;
    std::string target;

    std::cin >> row >> col >> target;

    Matrix m(row, col);

    std::cin >> m;


    if (m.find(target.c_str(), row, col)) {
        std::cout << row + 1 << ' ' << col + 1 << std::endl;
    } else {
        std::cout << "NO" << std::endl;
    }

    return 0;
}

CGO中处理C中的回调函数

发表于 2020-09-24 更新于 2025-06-12
本文字数： 1.9k 阅读时长 ≈ 2 分钟

CGO中处理C中的回调函数

假设有以下 C语言的接口

api.h

#ifndef API_H
#define API_H

#ifdef __cplusplus
extern "C" {
#endif

typedef void (*IntCallback)(void *, int);

void SetIntCallback(IntCallback cb, void *data);

void DoIntCallback(int value);

#ifdef __cplusplus
}
#endif
#endif

此时如果我们想要通过CGO来将上述的两个(尤其是设置回调函数的SetIntCallback)导入到golang中来使用，该怎么做呢？

思考

C语言中的void *与 GO中的什么类型对应呢？
C语言中的函数指针与GO中的函数怎么对应呢？

思考结果如下

C语言中的 void *和 Go中的unsafe.Pointer对应
C语言中的函数和 Go中的函数可以通过 //export NAME的方式来建立对应关系

实际操作

1. 先在`CGO`中声明一下回调函数需要用到的`C函数`

package main

/*
#include "api.h"
extern void cgoCall(void *, int); // 这里与api.h中的IntCallback保持类型一致
*/
import "C"

2. 在`Golang`中通过 `//export`方式实现上述的`C函数`

//此处省略上述重复代码

//export cgoCall
func cgoCall(p unsafe.Pointer, number C.int) {
	// TODO: 这里先留空，我们还没确定传进来的 p是什么具体类型
}

3. 在`Golang`中定义一个`interface`来接收上面的函数里的`C.int`类型的参数

//此处省略上述重复代码

type Caller interface {
	Call(int)
}

此时我们可以将Caller类型作为步骤2中的p传进去作为参数了

4. 在完善一下`步骤2`中的`cgoCall`

//此处省略上述重复代码

//export cgoCall
func cgoCall(p unsafe.Pointer, number C.int) {
	caller := *(*Caller)(p)
	caller.Call(int(number))
}

说明:
我们在这里将p参数转化为一个 Caller的interface类型，再调用 Caller类型的Call(int)函数。表明我们在调用 C语言中的SetIntCallback时， data参数给的是一个 Caller类型的指针

5. 定义一个具体的类型实现 Caller接口测试一下

//此处省略上述重复代码

type OneCaller struct {}
type AnotherCaller struct {}

func (o OneCaller) Call(value int) {
	println("one:", value)
}

func (o AnotherCaller) Call(value int) {
	println("another:", value)
}

func SetCallback(caller Caller) {
	C.SetIntCallback(C.IntCallback(C.cgoCall), unsafe.Pointer(&caller))
}

func DoCallback(value int) {
	C.DoIntCallback(C.int(value))
} 

func main() {
	one := OneCaller {}

	SetCallback(one)	
	DoCallback(1234)
	another := AnotherCaller {}
	
	SetCallback(another)	
	DoCallback(5678)
}

完整的运行测试一下，发现可以输出：

1 2	one: 1234 another: 5678

总结

为了使用C语言中的回调函数, 我们使用到了以下技术来实现

unsafe.Pointer：将Go中的指针传入到C语言中的 void *
//export XXX: 在GO 中实现 C语言中声明的函数
通过interface技术将 C语言中的回调函数类型绑定实现了多态或泛型

CGO 中对C语言的void *和void **的处理

发表于 2020-09-24 更新于 2025-06-12
本文字数： 1.3k 阅读时长 ≈ 1 分钟

CGO 中对C语言的`void *`和`void **`的处理

1. `void *`与`unsafe.Pointer`

CGO中的 unsafe.Pointer与C语言中的 void *是对应的
Go中的结构体如果要传入 C语言的某个函数作为参数, 可以使用 unsafe.Pointer来转化

package main

/*

//假设这段定义在外部C源码中对cgo不可见
//typedef struct User {
//	int id;
//	int age;
//	int number;
//} User;



static void User_SetId(void *user, int id) {
	((User *)user)->id = id;
}

static void User_SetAge(void *user, int age) {
	((User *)user)->age = age;
}

static void User_SetNumber(void *user, int number) {
	((User *)user)->number = number;
}
*/
import "C"

import (
	"fmt"
	"unsafe"
)

type User struct {
	Id int32
	Age int32
	Number int32
}

func main() {
	var user User

	pointer := unsafe.Pointer(&user)

	C.User_SetId(pointer, C.int(1))
	C.User_setAge(pointer, C.int(25))
	C.User_setNumber(pointer, C.int(10001))

	fmt.Println(user)	

}

2. 对应的 `void **`只需要在现有的 `void *`类型(CGO中的`unsafe.Pointer`)的对象上取地址就可以了

package main
/*
typedef struct User {
	int id;
	int age;
	int number;
} User;
static void createUser(void **pUser) {
	if(pUser) *pUser = malloc(sizeof(User))
}


*/
import "C"

import (
	"fmt"
	"unsafe"
)

type User C.User

func main() {

	pointer := unsafe.Pointer(nil)

	C.createUser(&pointer)

	user := (*User)(pointer)

	fmt.Println(user)
}

CGO中的一些使用注意事项

发表于 2020-09-24 更新于 2025-06-12
本文字数： 1.4k 阅读时长 ≈ 1 分钟

CGO中的一些使用注意事项

1. CGO中的内容必须紧挨着`import "C"`, 中间不得有其他`import`

错误示范

package main

// #include <stdio.h>
import "fmt"
import "C"

func main() {
 fmt.Println(C.puts(C.CString("这是一个golang字符串")))
}

应该改为

package main

// #include <stdio.h>
import "C"
import "fmt"

func main() {
 fmt.Println(C.puts(C.CString("这是一个golang字符串")))
}

2. import “C”前面的注释与import “C”之间不得有空行

错误示范

package main

// #include <stdio.h>

import "C"
import "fmt"

func main() {
 fmt.Println(C.puts(C.CString("这是一个golang字符串")))
}

正确应为

package main

// #include <stdio.h>
import "C"
import "fmt"

func main() {
 fmt.Println(C.puts(C.CString("这是一个golang字符串")))
}

3. go中无法直接使用C语言头文件中的 `enum`,`struct`和`union`, 需要使用时，需要对相关的类型进行 `typedef`重定义

错误示范

package main

/*
enum CEnum {
 zero,
 one,
 two,
 three
};
struct CStruct {
 int number;
};
*/
import "C"

func main() {
 var cenum C.CEnum = C.zero
 var cstruct C.CStruct
 fmt.Println(cenum, cstruct.number)
}

正确应为

package main
/*
typedef enum CEnum {
	zero,
	one,
	two,
	three
} CEnum;
typedef struct CStruct {
	int number;
} CStruct;
*/
import "C"

func main() {
	var cenum C.CEnum = C.zero
	var cstruct C.CStruct
	fmt.Println(cenum, cstruct.number)
}

4. C中的union在CGO里面表现为`[N]byte`类型(其中N为该union类型占用的最大字节数)

package main

/*
typedef union Val {
	int i;
	float f;
	double d;
} Val;
*/
import "C"

func main() {
	var value = C.Val {100}
	println(len(value), value[0]) // 8 100
}

C++小技巧: 集合(vector, list, map, set)的反向遍历

发表于 2020-09-24 更新于 2025-06-12
本文字数： 3.2k 阅读时长 ≈ 3 分钟

一般的正向集合遍历

for/index/size模式

1
2
3

for(int i = 0; i < collection.size(); ++i) {
 std::cout << collection[i] << std::endl;
}

弊端: 只适合std::vector这种可以通过下标随机O(1)时间访问的集合类型

for/begin/end 模式

for(auto it = collection.begin(); it != collection.end(); ++it) {
 std::cout << *it << std::endl;
 // std::cout << it->first << ", " << it->second << std::endl;
}

这种适合大多数的集合遍历模式

for/in 模式(`for/begin/end`模式的精简版)

for(auto& item: collection) {
 std::cout << item << std::endl;
 // std::cout << item.first << ", " << item.second << std::endl;
}

这种写法属于C++11开始出现的语法糖，只要集合(包括标准库的集合和用户自定义的集合甚至伪集合)能使用for/begin/end模式的遍历方式就能使用这种语法糖模式

如果想反向遍历怎么办

可能的思路

将集合先反转再遍历：可能集合被限制为常量不可反转自身，受限
将集合反向拷贝再遍历: 集合数量比较庞大时，会占用大量内存，慎用
反向迭代器(rbegin+rend): 我觉得可以，推荐

反向迭代器

示例代码:

for(auto it = collection.rbegin(); it != collection.rend(); ++it) {
 std::cout << *it << std::endl;
 // std::cout << it->first << ", " << it->second << std::endl;
}

其实用法和for/begin/end模式几乎一样，只是需要使用rbegin和rend来代替begin和end, rbegin()表示反向迭代器的开始, 也就是正向的末尾, rend()表示反向迭代器的末尾也就是正向迭代器的开始

能不能使用语法糖

直接使用当然不行，但并不表示我们不能使用

回想下上面的一句很关键的话: 只要集合(包括标准库的集合和用户自定义的集合甚至伪集合)能使用(for/begin/end模式)的遍历方式就能使用这种语法糖模式

解决方案

把当前集合rbegin和rend接口调用转换成另外一个对象的 begin()和end()接口调用，并且返回的迭代器是不变的

具体实现

示例代码

namespace oyoung {
    template<typename T>
    struct CollectionReverse {

        using iterator = typename T::reverse_iterator;
        using const_iterator = typename T::const_reverse_iterator;

        explicit CollectionReverse(T& col)
            : _M_collection(col) {}

        iterator begin() {
            return _M_collection.rbegin();
        }

        const_iterator begin() const {
            return _M_collection.rbegin();
        }

        iterator end() {
            return _M_collection.rend();
        }

        const_iterator end() const {
            return _M_collection.rend();
        }

    private:
        T & _M_collection;
    };

    template<typename T>
    CollectionReverse<T> reverse(T& col) {
        return CollectionReverse<T>(col);
    }
}

如何使用呢?

#include <map>
#include <set>
#include <list>
#include <vector>

#include <iostream>

int main(int argc, const char * argv[]) {


    std::vector<int> vi {0,1, 2, 3, 4, 5};

    std::list<int> li {10, 11, 12, 12, 14, 15};

    std::map<int, int> mii {
        {0, 10}, {1, 11}, {2, 12}, {3, 13}, {4,14}, {5,15}
    };

    std::set<int> si {0, 1, 2, 3, 4, 4, 5, 5};

    std::cout << "reversed vector: ";
    for(auto i: oyoung::reverse(vi)) {
        std::cout << i << ' ';
    }

    std::cout << std::endl;
    std::cout << "reversed list: ";
    for(auto i: oyoung::reverse(li)) {
        std::cout << i << ' ';
    }
    std::cout << std::endl;
    std::cout << "reversed map: ";
    for(auto pair: oyoung::reverse(mii)) {
        std::cout << '(' << pair.first << ": " << pair.second << "),";
    }
    std::cout << std::endl;
    std::cout << "reversed set: ";
    for(auto i: oyoung::reverse(si)) {
        std::cout << i << ' ';
    }
    std::cout << std::endl;
    return 0;
}

输出结果对不对呢？ 😉

reversed vector: 5 4 3 2 1 0
reversed list: 15 14 12 12 11 10
reversed map: (5: 15),(4: 14),(3: 13),(2: 12),(1: 11),(0: 10),
reversed set: 5 4 3 2 1 0

算法题: 找到它

标题: 找到它

题描述

输入描述

输出描述

测试示例

解题思路

示例代码

CGO中处理C中的回调函数

假设有以下 C语言的接口

思考

思考结果如下

实际操作

1. 先在CGO中声明一下回调函数需要用到的C函数

2. 在Golang中通过 //export方式实现上述的C函数

3. 在Golang中定义一个interface来接收上面的函数里的C.int类型的参数

4. 在完善一下步骤2中的cgoCall

5. 定义一个具体的类型实现 Caller接口测试一下

总结

CGO 中对C语言的void *和void **的处理

1. void *与unsafe.Pointer

2. 对应的 void **只需要在现有的 void *类型(CGO中的unsafe.Pointer)的对象上取地址就可以了

CGO中的一些使用注意事项

1. CGO中的内容必须紧挨着import "C", 中间不得有其他import

2. import “C”前面的注释与import “C”之间不得有空行

3. go中无法直接使用C语言头文件中的 enum,struct和union, 需要使用时，需要对相关的类型进行 typedef重定义

4. C中的union在CGO里面表现为[N]byte类型(其中N为该union类型占用的最大字节数)

一般的正向集合遍历

for/index/size模式

for/begin/end 模式

for/in 模式(for/begin/end模式的精简版)

如果想反向遍历怎么办

可能的思路

反向迭代器

能不能使用语法糖

解决方案

具体实现

示例代码

如何使用呢?

1. 先在`CGO`中声明一下回调函数需要用到的`C函数`

2. 在`Golang`中通过 `//export`方式实现上述的`C函数`

3. 在`Golang`中定义一个`interface`来接收上面的函数里的`C.int`类型的参数

4. 在完善一下`步骤2`中的`cgoCall`

CGO 中对C语言的`void *`和`void **`的处理

1. `void *`与`unsafe.Pointer`

2. 对应的 `void **`只需要在现有的 `void *`类型(CGO中的`unsafe.Pointer`)的对象上取地址就可以了

1. CGO中的内容必须紧挨着`import "C"`, 中间不得有其他`import`

3. go中无法直接使用C语言头文件中的 `enum`,`struct`和`union`, 需要使用时，需要对相关的类型进行 `typedef`重定义

4. C中的union在CGO里面表现为`[N]byte`类型(其中N为该union类型占用的最大字节数)

for/in 模式(`for/begin/end`模式的精简版)