高行行的个人博客

/**
 * @Description https://www.youtube.com/watch?v=xxIpSooeZfQ
 * @Author Gao Hang Hang
 * @Date 2019-11-06 00:20
 **/
public class Solution {
    /*
    思路:
        bfs 广度优先
        left -> right 一旦 null，后面全 null
    时间复杂度：O(N)，因为遍历了二叉树
    空间复杂度：O(N)，使用Queue
     */
    public boolean isCompleteTree(TreeNode root) {
        // corner case
        if (root == null) return true;
        // 是否遇到过空节点，true：遇到过null，false：没遇到过null
        boolean end = false;
        Queue<TreeNode> q = new LinkedList<>();
        // offer 添加一个元素并返回true  如果队列已满，则返回false
        q.offer(root);
        while (!q.isEmpty()) {
            // left -> right
            TreeNode node = q.poll(); // poll 移除并返问队列头部的元素  如果队列为空，则返回null
            // null
            if (node == null) {
                end = true;
            } else { // not null
                if (end) return false;
                // 添加左节点
                q.offer(node.left);
                // 添加右节点
                q.offer(node.right);
            }
        }
        return true;
    }
}

@Service
public class UserServiceImpl implements UserService {
    @Override
    public User get(Long id) {
        try {Thread.sleep(1000L);} catch (InterruptedException e) {}
        /* mock a user*/
        User user = new User();
        user.setId(id);
        user.setEmail("lvyahui8@gmail.com");
        user.setUsername("lvyahui8");
        return user;
    }
}

@Service
public class PostServiceImpl implements PostService {
    @Override
    public List<Post> getPosts(Long userId) {
        try { Thread.sleep(1000L); } catch (InterruptedException e) {}
        Post post = new Post();
        post.setTitle("spring data aggregate example");
        post.setContent("No active profile set, falling back to default profiles");
        return Collections.singletonList(post);
    }
}

@Service
public class FollowServiceImpl implements FollowService {
    @Override
    public List<User> getFollowers(Long userId) {
        try { Thread.sleep(1000L); } catch (InterruptedException e) {}
        int size = 10;
        List<User> users = new ArrayList<>(size);
        for(int i = 0 ; i < size; i++) {
            User user = new User();
            user.setUsername("name"+i);
            user.setEmail("email"+i+"@fox.com");
            user.setId((long) i);
            users.add(user);
        };
        return users;
    }
}

@Component
public class UserQueryFacade {
    @Autowired
    private FollowService followService;
    @Autowired
    private PostService postService;
    @Autowired
    private UserService userService;

    public User getUserData(Long userId) {
        User user = userService.get(userId);
        user.setPosts(postService.getPosts(userId));
        user.setFollowers(followService.getFollowers(userId));
        return user;
    }
}

@Component
public class UserQueryFacade {
    @Autowired
    private FollowService followService;
    @Autowired
    private PostService postService;
    @Autowired
    private UserService userService;

    public User getUserDataByParallel(Long userId) throws InterruptedException, ExecutionException {
      	// 创建固定大小的线程池
        ExecutorService executorService = Executors.newFixedThreadPool(3);
      	// CountDownLatch类位于java.util.concurrent包下，利用它可以实现类似计数器的功能。比如有一个任务A，它要等待其他4个任务执行完毕之后才能执行，此时就可以利用CountDownLatch来实现这种功能了。
        CountDownLatch countDownLatch = new CountDownLatch(3); // 参数count为计数值
        Future<User> userFuture = executorService.submit(() -> {
            try{
                return userService.get(userId);
            }finally {
                countDownLatch.countDown();
            }
        });
        Future<List<Post>> postsFuture = executorService.submit(() -> {
            try{
                return postService.getPosts(userId);
            }finally {
                countDownLatch.countDown();
            }
        });
        Future<List<User>> followersFuture = executorService.submit(() -> {
            try{
                return followService.getFollowers(userId);
            }finally {
                countDownLatch.countDown();
            }
        });
      	// 使当前线程在锁存器倒计数至零之前一直等待，除非线程被中断。
        countDownLatch.await();
        User user = userFuture.get();
        user.setFollowers(followersFuture.get());
        user.setPosts(postsFuture.get());
        return user;
    }
}

