发表更新安卓逆向20 分钟读完 (大约3046个字)

安卓逆向学习之frida基础用法

frida 是一款方便并且易用的跨平台 Hook 工具，使用它不仅可以 Hook Java 写的应用程序，而且还可以 Hook 原生的应用程序。

frida 分客户端环境和服务端环境。在客户端我们可以编写 Python 代码，用于连接远程设备，提交要注入的代码到远程，接受服务端的发来的消息等。在服务端，我们需要用 Javascript 代码注入到目标进程，操作内存数据，给客户端发送消息等操作。我们也可以把客户端理解成控制端，服务端理解成被控端。
假如我们要用 PC 来对 Android 设备上的某个进程进行操作，那么 PC 就是客户端，而 Android 设备就是服务端。

阅读更多
安卓逆向学习之 FRIDA HOOK AES DES RSA 自吐算法
浅谈c++的深拷贝与浅拷贝
发表更新6 分钟读完 (大约947个字)

浅谈c++的深拷贝与浅拷贝

初次见面

正如字面意思，深与浅无非是拷贝力度的大小。那么怎么理解深和浅呢？

深：将拷贝对象的所有属性复制一遍

浅：仅拷贝对象的地址

那么为什么要有浅拷贝与深拷贝呢？

总的目的来说，浅拷贝是为了提高速率，让程序员可以直接操纵对象地址，不用再花时间与内存去复制一份新的出来。显而易见可以看出浅拷贝是很方便操作的。

既然浅拷贝很好 那么我不防聊一聊它的坏处

阅读更多
发表更新MachineLea11 分钟读完 (大约1712个字)

决策树

1.划分数据集

1.1 基本概念

在度量数据集的无序程度的时候，分类算法除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确的划分了数据集。
我们将对每个特征数据集划分的结果计算一次信息熵，然后判断按照那个特征划分数据集是最好的划分方式。
也就是说，我们依次选取我们数据集当中的所有特征作为我们划定的特征，然后计算选取该特征时的信息增益，当信息增益最大时我们就选取对应信息增益最大的特征作为我们分类的最佳特征。

阅读更多
发表更新MachineLea5 分钟读完 (大约791个字)

k-NearestNeighbor

KNN 近邻算法的初次实现和做法

KNN 概述

k-近邻（kNN, k-NearestNeighbor）算法是一种基本分类与回归方法，我们这里只讨论分类问题中的 k-近邻算法。

一句话总结: 近朱者赤近墨者黑！

k 近邻算法实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。 k 值的选择、距离度量以及分类决策规则是 k 近邻算法的三个基本要素。

KNN 场景

电影可以按照题材分类，那么如何区分 动作片 和 爱情片 呢？

  1. 动作片: 打斗次数更多
  2. 爱情片: 亲吻次数更多

基于电影中的亲吻、打斗出现的次数，使用 k-近邻算法构造程序，就可以自动划分电影的题材类型。

KNN 原理

KNN 工作原理
  1. 假设有一个带有标签的样本数据集（训练样本集），其中包含每条数据与所属分类的对应关系。
  2. 输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
    1. 计算新数据与样本数据集中每条数据的距离。
    2. 对求得的所有距离进行排序（从小到大，越小表示越相似）。
    3. 取前 k （k 一般小于等于 20 ）个样本数据对应的分类标签。
  3. 求 k 个数据中出现次数最多的分类标签作为新数据的分类。
KNN 通俗理解

给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的 k 个实例，这 k 个实例的多数属于某个类，就把该输入实例分为这个类。

KNN 算法的特点
1
2
3
优点: 精度高、对异常值不敏感、无数据输入假定
缺点: 计算复杂度高、空间复杂度高
适用数据范围: 数值型和标称型
阅读更多
发表更新MachineLea2 分钟读完 (大约237个字)

归一化

什么是归一化？

