测试打印算法

总结的笔试/面试算法题

2016-09-19  本文已影响983人  MigrationUK

目录

1. 栈和队列

1.用两个队列实现栈
2.用两个栈实现队列
3.实现一个栈,可以用常数级时间找出栈中的最小值
4.判断栈的压栈、弹栈序列是否合法

2. 链表

1.反转链表(使用递归和迭代两种解法,了解头插法)
2.删除链表的当前节点
3.删除倒数第 k 个节点
4.两个有序链表合并
5.判断链表是否有环
6.两个链表的第一个公共节点(提示:考虑链表有环的情况)
7.删除链表中重复节点

3. 树、二分

1.一个序列,它的形式是12349678,9是峰值,经历了一个上升又下降的过程,找出里面的最大值的位置O(logN)
2.深度优先遍历二叉树
3.广度优先遍历二叉树
4.前序遍历二叉树
5.中序遍历二叉树
6.输入一棵二叉树的根结点,求该树的深度
7.根据中序和后序遍历结果重建二叉树
8.根据中序和前序遍历结果重建二叉树
9.翻转二叉树
10.判断某个数组是不是二叉树的后序遍历结果
11.二叉树中和为某个值的路径
12.二叉树中某个节点的下一个节点

4. 递归、动态规划

1.股票买入卖出的最佳时间
2.递归方法求数组的最大值
3.背包问题
4.连续子数组的最大和
5.实现简单的正则表达式匹配

5.字符串

1.给一串字符串比如abbbcccd,输出a1b3c3d1,O(n)
2.例如输入字符串”I am a student. ”,则输出”student. a am I”
3.比如输入字符串”abcefg”和数字 2,该函数将返回左旋转 2 位得到的结”cdefab”
4.判断是否是回文字符
5.最长回文子串
6.最长无重复子串
7.字符串转数字
8.KMP 算法
9.字符串全排列
10.翻转字符串

6. 排序

1.归并排序、拓展:求数组中的逆序对个数
2.快速排序 重点:partion 函数的实现
3.堆排序
4.数组元素值域已知时,考虑 基数排序 和 桶排序

7. 大数据

1.海量N个数中求前M大个数(选择第M大数)

8. 数组、矩阵

1.回形,矩阵
2.蛇形矩阵
3.在排序数组中查找和为给定值的两个数字(思路)

9. 位运算

1.给一个十进制数字,求它的二进制表示中,有多少个 1 (n &= n - 1)
2.给一个数组,所有数字都出现了偶数次,只有一个出现了一次,找出这个数
3.给一个数组,所有数字都出现了三次,只有一个出现了一次,找出这个数
4.给一个数组,所有数组都出现了偶数次,只有两个数字出现了一次,找出这两个数

10. JAVA相关题

1.生产者/消费者(wait() / notify()方法)
2.生产者/消费者(await() / signal()方法)
3.生产者/消费者(BlockingQueue阻塞队列方法)
4.观察者设计模式

---持续跟新,欢迎纠错---
---【】数字越大问题越难---
--- 根据目录Ctrl C.V快速定位题解答---

