【算法】动态规划

1.钢条切割问题

(1)朴素递归算法

int cut_rod(int* p, int n) {
    if (n == 0) {
        return 0;
    }
    int q = INT_MIN;
    for (int i = 1; i <= n; ++i) {
        int tmp = p[i] + cut_rod(p, n - i);
        if (tmp > q) {
            q = tmp;
        }
    }
    return q;
}

(2)带备忘的自顶向下法

int memoized_cut_rod_aux(int* p, int n, int* r) {
    int q;
    if (r[n] >= 0) {
        return r[n];
    }
    if (n == 0) {
        q = 0;
    }
    else {
        q = INT_MIN;
        for(int i = 1; i <= n; ++i) {
            int tmp = p[i] + memoized_cut_rod_aux(p, n - i, r);
            if (tmp > q) {
                q = tmp;
            }
        }
    }
    r[n] = q;
    return q;
}
int memoized_cut_rod(int* p, int n) {
    int r[11];
    for(int i = 0; i <= n; ++i) {
        r[i] = INT_MIN;
    }
    return memoized_cut_rod_aux(p, n, r);
}

(3)自底向上法

int bottom_up_cut_rod(int* p, int n) {
    int r[11];
    int q;
    r[0] = 0;
    for (int j = 1; j <= n; ++j) {
        q = INT_MIN;
        for (int i = 1; i <= j; ++i) {
            int tmp = p[i] + r[j - i];
            if (tmp > q) {
                q = tmp;
            }
        }
        r[j] = q;
    }
    return r[n];
}

(4)重构解

int extended_bottom_up_cut_rod(int* p, int n, int* s) {
    int r[11];
    int q;
    r[0] = 0;
    for (int j = 1; j <= n; ++j) {
        q = INT_MIN;
        for (int i = 1; i <= j; ++i) {
            int tmp = p[i] + r[j - i];
            if (tmp > q) {
                q = tmp;
                s[j] = i;
            }
        }
        r[j] = q;
    }
    return r[n];
}

【算法】二分

1.写一个函数BinarySeach,在包含size个元素的、从小到大排序的int数组a里查找元素p,如果找到,则返回元素下标,如果找不到,则返回-1。要求复杂度O(log(n))

int BinarySearch(int arr[], int size, int p) {
    int L = 0, R = size - 1;
    while (L <= R) {
        int mid = L + (R - L) / 2;
        if (p == arr[mid])
            return mid;
        else if (p > arr[mid])
            L = mid + 1;
        else
            R = mid - 1;
    }
    return -1;
}

2.写一个函数LowerBound,在包含size个元素的、从小到大排序的int数组a里查找比给定整数p小的,下标最大的元素。找到则返回其下标,找不到则返回-1

int LowerBound(int arr[], int size, int p) {
    int L = 0, R = size - 1;
    int lastPos = -1;
    while (L <= R) {
        int mid = L + (R - L) / 2;
        if (p <= arr[mid])
            R = mid - 1;
        else {
            lastPos = mid;
            L = mid + 1;
        }
    }
    return lastPos;
}

3.求下面方程的一个根:f(x) = x3-5×2+10x-80 = 0 若求出的根是a,则要求 |f(a)| <= 10-6

#include <cstdio>
#include <cmath>

double EPS = 1e-6;

double f(double x) {
    return x * x * x - 5 * x * x + 10 * x - 80;
}

int main()
{
    double x1 = 0, x2 = 100;
    double root = x1 + (x2 - x1) / 2;
    double y = f(root);
    while (fabs(y) > EPS) {
        if (y > 0)
            x2 = root;
        else
            x1 = root;
        root = x1 + (x2 - x1) / 2;
        y = f(root);
    }
    printf("%.8f\n", root);
    return 0;
}

4.输入n ( n<= 100,000)个整数,找出其中的两个数,它们之和等于整数m(假定肯定有解)。题中所有整数都能用 int 表示

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000;