以实际例子来说，在国家贸易中，各个国家的货币价值不一样，当 A 国想买 10 吨煤的时候，我们一般是先将钱转化为美元，再用美元去买 10 吨煤，这样中间就有了一个标准

归一化有什么用？

归一化在处理数学问题和权重问题的时候具有实用的意义，比如说大学生自习室安排问题中，宿舍距各教室路线长短，教室大小，照明质量，满座率等都是影响结果的因素，这些因素本身有一个相对值，但没有一个统一的标准去衡量他们，于是出现了归一化。使每个大因素和小变量之间都有了一个桥梁，合理的去参与到对决策的影响中。

发表更新algorithm2 分钟读完 (大约290个字)

排序算法

三种排序[选择，归并，冒泡]

选择排序

优点：处理小数据的时候很快，时间复杂度(O^2)

选择排序就跟扑克牌一样，从牌堆里面选择一张牌插入到牌中，依次选择手中的牌，把相对较小的插入到其中

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(int arr[]){
    for(int i = 0 ; i < 6 ; i ++){
        int key = arr[i];
        int j = i - 1;
        while(j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j --;
        }
        arr[j + 1] = key;
    }
}

快速排序

时间复杂度为 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

归并排序

**时间复杂度 O(n log 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
void mergeSort(int arr[], int l, int r)
{
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid + 1, r);
    int k = 0, i = l, j = mid + 1;
    int tmp[r - l + 1];
    while (i <= mid && j <= r)
    {
        if (arr[i] < arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= mid)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];

    for (i = l, j = 0; i <= r; i++, j++)
        arr[i] = tmp[j];
}

快速排序和快速排序都是分治思想

发表更新algorithm6 分钟读完 (大约960个字)

哈希表

近似 O(1)的时间复杂度

哈希表一般算法中处理的问题

  1. 插入一个数
  2. 查找一个数
  3. 删除一个数

实现哈希表的两种做法

拉链法

首先选择拉链法来解决问题，拉链法用通俗的话来说，就是数组+单链表的实现
选择 hash 函数 将大整数 x 映射成为小整数的

840. 模拟散列表

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<cstring>
using namespace std;
const int N = 100002;

int e[N],ne[N],idx;
int h[N];

void insert(int x){
    int y = (x % N + N) % N; //为了缩小y 同时也避免负数的存在
    e[idx] = x; //在每一个数组下面拉出一条链 insert等同于单链表的操作
    ne[idx] = h[y];
    h[y] = idx++;
}

bool find(int x){
    int y = (x % N + N ) % N;
    for(int i = h[y] ; i != -1 ; i = ne[i])
        if(e[i] == x)
            return true;
    return false;
}