栈和队列

  1. 【2】用两个队列实现栈
    public class TwoQueue {
      private LinkedList<String> queue1;
      private LinkedList<String> queue2;
    
    public TwoQueue(){
        queue1 = new LinkedList<String>();
        queue2 = new LinkedList<String>();
    }   
    public String pop(){
        String re =null;
        if(queue1.size() == 0 && queue2.size() == 0){
            return null;
        }
        if(queue2.size() == 0){
            while(queue1.size() >0){
                re = queue1.removeFirst();
                if(queue1.size() != 0){ //最后一个不存进去
                    queue2.addLast(re);
                }
            }
        }else if(queue1.size() == 0){
            while(queue2.size() >0){
                re = queue2.removeFirst();
                if(queue2.size()!=0){
                    queue1.addLast(re);
                }
            }
        }
        return re;
    }
    public String push(String str){
        if(queue1.size() ==0 && queue2.size() == 0){
            queue1.addLast(str);
        }
        if(queue1.size()!=0){
            queue1.addLast(str);
        }else if(queue2.size()!=0){
            queue2.addLast(str);
        }
        return str;
    }
    
  2. 【2】用两个栈实现队列
    class MList<T> {
      // 插入栈,只用于插入的数据
      private Stack<T> stack1 = new Stack<T>(); // 弹出栈,只用于弹出数据
      private Stack<T> stack2 = new Stack<T>();
    
    public MList() {
    }
    
    // 添加操作,入队
    public void appendTail(T t) {
        stack1.add(t);
    }
    
    // 删除操作,出队
    public T deleteHead() {
        // 先判断弹出栈是否为空,如果为空就将插入栈的所有数据弹出栈, // 并且将弹出的数据压入弹出栈中
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.add(stack1.pop());
            }
        }
        // 如果弹出栈中还没有数据就抛出异常
        if (stack2.isEmpty()) {
            throw new RuntimeException("No more element.");
        }
        // 返回弹出栈的栈顶元素,对应的就是队首元素。
        return stack2.pop();
      }
    }
    
  3. 【2】实现一个栈,可以用常数级时间找出栈中的最小值
  4. 【3】判断栈的压栈、弹栈序列是否合法

链表

  1. 【2】反转链表(使用递归和迭代两种解法,了解头插法)

    public static ListNode reverseList(ListNode head) {
       // 创建一个临时结点,当作尾插法的逻辑头结点
       ListNode root = new ListNode();
       // 逻辑头结点点的下一个结点为空
       root.next = null;
       // 用于记录要处理的下一个结点
       ListNode next;
       // 当前处理的结点不为空
       while (head != null) {
           // 记录要处理的下一个结点
           next = head.next;
           // 当前结点的下一个结点指向逻辑头结点的下一个结点
           head.next = root.next;
           // 逻辑头结点的下一个结点指向当前处理的结点
           root.next = head;
           // 上面操作完成了一个结点的头插
           // 当前结点指向下一个要处理的结点
           head = next;
       }
       // 逻辑头结点的下一个结点就是返回后的头结点
       return root.next;
    }
    
  2. 【3】删除链表的当前节点

  3. 【3】删除倒数第 k 个节点

    public static ListNode findKthToTail(ListNode head, int k) 
    { 
      // 输入的链表不能为空,并且k大于0
      if (k < 1 || head == null) {
        return null; 
    }
      // 指向头结点
      ListNode pointer = head;
      // 倒数第k个结点与倒数第一个结点相隔k-1个位置 // pointer先走k-1个位置
      for (int i = 1; i < k; i++) {
        // 说明还有结点
          if (pointer.next != null) {
            pointer = pointer.next; 
          }
        // 已经没有节点了,但是i还没有到达k-1说明k太大,链表中没有那么多的元素 
        else {
        // 返回结果
            return null; }
        }
        // pointer还没有走到链表的末尾,那么pointer和head一起走,
        // 当pointer走到最后一个结点即,pointer.next=null时,head就是倒数第k个结点 
      while (pointer.next != null) {
          head = head.next;
          pointer = pointer.next; 
      }
        // 返回结果
      return head; 
    }
    
  4. 【1】两个有序链表合并

  5. 【2*】判断链表是否有环

  6. 【3*】两个链表的第一个公共节点(提示:考虑链表有环的情况)

    public static ListNode findFirstCommonNode(ListNode head1, ListNode head2) {
        int length1 = getListLength(head1); 
        int length2 = getListLength(head2);
        int diff = length1 - length2;
        ListNode longListHead = head1;
        ListNode shortListHead = head2;
        if (diff < 0) {
            longListHead = head2;
            shortListHead = head1;
            diff = length2 - length1;
        }
        for (int i = 0; i < diff; i++) {
            longListHead = longListHead.next;
        }
        while (longListHead != null && shortListHead != null
                && longListHead != shortListHead) {
            longListHead = longListHead.next;
            shortListHead = shortListHead.next;
        }
        // 返回第一个相同的公共结点,如果没有返回null
        return longListHead;
    }
    
    private static int getListLength(ListNode head) {
        int result = 0;
        while (head != null) {
            result++;
            head = head.next;
        }
        return result;
    }
    
  7. 【3】删除链表中重复节点


