By

题目

一组整型数中，有一个数字重复3遍，其它数字重复2遍，请找出这个重复3遍的数字。比如：[88, 459, 5262, 88, -17, 677, 88, 677, -17, 459, 5262], 结果为88。要求程序代码中额外申请的空间为O(1)，请给出一个平均时间复杂度不大于O(nlogn)的算法。请首先用文字阐述答题思路，然后用Java程序实现。(阿里　2016)

解答１

  1. 两个相同的数异或（^）之后的值为０
  2. 将所有的数异或起来就可以消去相同的两个数
  3. 任意数和０异或都得到自身

代码１

1
2
3
4
5
6
7
public static int xorArray(int[] arr){
    int result = 0;
    for (int i : arr) {
        result ^= i;
    }
    return result;
}

测试用例如下：

1
2
3
4
5
@Test
public void testXorArray(){
    int[] arr = {88, 459, 5262, 88, -17, 677, 88, 677, -17, 459, 5262};
    assertEquals(88, xorArray(arr));
}

解答２

  1. 参考快速排序partition方法，将小于选中的数全部放在左边，大于或等于选中的数则放在右边。其中如果选中的数有多个，则最后一个数也必须是该数
  2. 如果小于当前数的个数是偶数，则待查找的数大于等于选中的数。如果最后一位数不等于选中的数，则表示选中的数只有一个，此时选中的数即为要查找的数；递归查找大于或等于选中的数（去掉两头的数）
  3. 如果小于当前数的个数是偶数，则待查找的数小于选中的数，递归查找所有小于选中的数

  4. 如果右边没有数字，即所有的数都小于选中的数，则该数即为要查找的数

    更多

By

如何禁止（disable）一个容器的所有行为（包括不响应任何事件）？

分析

  1. 一个容器还包括子容器，子容器也是需要禁止的，因此需要使用递归来解决。代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    /**
     * 改变一个容器及其子容器的enbale状态
     * @param container
     * @param enable　如果为false则Disable  容器
     */
    public static void enableComponents(Container container, boolean enable) {
        Component[] components = container.getComponents();
        for (Component component : components) {
            component.setEnabled(enable);
            if (component instanceof Container) {
                enableComponents((Container)component, enable);
            }
        }
    }

  2. disable一个容器并不会临时移除事件

    javadoc中的描述是：

    Enables or disables this component, depending on the value of the parameter b. An enabled component can respond
    to user input and generate events. Components are enabled initially by default.
    Note: Disabling a lightweight component does not prevent it from receiving MouseEvents.
    Note: Disabling a heavyweight container prevents all components in this container from receiving any input events.

    可以看到，disable一个容器并不会临时移除事件。此时有两种解决方案：

  • 移除所有事件。但如果以后还需要添加这些事件的话，需要保存这些事件，操作起来比较麻烦。
  • 在所有事件的处理方法开始时，添加判断isEnabled代码，如果为false则直接返回。代码如下：
    1
    2
    3
    if (!container.isEnabled()) {//确保panel被禁止时不处理事件。
        return;
    }

By

如何使JOptionPane.showMessageDialog 显示的信息分行显示且可复制?

分析

  1. 使用JTextArea，并将其设为不可编辑，使用其克复制功能
  2. 调用setLineWrap和setWrapStyleWord方法使JTextArea按单词计数分行显示
  3. 调用setHorizontalScrollBarPolicy(ScrollPaneConstants.HORIZONTAL_SCROLLBAR_NEVER)使得水平滑动按钮消失。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    /**
     * 显示错误信息提示框，以便提示用户错误信息
     * @param errorMsg 错误信息
     */
    public static void showErrorDialog(String errorMsg){
         // create a JTextArea
          JTextArea textArea = new JTextArea(6, 25);
          textArea.setText(errorMsg + ErrorMsg.SEE_ERROR_LOG );
          textArea.setEditable(false);
          textArea.setWrapStyleWord(true);
          textArea.setLineWrap(true);
          textArea.setCaretPosition(0);
           
          // wrap a scrollpane around it
          JScrollPane scrollPane = new JScrollPane(textArea);
          scrollPane.setHorizontalScrollBarPolicy(ScrollPaneConstants.HORIZONTAL_SCROLLBAR_NEVER);
//      String msg = CommonUtils.divideIntoMultiLines(errorMsg + ErrorMsg.SEE_ERROR_LOG, 20)  ;
          JOptionPane.showMessageDialog(null,scrollPane ,  "错误信息", JOptionPane.ERROR_MESSAGE);
    }

By

如何将一行太长的字符串分割成多行？

分析

