发表更新算法2 分钟读完 (大约362个字)

KY191 矩阵幂

算法内容

本文件实现牛客 KY191「矩阵幂」的一个基础版本。程序读取矩阵阶数 n 和幂次 k，再读取 n 阶矩阵并输出矩阵的 k 次幂。

mul 完成普通矩阵乘法，并把结果写回第一个矩阵；matPow 根据 pow 的取值执行固定次数的乘法。当前实现只显式处理 1 到 5 次幂，适合题目幂次范围较小或练习矩阵乘法流程的场景。矩阵乘法单次时间复杂度 O(n^3)。如果 k 更大，通常需要改为快速幂，将复杂度优化为 O(n^3 log k)。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<unordered_map>

using namespace std;

void mul(vector<vector<int>>& a, const vector<vector<int>> b, int n) {
    for(int i = 0; i < n; i++) {
        vector<int> ta;
        for(int j  = 0; j < n; j++) {
            int m = 0;
            for(int k = 0; k < n; k++) {
                m += a[i][k] * b[k][j];
            }
            ta.push_back(m);
        }
        a[i] = ta;
    }
}

void matPow(int n, vector<vector<int>>& res, const vector<vector<int>>& arr, int pow) {
    switch(pow) {
        case 1:
            break;
        case 2:
            mul(res, arr, n);
            break;
        case 3:
            mul(res, arr, n);
            mul(res, arr, n);
            break;
        case 4:
            mul(res, arr, n);
            mul(res, res, n);
            break;
        case 5:
            mul(res, arr, n);
            mul(res, res, n);
            mul(res, arr, n);
            break;
    }
}
int main() {
    int n, k;
    while(scanf("%d%d", &n, &k) != EOF){
        vector<vector<int>> arr(n, vector<int>(n, 0));
        vector<vector<int>> res(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int t;
                scanf("%d", &t);
                res[i][j] = t;
                arr[i][j] = t;
            }
        }
        matPow(n, res, arr, k);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n-1; j++) {
                printf("%d ", res[i][j]);
            }
            printf("%d\n", res[i][n-1]);
        }
        
    }
    return 0;
}


发表更新算法2 分钟读完 (大约270个字)

decltypetest

算法内容

本文件是 C++ decltype、引用折叠和数组形参退化的学习代码。

f 对比 decltype(++i)、decltype(i++) 和 decltype(&i) 的推导结果：前置自增表达式得到左值引用类型，后置自增表达式得到值类型，取地址得到指针类型。f1 观察数组作为函数参数时会退化为指针。f2 则通过左值引用、右值引用和 move 展示引用变量在 decltype 中的类型保持规则。这个文件重点不是算法题，而是验证 C++ 类型推导行为。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<iomanip>
using namespace std;


int i = 0;
void f(decltype(++i) a, decltype(i++) b, decltype(&i) c) {
    a++;
    b++;
    (*c)++;
}
int arr[5] = {0};
void f1(decltype(arr) a) {
    cout << ios::hex << a << " " << a+1 <<  endl;
}

int &j = i;
int &n = j;
int &&k = move(i);
int &&m  = move(k);
void f2(decltype(j) a, decltype(k) b, decltype(m) c, decltype(n) d) {
    a++;
    b++;
    c++;
    d++;
    cout << a << " " << b << " " << c << " " << d << endl;

}

int main() {
    int a = 0, b = 0,c = 0, d = 0;
    f(a, b, &c);
    cout << a << " " << b << " " << c <<  endl;
    int brr[6] = {0};
    f1(brr);
    f2(a,move(b),move(c),d);
    cout << a << " " << b << " " << c << " " << d << endl;
    return 0;
}
发表更新算法2 分钟读完 (大约323个字)

k-min 第 k 小元素查找

算法内容

本文件实现基于快速选择思想的第 k 小元素查找。输入阶段会先用布尔数组去重，再在去重后的数组中查找第 k 小值。

partition 使用类似快速排序的双指针划分，把基准元素放到最终位置；searchK 根据基准位置和目标下标 k 的关系，只递归进入包含目标的半边区间，而不是完整排序。平均时间复杂度为 O(n)，最坏情况下为 O(n^2)。代码中会打印每次划分后的数组和基准位置，方便观察快速选择过程。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int partition(vector<int>& v, int l, int r) {
    int i = l;
    while(l<r) {
        while(r > l && v[r] >= v[i]) {
            r--;
        }
        swap(v[i], v[r]);
        i = r;
        while(r > l && v[l] <= v[i]) {
            l++;
        }
        swap(v[i], v[l]);
        i = l;
    }
    return i;
}

void searchK(vector<int>& v, int k, int l, int r) {
    //partition
    int n = partition(v,l,r);
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl<< n;
    cout << endl;
    //search
    if(n > k) {
        searchK(v, k, l, n-1);
    } else if(n < k) {
        searchK(v, k, n+1, r);
    }
}
int main() {
    int n,k;
    cin >> n;
    vector<int> v;
    vector<bool> has(1001, false);
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if(!has[x]) {
            has[x] = true;
            v.push_back(x);
        }
    }
    cin >> k;
    k--;
    searchK(v, k, 0, v.size()-1);
    cout << v[k];
    return 0;
}
发表更新算法2 分钟读完 (大约303个字)