树、二分

  1. 【2】一个序列,它的形式是12349678,9是峰值,经历了一个上升又下降的过程,找出里面的最大值的位置O(logN)

    public static int findPeakElement(int [] nums){
      if (nums.length ==1) 
          return 0;
      int low = 0, high = nums.length - 1, mid;
      while (low+1 < high) {
          mid = low + ((high - low) >> 1);
          if (nums[mid] < nums[mid - 1]) 
              high = mid;  //上坡
          else if (nums[mid] < nums[mid+1]) 
              low = mid;   //下坡
          else return mid;
      }
      return nums[low ] >nums[high] ?low:high;
    }
    
  2. 【2】深度优先遍历二叉树,其实就是前序遍历

      public void depthOrderTraversal(){
        if(root==null){
            System.out.println("empty tree");
            return;
        }       
        ArrayDeque<TreeNode> stack=new ArrayDeque<TreeNode>();
        stack.push(root);       
        while(stack.isEmpty()==false){
            TreeNode node=stack.pop();
            System.out.print(node.value+"    ");
            if(node.right!=null){
                stack.push(node.right);
            }
            if(node.left!=null){
                stack.push(node.left);
            }           
        }
        System.out.print("\n");
    }
    
  3. 【2】二叉树广度优先遍历

    public void levelOrderTraversal(){
    if(root==null){
        System.out.println("empty tree");
        return;
    }
    ArrayDeque<TreeNode> queue=new ArrayDeque<TreeNode>();
    queue.add(root);
    while(queue.isEmpty()==false){
        TreeNode node=queue.remove();  //从队头移除
        System.out.print(node.value+"    ");
        if(node.left!=null){
            queue.add(node.left);
        }
        if(node.right!=null){
            queue.add(node.right);
        }
    }
      System.out.print("\n");
    }
    
  4. 前序遍历二叉树

      public void preOrderTraverse1(TreeNoderoot){
      if(root!=null){
          System.out.print(root.val+"");
          preOrderTraverse1(root.left);
          preOrderTraverse1(root.right);
      }
    }
    //非递归
    public void preOrderTraverse2(TreeNoderoot){
      LinkedList<TreeNode>stack=newLinkedList<>();
      TreeNodepNode=root;
    while(pNode!=null||!stack.isEmpty()){
        if(pNode!=null){
           System.out.print(pNode.val+"");
          stack.push(pNode);
          pNode=pNode.left;
      }else{//pNode==null&&!stack.isEmpty()
          TreeNodenode=stack.pop();
          pNode=node.right;
        }
      }
    }
    
  5. 中序遍历二叉树

    public void inOrderTraverse1(TreeNoderoot){
    if(root!=null){
        inOrderTraverse1(root.left);
        System.out.print(root.val+"");
        inOrderTraverse1(root.right);
      }
    }
    //非递归
    public void inOrderTraverse2(TreeNoderoot){
    LinkedList<TreeNode>stack=newLinkedList<>();
    TreeNodepNode=root;
    while(pNode!=null||!stack.isEmpty()){
        if(pNode!=null){
            stack.push(pNode);
            pNode=pNode.left;
        }else{//pNode==null&&!stack.isEmpty()
            TreeNodenode=stack.pop();
            System.out.print(node.val+"");
            pNode=node.right;
        }
      }
    }
    
  6. 【2】输入一棵二叉树的根结点,求该树的深度

    public static int treeDepth(BinaryTreeNode root) {
      if (root == null) {
        return 0;
      }
      int left = treeDepth(root.left);
      int right = treeDepth(root.right);
      return left > right ? (left + 1) : (right + 1);
     }
    
  7. 【3】根据中序和后序遍历结果重建二叉树

  8. 【3】根据中序和前序遍历结果重建二叉树

    public static BinaryTreeNode construct(int[] preorder, int ps, int pe,
            int[] inorder, int is, int ie) {
        // 开始位置大于结束位置说明已经没有需要处理的元素了
        if (ps > pe) {
            return null;
        }
        // 取前序遍历的第一个数字,就是当前的根结点
        int value = preorder[ps];
        int index = is;
        // 在中序遍历的数组中找根结点的位置
        while (index <= ie && inorder[index] != value) {
            index++;
        }
        // 如果在整个中序遍历的数组中没有找到,说明输入的参数是不合法的,抛出异常
        if (index > ie) {
            throw new RuntimeException("Invalid input");
        }
        // 创建当前的根结点,并且为结点赋值
        BinaryTreeNode node = new BinaryTreeNode();
        node.value = value;
        // 递归构建当前根结点的左子树,左子树的元素个数:index-is+1个
        // 左子树对应的前序遍历的位置在[ps+1, ps+index-is]
        // 左子树对应的中序遍历的位置在[is, index-1]
        node.left = construct(preorder, ps + 1, ps + index - is, inorder, is,
                index - 1); // 递归构建当前根结点的右子树,右子树的元素个数:ie-index个
        // 右子树对应的前序遍历的位置在[ps+index-is+1, pe]
        // 右子树对应的中序遍历的位置在[index+1, ie]
        node.right = construct(preorder, ps + index - is + 1, pe, inorder,
                index + 1, ie); // 返回创建的根结点
        return node;
    }
    
  9. 【2】翻转二叉树

    public static void mirror(BinaryTreeNode node) { // 如果当前结点不为空则进行操作
      if (node != null) {
      // 下面是交换结点左右两个子树
      BinaryTreeNode tmp = node.left;
      node.left = node.right;
      node.right = tmp;
      // 对结点的左右两个子树进行处理
      mirror(node.left);
      mirror(node.right);
      }
    }
    
  10. 【3】判断某个数组是不是二叉树的后序遍历结果 (剑指 offer 第 24 题)

    public static boolean verifySequenceOfBST(int[] sequence, int start, int end) {
        // 如果对应要处理的数据只有一个或者已经没有数据要处理(start>end)就返回true
        if (start >= end) {
            return true;
        }
        // 从左向右找第一个不大于根结点(sequence[end])的元素的位置
        int index = start;
        while (index < end - 1 && sequence[index] < sequence[end]) {
            index++;
        }
        // 执行到此处[end, index-1]的元素都是小于根结点的(sequence[end]) // [end,
        // index-1]可以看作是根结点的左子树
        // right用于记录第一个不小于根结点的元素的位置
        int right = index;
        // 接下来要保证[index, end-1]的所有元素都是大于根根点的【A】
        // 因为[index, end-1]只有成为根结点的右子树
        // 从第一个不小于根结点的元素开始,找第一个不大于根结点的元素
        while (index < end - 1 && sequence[index] > sequence[end]) {
            index++;
        }
        // 如果【A】条件满足,那么一定有index=end-1,
        // 如果不满足那说明根结点的右子树[index, end-1]中有小于等于根结点的元素, // 不符合二叉搜索树的定义,返回false
        if (index != end - 1) {
            return false;
        }
        // 执行到此处说明直到目前为止,还是合法的 // [start, index-1]为根结点左子树的位置
        // [index, end-1]为根结点右子树的位置
        index = right;
        return verifySequenceOfBST(sequence, start, index - 1)
                    && verifySequenceOfBST(sequence, index, end - 1);
    }
    
  11. 【3】二叉树中和为某个值的路径

        public static void findPath(BinaryTreeNode root, int curSum,
        int expectedSum, List<Integer> result) {
        // 如果结点不为空就进行处理
        if (root != null) {
            // 加上当前结点的值
            curSum += root.value;
            // 将当前结点入队
            result.add(root.value);
            // 如果当前结点的值小于期望的和
            if (curSum < expectedSum) {
                // 递归处理左子树
                findPath(root.left, curSum, expectedSum, result);
                // 递归处理右子树
                findPath(root.right, curSum, expectedSum, result);
            }
            // 如果当前和与期望的和相等
            else if (curSum == expectedSum) {
                // 当前结点是叶结点,则输出结果
                if (root.left == null && root.right == null) {
                    System.out.println(result);
                }
            }
            // 移除当前结点,回溯吧
            result.remove(result.size() - 1);
        }
    }
    
  12. 【3*】二叉树中某个节点的下一个节点 (强烈推荐准备一下,剑指 offer 第 58 题)