首先我们需要考虑中文字符的情况，一个汉字 getBytes().length == 2

  1. 判断一个字符是否中文字符的方法如下：

    1
    2
    3
    public static boolean isChineseChar(char ch) throws UnsupportedEncodingException{
        return String.valueOf(ch).getBytes("GBK").length >1;
    }

  2. 遍历字符串，遇到英文字符计数加１，遇到中文字符计数加２。当计数大于或等于每行要求的字符数时，添加换行符并重置计数。

代码

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
/**
 * 将一行字符串以固定字节（非字符）长度分成多行显示。每行显示的字符至多为<code>numbersPerLine+1</code>
 * @param source　原字串
 * @param numbersPerLine 每行的字节数， 如果是负数，则看成无穷大，返回原字串
 * @return 在合适位置添加了换行符的字串
 * @throws UnsupportedEncodingException 
 */
public static String divideIntoMultiLines(String source,int numbersPerLine)
     throws UnsupportedEncodingException{
    if (null == source ) {
        return null;
    }
    
    int gbkLen = source.getBytes("GBK").length;
    if (gbkLen <= numbersPerLine || numbersPerLine <=0) {
        return source;
    }
    int  countOfLines = (gbkLen - 1) / numbersPerLine +1 ;
    StringBuilder sb = new StringBuilder(gbkLen + countOfLines-1);
    int count = 0;
    char ch;
    int len = source.length();
    for (int i = 0; i < len ; i++) {
        ch = source.charAt(i);
        count++;
        if (isChineseChar(ch)) {
            count++;//中文字符占两个字节
        }
        sb.append(ch);
        if (count >= numbersPerLine) {//完成一行分割
            count = 0 ;
            sb.append('\n');
        }
    }
    return sb.toString();
}

By

原文转载自Java 的swing.GroupLayout布局管理器的使用方法和实例

GroupLayout

  1. GroupLayout 是一个 LayoutManager，它将组件按层次分组，以决定它们在 Container 中的位置。GroupLayout 主要供生成器使用，但也可以手工编码。分组由 Group 类的实例来完成。GroupLayout 支持两种组。串行组 (sequential group) 按顺序一个接一个地放置其子元素。并行组 (parallel group) 能够以四种方式对齐其子元素。
  2. 每个组可以包含任意数量的元素，其中元素有 Group、Component 或间隙 (gap)。间隙可被视为一个具有最小大小、首选大小和最大大小的不可见组件。此外，GroupLayout 还支持其值取自 LayoutStyle 的首选间隙。
  3. GroupLayout是一个很重要的是额布局管理器，在jdk 1.6才加入，配合其它的管理器可以实现很好的界面。
  4. GroupLayout必须要设置它的GroupLayout.setHorizontalGroup和GroupLayout.setVerticalGroup。
  5. GroupLayout.setHorizontalGroup是指按照水平来确定，下面例子“账号”和“密码”是一个级别的，其它的组件也是一个级别的。详情请看代码
  6. GroupLayout.setVerticalGroup。是按照垂直来确定的。他们的级别是按照Group去设置组件的优先级别，级别越高就显示越上面。
  7. 添加顺序：GroupLayout.setHorizontalGroup(SequentialGroup(ParallelGroup(component))); 。大概就是按照这个顺序去添加,当然不是就这么简单设置，多个component添加到ParallelGroup，然后多个ParallelGroup添加到SequentialGroup里面，然后就设置到GroupLayout。

例子

  1. 程序效果
    需要实现的效果如下图：
    程序效果
  2. 程序分析
    下面的实例，设置GroupLayout.setHorizontalGroup，就是把2和4添加到一个ParallelGroup.addComponent(component)，其它1,3,5,6,7,8添加到另一个ParallelGroup，然后把这两个ParallelGroup按照顺序添加到SequentialGroup.addGrou(ParallelGroup);
    程序分析

代码

更多

By

题目

给定一个数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法：要求O（1）空间复杂度和O（n）的时间复杂度；除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）

解答