int main(){
    int n;
    cin >> n;
    memset(h,-1,sizeof h);
    while(n --){
        char op;
        int k;
        cin >> op >> k;
        if(op == 'I')insert(k);
        else{
            if(find(k))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}
阅读更多
发表更新algorithm7 分钟读完 (大约1046个字)

堆排序

堆分为小根堆和大根堆（本质上是一颗完全二叉树）

堆可以干什么？

  • 找到一个集合当中的最小值
  • 删除一个集合当中的最小值
  • 插入一个数

如何调整小根堆或者大根堆？

以小根堆为例子

  • down -> 选择这个数和子节点的最小值进行交换
  • up -> 选择这个节点与父节点进行交换

如何存储堆？

下标从 1 开始 保证了数组子节点的可行性

选择用数组的形式来存储 1 2 3 4 5 6 7 8
k 的 子节点为 2k 2k+1

如何手写一个堆

  1. 插入一个数：heap[++size] = x;
  2. 求集合当中的最小元素：heap[1];
  3. 删除最小的元素：heap[1] = heap[size]; size ++; down(1) //将末尾的元素覆盖到头节点，数组删除头节点是很麻烦的一件事
  4. 删除任意一个元素：heap[k] = heap[size]; size ++; down(k); up(k)；
  5. 修改任意一个元素：heap[k] = x;up(x);down(x); 保证 down 和 up 只执行一次
阅读更多
发表更新algorithm6 分钟读完 (大约871个字)

并查集

近似 O(1)的时间复杂度

并查集能解决什么问题？

  • 如何合并两个集合
  • 如何两个元素在不在同一个区间内

并查集原理？

用一棵树来存储整个集合，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]代表它的父节点

衍生出问题

  1. 如何判断树根？if(p[x] == x)
  2. 如何求 x 的编号？while(p[x] != x) x = p[x]
  3. 如何合并两个集合，x 代表第一个集合，y 代表第二个集合？p[x] = y

如何优化？

每遍历一次，让这个节点直接指向根节点，即可将时间复杂度优化为 O(1);

模版应用

836. 合并集合

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
import java.util.*;
import java.io.*;
public class Main{
    private static int p[] = new int[100010]; //声明父节点;
    public static void main(String [] args) throws IOException {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        int m = in.nextInt();
        while(m -- != 0){
            String op = in.next();
            if(op.equals("M")){
                int a = in.nextInt();
                int b = in.nextInt();
                p[find(a)] = find(b);
            }else{
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }
        }
        log.flush();
        log.close();
    }
    //查找x节点的父亲
    public static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
}

837. 连通块中点的数量

同时维护当前区间内，有多少个数量

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
import java.util.*;
import java.io.*;
public class Main{
    public static int p[] = new int[100010];
    public static int size[] = new int[100010];

    public static void main(String[] args) throws IOException
    {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i = 1 ; i <= n ; i ++){
            p[i] = i;
            size[i] = 1;
        }
        while(m -- != 0){
            String op = in.next();
            if(op.equals("C")){

                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b)) continue;
                size[find(b)] += size[find(a)];
                p[find(a)] = b;
            }else if(op.equals("Q1")){
                int a = in.nextInt();
                int b = in.nextInt();
                if(find(a) == find(b))log.write("Yes\n");
                else log.write("No\n");
            }else{
                int k = in.nextInt();
                log.write(size[find(k)] + "\n");
            }
        }
        log.flush();
        log.close();

    }
    public static int find(int x){
        if(p[x] != x)p[x] = find(p[x]);
        return p[x];
    }
}

240. 食物链

维护当前集合里面到根节点的距离

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
74
import java.io.*;
import java.util.*;
public class Main{
    public static int[] p,d; //p存储父节点 d存储距离
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = in.nextInt();
        int m = in.nextInt();
        p = new int[n + 1];
        d = new int[n + 1];
        int ans = 0 ; //表示假话的个数
        for(int i = 1 ; i <= n ; i ++)p[i] = i;
        while(m -- != 0){
            int op = in.nextInt();
            int x = in.nextInt();
            int y = in.nextInt();
            if(x > n || y > n){
                ans += 1;
                continue;
            }
            int px = find(x);
            int py = find(y);
            switch (op) {
                case 1 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        if ((d[x] - d[y])%3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x];
                        p[px] = py;
                    }
                    break;
                }
                case 2 : {
                    //同一个集合中，表示已确立相互关系
                    if (px == py) {
                        //推导出的关系为 （d[x]-d[y]）%3 == 1 则认为x可以吃y
                        //写成（d[x]-d[y]-1）%3 == 0 可以避免余数是负数的问题
                        //也可以写成（d[x]-d[y]）%3 +3 == 1
                        //==正确 -> != 错误
                        if ((d[x] - d[y] - 1) % 3 != 0) {
                            ans++;
                            continue;
                        }
                    }
                    //不同集合中，现在建立相互关系
                    else {
                        d[px] = d[y] - d[x] + 1;
                        p[px] = py;
                    }
                    break;
                }
                default : System.out.print("--");
            }
        }
        log.write(ans + " ");
        log.flush();
        log.close();
    }
    public static int find(int x){
        if(x != p[x]){
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }
}

最新文章

链接

×