递归、动态规划

  1. 股票买入卖出的最佳时间
     public int maxProfit(int num[]){
       int max=-1;
       int ans=-1;
       for(inti=len-1;i>=0;i--)
         if(num[i]>max)
           max=num[i];
         if(max-num[i]>ans)
           ans=max-num[i];
     return ans;
    }
    
  2. 【2】递归方法求数组的最大值
    int max(int arr[], int len) {
    if (1 == len){ // 只有一个元素
            return arr[0];
    }
    int a = arr[0]; // 第一个元素
    int b = max(arr + 1, len - 1); // 第二个元素起的最大值
    return a > b ? a : b;
    }
    
  3. 【2】背包问题
  4. 【3】连续子数组的最大和
  5. 【4】实现简单的正则表达式匹配

字符串

  1. 【2】给一串字符串比如abbbcccd,输出a1b3c3d1,O(n)

    public static void main(String[] args) {
        String str= "abbbcccd";
        int[] count= new int[256];
        for (int i = 0 ;i<str.length();i++) {
            count[str.charAt(i)]++;
        }
        for (int i = 0;i<256;i++) {
            if(count[i]>0){
                System.out.printf("%c%d",i,count[i]);
            }
        }
    }
    
  2. 【2】例如输入字符串”I am a student. ”,则输出”student. a am I”

    public static void reverse(char[] data, int start, int end) {
       if (data == null || data.length < 1 || start < 0 || end > data.length
               || start > end) {
           return;
       }
       while (start < end) {
           char tmp = data[start];
           data[start] = data[end];
           data[end] = tmp;
           start++;
           end--;
       }
    }
    
    public static char[] reverseSentence(char[] data) {
       if (data == null || data.length < 1) {
           return data;
       }
       reverse(data, 0, data.length - 1);// 首先全局逆转
       int start = 0;
       int end = 0;
       while (start < data.length) {
           if (data[start] == ' ') { // 排除开头空格
               start++;
               end++;
           } else if (end == data.length || data[end] == ' ') {// 单词结束边界
               reverse(data, start, end - 1);
               end++;
               start = end;
           } else {
               end++;
           }
       }
       return data;
    }
    
  3. 【2】比如输入字符串”abcefg”和数字 2,该函数将返回左旋转 2 位得到的结”cdefab”

    public static void reverse(char[] data, int start, int end) {
         if (data == null || data.length < 1 || start < 0 || end > data.length
                 || start > end) {
             return;
         }
         while (start < end) {
             char tmp = data[start];
             data[start] = data[end];
             data[end] = tmp;
             start++;
             end--;
         }
     }
         public static char[] leftRotateString(char[] data, int n) {
         if (data == null || n < 0 || n > data.length) {
             return data;
         }
         reverse(data, 0, data.length - 1);
         reverse(data, 0, data.length - n - 1);
         reverse(data, data.length - n, data.length - 1);
         return data;
     }
    
  4. 【2】java判断是否是回文字符

    public static boolean isPalidrome(Stringstr){
      char[] ch=str.toCharArray();
      int len=ch.length;
      for(inti=0,intj=len-1;i<=j;){
      if(ch[i++]==ch[j--]){
        }else{
          return false;
        }
      }
      return ture;
    }
    
  5. 【3】最长回文子串

  6. 【3】最长无重复子串

  7. 【1*】字符串转数字

  8. 【4】KMP 算法

  9. 【2】字符串全排列

    public static void permutation(char[] chars, int begin) { // 如果是最后一个元素了,就输出排列结果
        if (chars.length - 1 == begin) {
            System.out.print(new String(chars) + " ");
        } else {
            char tmp;
            // 对当前还未处理的字符串进行处理,每个字符都可以作为当前处理位置的元素
            for (int i = begin; i < chars.length; i++) {
                // 下面是交换元素的位置
                tmp = chars[begin];
                chars[begin] = chars[i];
                chars[i] = tmp;
                // 处理下一个位置
                permutation(chars, begin + 1);
                // 恢复
                tmp = chars[begin];
                chars[begin] = chars[i];
                chars[i] = tmp;
            }
        }
    }```
    
  10. 【2*】翻转字符串


排序

  1. 归并排序、拓展:求数组中的逆序对个数
  2. 快速排序 重点:partion 函数的实现
  3. 堆排序
  4. 数组元素值域已知时,考虑 基数排序 和 桶排序

大数据

1.【3】海量N个数中求前M大个数(选择第M大数)


数组、矩阵

  1. 回形矩阵
    public static void spiralOrderPrint(int[][] matrix) {
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            printEdge(matrix, tR++, tC++, dR--, dC--);
        }
    }
    
    public static void printEdge(int[][] m, int tR, int tC, int dR, int dC) {
        if (tR == dR) { // 子矩阵只有一行时
            for (int i = tC; i <= dC; i++) {
                System.out.print(m[tR][i] + " ");
            }
        } else if (tC == dC) { // 子矩阵只有一列时
            for (int i = tR; i <= dR; i++) {
                System.out.print(m[i][tC] + " ");
            }
        } else { // 一般情况
            int curC = tC;
            int curR = tR;
            while (curC != dC) {
                System.out.print(m[tR][curC] + " ");
                curC++;
            }
            while (curR != dR) {
                System.out.print(m[curR][dC] + " ");
                curR++;
            }
            while (curC != tC) {
                System.out.print(m[dR][curC] + " ");
                curC--;
            }
            while (curR != tR) {
                System.out.print(m[curR][tC] + " ");
                curR--;
            }
        }
    }```
    
  2. 蛇形矩阵
  3. 【2】在排序数组中查找和为给定值的两个数字(思路)
    1. 找到数组的第一个数字和最后一个数字。
    2. 当两个数字的和大于输入的数字时,把较大的数字往前移动;
    3. 当两个数字的和小于数字时,把较小的数字往后移动;
    4. 当相等时,输出等式。这样扫描的顺序是从数组的两端向数组的中间扫描。

