发表更新算法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--;
        }
    }
};
阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1600个字)

LeetCode-10

2020-07-25

Z 字形变换

AC代码

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
class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows <= 1) {
            return s;
        }
        int n = s.size();
        string temp[numRows];
        int t_numRows = 0;
        int p = 0;
        while(p < n) {
            while(p < n && t_numRows < numRows) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows++;
            }
            t_numRows = numRows -2;
            while (p < n && t_numRows > 0) {
                temp[t_numRows] += s[p];
                p++;
                t_numRows--;
            }
        }
        string res;
        for(int i = 0 ; i < numRows; i++) {
            res = res + temp[i];
        }
        return res;
    }
};

优化思路

  1. 两层while循环多次判断p<n,效率底下，实际上只需要当t_numRows==0或t_numRows==numRows-1时改变方向即可

  2. 实际上需要的string数组长度是min(n, numRows)

    优化代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
    public:
     string convert(string s, int numRows) {
         if (numRows <= 1) {
             return s;
         }
         int n = int(s.size());
         int len = min(numRows, n);
         vector<string> temp(len);
         int t_numRows = 0;
         bool goingDown = false;
         for(int i = 0; i < n; i++) {
             temp[t_numRows] += s[i];
             if (t_numRows == 0 || t_numRows == numRows-1) {
                 goingDown = !goingDown;
             }
             t_numRows += goingDown ? 1 :-1;
         }
         string res;
         for (int i = 0; i < len; i++) res += temp[i];
         return res;
     }
    };

    再次优化

    可以直接找新旧数列的数字关系，直接计算

    优化代码

    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
    class Solution {
    public:
     string convert(string s, int numRows) {
         if (numRows <= 1) {
             return s;
         }
         int len_s = int(s.size());
         int unit =(2*numRows-2);
         int n = len_s/unit;
         int remain = len_s%unit;
         string res(len_s, 0);
         for (int i = 0; i < len_s; i++) {
             int p = 0;
             if (i%unit == 0) {
                 p = i/unit+1;
             } else {
                 int r = i%unit + 1,c = i/unit+1;
                 if (r > numRows) {
                     r = unit-r+2;
                     p = 1;
                 } else if (r == numRows) {
                     p = 1-c;
                 }
                 p += n + (n*2)*(r-2) + 2*(c-1) + min(r-1, remain)+1;
                 if (remain > numRows) {
                     p += max(r-(unit-remain+2),0);
                 }
             }
             res[p-1] = s[i];
         }
         return res;
     }
    };

    最终成绩

    执行用时：8 ms, 在所有 C++ 提交中击败了98.89%的用户

    内存消耗：7.7 MB, 在所有 C++ 提交中击败了100.00%的用户

阅读更多
发表更新LeetCode / 算法9 分钟读完 (大约1344个字)

LeetCode-11

2020-07-27

55. 跳跃游戏

思路

  1. 对nums数组，令nums[i] += i,这样表示i位置最远可以走到的距离

  2. 算法

    从i = 0开始
    对于当前i，可以从0走到nums[i]，选取0-nums[i]的最大值，如果最大值大于等于n-1，则可以到达最后，若小于，重复这个步骤，除非i=最大值，则不能到达最后

  3. 为了降低时间复杂度，创建一个数组v，v[i] = max(nums[k]), k = 0,1,…,i

AC代码

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
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = int(nums.size());
        for(int i = 0; i < n; i++) {
            nums[i] += i;
        }
        vector<int> v;
        int max = nums[0];
        for(int i = 0; i < n; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            v.push_back(max);
        }
        int i = 0;
        while (i != v[i]) {
            i = v[i];
            if (i >= n-1) {
                return true;
            }
        }
        return false || n == 1;
    }
};
阅读更多
关注我

链接

分类

最新文章

归档

标签

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
×