d-进制反转素数

算法内容

本文件实现素数判断和进制反转判断。程序持续读取 n 和进制 d，判断 n 是否为素数，以及 n 在 d 进制下反转后的数是否也为素数。

initPrimes 预生成前 MAX_PRIME 个素数；isPrime 在素数表中二分查找目标数；reverse 按 d 进制逐位取余并重新累积，得到反转后的数。主循环输出 Yes 或 No。这个写法适合数值范围受控的题目；如果输入可能超过预生成素数表覆盖范围，则需要改成按平方根试除或扩大素数表。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int reverse(int n, int d) {
    int res = 0;
    while(n != 0) {
        res *= d;
        res += n % d;
        n /= d;
    }
    return res;
}

const int MAX_PRIME = 10000;
int primes[MAX_PRIME] = {0};
int primeCount = 0;
void initPrimes() {
    primes[0] = 2;
    primes[1] = 3;
    primeCount = 2;
    for(int i = 5; primeCount < MAX_PRIME; i+=2) {
        primes[primeCount] = i;
        primeCount++;
        for(int j = 0; j < primeCount && primes[j]*primes[j] <= i; j++) {
            if(i%primes[j] == 0) {
                primeCount--;
                break;
            }
        }
    }
}

bool isPrime(int n) {
    int l = 0, r = primeCount;
    while(l <= r) {
        int mid = (r-l)/2 + l;
        if(primes[mid] == n) return true;
        else if(primes[mid] > n) r = mid-1;
        else l = mid+1;
    }
    return false;
}

int main() {
    int n, d;
    initPrimes();
    while(cin >> n >> d) {
        if(isPrime(n) && isPrime(reverse(n, d))) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }
    return 0;
}
发表更新算法2 分钟读完 (大约249个字)

C++ 析构函数中delete this

算法内容

本文件是 C++ 对象传值、指针对象生命周期和析构行为的学习代码。

代码定义类 A 和结构体 B，并尝试通过函数传值修改对象副本。main 中使用 new A 创建堆对象，再通过 delete a 触发析构。需要特别注意：A 的析构函数内部又执行 delete this，这会导致递归析构或重复释放，是未定义行为。这个例子可以作为理解对象生命周期风险的反面案例：析构函数里通常不应该 delete this。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
class A {
    public:
    int a;
    int b;
    A(int a0, int b0) : a(a0), b(b0) {}
    ~A() {
        cout << "delete this" << endl;
        delete this;
    }
};

struct B
{
    int a;
    int b;
    B(int a0, int b0) : a(a0), b(b0) {}
};

void f1(A a, B b) {
    a.a = 5, a.b = 6;
    b.a = 5, b.b = 6;
}

int main() {
    A *a = new A(1,2);
    B b(1,2);
    // f1(a, b);
    cout << a->a << " " << a->b << endl;
    // cout << b.a << " " << b.b << endl;
    delete a;
    return 0;
}
发表更新算法1 分钟读完 (大约174个字)

多继承

算法内容

本文件演示 C++ 多继承和纯虚函数实现。

A 和 B 都是包含纯虚函数的抽象基类，C 同时继承二者，并分别实现 afun 和 bfun。main 创建 C 的对象后调用两个接口，输出对应返回值。这个例子用于观察一个派生类如何同时满足多个抽象接口，以及多继承下虚函数调用的基本形式。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class A {
    public:
    virtual int afun() = 0;
};

class B {
    public:
    virtual int bfun() = 0;
};

class C : public A, public B {
    public:
    virtual int afun() {
        return 0;
    }
    virtual int bfun() {
        return 1;
    }

};

#include<iostream>
using namespace std;

int main() {
    C c;
    int a = c.afun();
    int b = c.bfun();

    cout << a << b << endl;
    return 0;
}
发表更新算法2 分钟读完 (大约297个字)

差分数组

算法内容

本文件演示差分数组的基本思想。差分数组适合处理“区间统一增减、最后还原数组”的场景。

diffOf 将原数组转换为差分数组，其中 diff[i] = data[i] - data[i - 1]；dataOf 对差分数组求前缀和，还原原数组。主循环读取 l, r, diff，表示对半开区间 [l, r) 加上 diff，只需要执行 data_diff[l] += diff 和 data_diff[r] -= diff，再还原即可看到更新后的数组。区间更新为 O(1)，还原数组为 O(n)。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <vector>
#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>
#include <unordered_map>

using namespace std;

void printVec(const vector<int> &v, const string& head = "")
{
    if(head != "") {
        cout << head << ": ";
    }
    for (int i : v)
    {
        cout << i << " ";
    }
    cout << "\n";
}

vector<int> diffOf(const vector<int> &v)
{
    int len = v.size();
    vector<int> diff(len, 0);
    diff[0] = v[0];
    for (int i = 1; i < len; i++)
    {
        diff[i] = v[i] - v[i - 1];
    }
    return diff;
}

