产生所有排列--字典顺序

發表於 2015-10-31

编写一个程序，用字典顺序列出n个元素的所有排列(Permutation).

说明:
下面是一个n = 4，用字典顺序列出来的所有排列，一共为4! = 24个。
1234 2134 3124 4123
1243 2143 3142 4132
1324 2314 3214 4213
1342 2341 3241 4231
1423 2413 3412 4312
1432 2431 3421 4321

这里是一个递归的做法。看上面4! = 24个排列的第一列，它们的第一个元素都是1，第一列的最后一个是以1开头，用字典顺序排出来的最后，自然是1432.事实上，如果是n个元素的排列，以1开头的最后一个应该是1n(n-1)…432。下一列是2开头，把n(n-1)…432中最小的一个与第一个互换，也就是把倒数第一个与第一个互换，得到2n(n-1)..431，但这不是1n(n-1)…432的下一个，但是如果把后面的n - 1个元素反过来，就会得到2134…(n-1)n，是正确的顺序，于是进入第二列。

第二列的最后一个应该是2n(n-1)…431,把 n(n-1)…431中最小的与第一个互换，但因为1已经出现过了，所以把倒数第二个元素(自然是3)与第一个互换，得到3n(n-1)…421，再把后面的n - 1个元素反过来，得到3124…(n-1)n，就得到第三列的第一个。

第三列的最后一个是3n(n-1)…421, 把n(n-1)…421中最小的与第一个互换，但因为1，2已经出现过了，所以把倒数第3个元素(自然是4)与第一个互换，得到4n(n-1)…321，再将后面n - 1个反过来排，得到4123…(n - 1)n，正好是第4列的第一个元素。

于是我们可以得到一个递归的做法，从1234…n起，用一个递归的程序
1. i = n
2. 对后面n - 1个进行排列(递归的)
3. 把第i位与第1位互换
4. i减去1
5. 把后面的n - 1位反过来排
6. 回到第2步
当i到第一位时程序结束。

需要注意的一点是，排序结束后，数组元素的位置是逆置的，要保证不改变数组元素，我们需要将数组进行一个逆置。

package chapter3;

import java.util.ArrayList;
import java.util.List;

