壓縮字符串
題目：給定一組字符，使用原地算法將其壓縮。壓縮后的長度必須始終小于或等于原數(shù)組長度。數(shù)組的每個(gè)元素應(yīng)該是長度為1 的字符（不是 int 整數(shù)類型）。在完成原地修改輸入數(shù)組后，返回?cái)?shù)組的新長度。
示例 1：
輸入：
["a","a","b","b","c","c","c"]
輸出：
返回6，輸入數(shù)組的前6個(gè)字符應(yīng)該是：["a","2","b","2","c","3"]
說明：
"aa"被"a2"替代。"bb"被"b2"替代。"ccc"被"c3"替代。
示例 2：
輸入：
["a"]
輸出：
返回1，輸入數(shù)組的前1個(gè)字符應(yīng)該是：["a"]
說明：
沒有任何字符串被替代。
示例 3：
輸入：
["a","b","b","b","b","b","b","b","b","b","b","b","b"]
輸出：
返回4，輸入數(shù)組的前4個(gè)字符應(yīng)該是：["a","b","1","2"]。
說明：
由于字符"a"不重復(fù)，所以不會(huì)被壓縮。"bbbbbbbbbbbb"被“b12”替代。
注意每個(gè)數(shù)字在數(shù)組中都有它自己的位置。
進(jìn)階：
你能否僅使用O(1) 空間解決問題？
注意：
所有字符都有一個(gè)ASCII值在[35, 126]區(qū)間內(nèi)。
1 <= len(chars) <= 1000。
思路：好吧，我真心覺得這道題很難，難得我腦闊痛。歸根結(jié)底怪我想太多。寫著寫著覺得太磨嘰了，是不是我想錯(cuò)思路了，然后在繼續(xù)和看題解中掙扎半天，但是因?yàn)檫@道題是今天第一道題，最終還是咬咬牙自己做。看審題：首先重要是空間復(fù)雜度O(1)，所以就原地處理，什么map或者新數(shù)組存儲(chǔ)肯定是不行了，還有提示數(shù)組長度小于1000。所以最大的連續(xù)字符不會(huì)超過一千，也就是只需要考慮百位數(shù)就可以了。雖然現(xiàn)在寫完了性能也超過百分百，但是我還是覺得我自己寫的有點(diǎn)墨跡。直接上代碼吧
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是下標(biāo)，長度要+1
return index+1;
}
}
其實(shí)主要邏輯分為：是否有相同字符連著，有則第一個(gè)輸出。剩下的計(jì)數(shù)。
第二個(gè)邏輯是計(jì)數(shù)多少： 個(gè)十百位（長度原因不會(huì)有千位）要分開寫，這個(gè)有點(diǎn)超出以前的習(xí)慣不能從小到大獲取，必須從大到小獲取。然后我上面的代碼墨跡階段主要就是這塊。差不多的代碼寫了兩遍，也是日狗了！
現(xiàn)在看了題解其實(shí)可以都放在循環(huán)里的，就是循環(huán)到數(shù)組外的一位。不過我當(dāng)時(shí)確實(shí)是沒想到。
現(xiàn)在看了下別人寫的，邏輯差不多，而且我這里純數(shù)字處理沒用到字符串反而性能不錯(cuò)，至于代碼墨跡還有的優(yōu)化呢！估計(jì)都放到循環(huán)里就能好很多，我去試試。勉強(qiáng)算是優(yōu)化完了，總之比之前的要好 ：
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;
}
}
下一題吧，優(yōu)化的我心累。
回旋鏢的數(shù)量
給定平面上 n 對(duì)不同的點(diǎn)，“回旋鏢” 是由點(diǎn)表示的元組 (i, j, k) ，其中 i 和 j 之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序）。找到所有回旋鏢的數(shù)量。你可以假設(shè) n 最大為 500，所有點(diǎn)的坐標(biāo)在閉區(qū)間 [-10000, 10000] 中。
示例:
輸入:[[0,0],[1,0],[2,0]]
輸出:
2
解釋:
兩個(gè)回旋鏢為 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]
思路：這個(gè)有點(diǎn)抽象，我是用圖理解題目的。大概通俗點(diǎn)理解：一個(gè)標(biāo)往前扔多少能往后退雙倍的。換言之從扔點(diǎn)開始，扔達(dá)點(diǎn)和回旋后的落腳點(diǎn)距離始發(fā)點(diǎn)是一樣的。再換言之：兩個(gè)點(diǎn)連線，如果線的中點(diǎn)也存在說明這是兩個(gè)回旋鏢（因?yàn)榭梢酝叭右部梢酝笕?。?/strong>
其實(shí)這道題的難點(diǎn)在于點(diǎn)和點(diǎn)的距離，很不直觀。而且不容易算。這里用到了勾股定理的規(guī)律：將兩個(gè)點(diǎn) 位移，計(jì)算出兩個(gè)點(diǎn)的橫坐標(biāo)的差距和縱坐標(biāo)的差距為兩個(gè)直角邊。而兩個(gè)點(diǎn)的距離就是斜邊了。（如果這兩個(gè)點(diǎn)本身就在一條線上，那么另一個(gè)具體就是0，所以距離計(jì)算也是對(duì)的。）
能計(jì)算出兩個(gè)點(diǎn)的距離也就能計(jì)算出一個(gè)點(diǎn)和其他所有點(diǎn)的距離。如果距離其中一個(gè)點(diǎn)的兩個(gè)點(diǎn)距離相等，說明多了兩個(gè)回旋鏢（因?yàn)榭梢酝鶅蓚€(gè)方向扔）。如果具體一個(gè)點(diǎn)的三個(gè)點(diǎn)距離相等是多了六個(gè)回旋鏢（自己畫草圖看看，三個(gè)可以1-2,1-3,2-3,2-1,3-2,3-1）。同樣四個(gè)的話是n*(n-1)而不是簡單的多兩個(gè)。
一個(gè)點(diǎn)做中點(diǎn)可以扔的回旋鏢數(shù)求出來，再把每一個(gè)點(diǎn)都累加一遍，這道題就做完了，講真，我覺得這個(gè)不僅僅是簡單難度的，接下來貼代碼：
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;
}
}
下一題，不知道為什么，現(xiàn)在覺得每個(gè)題都賊難。。
找到所有數(shù)組中消失的數(shù)字
題目：給定一個(gè)范圍在 1 ≤ a[i] ≤ n ( n = 數(shù)組大小 ) 的 整型數(shù)組，數(shù)組中的元素一些出現(xiàn)了兩次，另一些只出現(xiàn)一次。找到所有在 [1, n] 范圍之間沒有出現(xiàn)在數(shù)組中的數(shù)字。您能在不使用額外空間且時(shí)間復(fù)雜度為O(n)的情況下完成這個(gè)任務(wù)嗎? 你可以假定返回的數(shù)組不算在額外空間內(nèi)。
示例:
輸入:
[4,3,2,7,8,2,3,1]
輸出:
[5,6]
思路：這個(gè)題說簡單就是會(huì)編程就能做，說難是不使用額外空間切時(shí)間復(fù)雜度O（n）。目前思路是先排序再挨個(gè)判斷哪個(gè)數(shù)字是被跳過的。我也不知道排序能不能用，反正第一思路是這樣。
第一版代碼出爐，我覺得今天可能早晨起床沒帶腦子，反正性能差的一批:
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;
}
}
其實(shí)邏輯說簡單也簡單。j是判斷應(yīng)該到了哪個(gè)數(shù)字。i是判斷遍歷到哪個(gè)數(shù)字。如果碰到相同的直接跳過，如果是正常的j正常++。如果遇到不是重復(fù)但是也不是應(yīng)該有的數(shù)字說明這塊有缺的了，先添加到list中，然后讓j正常++。但是i得--這樣下一次遍歷還是判斷這個(gè)數(shù)字是不是下一個(gè)。自覺哪怕是連著卻的數(shù)字也能發(fā)現(xiàn)。
我總覺得我這么寫肯定是忽略了什么省事的方法，因?yàn)檫@樣空間復(fù)雜度滿足了可是時(shí)間復(fù)雜度應(yīng)該不是O（n）。我再想想思路。
看到了一種很秀的思路：把每一個(gè)出現(xiàn)的數(shù)字的數(shù)字位改成負(fù)數(shù)。然后遍歷（判斷的時(shí)候要取這個(gè)數(shù)的絕對(duì)值）。遍歷一遍后數(shù)組中還是正數(shù)的位數(shù)說明缺這個(gè)數(shù)字（記得下標(biāo)要+1才是位數(shù)）。
只能說真的秀！比什么鴿子原理什么的看著易懂還簡單。我去試著寫代碼：
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for(int i=0;i<nums.length;i++){
//一定要判斷是不是大于0.不然一個(gè)數(shù)負(fù)兩次，負(fù)負(fù)得正了
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;
}
}
看了下性能靠前的代碼，都是用了額外空間了，我還是下一題吧。
最小移動(dòng)次數(shù)使數(shù)組相等
題目：給定一個(gè)長度為 n 的非空整數(shù)數(shù)組，找到讓數(shù)組所有元素相等的最小移動(dòng)次數(shù)。每次移動(dòng)可以使 n - 1 個(gè)元素增加 1。
示例:
輸入:
[1,2,3]
輸出:
3
解釋:
只需要3次移動(dòng)（注意每次移動(dòng)會(huì)增加兩個(gè)元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
思路：哎，現(xiàn)在別說思路了，審題都得審一會(huì)兒，反正大概思路就是每次最大的數(shù)不要?jiǎng)?，其余?1，一直加到所有數(shù)組元素都相等。我去理理思路。
我剛剛靈機(jī)一動(dòng)?。。∥矣X得自己簡直聰明絕頂了，所有除了最大元素+1.和最大元素-1.雖然數(shù)值不一樣，但是本質(zhì)上相等比較是一樣！！！
所以每次最大元素減1.什么時(shí)候減到所有元素相等就行了?。?！簡直被我自己的機(jī)智感動(dòng)哭了~~~完美測試通過，雖然性能不是那么好，但是真的挺無腦的，哈哈，這道題比想的簡單多了。
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;
}
}
我發(fā)現(xiàn)我上面最大的失誤就是sort排序，其實(shí)只要知道最小值就行了，沒必要排序，所以這里用一個(gè)循環(huán)自己找出最小值比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;
}
}
這道題思路很順，我覺得我還是喜歡晚上學(xué)習(xí)，比白天效率要高的多。
分發(fā)餅干
題目：假設(shè)你是一位很棒的家長，想要給你的孩子們一些小餅干。但是，每個(gè)孩子最多只能給一塊餅干。對(duì)每個(gè)孩子 i ，都有一個(gè)胃口值 gi ，這是能讓孩子們滿足胃口的餅干的最小尺寸；并且每塊餅干 j ，都有一個(gè)尺寸 sj 。如果 sj >= gi ，我們可以將這個(gè)餅干 j 分配給孩子 i ，這個(gè)孩子會(huì)得到滿足。你的目標(biāo)是盡可能滿足越多數(shù)量的孩子，并輸出這個(gè)最大數(shù)值。注意：你可以假設(shè)胃口值為正。一個(gè)小朋友最多只能擁有一塊餅干。
示例 1:
輸入: [1,2,3], [1,1]
輸出: 1
解釋
你有三個(gè)孩子和兩塊小餅干，3個(gè)孩子的胃口值分別是1 2 3
雖然你有兩塊小餅干，由于他們的尺寸都是1，你只能讓胃口值是1的孩子滿足。
所以你應(yīng)該輸出1。
示例 2
輸入: [1,2], [1,2,3]
輸出: 2
解釋:你有兩個(gè)孩子和三塊小餅干，2個(gè)孩子的胃口值分別是1,2。
你擁有的餅干數(shù)量和尺寸都足以讓所有孩子滿足。所以你應(yīng)該輸出2.
思路：最麻煩的來說就是兩個(gè)數(shù)組排序，從最小開始挨個(gè)比對(duì)（餅干小于孩子胃口就餅干往后，孩子不變），一直比對(duì)到餅干沒有了。這個(gè)時(shí)候比過的孩子就是可以喂飽的孩子。
這只是一個(gè)初步的思路，具體的內(nèi)容還要慢慢實(shí)現(xiàn)，我先去寫代碼。寫完出來了，這個(gè)思路沒問題，還很簡單：
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;
}
}
就是如圖，能滿足則孩子餅干都往下走，不然孩子不走餅干走。
不知道是晚上做的題都簡單還是說白天思路不好，一整個(gè)白天做了兩道題，結(jié)果晚上一個(gè)多小時(shí)做了三道。哈哈。
今天的筆記就記錄到這里了，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注呦~！也祝大家工作順順利利！
