发表于 | 分类于

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

输入描述

1
2
3
4
5
题目保证输入的数组中没有的相同的数字
数据范围：
	对于%50的数据,size<=10^4
	对于%75的数据,size<=10^5
	对于%100的数据,size<=2*10^5

示例1

输入

1
1,2,3,4,5,6,7,0

输出

1
7

解题思路： 来自牛客网

归并排序

看到这个题目，我们的第一反应是顺序扫描整个数组。没扫描到一个数组的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成了一个逆序对。假设数组中含有n个数字。由于每个数字都要和O(n)这个数字比较，因此这个算法的时间复杂度为O(nn)。
我们以数组{7,5,6,4}为例来分析统计逆序对的过程。每次扫描到一个数字的时候，我们不拿ta和后面的每一个数字作比较，否则时间复杂度就是O(nn)，因此我们可以考虑先比较两个相邻的数字。

点击查看

(a) 把长度为4的数组分解成两个长度为2的子数组；
(b) 把长度为2的数组分解成两个成都为1的子数组；
(c) 把长度为1的子数组 合并、排序并统计逆序对 ；
(d) 把长度为2的子数组合并、排序，并统计逆序对；
在上图（a）和（b）中，我们先把数组分解成两个长度为2的子数组，再把这两个子数组分别拆成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7大于5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}、{4}中也有逆序对（6,4）。由于我们已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组 排序 如上图（c）所示， 以免在以后的统计过程中再重复统计。
接下来我们统计两个长度为2的子数组子数组之间的逆序对。合并子数组并统计逆序对的过程如下图如下图所示。
我们先用两个指针分别指向两个子数组的末尾，并每次比较两个指针指向的数字。如果第一个子数组中的数字大于第二个数组中的数字，则构成逆序对，并且逆序对的数目等于第二个子数组中剩余数字的个数，如下图（a）和（c）所示。如果第一个数组的数字小于或等于第二个数组中的数字，则不构成逆序对，如图b所示。每一次比较的时候，我们都把较大的数字从后面往前复制到一个辅助数组中，确保 辅助数组（记为copy） 中的数字是递增排序的。在把较大的数字复制到辅助数组之后，把对应的指针向前移动一位，接下来进行下一轮比较。

点击查看

过程：先把数组分割成子数组，先统计出子数组内部的逆序对的数目，然后再统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。如果对排序算法很熟悉，我们不难发现这个过程实际上就是归并排序。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Solution {
    
    private int InvertPairsHelper(int []data, int []copy, int lo, int hi){
        if(lo >= hi){
            return 0;
        }
        int len = (hi - lo) / 2;
        //进入递归的copy为无序，递归弹出栈的时候的，变为部分有序
        int left = InvertPairsHelper(copy, data, lo, lo+len) % 1000000007;
        int right = InvertPairsHelper(copy, data, lo+len+1, hi) % 1000000007;
        
        int cnt = 0;
        int i = lo+len;
        int j = hi;
        int indexCopy = hi;
        while(i >= lo && j >= lo+len+1){
            if(data[i] > data[j]){
                copy[indexCopy--] = data[i--];
                cnt += (j-lo-len);
                cnt %= 1000000007;
            }
            else{
                copy[indexCopy--] = data[j--];
            }
        }
        
        while(i >= lo){
            copy[indexCopy--] = data[i--];
        }
        
        while(j >= lo+len+1){
            copy[indexCopy--] = data[j--];
        }
        
        return (cnt + left + right) % 1000000007;
    }
    
    
    public int InversePairs(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        int []copy = new int[array.length];
        for(int i = 0; i < array.length; ++i){
            copy[i] = array[i];
        }
        return InvertPairsHelper(array, copy, 0, array.length-1);
    }
    
    
}

发表于 | 分类于

题目

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

解题思路

使用HashMap记录字符的出现次数

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
import java.util.HashMap;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if(str == null || str.length() == 0){
            return -1;
        }
        
        HashMap<Character, Integer> map = new HashMap<>(); 
        for(int i = 0; i < str.length(); ++i){
            char c = str.charAt(i);
            if(map.containsKey(c)){
                map.put(c, 1+map.get(c));
            }
            else{
				map.put(c, 1);
            }
        }
        for(int i = 0; i < str.length(); ++i){
            if(map.get(str.charAt(i)) == 1){
                return i;
            }
        }
        
        return -1;
    }
}

发表于 | 分类于

题目

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

解题思路

后面的丑数是由前面的丑数乘以2, 3或5得到的。

使用动态规划求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0){
            return 0;
        }
        
        int A[] = new int[index];
        A[0] = 1;
        int j = 0, k = 0, l = 0;
        for(int i = 1; i < index; ++i){
            A[i] = Math.min((Math.min(A[j]*2, A[k]*3)), A[l]*5);
            if(A[i] == A[j]*2){
                ++j;
            }
            if(A[i] == A[k]*3){
                ++k;
            }
            if(A[i] == A[l]*5){
                ++l;
            }
        }
        return A[index-1];
    }
}

发表于 | 分类于

题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

解题思路

将数组进行进行排序，排序方法是，先将两个Integer拼成String，再转成Integer进行比较，排序后的序列，拼成一个String就是最小数字。

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
37
38
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
		if(numbers == null || numbers.length == 0){
            return "";
        }
        
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < numbers.length; ++i){
            list.add(numbers[i]);
        }
        Collections.sort(list, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                String s1 = o1 + "" + o2;
                String s2 = o2 + "" + o1;
                if(Integer.valueOf(s1) < Integer.valueOf(s2)){
                    return -1;
                }
                else if(Integer.valueOf(s1) > Integer.valueOf(s2)){
                    return 1;
                }
                else{
                    return 0;
                }
            }
        });
        
        StringBuffer sb = new StringBuffer();
        for(Integer i : list){
            sb.append(String.valueOf(i));
        }
        return sb.toString();
    }
}

