压缩字符串

题目：给定一组字符，使用原地算法将其压缩。压缩后的长度必须始终小于或等于原数组长度。数组的每个元素应该是长度为1 的字符（不是 int 整数类型）。在完成原地修改输入数组后，返回数组的新长度。

示例 1：
输入：
["a","a","b","b","c","c","c"]
输出：
返回6，输入数组的前6个字符应该是：["a","2","b","2","c","3"]
说明：
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
示例 2：
输入：
["a"]
输出：
返回1，输入数组的前1个字符应该是：["a"]
说明：
没有任何字符串被替代。
示例 3：
输入：
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
输出：
返回4，输入数组的前4个字符应该是：["a","b","1","2"]。
说明：
由于字符"a"不重复，所以不会被压缩。"bbbbbbbbbbbb"被“b12”替代。
注意每个数字在数组中都有它自己的位置。
进阶：
你能否仅使用O(1) 空间解决问题？
注意：
所有字符都有一个ASCII值在[35, 126]区间内。
1 <= len(chars) <= 1000。

思路：好吧，我真心觉得这道题很难，难得我脑阔痛。归根结底怪我想太多。写着写着觉得太磨叽了，是不是我想错思路了，然后在继续和看题解中挣扎半天，但是因为这道题是今天第一道题，最终还是咬咬牙自己做。看审题：首先重要是空间复杂度O(1)，所以就原地处理，什么map或者新数组存储肯定是不行了，还有提示数组长度小于1000。所以最大的连续字符不会超过一千，也就是只需要考虑百位数就可以了。虽然现在写完了性能也超过百分百，但是我还是觉得我自己写的有点墨迹。直接上代码吧

class Solution {
    public int compress(char[] chars) {
        int sum = 0;
        int index = 0;
        char temp = chars[0];
        for(int i = 0;i<chars.length;i++){
            if(temp==chars[i]){                
                sum++;
            }else{
                chars[index]=temp;
                index++;
                if(sum>1) {                   
                        if(sum/100!=0){
                            chars[index] = (char)(sum/100+'0');
                            index++;
                            sum = sum-(sum/100*100);
                            chars[index] = (char)(sum/10+'0');
                            index++;
                            sum = sum-(sum/10*10); 
                            chars[index] = (char)(sum+'0');
                            index++;
                        }else if(sum/10!=0){
                            chars[index] = (char)(sum/10+'0');
                            index++;
                            sum = sum-(sum/10*10); 
                            chars[index] = (char)(sum+'0');
                            index++;
                        }else{
                            chars[index] = (char)(sum+'0');
                            index++;
                        }                
                }
                temp= chars[i];                
                sum=1;
            }
        }
        chars[index] = chars[chars.length-1];
        // System.out.println(sum);
        if(sum>1) {    
            index++;               
            if(sum/100!=0){
                chars[index] = (char)(sum/100+'0');
                index++;
                sum = sum-(sum/100*100);
                chars[index] = (char)(sum/10+'0');
                index++;
                sum = sum-(sum/10*10); 
                chars[index] = (char)(sum+'0');
            }else if(sum/10!=0){
                chars[index] = (char)(sum/10+'0');
                index++;
                sum = sum-(sum/10*10); 
                chars[index] = (char)(sum+'0');
            }else{
                chars[index] = (char)(sum+'0');
            }                
        }      
        //index是下标，长度要+1
        return index+1;        
    }
}

其实主要逻辑分为：是否有相同字符连着，有则第一个输出。剩下的计数。
第二个逻辑是计数多少： 个十百位（长度原因不会有千位）要分开写，这个有点超出以前的习惯不能从小到大获取，必须从大到小获取。然后我上面的代码墨迹阶段主要就是这块。差不多的代码写了两遍，也是日狗了！
现在看了题解其实可以都放在循环里的，就是循环到数组外的一位。不过我当时确实是没想到。
现在看了下别人写的，逻辑差不多，而且我这里纯数字处理没用到字符串反而性能不错，至于代码墨迹还有的优化呢！估计都放到循环里就能好很多，我去试试。勉强算是优化完了，总之比之前的要好 ：