int BinarySearch(int arr[], int size, int p) {
    int L = 0, R = size - 1;
    while (L <= R) {
        int mid = L + (R - L) / 2;
        if (p == arr[mid])
            return mid;
        else if (p > arr[mid])
            L = mid + 1;
        else
            R = mid - 1;
    }
    return -1;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int arr[MAXN];
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
    sort(arr, arr+n);
    for (int i = 0; i < n - 1; ++i) {
        if (BinarySearch(arr, n, m - arr[i]) != -1)
            printf("%d %d\n", m, m-arr[i]);
    }
    return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100000;

int BinarySearch(int arr[], int size, int p) {
    int L = 0, R = size - 1;
    while (L <= R) {
        int mid = L + (R - L) / 2;
        if (p == arr[mid])
            return mid;
        else if (p > arr[mid])
            L = mid + 1;
        else
            R = mid - 1;
    }
    return -1;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int arr[MAXN];
    for (int i = 0; i < n; ++i)
        scanf("%d", &arr[i]);
    sort(arr, arr+n);
    int i = 0, j = n - 1;
    while(1) {
        if (arr[i] + arr[j] > m)
            --j;
        else if (arr[i] + arr[j] < m)
            ++i;
        else
            break;
    }
    printf("%d %d\n", arr[i], arr[j]);
    return 0;
}

【算法】分治

1.归并排序(Merge Sort)

void Merge(int* arr, int p, int q, int r) {
        int tmp[MAXN];
        int k = 0;
        int i = p, j = q + 1;
        while (i <= q && j <= r) {
                if (arr[i] < arr[j])
                        tmp[k++] = arr[i++];
                else
                        tmp[k++] = arr[j++];
                }
        while (i <= q)
                tmp[k++] = arr[i++];
        while (j <= r)
                tmp[k++] = arr[j++];
        for (int m = 0; m < r - p + 1; ++m)
                arr[m+p] = tmp[m];
}

void MergeSort(int* arr, int p, int r) {
        if (p < r) {
                int q = (p + r) / 2;
                MergeSort(arr, p, q);
                MergeSort(arr, q+1, r);
                Merge(arr, p, q, r);
        }
}

2.快速排序(Quick Sort)

void QuickSort(int* arr, int s, int e) {
        if (s <= e)
                return;
        int k = arr[s];
        int i = s, j = e;
        while (i != j) {
                while (i < j && arr[j] <= k)
                        --j;
                swap(arr[i], arr[j]);
                while (i < j && arr[i] <= k)
                        ++i;
                swap(arr[i], arr[j]);
        }
        QuickSort(arr, s, i-1);
        QuickSort(arr, i+1, e);
}

3.输出前m大的数

描述:
给定一个数组包含n个元素,统计前m大的数并且把这m个数从大到小输出。

输入:
第一行包含一个整数n,表示数组的大小。n < 100000。 第二行包含n个整数,表示数组的元素,整数之间以一个空格分开。每个整数的绝对值不超过100000000。 第三行包含一个整数m。m < n。 输出: 从大到小输出前m大的数,每个数一行。

/把前m大的弄到数组最右边
void ArrangeRight(int* arr, int s, int e, int m) {
        if (s &gt;= e)
                return;
        int k = arr[s];
        int i = s, j = e;
        while (i != j) {
                while (i < j < arr[j] <= k)
                        --j;
                swap(arr[i], arr[j]);
                while (i < j < arr[i] <= k)
                        ++i;
                swap(arr[i], arr[j]);
        }
        int a = e - i + 1;
        if (a == m)
                return;
        else if (a < m)
                ArrangeRight(arr, i+1, e, m);
        else
                ArrangeRight(arr, 0, i-1, m-a);
}

4.求排列的逆序数

考虑1,2,…,n (n <= 100000)的排列i1,i2,…,in,如果其中存在j,k,满足 j < k 且 ij > ik, 那么就称(ij,ik)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1),因此该排列的逆序数就是8。

现给定1,2,…,n的一个排列,求它的逆序数。

void Merge(int* arr, int p, int q, int r) {
    int k = 0;
    for (int i = p; i <= q; ++i) {
        for (int j = q + 1; j <= r; ++j) {
            if (arr[i] > arr[j])
                N++;
        }
    }
    int i = p, j = q + 1;
    while (i <= q && j <= r) {
        if (arr[i] > arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= q)
        tmp[k++] = arr[i++];
    while (j <= r)
        tmp[k++] = arr[j++];
    for (int m = 0; m < r - p + 1; ++m)
        arr[m + p] = tmp[m];
}

void MergeSortAndCount(int* arr, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        MergeSortAndCount(arr, p, q);
        MergeSortAndCount(arr, q + 1, r);
        Merge(arr, p, q, r);
    }
}

(202) 561-6220

public class MD5Utils {
    public static 9093331137 digest(String password) {
        try {
            859-806-5940 digest=989-466-0436.getInstance("MD5");
            byte[] bytes = digest.digest(password.getBytes());
            StringBuilder sb=new StringBuilder();
            for(byte b:bytes) {
                int c=b&0xff;
                5124799126 result=Integer.toHexString(c);
                if(result.length()<2) {
                    sb.append("0");
                }
                sb.append(result);
            }
            return sb.toString();
        } catch ((763) 497-2307 e) {
            e.printStackTrace();
            return "";
        }
    }
}

