【算法练习】日常刷题记录

本文主要是介绍【算法练习】日常刷题记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、递归与递推

递归实现指数型枚举

import java.util.*;

public class Main {
    static int n;
    static LinkedList<Integer> tmp = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs(1);
    }
    static void dfs(int start) {
        if (tmp.size() == 0) {
            System.out.println();
        }
        if (tmp.size() >= 1) {
            for (int i = 0; i < tmp.size(); i++) {
                System.out.printf("%d ", tmp.get(i));
            }
            System.out.println();
        }
        if (tmp.size() > n) {
            return;
        }
        for (int i = start; i <= n; i++) {
            tmp.add(i);
            dfs(i + 1);
            tmp.removeLast();
        }
    }
}

递归实现排列型枚举

import java.util.*;

public class Main {
    static int n;
    static int[] vis = new int[10];
    static LinkedList<Integer> tmp = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs();
    }
    static void dfs() {
        if (tmp.size() == n) {
            for (int i = 0; i < tmp.size(); i++) {
                System.out.printf("%d ", tmp.get(i));
            }
            System.out.println();
        }
        if (tmp.size() > n) {
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 1) {
                continue;
            }
            vis[i] = 1;
            tmp.add(i);
            dfs();
            vis[i] = 0;
            tmp.removeLast();
        }
    }
}

用System.out.println会超时，改用BufferedWriter，比System.out.println快20倍。

package Chapter_5;

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int n;
    static int[] vis = new int[10];
    static LinkedList<Integer> tmp = new LinkedList<>();
    // 加快打印速度
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        dfs();
        log.flush();
    }
    static void dfs() throws IOException {
        if (tmp.size() == n) {
            for (int i = 0; i < tmp.size(); i++) {
                log.write(tmp.get(i) + " ");
            }
            log.write("\n");
        }
        if (tmp.size() > n) {
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i] == 1) {
                continue;
            }
            vis[i] = 1;
            tmp.add(i);
            dfs();
            vis[i] = 0;
            tmp.removeLast();
        }
    }
}

递归实现组合型枚举

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int m;
    static LinkedList<Integer> tmp = new LinkedList<>();
    // 加快打印速度
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        dfs(1);
        log.flush();
    }
    static void dfs(int start) throws IOException {
        if (tmp.size() == m) {
            for (int i = 0; i < tmp.size(); i++) {
                log.write(tmp.get(i) + " ");
            }
            log.write("\n");
        }
        if (tmp.size() > m) {
            return;
        }
        for (int i = start; i <= n; i++) {
            tmp.add(i);
            dfs(i + 1);
            tmp.removeLast();
        }
    }
}

飞行员兄弟

从左到右，从上往下，依次遍历每个开关，对某个开关有两种状态，可以change，也可以不change，所以就需要回溯。

import java.io.*;
import java.util.*;

class node {
    int x, y;
    node() {};
    node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static char[][] map = new char[4][4];
    static LinkedList<node> nodes = new LinkedList<>();
    static LinkedList<node> ans = new LinkedList<>();
    // 加快打印速度
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        for (int i = 0; i < 4; i++) {
            map[i] = scan.next().toCharArray();
        }
        // 从左到右、从上到下遍历每个开关，直到遍历完，整个过程中查看是否成功
        dfs(0, 0);
        System.out.println(ans.size());
        for (int i = 0; i < ans.size(); i++) {
            System.out.printf("%d %d\n", ans.get(i).x + 1, ans.get(i).y + 1);
        }
    }
    static void openOneUp(int x, int y) {
        if (map[x][y] == '+') map[x][y] = '-';
        else map[x][y] = '+';
    }
    static void openAllUp(int x, int y) {
        for (int i = 0; i < 4; i++) {
            openOneUp(x, i);
            openOneUp(i, y);
        }
        // 注意上面会把x,y重置（两次change = 不change）
        // 还需要单独open(x,y)
        openOneUp(x, y);
    }
    static void dfs(int x, int y) {
        if (x == 3 && y == 4) {
            // 所有开关都遍历完了，看当前冰箱能否打开
            boolean flag = true;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (map[i][j] == '+') {
                        flag = false;
                        break;
                    }
                }
                if (flag == false) {
                    break;
                }
            }
            if (flag) {
                // 所需的最小切换把手次数
                if (ans.isEmpty() || ans.size() > nodes.size()) {
                    // 必须要用clone，否则nodes的变化会导致ans的变化
                    ans = (LinkedList<node>) nodes.clone();
                }
            }
            return;
        }
        // 当前行遍历完了，遍历下一行
        if (y == 4) {
            x++;
            y = 0;
        }
        openAllUp(x, y);
        node tmp = new node(x, y);
        nodes.add(tmp);
        // 遍历右边一个
        dfs(x, y + 1);
        // 回溯
        nodes.removeLast();
        // 回溯，之前的状态也要全部回溯
        openAllUp(x, y);
        dfs(x, y + 1);
    }
}

二、二分

数的范围

一次二分找最开始位置，一次二分找第一个大于它的位置即可。

