题目描述

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

思路

其实思路也很简单，只要你知道归并排序是怎么做到的；简单来说，归并排序分为两步，划分，和归并；难点就在归并上，简单地说，归并时已经比较的在都在一9起，然后我们取两个来比较一下呗；
（5，7）与（4，6）正常归并肯定是从第一个开始，我们不要，我们从后往前来，比如说7>6 那么7也一定大于6之前的数；这样比较就很简单了；

more >>

题目描述

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

思路

1. 暴力法很好解得；
2. 你很容想到，遍历一遍记下出现的次数，由于字符不变，很容易也就想到了HashMap喽

   more >>

题目描述

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

思路

1. 第一反应肯定是暴力法呗；但是我们低估了丑数也不是那么多的；毕竟丑数相当于(2^x)(3^y)(5^z);所以数量级是非常大的；
2. 数组储存，这种方法书上说了半天也没看懂，还不如自己来呢；其实呢就相当于数组里已经存好了数，现在要加一个，这个数从哪里来的，其实就看当前，2为首，3为首，5为首他们的最新值谁最小；
   举个例子啊
   (2,3,4,5,6,8,9,10)
   4是怎么来的，之前的数组已经有2，3了，然后我们对于2，3，5，都给2乘一下；找到最小值；这时肯定知道不能是3对吧；那么2*2=4；此时这个2在乘以2的次数就消耗掉了；比如6来说，此时对于这个2，就只能乘以3，或者5得到最小值；这样我们最后也是可以得到数组的；

   more >>

题目描述

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

思路

1. 首先想到的是自然是暴力全拍列；
2. 然后想到了变成字符，通过Collections.sort()排序，后来发现，是数组；也就是说（3，32）只能组成332或者323；这个想法是不对的
3. 于是自然也就想到了，对每两个数变成string来比较，但是不会写。。。。然后就发现人家的代码是重写了sort方法，简单来说就是

   more >>

题目描述

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

思路

1. 暴力法，你可以对每一个数的每一位检查一下是否有1；
2. 暴力法，变成字符串，检查‘1’的个数；
3. 数学规律法

核心思路：

1.分别判断每一位上1出现过的次数，从个位往高位递推；


2.对于当前处理的位，需要根据其值是0,1，还是>1 对应有不同的处理。


    例如，假设当前考虑百位：


    (1 )如果百位>1,那么百位上1的次数 = (n/100 + 1) * 100;由高位和低位共同决定


    (2)如果百位=1，那么百位上1的数次 = (n/100) * 100 + (n%100 + 1)；由高位和低位共同决定


    (3)如果百位<1，那么百位上1的次数 = (n/100) * 100;由高位决定。

more >>