class Solution {
    public int compress(char[] chars) {
        int sum = 0;
        int index = 0;
        char temp = chars[0];
        for(int i = 0;i<=chars.length;i++){
            if(i==chars.length || temp!=chars[i] ){
                chars[index]=temp;
                index++;
                if(sum>1) {                   
                        if(sum/100!=0){
                            chars[index] = (char)(sum/100+'0');
                            index++;
                            sum = sum-(sum/100*100);
                            chars[index] = (char)(sum/10+'0');
                            index++;
                            sum = sum-(sum/10*10); 
                            chars[index] = (char)(sum+'0');
                            index++;
                        }else if(sum/10!=0){
                            chars[index] = (char)(sum/10+'0');
                            index++;
                            sum = sum-(sum/10*10); 
                            chars[index] = (char)(sum+'0');
                            index++;
                        }else{
                            chars[index] = (char)(sum+'0');
                            index++;
                        }                
                }
                if(i!=chars.length) temp= chars[i];                
                sum=1;
            }else{            
                sum++;
            }
        }
        return index;        
    }
}

下一题吧，优化的我心累。

回旋镖的数量

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

示例:
输入:[[0,0],[1,0],[2,0]]
输出:
2
解释:
两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

思路：这个有点抽象，我是用图理解题目的。大概通俗点理解：一个标往前扔多少能往后退双倍的。换言之从扔点开始，扔达点和回旋后的落脚点距离始发点是一样的。再换言之：两个点连线，如果线的中点也存在说明这是两个回旋镖（因为可以往前扔也可以往后扔。）
其实这道题的难点在于点和点的距离，很不直观。而且不容易算。这里用到了勾股定理的规律：将两个点 位移，计算出两个点的横坐标的差距和纵坐标的差距为两个直角边。而两个点的距离就是斜边了。（如果这两个点本身就在一条线上，那么另一个具体就是0，所以距离计算也是对的。）
能计算出两个点的距离也就能计算出一个点和其他所有点的距离。如果距离其中一个点的两个点距离相等，说明多了两个回旋镖（因为可以往两个方向扔）。如果具体一个点的三个点距离相等是多了六个回旋镖（自己画草图看看，三个可以1-2,1-3,2-3,2-1,3-2,3-1）。同样四个的话是n*(n-1)而不是简单的多两个。
一个点做中点可以扔的回旋镖数求出来，再把每一个点都累加一遍，这道题就做完了，讲真，我觉得这个不仅仅是简单难度的，接下来贴代码：

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        int res = 0;
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i = 0;i<points.length;i++){
            map.clear();
            for(int j = 0;j<points.length; j++){
                if(i==j){
                    continue;
                }
                //三角形两直角边平方和等于斜边平方和
                int d = (points[i][0] - points[j][0])*(points[i][0] - points[j][0])+(points[i][1]-points[j][1])*(points[i][1]-points[j][1]);
                if(map.containsKey(d)){
                    res += 2*map.get(d);
                    map.put(d,map.get(d)+1); 
                }else{
                    map.put(d,1);
                }
            }
        }
        return res;    
    }
}

下一题，不知道为什么，现在觉得每个题都贼难。。

找到所有数组中消失的数字

题目：给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]

思路：这个题说简单就是会编程就能做，说难是不使用额外空间切时间复杂度O（n）。目前思路是先排序再挨个判断哪个数字是被跳过的。我也不知道排序能不能用，反正第一思路是这样。
第一版代码出炉，我觉得今天可能早晨起床没带脑子，反正性能差的一批:

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        Arrays.sort(nums);
        int j = 1;
        List<Integer> res = new ArrayList<Integer>();
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==j){
                j++;
            }else if(i!=0 &&nums[i]==nums[i-1]){
                continue;
            }else{
                res.add(j);
                i --;
                j ++;
            }
        }
        for(int k = j;k<=nums.length;k++){
            res.add(k);
        }
        return res;
    }
}