public class Permutions {
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums.length == 0)
            return result;
        permute(nums, 0, result);
        reverse(nums, 0, nums.length - 1); //after permutation, we need to reverse array
        return result;
    }
    public static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void reverse(int[] nums, int begin, int end) {
        while (begin < end) {
            swap(nums, begin, end);
            begin++;
            end--;
        }
    }
    public static void permute(int[] nums, int start, List<List<Integer>> result) {
        if (start == nums.length - 1) {
            List<Integer> temp = new ArrayList<Integer>();
            for (int i = 0; i < nums.length; i++) {
                temp.add(nums[i]);
            }
            result.add(temp);
            return;
        }
        int i = nums.length;
        while (i > start) {
            permute(nums, start + 1, result);
            swap(nums, start, i - 1);
            i--;
            if (i <= start)
                break;
            reverse(nums, start + 1, nums.length - 1);    
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        List<List<Integer>> result = permute(nums);
        for (List<Integer> list: result) {
            for (Integer i: list) {
                System.out.print(i);
            }
            System.out.println("");
        }
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

联系作者

N后问题递归解

By robinjia

發表於 2015-10-30

8后问题(Eight Queen Problem)是指在一个8 8的西洋棋盘上要如何放置8个皇后棋且不会互相吃到对方；皇后棋可以吃掉任何它所在的那一列、那一行，以及那两个对角线(米字形)上的任何棋子。请写一个程序，读入一个值n表示棋盘的大小，然后求出n n格棋盘上放n个皇后棋且不会相互吃掉对方的所有解答。

说明。这是广义的N后问题，因为所要求的是“所有”解答，而不单是其中的一组，对大多数会运用递归的人来说，这个题目反而容易做些。这一类型题目的揭发通常要用到回溯(Backtrack)的技巧–不管用递归还是不用递归都是如此，虽然会浪费时间，但多半会找到答案。

依据题意，写了一个递归的方法，判断是否能放置皇后时有点麻烦，应该有更简便的方法。

 import java.util.Arrays;

public class NQueens {
    public static int totalNQueens(int n) {
        boolean[][] board = new boolean[n][n];
        return totalNQueens(0, n, board);
    }
    //check if queen can put on board[row][col]
    private static boolean canPutCheck(int row, int col, int n, boolean[][] board) {
        for (int i = 0; i < n; i++) {
            if (board[row][i]) //row
                return false;
            if (board[i][col]) //col
                return false;
        }
        //diagonal
        int i = 0;
        while (row + i < n && col + i < n) {
            if (board[row + i][col +i])
                return false;
            i++;
        }
        i = 0;
        while (row - i >= 0 && col - i >= 0) {
            if (board[row - i][col - i])
                return false;
            i++;
        }
        //back diagonal
        i = 0;
        while (row + i < n && col - i >= 0) {
            if (board[row + i][col - i])
                return false;
            i++;
        }
        i = 0;
        while (row - i >= 0 && col + i < n) {
            if (board[row - i][col + i])
                return false;
            i++;
        }
        return true;

    }
    private static int totalNQueens(int row, int n, boolean[][] board) {
        if (row == n) { 
            return 1;
        }
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (canPutCheck(row, j, n, board)) {
                board[row][j] = true;
                count += totalNQueens(row + 1, n, board);
                board[row][j] = false; //backtrack
            }
        }
        return count;

    }
    public static void main(String[] args) {
        for (int i = 4; i < 10; i++)
            System.out.println(i + " " + totalNQueens(i));
    }
}

联系作者

产生Gray码

By robinjia

發表於 2015-10-29

编写一个程序，用Gray码(Gray Code)的顺序列出一个集合的所有子集。

什么是Gray码? nbit的Gray码是一连串共有2的n次方个元素的数列，每一个元素都有nbit,而且任何相邻的两个元素之间都只有1bit的值不同。例如，
两个bit的Gray码:
00 01 11 10 是一组Gray码
3个bit的Gray码:
000 001 011 010 110 111 101 100 是一组Gray码
但是Gray码并不是惟一的，把他循环排列或是用反过来的顺序写，也会得到一组Gray码；比如说，如果把3bitGray码的最后3个元素放在前面去，就会得到:
111 101 100 000 001 011 010 110 也是一组Gray码

产生Gray码的方法很多，这里这介绍其中一种。
将2bit Gray码列出
00
01
11
10
将3bit Gray码列出
000
001
011
010
110
111
101
100
观察3bit Gray码可以发现，它可以由2bit Gray码来得到。
3bit Gray码的前四个由2bit Gray码从第一个到最后一个在最前面的加上0得到
3bit Gray码的后四个可以将2bit Gray从最后一个到第一个在最前面加上1得到
写成代码如下

public class GrayCode {
    public static List<Integer> grayCode(int n) {
         List<Integer> result = new ArrayList<Integer>();
         if (n == 0) {
             result.add(0);
         } else {
             List<Integer> temp = grayCode(n-1);
             for (Integer i: temp) {
                 result.add(i);
             }
             for (int i = temp.size() - 1; i >= 0; i--) {
                 result.add(temp.get(i) + (1 << (n - 1)));
             }
         }
         return result;
    }
    public static void main(String[] args) {
        List<Integer> result = grayCode(1);
        for (Integer i: result) {
            System.out.println(i);
        }
    }
}

联系作者

查找矩阵

By robinjia

發表於 2015-10-29

已知一个m行n列的矩阵M,它的元素满足一个很特殊的性质，即任一元素M[i][j]都小于它右边与下方的元素(如果存在的话),换言之，M[i][j] < M[i][j + 1]且M[i][j] < M[i + 1][j]。如int[ ][ ] nums = { {1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};

现在有一个值K，编写一个程序，检查矩阵M中是否有K。

对于矩阵M，可以将它划分成两部分区域，一部分是小于等于K的区域，一部分是大于K的区域。沿着两部分区域的边界线查找K即可。

public class SearchaMatrix {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] > target) {
                j--;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                return true;
            }       
        }
        return false;
    }
    public static void main(String[] args) {
        int[][] nums = { {1, 4, 7, 11, 15},{2, 5, 8, 12, 19},{3, 6, 9, 16, 22},{10, 13, 14, 17, 24},{18, 21, 23, 26, 30}};
        System.out.println(searchMatrix(nums, 17));
    }
}

联系作者

最大连续元素和

By robinjia

發表於 2015-10-26