不能使用除法，那就不能直接全部做乘法再做除法。
b[j]=a[0]*a[1]…a[N-1] / a[j]，其实就是a中除去第j个数其他数相乘。
既然不能使用除法，就只能将整个式子分成两部分：a[0]*a[1]*...*a[j-1] 和 a[j+1]*a[j+2]*...*a[N-1]

  1. 首先构造第一部分
    令b[0] = 1 , b[j] = b[j-1]*a[j-1]
    b[1] = a[0]
    b[2] = a[0]*a[1]
    …
    b[j] = a[0]*a[1]*…*a[j-1]
    …
    b[n-1] = a[0]*a[1]*…*a[n-2]

  2. 然后开始构造第二部分
    因为初始都是从1开始构造，所以这次我们需要从后往后前构造。
    令b[0] = 1 , b[j] = b[0]*b[j] ，每次前进重新计算b[0]的值，作为临时变量 : b[0]= b[0]*a[j]

    b[n-1] = a[0]*a[1]*…*a[n-2]* 1 , b[0] = a[n-1]
    b[n-2] = a[0]*a[1]*…*a[n-3]* a[n-1] , b[0] = a[n-1]*a[n-2]
    b[n-3] = a[0]*a[1]*…*a[n-4]*a[n-2]* a[n-1] , b[0] = a[n-1]*a[n-2]*a[n-3]
    …
    b[j] = a[0]*a[1]*…*a[j-1].*a[j+1]* a[j+2]*..*a[n-2]* a[n-1] , b[0] = a[n-1]*a[n-2]*..*a[j]
    …
    b[1] = a[0]*a[2]*…*a[n-3]*a[n-2]* a[n-1], b[0] = a[n-1]*a[n-2]*..*a[1]

    此部分，每当计算b[j]时，b[0] = a[n-1]*a[n-2]*...a[j] ,正好是下一次需要计算的右边部分。
    此时，所有的b[j] 都满足 b[j]=a[0]*a[1]…a[N-1] / a[j]

    更多

By

题目

给你一个大于0的整数n，请输出一个n行n列的数据表，并且要满足以下规律（以n=10为例）

n行n列的数据表

解答

  1. 按圈遍历数组
    函数：int[][] genCycleMatrix(int rows, int columns)

    • 数字是按顺时针一圈一圈递增的，从1 开始 ；
    • 每一圈数字的开头都是方阵[n×n]对角线上的数字（[0,0],[1,1]…）,n = min（rows, columns），其中rows, columns分别为行数和列数
    • 一般情况下，一圈有两行两列，当行数或列数为奇数时，最后一圈会出现少行少列现象。故按圈打印数字的终止条件是start * 2 <n
      代码如下：
      1
      2
      3
      4
      int startNumber = 1;
      for (int start = 0; start * 2 < rows && start *2 < columns ;start++) {
          startNumber = genCycleMatrix(a, rows, columns, start, startNumber);
      }

  2. 遍历一圈数组，为依次遍历的元素赋值，并返回下一圈应该开始的数字
    函数：int genCycleMatrix(int[][] a, int rows, int columns , int start ,int startNumber)
    依次分四个方向从左到右，从上到下 ，从右到左 ，从下到上。
    相对于剑指Offer中花大篇幅讲的判断条件，其实可以先写出循环代码，再写满足循环的判断条件，这样就简单许多。
    需要注意的是后两个方向还需要添加条件start < endX .

    更多

By

题目

求1到100内，任取5个不同整数之和小于100的取法有多少中。列出主要思路即可。（新浪研发笔试）

解答

需要取5个不同整数，设为x1,x2,x3,x4,x5 (x1<x2<x3<x4<x5 且 x1+x2+x3+x4+x5<100) 。
由100 > x1+x2+x3+x4+x5 > x1+x1+x1+x1+x1 >5*x1 得 x1 <20
直接使用5重循环即可解决。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
long count = 0;
for (int x1 = 1; x1 < 20; x1++) {
    for (int x2 = x1+1; x2 <100; x2++) {
        for (int x3 = x2+1; x3 <100; x3++) {
            for (int x4 = x3+1; x4 <100; x4++) {
                for (int x5 = x4+1; x5 <100; x5++) {
                    if (x1+x2+x3+x4+x5 < 100) {
                        System.out.printf("%d %d %d %d %d \n",x1,x2,x3,x4,x5);
                        count++;
                    }
                }
            }
        }
    }
}
System.out.println(count);

By

  1. 一个整型数组中只有一个数字出现过一次，其他的出现两次，如何找出只出现一次的那个数字？
    解答： 异或运算有一个性质： 任何一个数字异或自己都等于0。
    如果我们将数组中的数字依次异或，最后得到的就是那个只出现一次的数字。

  2. 如果一个整型数组只有两个数字只出现一次，其余都出现两次呢？
    解答： 仿照刚刚的思路，将数组拆分成两个子数组：出现两次的数字需要出现在同一个子数组中，而两个只出现一次的数字分别出现在两个子数组中。
    可按如下步骤进行：

    • 将数组中的数字依次异或，最后得到的就是l两个只出现一次的数字的异或结果 a。
    • 记下a 中第一个为 1 的位的位置 n ，因为异或这一位的结果为1，所以两个只出现一次的数字在这一位分别为0和1，故可分到两组中。
      而出现两次的数字两个都将被分到同一组，因为他们的每一位都相同。
    • 分别将两个子数组中的所有数字都异或，即可得到两个只出现一次的数字

参考

[1]： 剑指Offer