位运算

  1. 【2】给一个十进制数字,求它的二进制表示中,有多少个 1 (n &= n - 1)
  2. 【3】给一个数组,所有数字都出现了偶数次,只有一个出现了一次,找出这个数
  3. 【4】给一个数组,所有数字都出现了三次,只有一个出现了一次,找出这个数
  4. 【3】给一个数组,所有数组都出现了偶数次,只有两个数字出现了一次,找出这两个数

JAVA相关题

  1. 【2】生产者/消费者(wait() / notify()方法)

    public class Storage {
    // 仓库最大存储量
    private final int MAX_SIZE = 100;
    // 仓库存储的载体
    private LinkedList<Object> list = new LinkedList<Object>();
    
    // 生产num个产品
    public void produce(int num) {
        // 同步代码段
        synchronized (list) {
            // 如果仓库剩余容量不足
            while (list.size() + num > MAX_SIZE) {
                try {
                    list.wait();    // 由于条件不满足,生产阻塞
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            // 生产条件满足情况下,生产num个产品
            for (int i = 1; i <= num; ++i) {
                list.add(new Object());
            }
            list.notifyAll();
        }
    }
    
    // 消费num个产品
    public void consume(int num) {
        // 同步代码段
        synchronized (list) {
            // 如果仓库存储量不足
            while (list.size() < num) {
                try {
                    list.wait();    // 由于条件不满足,消费阻塞
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
    
            // 消费条件满足情况下,消费num个产品
            for (int i = 1; i <= num; ++i) {
                list.remove();
            }
            list.notifyAll();
        }
    }
    }
    
  2. 【3】生产者/消费者(await() / signal()方法)

    public class Storage  {  
    // 仓库最大存储量  
    private final int MAX_SIZE = 100;  
    // 仓库存储的载体  
    private LinkedList<Object> list = new LinkedList<Object>();  
    // 锁  
    private final Lock lock = new ReentrantLock();  
    // 仓库满的条件变量  
    private final Condition full = lock.newCondition();  
    // 仓库空的条件变量  
    private final Condition empty = lock.newCondition();  
    
    // 生产num个产品  
    public void produce(int num)      {  
      // 获得锁  
      lock.lock();  
      // 如果仓库剩余容量不足  
      while (list.size() + num > MAX_SIZE)   {  
          try  {  
              full.await();   // 由于条件不满足,生产阻塞  
          }  
          catch (InterruptedException e)  {  
              e.printStackTrace();  
          }  
      }  
    
      // 生产条件满足情况下,生产num个产品  
      for (int i = 1; i <= num; ++i)    {  
          list.add(new Object());  
      }  
    
      // 唤醒其他所有线程  
      full.signalAll();  
      empty.signalAll();  
    
      // 释放锁  
      lock.unlock();  
    }  
    
    // 消费num个产品  
    public void consume(int num)  {  
      // 获得锁  
      lock.lock();  
    
      // 如果仓库存储量不足  
      while (list.size() < num)   {  
          try  {  
              empty.await();  // 由于条件不满足,消费阻塞  
          }  
          catch (InterruptedException e)   {  
              e.printStackTrace();  
          }  
      }  
    
      // 消费条件满足情况下,消费num个产品  
      for (int i = 1; i <= num; ++i)  {  
          list.remove();  
      }  
    
      // 唤醒其他所有线程  
      full.signalAll();  
      empty.signalAll();  
    
      // 释放锁  
      lock.unlock();  
    }  
    }
    
  3. 【2】生产者/消费者(BlockingQueue阻塞队列方法)

    public class Storage  
    {  
    // 仓库最大存储量  
    private final int MAX_SIZE = 100;  
    // 仓库存储的载体  
    private LinkedBlockingQueue<Object> list = new LinkedBlockingQueue<Object>(100);  
    
    // 生产num个产品  
    public void produce(int num)  {  
        // 如果仓库剩余容量为0  
        if (list.size() == MAX_SIZE)  {  
            System.out.println("暂时不能执行生产任务!");  
        }  
    
        // 生产条件满足情况下,生产num个产品  
        for (int i = 1; i <= num; ++i)  {  
            try  {  
                // 放入产品,自动阻塞  
                list.put(new Object());  
            }  
            catch (InterruptedException e)  {  
                e.printStackTrace();  
            }   
        }  
    }  
    
    // 消费num个产品  
    public void consume(int num)  
    {  
        // 如果仓库存储量不足  
        if (list.size() == 0)  {  
            System.out.println("暂时不能执行消费任务!");  
        }  
    
        // 消费条件满足情况下,消费num个产品  
        for (int i = 1; i <= num; ++i)  {  
            try  {  
                // 消费产品,自动阻塞  
                list.take();  
            }  
            catch (InterruptedException e)  {  
                e.printStackTrace();  
            }  
        }  
     }  
    } 
    
  4. 【3】观察者设计模式

     public class SimpleObservable extends Observable{    
     private int data = 0;    
     public int getData(){     
       return data;    
    }     
     public void setData(int i){    
       if(this.data != i) {   
          this.data = i;   
          setChanged();    
          //只有在setChange()被调用后,notifyObservers()才会去调用update(),否则什么都不干。  
          notifyObservers();      
       }    
     }    
    } 
    public class SimpleObserver implements Observer{    
     public SimpleObserver(SimpleObservable simpleObservable){    
      simpleObservable.addObserver(this );    
    }        
     public void update(Observable observable ,Object data){  // data为任意对象,用于传递参数  
      System.out.println(“Data has changed to” + (SimpleObservable)observable.getData());    
     }    
    } 
    public class SimpleTest{    
     public static void main(String[] args){    
      SimpleObservable doc = new SimpleObservable ();    
      SimpleObserver view = new SimpleObserver (doc);    
      doc.setData(1);    
      doc.setData(2);    
      doc.setData(2);    
      doc.setData(3);     
       }    
    }   
    
上一篇下一篇

猜你喜欢

热点阅读