发表于 | 更新于:

汉字编码实验

  • 遇到的问题
  1. ansi与gbk的关系 utf-8.为什么gb2312的文本格式要以ansi存盘
  2. -A0A0的补码dfe0
  3. gbk转十六进制代码 hexString
  • 以上问题有一个综合答案，为什么要半角转全角？因为国标转区位码电路是针对中文字符的电路，如果用半角的电路，在字库中找不到对应的字符，自然就显示不了当前字符。其他的细枝末节就不用关心了。例如，逗号句号的全角半角，这些都不重要。

海明编码实验

  • 遇到的问题
  1. 为什么p6要与所有的输入相异或
  2. g6的总偶校验实现原理是什么？
  3. p6和g6的关系是什么？(奇偶校验的原理)
  • 解决的问题：
  1. 回顾了一下解码器，通过真值表的最小项相或画电路图。
  2. 想了一下，无论任何电路，增加一位总的奇/偶校验位，就可以验证总的编码是否出错.(该实验一是将偶校验用在了海明编码电路中p6,而是将偶校验用在了海明解码电路中G6)
    阅读全文 »

发表于 | 更新于:

A. 来自瑞思拜龙的善意 (参照”工具人”的解答)

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
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int i = sc.nextInt();
        int[] arr=new int[i];
        int[] ret=new int[i];
        int idx=0;
        while(i>0){
            int i1 = sc.nextInt();
            arr[idx]=i1;
            idx++;
            i--;
        }
        idx=0;
        for (int i1 : arr) {
            if(isPrime(i1+1)){
                ret[idx]=i1+1;
            }else ret[idx]=-1;
            idx++;
        }
        for (int i1 : ret) {
            System.out.println(i1);
        }
    }
    public static boolean isPrime(int x){
        if(x==2) return true;
        if(x==1) return false;
        for(int i=2;i<=Math.sqrt(x);i++){
            if(x%i==0) return false;
        }
        return true;
    }
}

C. CUIT_WIFI咋又断啦！！！