public class Example {
    public static void sort(int[] a) {
        /* 请见算法2.1、算法2.second、算法2.3、算法2.4、算法2.5、算法2.6或算法2.7*/
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将它们排序并输出
        int[] a = {5, 6, 9, 1, 2, 3};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

/**
 * 时间复杂度: O(n^second)
 * 空间复杂度: O(n^second)
 * 稳定性: 不稳定
 * 复杂性: 简单
 *
 * @Description: 选择排序
 * @author: Gao Hang Hang
 * @date 2019/01/18 19:38
 */
public class Selection {
    public static void sort(int[] a) {
        // 将a[]按升序排列
        int N = a.length;           // 数组长度
        for (int i = 0; i < N; i++) {
            // 将a[i]和a[i+1..N]中最小的元素交换
            int min = i;
            for (int j = i + 1; j < N; j++)
                if (less(a[j], a[min])) min = j;
            exch(a, i, min);
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(int[] a) {
        // 在单行打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] nums = {6, 3, 5, 9, 1, 2};
        sort(nums);
        show(nums);
        System.out.println(isSorted(nums));
    }
}

/**
 * 时间复杂度: O(n^2)
 * 空间复杂度: O(n^2)
 * 稳定性: 稳定
 * 复杂性: 简单
 *
 * @Description: a2_插入排序
 * @author: Gao Hang Hang
 * @date 2019/01/02 12:04
 */
public class InsertSort {
    public static void sort(int[] a) {
        // 将a[]按升序排列
        int N = a.length;
        for (int i = 0; i < N; i++) {
            // 将 a[i] 插入到 a[i-1]、a[i-2]、a[i-3]...之中
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

/**
 * 时间复杂度: O(n^1.3)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 * 复杂性: 较复杂
 *
 * 思想: 先部分排序，再插入排序
 *
 * @Description: 希尔排序
 * @author: Gao Hang Hang
 * @date 2019/01/18 21:44
 */
public class Shell {
    public static void sort(int[] a) {
        // 将a[]按升序排列
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
        while (h >= 1) {
            // 将数组变为h有序
            for (int i = h; i < N; i++) {
                // 将a[i] 插入到a[i-h], a[i-second*h], a[i-3*h]... 之中
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3, 19};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

/**
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(n)
 * 稳定性: 稳定
 * 复杂性: 较复杂
 *
 * @Description:
 * @author: Gao Hang Hang
 * @date 2019/01/19 22:15
 */
public class Merge {

    private static int[] aux;      // 归并所需的辅助数组

    public static void sort(int[] a) {
        aux = new int[a.length];   // 一次性分配空间
        sort(a, 0, a.length - 1);
    }

    private static void sort(int[] a, int lo, int hi) {
        // 将数组a[lo..hi]排序
        if (hi <= lo) return;       // 边界条件
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid);            // 将左半边排序
        sort(a, mid + 1, hi);    // 将右半边排序
        merge(a, lo, mid, hi);       // 归并结果
    }

    public static void merge(int[] a, int lo, int mid, int hi) {
        // 将a[lo..mid] 和 a[mid+1..hi] 归并
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) // 将a[lo..hi]复制到aux[lo..hi]
            aux[k] = a[k];

        for (int k = lo; k <= hi; k++) { // 归并回到a[lo..hi]
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3, 19};
        sort(a);
        show(a);
    }
}

/**
 * 时间复杂度: O(nlogn)
 * 空间复杂度: O(logn)
 * 稳定性: 不稳定
 * 复杂性: 较复杂
 *
 * @Description: 快速排序
 * @author: Gao Hang Hang
 * @date 2019/01/19 22:43
 */
public class Quick {
    public static void sort(int[] a) {
        sort(a, 0, a.length -1);
    }

    private static void sort(int[] a, int lo, int hi) {
        if (hi <= lo) return;
        int j = prrtion(a, lo, hi);   // 切分
        sort(a, lo, j -1);        // 将左半边部分a[lo .. j-1]排序
        sort(a, j+1, hi);         // 将右半部分a[j+1 .. hi]排序
    }

    private static int prrtion(int[] a, int lo, int hi) {
        // 将数组切分为a[lo..i-1], a[i], a[i+1..hi]
        int i = lo, j = hi + 1; // 左右扫描指针
        int v = a[lo];          // 切分元素
        while (true) {
            // 扫描左右，检查扫描是否结束并交换元素
            while (less(a[++i], v)) if (i == hi) break;
            while (less(v, a[--j])) if (j == lo) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, lo, j);         // 将v = a[j]放入正确的位置
        return j;               // a[lo..j-1] <= a[j] <= a[j+1..hi] 达成
    }

    private static boolean less(int v, int w) {
        return v < w;
    }

    private static void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void show(int[] a) {
        // 在单行中打印数组
        for (int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println();
    }

    private static boolean isSorted(int[] a) {
        // 测试数组元素是否有序
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    public static void main(String[] args) {
        int[] a = {5, 6, 9, 1, 2, 3};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}