import java.io.*;
import java.util.*;

public class Main {
    static int[] nums;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int q = scan.nextInt();
        nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        for (int i = 0; i < q; i++) {
            int key = scan.nextInt();
            int res = binarySearch(key);
            if (res == -1) {
                System.out.printf("-1 -1\n");
            } else {
                int res1 = binarySearch1(key);
                System.out.printf("%d %d\n", res, res1 - 1);
            }
        }
    }
    static int binarySearch(int key) {
        int res = -1;
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == key) {
                res = mid;
                // 要找第一次出现的位置
                right = mid - 1;
            } else if (nums[mid] > key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
    // 找第一个大于key的下标
    static int binarySearch1(int key) {
        int left = 0;
        int right = nums.length;
        int mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] > key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

数的三次方根

从n的左右边界开始遍历

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        double key = scan.nextDouble();
        // 注意x的范围可正可夫，所以左右边界要为边界
        double left = -10000;
        double right = 10000;
        double eps = 0.00000001;
        double mid;
        while (right - left >= eps) {
            mid = left + (right - left) / 2;
            if (mid * mid * mid <= key) {
                left = mid;
            } else {
                right = mid;
            }
        }
        System.out.printf("%.6f", left);
    }
}

能用二分的地方，都是存在单调性的地方！

三、模拟

注意不能斜向走，找到两个坐标，然后求曼哈顿距离。

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int w = scan.nextInt();
        int m = scan.nextInt();
        int n = scan.nextInt();
        m--;n--;
        int x1 = m / w;
        int x2 = n / w;
        int y1 = m % w;
        if (x1 % 2 == 0) {
            y1 = w - y1 - 1;
        }
        int y2 = n % w;
        if (x2 % 2 == 0) {
            y2 = w - y2 - 1;
        }
        System.out.println(Math.abs(x1 - x2) + Math.abs(y1 - y2));
    }
}

四、搜索

献给阿尔吉侬的花束

正常的BFS，直接做就行。

import java.util.*;

class node {
    int x, y, step;
    node() {};
    node(int x, int y, int step) {
        this.x = x;
        this.y = y;
        this.step = step;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        char[][] map;
        int[][] vis;
        int[] xx = new int[] {-1,1,0,0};
        int[] yy = new int[] {0,0,-1,1};
        for (int i = 0; i < t; i++) {
            int r = scan.nextInt();
            int c = scan.nextInt();
            vis = new int[201][201];
            map = new char[201][201];
            node b = new node();
            for (int j = 0; j < r; j++) {
                map[j] = scan.next().toCharArray();
                for (int k = 0; k < c; k++) {
                    if (map[j][k] == 'S') {
                        b = new node(j, k, 0);
                        vis[j][k] = 1;
                    }
                }
            }
            int ans = Integer.MAX_VALUE;
            Queue<node> Q = new LinkedList<>();
            Q.offer(b);
            while (!Q.isEmpty()) {
                node tmp = Q.poll();
                if (map[tmp.x][tmp.y] == 'E') {
                    ans = tmp.step;
                    break;
                }
                for (int j = 0; j < 4; j++) {
                    // 注意这里不要直接temp = tmp!!!
                    node temp = new node();
                    temp.x = tmp.x + xx[j];
                    temp.y = tmp.y + yy[j];
                    if (temp.x < 0 || temp.y < 0 || temp.x >= r || temp.y >= c || map[temp.x][temp.y] == '#') {
                        continue;
                    }
                    if (vis[temp.x][temp.y] == 1) {
                        continue;
                    }
                    vis[temp.x][temp.y] = 1;
                    temp.step = tmp.step + 1;
                    Q.offer(temp);
                }
            }
            if (ans == Integer.MAX_VALUE) {
                System.out.println("oop!");
            } else {
                System.out.println(ans);
            }
        }
    }
}

五、前缀和

普通的前缀和要超时，让女生=-1，男生=1，这样记录前缀和中每个和第一次出现的位置，后面再遇到同样的和时，减去第一次出现的位置即可。需要注意，可能有从头到某个位置只有1个零出现的情况，例如：1 1 -1 -1，前缀和为：1 2 1 0，只有1个0，所以需要在读入数据的时候单独求和判断一下。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        // 计算前缀和，比较当前区间和区间长度是否相等
        int[] nums = new int[n];
        int sum = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
            if (nums[i] == 0) {
                nums[i] = -1;
            }
            sum += nums[i];
            if (sum == 0) {
                // 如果从头到某个位置的和为0，且只出现1次，要特殊判断一下
                ans = i + 1;
            }
        }
        // 计算前缀和
        int[] preSum = new int[n + 1];
        int[] pos = new int[2 * n + 1];
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
            if (pos[preSum[i] + n] != 0) {
                ans = Math.max(i - pos[preSum[i] + n], ans);
            } else {
                pos[preSum[i] + n] = i;
            }
        }
        System.out.println(ans);            
    }
}

这道题滑动窗口做不了。

这篇关于【算法练习】日常刷题记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！