其实逻辑说简单也简单。j是判断应该到了哪个数字。i是判断遍历到哪个数字。如果碰到相同的直接跳过，如果是正常的j正常++。如果遇到不是重复但是也不是应该有的数字说明这块有缺的了，先添加到list中，然后让j正常++。但是i得--这样下一次遍历还是判断这个数字是不是下一个。自觉哪怕是连着却的数字也能发现。
我总觉得我这么写肯定是忽略了什么省事的方法，因为这样空间复杂度满足了可是时间复杂度应该不是O（n）。我再想想思路。
看到了一种很秀的思路：把每一个出现的数字的数字位改成负数。然后遍历（判断的时候要取这个数的绝对值）。遍历一遍后数组中还是正数的位数说明缺这个数字（记得下标要+1才是位数）。
只能说真的秀！比什么鸽子原理什么的看着易懂还简单。我去试着写代码：

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for(int i=0;i<nums.length;i++){
            //一定要判断是不是大于0.不然一个数负两次，负负得正了
            if(nums[Math.abs(nums[i])-1]>0){
                nums[Math.abs(nums[i])-1] =  -nums[Math.abs(nums[i])-1];
            }          
        }
        List<Integer> res = new ArrayList<Integer>();
        for(int j=0;j<nums.length;j++){
            if(nums[j]>0){
                res.add(j+1);
            }
        }        
        return res;
    }
}

看了下性能靠前的代码，都是用了额外空间了，我还是下一题吧。

最小移动次数使数组相等

题目：给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。

示例:
输入:
[1,2,3]
输出:
3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]

思路：哎，现在别说思路了，审题都得审一会儿，反正大概思路就是每次最大的数不要动，其余的+1，一直加到所有数组元素都相等。我去理理思路。

我刚刚灵机一动！！！我觉得自己简直聪明绝顶了，所有除了最大元素+1.和最大元素-1.虽然数值不一样，但是本质上相等比较是一样！！！
所以每次最大元素减1.什么时候减到所有元素相等就行了！！！简直被我自己的机智感动哭了~~~完美测试通过，虽然性能不是那么好，但是真的挺无脑的，哈哈，这道题比想的简单多了。

class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        for(int i=0;i<nums.length;i++){
            res += nums[i]-nums[0];
        }
        return res;
    }
}

我发现我上面最大的失误就是sort排序，其实只要知道最小值就行了，没必要排序，所以这里用一个循环自己找出最小值比sort性能要好。

class Solution {
    public int minMoves(int[] nums) {
int min = nums[0];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (min > nums[i]) min = nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            res += nums[i] - min;
        }
        return res;
    }
}

这道题思路很顺，我觉得我还是喜欢晚上学习，比白天效率要高的多。

分发饼干

题目：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。注意：你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

示例 1:
输入: [1,2,3], [1,1]
输出: 1
解释
你有三个孩子和两块小饼干，3个孩子的胃口值分别是1 2 3
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2
输入: [1,2], [1,2,3]
输出: 2
解释:你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2.

思路：最麻烦的来说就是两个数组排序，从最小开始挨个比对（饼干小于孩子胃口就饼干往后，孩子不变），一直比对到饼干没有了。这个时候比过的孩子就是可以喂饱的孩子。
这只是一个初步的思路，具体的内容还要慢慢实现，我先去写代码。写完出来了，这个思路没问题，还很简单：

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s); 
        int lg = 0;
        int sg = 0;
        while(lg<g.length && sg<s.length){
            if(g[lg]<=s[sg]){
                lg++;
                sg++;
            }else {
                sg++;
            }
        }
        return  lg;
    }
}

就是如图，能满足则孩子饼干都往下走，不然孩子不走饼干走。
不知道是晚上做的题都简单还是说白天思路不好，一整个白天做了两道题，结果晚上一个多小时做了三道。哈哈。
今天的笔记就记录到这里了，如果稍微帮到你了记得点个喜欢点个关注呦~！也祝大家工作顺顺利利！