已知数组x[ ]储存了一组整数，请写一个程序，找出在数组中连续元素的和中最大的一个。举例而言，如果有数组1，2，-6，3，-2，4，-1，3，2，-4，那么连续的元素和有1 + 2 = 3，1 + 2 + (-6) = -3，2 + (-6) = -4，。。。，但最大的就是3 + (-2) + 4 + (-1) + 3 + 2这一段，值为9。这个题目通常叫做最大连续元素和问题，或者叫做最大连续子数组。

一个自然的办法是使用双重循环，但是性能不好。这个问题要求O(n)解法，需要动点脑筋。

public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        int result = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (sum < 0) {
                sum = 0;
            }
            sum += nums[i];
            result = Math.max(result, sum);
        }
        return result;      
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

还有一种是分治的方法，效率慢一些

public class MaximumSubarray {
    public static int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);    
    }
    public static int maxSubArray(int[] nums, int left, int right) {
        if (left > right) {
            return Integer.MIN_VALUE;
        } else if (left == right) {
            return nums[left];
        } else {
            int middle = (right - left) / 2 + left;
            int leftMax = maxSubArray(nums, left, middle);
            int rightMax = maxSubArray(nums, middle + 1, right);
            int sum = 0;
            int maxToLeft = Integer.MIN_VALUE;
            for (int i = middle; i >= left; i--) {
                sum += nums[i];
                maxToLeft = Math.max(maxToLeft, sum);
            }
            sum = 0;
            int maxToRight = Integer.MIN_VALUE;
            for (int i = middle + 1; i <= right; i++) {
                sum += nums[i];
                maxToRight = Math.max(maxToRight, sum);
            }
            int result = maxToLeft + maxToRight;
            result = Math.max(result, leftMax);
            result = Math.max(result, rightMax);
            return result;
        }
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, -6, 3, -2, 4, -1, 3, 2, -4};
        System.out.println(maxSubArray(nums));
    }
}

联系作者

等值首尾和

By robinjia

發表於 2015-10-22

假设有一个数组x[ ], 它有n个元素，每一个都大于零，称x[0] + x[1] + … + x[i]为前置和(Prefix Sum),而 x[j] + x[j + 1] + … + x[n - 1]为后置和(Suffix Sum)。试编写一个程序，求出x[ ] 中有多少组相同的前置和与后置和。

说明
如果x[ ] 的元素是3，6，2，1，4，5，2，则x[ ]的前置和有一下7个，即3，9，11，12，16，21，23；后置和则是2，7，11，12，14，20，23；于是11，12，与23这3对就是值相同的前置和与后置和，因为：
11 = 3 + 6 + 2(前置和) = 2 + 5 + 4 (后置和)
12 = 3 + 6 + 2 + 1(前置和) = 2 + 5 + 4 + 1 (后置和)
因为23是整个数组元素的和，因此前置和与后置和一定相同。

可以用变量prefix来表示前置和，用suffix来表示后置和，用i表示前置和累加元素的位置，i从前往后加，用j表示后置和累加元素的位置, j从后往前加。当prefix > suffix时，累加后置和，也就是j向前走；当prefix < suffix时，累加前置和，也就是i往后走；当prefix == suffix时，同时累加前置和与后置和，也就是i往后走，j往前走