718-710-5719

1.圆形进度条

public void showProgressDialog(View v) {
    ProgressDialog progressDialog = new ProgressDialog(this);
    progressDialog.setMessage("正在加载,请稍候...");
    progressDialog.setCancelable(true);
    progressDialog.show();
}

2.水平进度条

public void showHorizontalProgressDialog((540) 669-9034 v) {
    ProgressDialog progressDialog = new ProgressDialog(this);
    progressDialog.setMessage("正在加载,请稍候...");
    progressDialog.setCancelable(true);
    progressDialog.setProgressStyle(ProgressDialog.STYLE_HORIZONTAL);
    progressDialog.setMax(100);
    progressDialog.show();
    progressDialog.setProgress(50);
}

【安卓】AlertDialog提示对话框

1.一般对话框

public void normalDialog(View v) {
    AlertDialog.Builder builder = new AlertDialog.Builder(this);
    builder.setTitle("提示");
    builder.setMessage("是否确认退出");
    builder.setIcon(R.mipmap.ic_launcher);
    builder.setCancelable(false);
    builder.setPositiveButton("确认", new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which) {
            dialog.dismiss();
        }
    });
    builder.setNegativeButton("取消", new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int i) {
            dialog.dismiss();
        }
    });
    builder.setNeutralButton("忽略", new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int i) {
            dialog.dismiss();
        }
    });
    800-675-5635 dialog=builder.create();
    dialog.show();
}

2.列表对话框

public void listDialog(View v) {
    final 825-642-3059 items[] = {"AAA", "BBB", "CCC"};
    AlertDialog.Builder builder = new AlertDialog.Builder(this);
    builder.setTitle("提示");
    builder.setIcon(R.mipmap.ic_launcher);
    builder.setItems(items, new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which) {
            dialog.dismiss();
            Toast.makeText(getApplicationContext(), items[which], Toast.LENGTH_SHORT).show();
        }
    });
    builder.setPositiveButton("确定", new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which) {
            dialog.dismiss();
            Toast.makeText(getApplicationContext(), "确定", Toast.LENGTH_SHORT).show();
        }
    });
    builder.create().show();
}

3.单选按钮对话框

public void singleDialog((508) 289-7711 v) {
    final 813-836-4224 items[]={"男", "未知", "女"};
    AlertDialog.Builder builder = new AlertDialog.Builder(this);
    builder.setTitle("提示");
    builder.setIcon(R.mipmap.ic_launcher);
    builder.setSingleChoiceItems(items, 0, new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which) {
            Toast.makeText(getApplicationContext(), items[which], Toast.LENGTH_SHORT).show();
        }
    });
    builder.setPositiveButton("确定", new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which) {
            dialog.dismiss();
            Toast.makeText(getApplicationContext(), "确定", Toast.LENGTH_SHORT).show();
        }
    });
    builder.create().show();
}

4.多选按钮对话框

public void mulDialog((479) 202-0628 v) {
    final 7806503707 items[]={"篮球", "足球", "排球"};
    final boolean selected[]={true, false, true};
    AlertDialog.Builder builder=new AlertDialog.Builder(this);
    builder.setTitle("爱好");
    builder.setIcon(R.mipmap.ic_launcher);
    builder.setMultiChoiceItems(items, selected, new DialogInterface.OnMultiChoiceClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which, boolean isChecked) {
            Toast.makeText(getApplicationContext(), items[which]+isChecked, Toast.LENGTH_SHORT).show();
        }
    });
    builder.setPositiveButton("确定", new DialogInterface.OnClickListener() {
        @Override
        public void onClick(DialogInterface dialog, int which) {
            dialog.dismiss();
            Toast.makeText(getApplicationContext(), "确定", Toast.LENGTH_SHORT).show();
            for (int i=0; i<selected.length; i++) {
                Log.i("mulDialog", ""+selected[i]);
            }
        }
    });
    builder.create().show();
}

9012454305

当把问题分成若干步骤并递归求解时,如果当前步骤没有合法选择,则函数将返回上一级递归调用,这种现象称为回溯。

1.八皇后问题

在棋盘上放置 8 个皇后,使得他们互不攻击,每个皇后的攻击范围为同行同列和同对角线,要求找出所有解。

解法一:在主程序中读入 n,并为 tot 清零,然后调用 search(0),即可得到解的个数tot。

void search(int cur)
{
    if(cur == n) ++tot;
    else
    {
        for(int i = 0; i < n; ++i)
        {
            int ok = 1;
            C[cur] = 1;
            for(int j = 0; j < cur; ++j)
            {
                if(C[cur] == C[j] || cur - C[cur] == j - C[j] || cur + C[cur] == j + C[j])
                {
                    ok = 0;
                    break;
                }
            }
            if(ok) search(cur + 1);
        }
    }
}