发表于 | 分类于

题目

求出1-13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

解题思路

这题可以使用数学知识解出，目前看不大懂，先贴个链接点击跳转

暴力解法：

遍历1-n，利用 x % 10，x / 10 的方法求解可得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
    	int cnt = 0; 
        for(int i = 1; i <= n; ++i){
            int x = i;
            while(x != 0){
                if(x % 10 == 1){
                    ++cnt;
                }
                x /= 10;
            }
        }
        return cnt;
    }
}

发表于 | 分类于

题目

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)

解题思路

一个max作为返回值，在数组未遍历完保存着当前最大的子数和。

一个temp作为试探值，
当temp <= 0 时，抛弃temp以前的值，重新计算子数和
当temp > 0 时， 将当前的array[i]加入子数和

temp 每次都和 max 比较，一旦temp大于max就可以更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array == null || array.length == 0){
            return -1;
        }
        int max = Integer.MIN_VALUE;
        int temp = 0;
        for(int i = 0; i < array.length; ++i){
            if(temp <= 0){
                temp = array[i];
            }
            else{
                temp += array[i];
            }
            
            if(max < temp){
                max = temp;
            }
        }
        return max;
    }
}

发表于 | 分类于

题目

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

解题思路

快速排序

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.ArrayList;
public class Solution {
    private void quickSort(int []A, int lo, int hi){
        if(lo >= hi){
            return ;
        }
        int pivot = partition(A, lo, hi);
        quickSort(A, lo, pivot-1);
        quickSort(A, pivot+1, hi);
    }
    
    private int partition(int []A, int lo, int hi){
		int pivot = lo;
        int i = lo;
        int j = ++hi;
        
        for( ; ; ){
        	//边界条件的判断
            while(i < hi && A[++i] < A[pivot]){}
            while(j > lo && A[--j] > A[pivot]){}
            if(i >= j){
                break;
            }
            swap(A, i, j);
        }
        swap(A, pivot, j);
        
        return j;
    }
    
    private void swap(int []A, int i, int j){
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
    
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input == null || input.length < k){
            return list;
        }
        quickSort(input, 0, input.length-1);
        
        for(int i = 0; i < k; ++i){
            list.add(input[i]);
        }
        return list;
    }
    
    
}

发表于 | 分类于

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路

O(n)时间复杂度：

a. 遍历数组，并找出num。通过更新cnt的值，记录num的值
b. 检查，确认num的值数数cnt的值

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
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        
        int num = array[0];
        int cnt = 1;
        for(int i = 1; i < array.length; ++i){
            if(array[i] == num){
                ++cnt;
            }
            else{
                --cnt;
                if(cnt == 0){
                    num = array[i];
                    cnt = 1;
                }
            }
        }
        
        cnt = 0;
        for(int i = 0; i < array.length; ++i){
            if(array[i] == num){
                ++cnt;
            }
        }
        if(cnt*2 > array.length){
            return num;
        }
        return 0;
    }
}

发表于

题目

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解题思路

输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a，b，c所能排列出来的所有字符串abc，acb，bac，bca，cab和cba

正常人的思维是，固定第一个字符，然后依次将后面的字符串与前面的交换，那么排列的个数就是除了第一个字符以外，其他字符的排列个数+1。

也就是固定一个字符串之后，之后再将问题变小，只需求出后面子串的排列个数就可以得出结果，当然第一时间想到的就是递归的算法了。

下面这张图很清楚的给出了递归的过程：

去重

由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不同，则需要交换，得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。

换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！

这样，我们得到在全排列中去掉重复的规则：
去重的全排列就是从第一个数字起，每个数分别与它后面非重复出现的数字交换。

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
37
38
39
40
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    private ArrayList<String> A = new ArrayList<>();
    private char []chars;
        
    private void PermutationHelper(int index){
        if(index == chars.length-1){
            A.add(new String(chars));
        }
        for(int i = index; i < chars.length; ++i){
        	//if条件句 去重操作
        	//第一次进入循环  i == index 总是成立
            if(i != index && chars[i] == chars[index]){
                continue;
            }
            swap(i, index);
            PermutationHelper(index+1);
            swap(i, index);
        }
    }
    
    private void swap(int i, int j){
        char x = chars[i];
        chars[i] = chars[j];
        chars[j] = x;
    }
        
    public ArrayList<String> Permutation(String str) {
        if(str == null || str.length() == 0){
            return A;
        }
        chars = str.toCharArray();
        PermutationHelper(0);
        Collections.sort(A);
        
        return A;
    }  
}

发表于 | 分类于

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

解题思路

递归实现，从链表的头部开始直到链表的尾部，即从BST的最左子树节点出发，到最右子树的节点

因为从子树节点递归返回到父节点，父节点是不是它的前作为当前链表的节点，并不清楚他的前节点应该左子树节点，右子树节点或者是空节点，所以设置了全局变量pre来作为先前节点。

在ConverHelper中，二叉树的中序遍历。

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
37
38
39
40
41
42
43
44
45
46
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    private TreeNode pre = null;
    
    private void ConvertHelper(TreeNode cur){
        if(cur == null){
            return;
        }
        ConvertHelper(cur.left);
        
        //设置双端指针
        cur.left = pre;
        if(pre != null){
            pre.right = cur;
        }
        pre = cur;
        
        ConvertHelper(cur.right);
    }
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        ConvertHelper(pRootOfTree);
        TreeNode pHead = pRootOfTree;
	
		//找链表的头结点
        while(pHead.left != null){
            pHead = pHead.left;
        }
        return pHead;
    }
}