public class HeadTail {
    public static int headTail(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        int prefix = 0;
        int suffix = 0;
        int result = 0;
        while (i < nums.length && j >= 0) {
            System.out.println(prefix + " " + suffix + " " + i + " " + j);
            if (prefix == suffix) {        
                prefix += nums[i++];
                suffix += nums[j--];
                result++;
            } else if (prefix > suffix) {
                suffix += nums[j--];
            } else {            
                prefix += nums[i++];
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums = {3, 6, 2, 1, 4, 5, 2};
        System.out.println(headTail(nums));
    }
}

联系作者

两数组最短距离

By robinjia

發表於 2015-10-22

已知两个元素从小到大排列的数组x[]与y[],请编写一个程序算出两个数组元素彼此之间差的绝对值最小的一个树，此值称为数组的距离。

说明：如果x[i]与y[i]是两个元素，那么 |x[i] - y[i]| 就是这两个元素之间的距离，所有这些距离的最小值，称为数组的距离。比如说x[]有1，3，5，7，9， y[]有2，6，8，那么最短距离就是1，因为x[0]与y[0]、 x[1]与y[0]、x[2]与y[1]、x[3]与y[1]、还有x[4]与y[2]的距离都是1。

依然是利用数组已经排好序的特性。

public class MinDist {
    public static int minDist(int[] x, int[] y) {
        int result = Integer.MAX_VALUE;
        int i = 0;
        int j = 0;
        while (i < x.length && j < y.length) {    
            if (x[i] >= y[j]) {
                result = Math.min(result, x[i] - y[j]);
                j++;
            } else {
                result = Math.min(result, y[j] - x[i]);
                i++;
            }    
        }
        return result;
    }
    public static void main(String[] args) {
        int[] x = {1, 3, 5, 7, 9};
        int[] y = {2, 6, 8};
        System.out.println(minDist(x, y));
    }
}

联系作者

等值数目

By robinjia

發表於 2015-10-22

已知两个整数数组f[]与g[]，它们的元素都已经从小到大排列好，而且两个数组中的元素都各不相同。例如，f[]中有1,3,4,7,9,而g[]中有3,5,7,8,10。试编写程序算出这两个数组之间有多少组相同的元素。

就上例而言，f[2]和g[1]为3是一组；f[3]与g[2]为7是第二组

依然是利用已经排好序的这个特性。

public class EQCount {
    public static int eqCount(int[] f, int[] g) {
        int i = 0;
        int j = 0;
        int result = 0;
        while (i < f.length && j < g.length) {
            if (f[i] == g[j]) {
                i++;
                j++;
                result++;
            } else if (f[i] > g[j]) {
                j++;
            } else {
                i++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] f = {1, 3, 4, 7, 9};
        int[] g = {3, 5, 7, 8, 10};
        System.out.println(eqCount(f, g));
    }
}

联系作者

支配值数目

By robinjia

發表於 2015-10-22

已知f[]与g[]两个整数数组，元素已经从小到大排列，请写一个程序，算出f[]中比g[]元素大的对数。换句话说，f[0]比g[]中多少个元素大，f[1]比g[]中多少元素大等，这些值的总和就是要求的答案。

例如，如果f[]中有1，3，5，7，9，而g[]中有2，3，4，7，8，比g[0]大的有f[1]~f[4], 比g[1]大的有f[2]~f[4]，比g[2]大的有f[2]~f[4]，比g[3]大的有f[4]，比g[4]大的有f[4]，因此答案是4 + 3 + 3 + 1 + 1 = 12

利用数组已经排好序的这个特性，可以写出高效的程序.

public class GTCount {
    public static int gtCount(int[] f, int[] g) {
        int i = 0;
        int j = 0;
        int result = 0;
        while (i < f.length && j < g.length) {
            if (f[i] > g[j]) {
                result += f.length - i;
                j++;
            } else {
                i++;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int[] f = {1, 3, 5, 7, 9};
        int[] g = {2, 3, 4, 7, 8};
        System.out.println(gtCount(f, g));
    }
}

联系作者

最长平台

By robinjia

發表於 2015-10-22

最近又把冼镜光的《C语言名题精选百则–技巧篇》拿出来看看，确实不错。

已知一个已经从小到大排序的数组，这个数组中的一个平台(plateau) 就是连续的一串相同的元素，并且这一串元素不能再延伸。例如，在1，2，2，3，3，3，4，5，5，6中1，2.2，3.3.3，4，5.5，6都是平台。试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。在上面的例子中，3.3.3就是该数组的最长平台。
这个问题曾经困扰过计算机科学家David Gries，他给出的方法如下

public class Pleateau {
    public static int pleateau(int[] nums) {
        int length = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - length]) {
                length++;
            }
        }
        return length;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6};
        System.out.println(pleateau(nums));
    }
}

自己想到的方法如下

public class Pleateau {
    public static int pleateau(int[] nums) {
        int length = 1;
        int i = 0;
        while (i + length < nums.length) {
            if (nums[i] == nums[i + length]) {
                length++;
            } else {
                i += length;
                while (i < nums.length && i > 0 &&  nums[i] == nums[i - 1]) {
                    i--;
                }
            }
        }
        return length;
    }
    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6};
        System.out.println(pleateau(nums));
    }
}

阿龙的学习笔记

兼济天下则达,独善其身则穷

产生所有排列--字典顺序

联系作者

N后问题递归解

联系作者

产生Gray码

联系作者

查找矩阵

联系作者

最大连续元素和

联系作者

等值首尾和

联系作者

两数组最短距离

联系作者

等值数目

联系作者

支配值数目

联系作者

最长平台

联系作者