《数据结构与算法分析》第一章练习

2020-04-28

练习

1.1 编写一个程序解决选择问题。令k=N/2。画出表格显示程序对N种不同的值的运行时间。

是我理解有问题吗，这题就是return N/2 ？？？好吧看下一题

1.2 编写一个程序求解字谜游戏问题。

起点在“从”字的格子里，可以横向或纵向走到相邻的格子里，但不能走到对角的格子或其它位置。一直要走到“华”字结束。

要求走过的路线刚好构成“从我做起振兴中华”。一共有多少种可能的路线

这是一道2013年蓝桥杯JAVA B组的一个真题，以这个为例。先来分析一下，我们可以发现从起点开始只有向下和向右这两种方向才能组成“从我做起振兴中华”一共要走7步组成8个字，也就是说到达终点“华”字无论如何都需要向右走m-1步向下走n-1步（m = 5,n = 4），显然，这就是一个排列组合问题了，由排列数的计算公式：

$A^m_n=n(n-1)(n-2)...(n-m+1)=\frac{n!}{(n-m)!}(m\leq n,m,n\in N^*)$

得

$A^{m-1}_{n+m-2}$

因此我们只需要计算该公式就能得到正确结果。但是需要注意的是因为是阶乘运算，remp result很容易溢出。

public int kf(int m, int n){
        int temp = 1;
        int result = 1;

        for (int i = 1; i <= m-1 ; i++)
        {
            temp *= i;
        }
        for (int i = n; i <= m + n - 2; i++)
        {
            result *= i;
        }
        result = result / temp;
        return result;
    }

因为溢出问题（虽然这道题绰绰有余），所以这个方法在面对20x20，50x50甚至100x100的矩形时完全没有办法，因此有了另外两种解题方式DP（动态规划），递归法。

动态规划

从终点反推来看，一共有两个格子可以到达目的地“华”分别是当前行的上一个和当前列的上一个，如下图：

我们将整个表格看做一个二维数组dp，那么到达终点dp[m][n]的方法数等于到达当前行的上一个方法数 + 到达当前列的上一个方法数 dp[m-1][n] + dp[m][n-1]

由此我们得到了一个动态规划递推方程： dp[m-1][n] + dp[m][n-1]

public int kf(int m, int n){
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;   //初始化行及列
        for (int i = 0; i < n; i++) dp[0][i] = 1;
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }

1.5 编写一种递归方法，它返回数N的二进制表示中1的个数。利用这样的事实：如果N是奇数，那么其1的个数等于N/2的二进制表示中1的个数加1。

这道题常规写法是除以二取余分别获取每个二进制位数做一个统计，但是我不！

作为一个有追求的coder怎么能容忍如此低效🙉，于是想到了另一种方法位运算。可以通过计算其 a &= (a-1) 统计1的个数，以11D为例：

计算前：000 010 11

计算后：000 010 10
计算前：000 010 10

计算后：000 010 00
计算前：000 000 00

每进行一次运算，二进制中就少了一个1，所以我们可以使用以下方法统计：

int cont = 0;
  public int oneNum(int n){
      if (n <= 0){	//递归终止条件
          return cont;
      }
      n &= (n-1);
      cont++;
      return oneNum(n);
  }

1.6 编写带有下列声明的例程：

1
2
3

public void permute(String str);

private void permute(char[] str, int low, int higt);

第一个例程是个驱动程序，他调用第二个例程并显示String str中的字符的所有排列。如果str是”abc”，那么输出的串则是abc，acb，bac，bca，cab和cba。第二个例程使用递归。

依旧是全排列问题，先分析一下，以abc为例：

a开头的排列有：[a,b,c] ,[a,c,b]；
b开头的排列有：[b,a,c] ,[b,c,a]；
c开头的排列有：[c,a,b] ,[c,b,a];

由此我们可以将这些排列画成一棵根节点为[]的枚举树：

这棵树的叶子节点就是我们需要找的排列，我们要使用的方法就是深度优先遍历。顾名思义，深度优先遍历是选择一个节点一直走到最终的叶子节点回溯。而广度优先遍历则是优先选择相邻的节点。

used：标记某个字符是否被选中，以避免重复选取。

path：双端队列这里作为一个栈来使用，用来保存字符串的组合

Deque<Character> path = new ArrayDeque<>(); //定义一个双端队列
   boolean[] used;  //标记字符是否已经被选择
   int len = 0;    //字符串长度
   public void permute(String str){
       if (str.length() == 0){	//当字符串长度为0时return
           return;
       }
       len = str.length();
       used = new boolean[len];
       permute(str.toCharArray(),0,len);
   }


   private void permute(char[] str, int low, int higt){
       if (low == higt){	//递归终止条件
           System.out.println(path.toString());
       }
       for (int i = 0; i < higt; i++) {
           if (used[i]){   //已使用 跳出本次循环
               continue;
           }
           path.addLast(str[i]); //将数字添加path的末尾
           used[i] = true; //更改标识为已使用
           permute(str, low+1,higt);   //递归
           path.removeLast();  //回溯
           used[i] = false;
       }
   }

本篇blog结束。

本文阅读量