《算法设计与分析》作业答案(转载自解凯华）

本文版权为原作者（解凯华）所有。

1.4

1.4.2

• Description: Modify ThreeSum to work properly even when the int values are so large that adding two of them might cause overflow.

• Solution:

  public class ThreeSum
  {
      public static int count(int[] a)
      {
          int N = a.length;
          int cnt = 0;
          for (int i = 0; i < N; i++)
              for (int j = i + 1; j < N; j++)
                  for (int k = j + 1; k < N; k++)
                      // 使用long类型避免溢出
                      if ((long) a[i] + a[j] + a[k] == 0)
                          cnt++;
          return cnt;
      }
  
      public static void main(String[] args)
      {
          int[] a = In.readInts(args[0]);
          StdOut.println(count(a));
      }
  }

1.4.5

• Description: Give tilde approximations for the following quantities:
  1. $N+1$
  2. $1+1/N$
  3. $(1+1/N)(1+2/N)$
  4. $2N^3-15N^2+N$
  5. $\lg(2N )/\lg N$
  6. $\lg(N^2+1)/\lg N$
  7. $N^{100}/2N$
• Solution:
  1. $N+1 \sim N$
  2. $1+1/N\sim 1$
  3. $(1+1/N)(1+2/N)\sim 1$
  4. $2N^3-15N^2+N\sim 2N^3$
  5. $\lg(2N )/\lg N=(\lg 2+\lg N)/\lg N\sim 1$
  6. $\lg(N^2+1)/\lg N\sim \lg(N^2)/\lg N =2$
  7. $N^{100}/2^N\sim 1/2^N$

1.4.6

• Description: Give the order of growth (as a function of N ) of the running times of each of the following code fragments:

  1. int sum = 0;
     for(int n = N; n > 0; n /= 2)
         for(int i = 0; i < n; i++)
             sum++;
     <!--code1-->
     
     

  2. int sum = 0;
     for (int i = 1; i < N; i *= 2)
         for (int j = 0; j < N; j++)
             sum++;
     <!--code2-->
     
     

1.4.15

• Description: Faster 3-sum. As a warmup, develop an implementation TwoSumFaster that uses a linear algorithm to count the pairs that sum to zero after the array is sorted (instead of the binary-search-based linearithmic algorithm). Then apply a similar idea to develop a quadratic algorithm for the 3-sum problem.

• Solution:

  • TwoSumFaster:
    先来考虑一个没有重复元素的有序数组，假定它是升序。考虑从头尾分别设立指针，双向遍历该数组。如果两数之和过大，欲使结果变小，只有左指针左移和右指针左移两种选择，但是左指针左侧的已经遍历过，所以只能左移右指针。两数之和过小同理。对于需要考虑重复元素的情形，处理起来会略微繁琐一点，但整体思路上一致。

    以指针移动次数作为基准，每次移动指针后，只进行了常数次操作，指针最多移动$N$次,故最坏情况下的时间复杂度为$\Theta(N)$

    不考虑重复元素的版本

    public static long twoSumFasterWithoutRepeat(int[] arr, int target)
    {
        return twoSumFasterWithoutRepeat(arr, target, 0, arr.length);
    }
    
    public static long twoSumFasterWithoutRepeat(int[] arr, int target, int begin, int end)
    {
        int left = begin;
        int right = end - 1;
        int count = 0;
        long sum;
        while (left < right)
        {
            sum = arr[left] + arr[right];
            if (sum == target)
            {
                count++;
                left++;
                right--;
            }
            else if (sum > target)
                right--;
            else
                left++;
        }
        return count;
    }

    考虑重复元素的版本

    public static long twoSumFaster(int[] arr, int target)
    {
        return twoSumFaster(arr, target, 0, arr.length);
    }
    // 在左闭右开区间中查找，即[begin, end)
    public static long twoSumFaster(int[] arr, int target, int begin, int end)
    {
        int left = begin;
        int right = end - 1;
        long count = 0;
        long lcount = 1;
        long rcount = 1;
        while (left < right)
        {
            if (arr[left] == arr[left + 1])
            {
                lcount++;
                left++;
                // 进入该分支说明left和right指向了相同的整数段，需要特判
                if (left == right && arr[left] * 2 == target)
                {
                    count += lcount * (lcount - 1) / 2;
                    lcount = 1;
                    continue;
                }
                continue;
            }
            if (arr[right] == arr[right - 1])
            {
                rcount++;
                right--;
                continue;
            }
    
            // 两数相等的情况
            if (arr[left] * 2 == target && lcount >= 2)
            {
                count += lcount * (lcount - 1) / 2;
                left++;
                lcount = 1;
                continue;
            }
            if (arr[right] * 2 == target && rcount >= 2)
            {
                count += rcount * (rcount - 1) / 2;
                right++;
                rcount = 1;
                continue;
            }
    
            // 两数不相等的情况
            int sum = arr[left] + arr[right];
            if (sum == target)
            {
                count += lcount * rcount;
                lcount = 1;
                rcount = 1;
                left++;
                right--;
            }
            else if (sum > target)
            {
                right--;
                rcount = 1;
            }
            else
            {
                left++;
                lcount = 1;
            }
        }
    
        return count;
    }

  • ThreeSumFaster:
    对于三数之和，只需要先遍历第一个数，剩下的两个数在第一个数的右侧部分选取，由于两数之和是$\Theta(N)$级别的算法，并且至多执行$N$次，排序算法的复杂度为$O(n\log n)$，故此处的三数之和是$O(N^2)$级别的算法

    public static long threeSumFaster(int[] arr, int target, int begin, int end)
    {
        Arrays.sort(arr);
        long count = 0;
        for (int i = begin; i < end - 2; i++)
            count += twoSumFaster(arr, target - arr[i], i + 1, end);
        return count;
    }
    
    public static long threeSumFaster(int[] arr, int target)
    {
        return threeSumFaster(arr, target, 0, arr.length);
    }
    
    public static long threeSumFaster(int[] arr)
    {
        return threeSumFaster(arr, 0);
    }

1.5

1.5.1

• Description: Show the contents of the id[] array and the number of times the array is accessed for each input pair when you use quick-find for the sequence 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2.

• Solution:

  • Initinitalize
    accessTimes=10

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	3	4	5	6	7	8	9

  • 9-0
    accessTimes=23

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	3	4	5	6	7	8	0

  • 3-4
    accessTimes=36

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	4	4	5	6	7	8	0

  • 5-8
    accessTimes=49

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	4	4	8	6	7	8	0

  • 7-2
    accessTimes=62

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	4	4	8	6	2	8	0

  • 2-1
    accessTimes=76

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	1	4	4	8	6	1	8	0

  • 5-7
    accessTimes=90

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	1	4	4	1	6	1	1	0

  • 0-3
    accessTimes=104

    node	0	1	2	3	4	5	6	7	8	9
    id	4	1	1	4	4	1	6	1	1	4

  • 4-2
    accessTimes=120

    node	0	1	2	3	4	5	6	7	8	9
    id	1	1	1	1	1	1	6	1	1	1

1.5.2

• Description: Do Exercise 1.5.1, but use quick-union (page 224). In addition, draw the forest of trees represented by the id[] array after each input pair is processed.

• Solution:

  • Initinitalize
    accessTimes=10

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	3	4	5	6	7	8	9

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    0---0
    1---1
    2---2
    3---3
    4---4
    5---5
    6---6
    7---7
    8---8
    9---9
    

  • 9-0
    accessTimes=13

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	3	4	5	6	7	8	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    0---0
    1---1
    2---2
    3---3
    4---4
    5---5
    6---6
    7---7
    8---8
    0---9
    

  • 3-4
    accessTimes=16

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	4	4	5	6	7	8	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    0---0
    1---1
    2---2
    4---3
    4---4
    5---5
    6---6
    7---7
    8---8
    0---9
    

  • 5-8
    accessTimes=19

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	4	4	8	6	7	8	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    0---0
    1---1
    2---2
    4---3
    4---4
    8---5
    6---6
    7---7
    8---8
    0---9
    

  • 7-2
    accessTimes=22

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	2	4	4	8	6	2	8	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    0---0
    1---1
    2---2
    4---3
    4---4
    8---5
    6---6
    2---7
    8---8
    0---9
    

  • 2-1
    accessTimes=25

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	1	4	4	8	6	2	8	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    0---0
    1---1
    1---2
    4---3
    4---4
    8---5
    6---6
    2---7
    8---8
    0---9
    

  • 5-7
    accessTimes=34

    node	0	1	2	3	4	5	6	7	8	9
    id	0	1	1	4	4	8	6	2	1	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    0---0
    1---1
    1---2
    4---3
    4---4
    8---5
    6---6
    2---7
    1---8
    0---9
    

  • 0-3
    accessTimes=39

    node	0	1	2	3	4	5	6	7	8	9
    id	4	1	1	4	4	8	6	2	1	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    4---0
    1---1
    1---2
    4---3
    4---4
    8---5
    6---6
    2---7
    1---8
    0---9
    

  • 4-2
    accessTimes=44

    node	0	1	2	3	4	5	6	7	8	9
    id	4	1	1	4	1	8	6	2	1	0

    graph TD;
    0((0))
    1((1))
    2((2))
    3((3))
    4((4))
    5((5))
    6((6))
    7((7))
    8((8))
    9((9))
    
    4---0
    1---1
    1---2
    4---3
    1---4
    8---5
    6---6
    2---7
    1---8
    0---9
    

1.5.3

• Description: Do Exercise 1.5.1, but use weighted quick-union (page 228).

• Solution:

• Initinitalize
  accessTimes=20

  node	0	1	2	3	4	5	6	7	8	9
  id	0	1	2	3	4	5	6	7	8	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  0---0
  1---1
  2---2
  3---3
  4---4
  5---5
  6---6
  7---7
  8---8
  9---9
  

• 9-0
  accessTimes=27

  node	0	1	2	3	4	5	6	7	8	9
  id	9	1	2	3	4	5	6	7	8	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  1---1
  2---2
  3---3
  4---4
  5---5
  6---6
  7---7
  8---8
  9---9
  

• 3-4
  accessTimes=34

  node	0	1	2	3	4	5	6	7	8	9
  id	9	1	2	3	3	5	6	7	8	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  1---1
  2---2
  3---3
  3---4
  5---5
  6---6
  7---7
  8---8
  9---9
  

• 5-8
  accessTimes=41

  node	0	1	2	3	4	5	6	7	8	9
  id	9	1	2	3	3	5	6	7	5	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  1---1
  2---2
  3---3
  3---4
  5---5
  6---6
  7---7
  5---8
  9---9
  

• 7-2
  accessTimes=48

  node	0	1	2	3	4	5	6	7	8	9
  id	9	1	7	3	3	5	6	7	5	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  1---1
  7---2
  3---3
  3---4
  5---5
  6---6
  7---7
  5---8
  9---9
  

• 2-1
  accessTimes=57

  node	0	1	2	3	4	5	6	7	8	9
  id	9	7	7	3	3	5	6	7	5	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  7---1
  7---2
  3---3
  3---4
  5---5
  6---6
  7---7
  5---8
  9---9
  

• 5-7
  accessTimes=64

  node	0	1	2	3	4	5	6	7	8	9
  id	9	7	7	3	3	7	6	7	5	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  7---1
  7---2
  3---3
  3---4
  7---5
  6---6
  7---7
  5---8
  9---9
  

• 0-3
  accessTimes=73

  node	0	1	2	3	4	5	6	7	8	9
  id	9	7	7	9	3	7	6	7	5	9

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  7---1
  7---2
  9---3
  3---4
  7---5
  6---6
  7---7
  5---8
  9---9
  

• 4-2
  accessTimes=86

  node	0	1	2	3	4	5	6	7	8	9
  id	9	7	7	9	3	7	6	7	5	7

  graph TD;
  0((0))
  1((1))
  2((2))
  3((3))
  4((4))
  5((5))
  6((6))
  7((7))
  8((8))
  9((9))
  
  9---0
  7---1
  7---2
  9---3
  3---4
  7---5
  6---6
  7---7
  5---8
  7---9