vector<int> dataOf(const vector<int> &v)
{
    int len = v.size();
    vector<int> data(len, 0);
    data[0] = v[0];
    for (int i = 1; i < len; i++)
    {
        data[i] = v[i] + data[i - 1];
    }
    return data;
}

int main()
{
    vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8};
    vector<int> data_diff = diffOf(data);
    printVec(dataOf(data_diff), "data");
    printVec(data_diff, "diff");
    int l, r, diff; //区间 [l, r) 的所有数增加 diff
    while (cin >> l >> r >> diff)
    {
        data_diff[l] += diff;
        data_diff[r] -= diff;
        printVec(dataOf(data_diff), "data");
        printVec(data_diff, "diff");
    }
    return 0;
}
发表更新算法1 分钟读完 (大约195个字)

越界死循环

算法内容

本文件是 C/C++ 数组越界行为的实验代码。

代码定义长度为 5 的数组 a，但循环写入 a[0] 到 a[30]，明显越界。越界写会破坏栈上的其他局部变量或控制信息，因此可能出现循环条件异常、输出异常、崩溃等未定义行为。这个文件的学习重点是：C/C++ 不会自动检查原生数组边界，越界访问不是稳定可依赖的行为，调试时可以借助 AddressSanitizer 等工具定位。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<vector>
#include<iostream>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int main() {
    int x, i=0 ,a[5];
    for(i = 0; i <= 30; i++) {
        a[i] = i;
        printf("%d:hello\n", i);
    }
    printf("%d:hello world!\n", i);
    printf("%d:hello world!\n", x);

    return 0;
}
发表更新LeetCode / 算法17 分钟读完 (大约2568个字)

2022年10月5日

1640. 能否连接形成数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        for(int i = 0; i < len_arr; i++) {
            arr_map[arr[i]] = i+1;
        }
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            int i_len = pieces[i].size();
            int diff = arr_map[pieces[i][0]];
            if(diff == 0) {
                return false;
            }
            for(int j = 1; j < i_len; j++) {
                if(diff != arr_map[pieces[i][j]] - j) {
                    return false;
                }
            }
        }
        return true;
    }
};

4ms，和最快的思路刚好相反，用map存储arr的index，最快的思路是反过来，用map存一个piece的第一个index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        int arr_map[105] = {0};
        int len_arr = arr.size();
        int pie_len = pieces.size();
        for(int i = 0; i < pie_len; i++) {
            arr_map[pieces[i][0]] = i+1;
        }
        int i = 0;
        while(i < len_arr) {
            int row = arr_map[arr[i]];
            if(row == 0) return false;
            vector<int>& subv = pieces[row-1];
            int i_len = subv.size();
            for(int j = 0; j < i_len; j++, i++) {
                if(arr[i] != subv[j]) {
                    return false;
                }
            }
        }
        return true;
    }
};

707. 设计链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
struct List {
    List *next;
    int val;
    List(int val0, List* next0 = nullptr):val(val0), next(next0) {}
};

class MyLinkedList {
private:
    List *root;
    List *tail;
    int size;
    inline List* getNode(int& index) {
        List *move = root;
        while(index > 0 && move->next != nullptr) {
            move = move->next;
            index--;
        }
        return move;
    }
public:
    MyLinkedList() {
        root = new List(0);
        tail = root;
        size = 0;
    }
    
    int get(int index) {
        List *move = getNode(index);
        return (move->next == nullptr) ? -1 : move->next->val;
    }
    
    void addAtHead(int val) {
        List* node = new List(val, root->next);
        root->next = node;
        if(root == tail) {
            tail = node;
        }
        size++;
    }
    
    void addAtTail(int val) {
        List* node = new List(val, tail->next);
        tail->next = node;
        tail = node;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        List *move = getNode(index);
        if(index > 0) {
            return;
        }
        List* node = new List(val, move->next);
        move->next = node;
        if(move == tail) {
            tail = node;
        }
        size++;
    }
    
    void deleteAtIndex(int index) {
        List *move = getNode(index);
        List *target = move->next;
        if(target != nullptr)  {
            move->next = target->next;
            if(target == tail) {
                tail = move;
            }
            delete target;
            size--;
        }
    }
};
阅读更多
发表更新Kotlin-Android17 分钟读完 (大约2483个字)

实习笔记-1

px dp sp 的区别
px 其实就是像素单位，比如我们通常说的手机分辨列表800*400都是px的单位
sp 同dp相似，还会根据用户的字体大小偏好来缩放
dp 虚拟像素，在不同的像素密度的设备上会自动适配

隐藏状态栏任务栏

在api30之前

1
getWindow().getDecorView().setSystemUIVisibility(View.SYSTEM_UI_FLAG_FULLSCREEN)
阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码6
Android车载1
Android面试查漏补缺2
C#9
C/C++1
CSharp9
Flutter1
Java基础 字节码2
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery6
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法69
×