二分+双指针

  • 思路：为什么可以二分？
  • 首先，一定存在一个x，使得如果路由器的覆盖范围小于x，那么就不能够覆盖所有机房，
  • 如果大于x，能够覆盖所有的机房
  • 综上，具有二段性，所以可以二分。
  • check()函数：双指针，路由器能够覆盖一个机房的条件为:
  1. 该路由器的位置+x>=机房的位置
  2. 该路由器的位置-x<=机房的位置
  • 有了这两个条件值后，接下来
  1. 先遍历机房，如果当前路由器能覆盖该机房，遍历下一个机房
  2. 如果当前的路由器不能覆盖该机房，遍历下一个路由器
  3. 如果所有的路由器遍历完之后，但凡有一个机房都不能被覆盖，说明该距离x不成立。重新改变二分的区间。
    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
    import java.util.Arrays;
    import java.util.Scanner;
    public class questionC {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            // 机房的数量
            int n = sc.nextInt();
            // 路由器的数量
            int m = sc.nextInt();
            int[] houses=new int[n];
            int[] routers=new int[n];
            int idx=0;
            while(n>0){
                houses[idx]=sc.nextInt();
                n--;
                idx++;
            }
            idx=0;
            while(m>0){
                routers[idx]=sc.nextInt();
                m--;
                idx++;
            }
            Arrays.sort(routers);
            Arrays.sort(houses);
            // 1. 划分二分区间
            int l = 0, r = (int) 1e9;
            
            while(l<r){
                int mid=(l+r)/2;
                if(check(houses,routers,mid)) r=mid;
                else l=mid+1;
            }
            System.out.println(l);
        }
        // 查看当前的距离x能否满足要求
        public static boolean check(int[] houses,int[] routers,int x){
            int n = houses.length;
            int m = routers.length;
            for(int i=0,j=0;i<n && j<m;i++){
                while(j<m&&routers[j]+x<houses[i]) j++;
                if(j<m&&routers[j]+x>=houses[i] &&routers[j]-x<=houses[i]) continue;
                return false;
            }
            return true;
        }
    }

    捎上二分查找的板子

    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
    public class binarySearch {
        // 查找第一个大于等于元素的下标
        public void bsForFirstGT(int[] arr,int find){
            int l=0,r=arr.length-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(l==r) break;
                else if(arr[mid]<find) l=mid+1;
                else if(arr[mid]>=find) r=mid;
            }
            if(arr[l]>find) System.out.println("找不到该元素,但是第一个大于等于该元素的下表为 "+l);
            else if(arr[l]==find) System.out.println("该元素的下标"+l);
            else System.out.println("数组中的所有元素全部小于find");
        }

        // 找第一个大于元素的下标
        public void bsForFirstG(int[] arr,int find){
            int l=0,r=arr.length-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(l==r) break;
                else if(arr[mid]<=find) l=mid+1;
                else if(arr[mid]>find) r=mid;
            }
            if(arr[l]<=find) System.out.println("找不到第一个大于该元素的值");
            else System.out.println(l);
        }
        // 查找第一个小于等于元素的下标
        public void bsForLast(int[] arr,int find){
            int l=0,r=arr.length-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(l==r || l==r-1) break;
                else if(arr[mid]<=find) l=mid;
                else if(arr[mid]>find) r=mid-1;
            }
            if(arr[r]<=find) System.out.println(r);
            else System.out.println(l);
        }
    }

    G. 忙碌的大学生活

    • 这里提供三种解法

      1.哈希表+记忆化递归

  • 如果使用暴力递归会超时
  • 这里的话，我是用哈希表HashMap<Integer,Integer>存每个节点的最短路径，防止节点重复访问。其次，还要建立一个逆向的邻接表,例如，题干给的是从2到5的捷径，如果直接利用题干给的数组去构建邻接表，求出来的就是每个节点到最后一个节点的最短路径，但是此题求的是从起始节点0到其余各点的最短路径，所以要建立一个逆向邻接表,这里我采用ArrayList<Integer>[]进行存储.

  • 如图，假如捷径为0到2，2到4。根据学过的，递归其实是从栈顶往栈底走，走到4，然后返回。

  • 这里举个例子。如图,假如从0开始递归，先递归这样一条路径，0->2->4.当从栈顶4开始返回时，返回到2，因为2还有另外一条路径,也就是2->3->4,所以此时的思路也就是dfs这个函数里面的for循环，step=Math.min(dfs()).这个意思就是说会得到两条路径中的最小值，也就是比较2->3->4和2->4这两条路的最小值。毫无疑问，肯定是1.所以一旦遍历完了两条路径，就将2这个节点和它对应的路径放入哈希表，之后再访问到2时，就不用再去走这两条老路了.比如之后还有一条路径是0->1->2.当这条路径走到2时，直接返回1. 对应于代码中的 if(map.contains()) return;
    参考图

    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
    import java.util.*;
    public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int idx=0;
        int[] arr=new int[n];
        // 初始化
        while(n>0){
            arr[idx]=sc.nextInt();
            idx++;
            n--;
        }
        n=arr.length;
        ArrayList<Integer>[] lists=new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            lists[i]=new ArrayList<>();
        }
        // i+1代表当前节点
        for(int i=n-1;i>=0;i--){
            if(i+1==arr[i]||arr[i]==i+2){
                lists[i+1].add(i);
                continue;
            }
            lists[i+1].add(i);
            lists[arr[i]].add(i+1);
        }
        int[] dp=new int[n+1];
        // 递归
        dfs(n, lists);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            Integer node = entry.getKey();
            Integer dist = entry.getValue();
            dp[node]=dist;
        }
        for(int i=1;i<n;i++){
            System.out.print(dp[i]+" ");
        }
        System.out.print(dp[n]);
    }
    public static int dfs(int curNode, ArrayList<Integer>[] lists) {
        // 遍历到最后一个节点
        if (curNode == 0){
            return 0;
        }
        // 如果之前的哈希表已经
        if(map.containsKey(curNode)) return map.get(curNode);
        int step=lists.length+1;
        for (Integer neigh : lists[curNode]) {
            step = Math.min(step, dfs(neigh, lists) + 1);
        }
        map.put(curNode,step);
        return step;
    }
    }

    2. 区间dp

  • dp[i][j]的定义:从i到j的最短距离
  • 思路:仿照Dijtsra算法(这里感谢”工具人”给我提供的帮助),外层len从2到n，len的意思如下,当len=2,求dp[0][2],dp[1][3]，当len=3,求dp[0][3],dp[1][4]以此类推。
  • 状态转移方程，这里先附上我之前写错的转移方程dp[i][j]=Math.min(Math.min(dp[i+1][j]+1,dp[i][j-1]+1),dp[i][j]),这里其实还少了一层for循环，因为dp[i][j]不单单只能由dp[i+1][j],dp[i][j-1]转移得来.还可能由dp[i][k]+dp[k][j]以及dp[i][m]+dp[m][j]等等转移得来，所以还需要加一层for循环.
    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
    import java.util.*;
    public class Main {
        static HashMap<Integer, Integer> map = new HashMap<>();   // k:节点 v:到达n的最短步数
        static HashMap<Integer, List<Integer>> distan = new HashMap<>();
        // 区间dp
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int idx = 1;
            int[] arr = new int[n + 1];
            while (n > 0) {
                arr[idx] = sc.nextInt();
                idx++;
                n--;
            }
            n = arr.length;
            int[][] dp = new int[n][n];
            for (int i = 1; i < n; i++) {
                int dest = arr[i];
                dp[i][dest] = 1;
            }
            for (int i = 0; i < n - 1; i++) {
                dp[i][i + 1] = 1;
            }
            for (int len = 2; len < n; len++) {
                for (int l = 0; l + len < n; l++) {
                    int r = l + len;
                    if (dp[l][r] == 1) continue;
                    dp[l][r] = n + 1;
                    for (int x = l + 1; x < r; x++) {
                        dp[l][r] = Math.min(dp[l][x] + dp[x][r], dp[l][r]);
                    }
                }
            }
            for(int i=1;i<n-1;i++){
                System.out.print(dp[0][i] + " ");
            }
            System.out.print(dp[0][n-1]);
        }
    }

    3. 一维dp (参照”工具人”的解答)

    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
    import java.util.*;
    public class Main {
         //dp
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int n = sc.nextInt();
            int idx=1;
            int[] arr = new int[n+1];
            while(n>0){
                arr[idx]=sc.nextInt();
                idx++;
                n--;
            }
            n = arr.length;
            int[] dp=new int[n];
            Arrays.fill(dp,n+1);
            dp[0]=0;
            for(int i=1;i<n;i++){
                dp[i] = Math.min(dp[i - 1] + 1, dp[i]);
                dp[arr[i]]=Math.min(dp[i]+1,dp[arr[i]]);
            }
            for(int i=1;i<n;i++){
                System.out.println(dp[i]);
            }
        }
    }
    }

    leetcode上与G题相似的题目

    375题猜数字大小
    526题优美的排列
    494题目标和