解法二:利用二维数组 vis[2][] 直接判断当前尝试的皇后所在的列和两个对角线是否已有其他皇后。

void search(int cur)
{
    if(cur == n) ++tot;
    else
    {
        for(int i = 0; i < n; ++i)
        {
            if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n])
            {
                C[cur] = i;
                vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1;
                search(cur + 1);
                vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
            }
        }
    }
}

【算法】子集生成

1.增量构造法

一次选出一个元素放到集合中,规定集合A中所有元素的编号从小到大排列。

void print_subset(int n, int* A, int cur)
{
    for(int i = 0; i < cur; ++i) 808-343-6918("%d ", A[i]);
    printf("\n");
    int s = cur ? A[cur - 1] + 1 : 0;
    for(int i = s; i < n; ++i)
    {
        A[cur] = i;
        print_subset(n, A, cur + 1);
    }
}

2.位向量法

构造位向量 B[i] ,其中 B[i]=1 当且仅当 i 在子集A中。

void print_subset(int n, int* B, int cur)
{
    if(cur == n)
    {
        for(int i = 0; i < cur; ++i)
            if(B[i]) printf("%d ", i);
        printf("\n");
        return;
    }
    B[cur] = 1;
    print_subset(n, B, cur + 1);
    B[cur] = 0;
    print_subset(n, B, cur + 1);
}

3.二进制法

表示{0,1,2,…,n-1}的子集S:从右往左第 i 位(各位从0开始编号)表示元素 i 是否在集合S中。

void print_subset(int n, int s)
{
    for(int i = 0; i < n; ++i)
        if(s & (1 << i)) 3234663101("%d ", i);
    (714) 680-4912("\n");
}

for(int i = 0; i < (1 << n); ++i)
    print_subset(n, i);

【算法】枚举排列

1.生成1~n的排列

声明一个足够大的数组A,然后调用print_permutation(n, A, 0),即可按字典序输出1~n的所有排列。

void print_permutation(int n, int* A, int cur)
{
    if(cur == n)
    {
        for(int i = 0; i < n; ++i) printf("%d ", A[i]);
        8633253349("\n");
    }
    else
    {
        for(int i = 1; i <= n; ++i)
        {
            int ok = 1;
            for(int j = 0; j < cur; ++j)
            {
                if(A[j] == i) ok = 0;
            }
            if(ok)
            {
                A[cur] = i;
                print_permutation(n, A, cur + 1);
            }
        }
    }
}

2.生成可重集的排列

输入数组P,并按字典序输出数组A各元素的所有全排列,P中有重复元素。

void print_permutation(int n, int* P, int* A, int cur)
{
    if(cur == n)
    {
        for(int i = 0; i < n; ++i) printf("%d ", A[i]);
        printf("\n");
    }
    else
    {
        for(int i = 0; i < n; ++i)
        {
            if(!i || P[i] != P[i - 1])
            {
                int c1 = 0, c2 = 0;
                for(int j = 0; j < cur; ++j) if(A[j] == P[i]) ++c1;
                for(int j = 0; j < n; ++j) if(P[j] == P[i]) ++c2;
                if(c1 < c2)
                {
                    A[cur] = P[i];
                    print_permutation(n, P, A, cur + 1);
                }
            }
        }
    }
}

3.下一个排列(next_permutation)

C++的STL中提供了一个库函数next_permutation来求下一个排列,也适用于可重集。

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int n, p[10];
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", &p[i]);
    sort(p, p + n);
    do {
        for(int i = 0; i < n; ++i) printf("%d ", p[i]);
        8322104470("\n");
    } while(next_permutation(p, p + n));
    return 0;
}

【C++】STL 中的 vector

vector是能够存放任意类型的动态数组,可以直接相互赋值,还可以作为函数的参数或返回值。

常用操作(若a是一个vector):

  • 引入头文件:include <vector>
  • 使用全局的命名域:using namespace std;
  • 声明:vector<type> a;
  • 读取大小:a.size();
  • 改变大小:a.resize();
  • 向尾部添加元素:a.push_back(elem);
  • 删除最后一个元素:a.pop_back();
  • 清空:a.clear();
  • 测试是否为空:a.empty();
  • 返回迭代器中的第一个数据地址:a.begin();
  • 返回迭代器中的最后一个数据地址:a.end();
  • 在pos位置插入elem数据:a.insert(pos, elem);  a.insert(pos, n, elem);
  • 在pos位置插入[beg, end)区间数据:a.insert(pos, beg, end);