最長(zhǎng)連續(xù)遞增數(shù)列
題目：給定一個(gè)未經(jīng)排序的整數(shù)數(shù)組，找到最長(zhǎng)且連續(xù)的的遞增序列。
示例 1:
輸入: [1,3,5,4,7]
輸出: 3
解釋: 最長(zhǎng)連續(xù)遞增序列是 [1,3,5], 長(zhǎng)度為3。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的，因?yàn)?和7在原數(shù)組里被4隔開。
示例 2:
輸入: [2,2,2,2,2]
輸出: 1
解釋: 最長(zhǎng)連續(xù)遞增序列是 [2], 長(zhǎng)度為1。
注意：數(shù)組長(zhǎng)度不會(huì)超過10000。
思路：這個(gè)題我真的覺得做過類似的，現(xiàn)有的思路：count=1，然后遍歷數(shù)組，如果后一個(gè)比前一個(gè)大count++，當(dāng)后一個(gè)比前一個(gè)小的時(shí)候cuount恢復(fù)到1、設(shè)置一個(gè)最大值max，max取count最大值。對(duì)了，還要判斷數(shù)組是不是為空。是的話返回1。大早晨的思路如此清晰，哈哈，開門大吉么？我去寫代碼了。
思路完全沒問題，性能超過百分百，直接貼代碼下一題吧：
class Solution {
public int findLengthOfLCIS(int[] nums) {
if(nums.length==0) return 0;
int max = 1;
int count = 1;
for(int i=0;i<nums.length-1;i++){
if(nums[i]<nums[i+1]){
count++;
}else{
max = max>count?max:count;
count=1;
}
}
return max>count?max:count;
}
}
驗(yàn)證回文字符串2
題目：給定一個(gè)非空字符串 s，最多刪除一個(gè)字符。判斷是否能成為回文字符串。
示例 1:
輸入: "aba"
輸出: True
示例 2:
輸入: "abca"
輸出: True
解釋: 你可以刪除c字符。
注意:
字符串只包含從 a-z 的小寫字母。字符串的最大長(zhǎng)度是50000。
思路：這道題就是普通點(diǎn)的驗(yàn)證回文串的進(jìn)化版，首先一個(gè)字符串本身就是回文串了，肯定是true的。其次在比較的時(shí)候如果拋去一個(gè)字符串可以做到回文還是true，不然是false。這個(gè)題昨天做過一個(gè)類似的，改變某元素能否成為升序數(shù)組的那個(gè)題就是這個(gè)思路。不過那道題比這個(gè)復(fù)雜， 那個(gè)題是改變其中一個(gè)元素，而這道題簡(jiǎn)單多了，就是刪除而已。我先去試著寫代碼，現(xiàn)在有一個(gè)模糊的思路。
做是做出來了，鬼知道我經(jīng)歷了什么？越改性能越差？
最好性能超過百分之八十多，越改越低，所以直接上最麻煩版本的代碼吧:
class Solution {
public boolean validPalindrome(String s) {
int l = 0;
int r = s.length()-1;
char[] c = s.toCharArray();
boolean flag = true;
boolean flag1 = true;
int count = 0;
while(l<r){
if(c[l]!=c[r]){
count++;
l++;
if(count==2) flag=false;
}else{
l++;
r--;
}
}
l = 0;
r = c.length-1;
count = 0;
while(l<r){
if(c[l]!=c[r]){
count++;
r--;
if(count==2) flag1=false;
}else{
l++;
r--;
}
}
return flag||flag1;
}
}
后期嘗試優(yōu)化，比如flag使用一個(gè)，或者在判斷玩第一遍循環(huán)如果是true直接返回，我以為性能會(huì)更好，但是不知道為什么越來越糟，心塞~~
反正思路就是那樣，遇到不同的要么刪除左邊的要么刪除右邊的，反正如果最終能回文說明true，還是不能回文就是false。
PS：剛剛發(fā)生件小事：我不是有個(gè)刷leetcode的群么，群友問了一道題，我去看了，一臉懵逼，就是一道二叉樹動(dòng)態(tài)規(guī)劃的題。本來我動(dòng)態(tài)規(guī)劃都是一知半解，還加上二叉樹，日狗了，智商上的碾壓~~這里立個(gè)flag：今天群友推薦的dp講解的視頻一定要學(xué)了并做筆記?。?！
棒球比賽
題目：你現(xiàn)在是棒球比賽記錄員。給定一個(gè)字符串列表，每個(gè)字符串可以是以下四種類型之一：
1.整數(shù)（一輪的得分）：直接表示您在本輪中獲得的積分?jǐn)?shù)。
2. "+"（一輪的得分）：表示本輪獲得的得分是前兩輪有效 回合得分的總和。
3. "D"（一輪的得分）：表示本輪獲得的得分是前一輪有效 回合得分的兩倍。
4. "C"（一個(gè)操作，這不是一個(gè)回合的分?jǐn)?shù)）：表示您獲得的最后一個(gè)有效 回合的分?jǐn)?shù)是無效的，應(yīng)該被移除。每一輪的操作都是永久性的，可能會(huì)對(duì)前一輪和后一輪產(chǎn)生影響。
你需要返回你在所有回合中得分的總和。
示例 1:
輸入: ["5","2","C","D","+"]
輸出: 30
解釋:
第1輪：你可以得到5分?？偤褪牵?。
第2輪：你可以得到2分?？偤褪牵?。
操作1：第2輪的數(shù)據(jù)無效。總和是：5。
第3輪：你可以得到10分（第2輪的數(shù)據(jù)已被刪除）。總數(shù)是：15。
第4輪：你可以得到5 + 10 = 15分。總數(shù)是：30。
示例 2:
輸入: ["5","-2","4","C","D","9","+","+"]
輸出: 27
解釋:
第1輪：你可以得到5分?？偤褪牵?。
第2輪：你可以得到-2分。總數(shù)是：3。
第3輪：你可以得到4分?？偤褪牵?。
操作1：第3輪的數(shù)據(jù)無效。總數(shù)是：3。
第4輪：你可以得到-4分（第三輪的數(shù)據(jù)已被刪除）?？偤褪牵?1。
第5輪：你可以得到9分。總數(shù)是：8。
第6輪：你可以得到-4 + 9 = 5分?？倲?shù)是13。
第7輪：你可以得到9 + 5 = 14分?？倲?shù)是27。
注意：
輸入列表的大小將介于1和1000之間。
列表中的每個(gè)整數(shù)都將介于-30000和30000之間。
思路：還好這個(gè)題沒說不能使用額外空間。我現(xiàn)在的建議就是每輪得分存放在一個(gè)數(shù)組里、這樣也好知道上一輪，上兩輪的分?jǐn)?shù)啥的。用一個(gè)數(shù)字表示數(shù)組下標(biāo)保證無效的，前兩個(gè)得分和，上一個(gè)得分兩倍的都能很容易找出。我去寫代碼試試。
嗯嗯，寫出來了，思路還可以，但是字符串判斷這塊我覺得有點(diǎn)浪費(fèi)性能？？反正效率不是很高，才超過百分之八十多的人，直接貼代碼：
class Solution {
public int calPoints(String[] ops) {
int[] c = new int[ops.length];
int index = 0;
for(int i = 0; i<ops.length;i++){
if(ops[i].equals("+")){
c[index] = index==0?0:(index==1?c[index-1]:c[index-1]+c[index-2]);
index++;
}else if(ops[i].equals("D")){
c[index] = index==0?0:c[index-1]*2;
index++;
}else if(ops[i].equals("C")){
index --;
}else{
c[index] = Integer.valueOf(ops[i]);
index++;
}
}
int sum = 0;
for(int j=0;j<index;j++){
sum += c[j];
}
return sum;
}
}
其實(shí)這個(gè)判斷，index從0開始，我在想如果從2開始 是不是就可以不用三目運(yùn)算了？我再改一下試試。思路對(duì)了，改完之后超過百分百的人了：
class Solution {
public int calPoints(String[] ops) {
int[] c = new int[ops.length+2];
int index = 2;
for(int i = 0; i<ops.length;i++){
if(ops[i].equals("+")){
c[index] = c[index-1]+c[index-2];
index++;
}else if(ops[i].equals("D")){
c[index] = c[index-1]*2;
index++;
}else if(ops[i].equals("C")){
index --;
}else{
c[index] = Integer.valueOf(ops[i]);
index++;
}
}
int sum = 0;
for(int j=2;j<index;j++){
sum += c[j];
}
return sum;
}
}
重復(fù)疊加字符串匹配
題目：給定兩個(gè)字符串 A 和 B, 尋找重復(fù)疊加字符串A的最小次數(shù)，使得字符串B成為疊加后的字符串A的子串，如果不存在則返回 -1。舉個(gè)例子，A = "abcd"，B = "cdabcdab"。答案為 3， 因?yàn)?A 重復(fù)疊加三遍后為 “abcdabcdabcd”，此時(shí) B 是其子串；A 重復(fù)疊加兩遍后為"abcdabcd"，B 并不是其子串。注意: A 與 B 字符串的長(zhǎng)度在1和10000區(qū)間范圍內(nèi)。
思路：思路就是不斷字符串匹配。其實(shí)這個(gè)題我做過類似的。這個(gè)題可以這么闡述：如果B是A的疊加然后掐頭去尾形成的子串。返回A疊加的次數(shù)。如果不是返回-1。只要能明白這句話這個(gè)題就簡(jiǎn)單的多了。只不過因?yàn)槎际亲址僮?，所以性能上?yīng)該要優(yōu)化。我先上第一版本的代碼
class Solution {
public int repeatedStringMatch(String A, String B) {
if(A.indexOf(B)!=-1) return 1;
String aa = A;
int l = B.length()/A.length();
int res = 1;
//最多就是前面去了點(diǎn)，后面去了點(diǎn)但是中間不能去。所以是倍數(shù)+2
for(int i = 2;i<=l+2;i++){
A += aa;
res++;
if(A.indexOf(B)!=-1) return res;
}
return -1;
}
}
性能一言難盡，咱們換一個(gè)話題，說說怎么優(yōu)化吧。感覺優(yōu)化點(diǎn)有兩個(gè)：
- string可以換成變長(zhǎng)字符串stringBuffer。
- 我感覺這個(gè)規(guī)律可以更加優(yōu)化的。
我去試著改良：不斷改良從超過百分之五到超過百分之六十多。就是上面說的兩個(gè)知識(shí)點(diǎn)。
下面是改良版的代碼：
class Solution {
public int repeatedStringMatch(String A, String B) {
if(A.indexOf(B)!=-1) return 1;
StringBuffer sb = new StringBuffer(A);
int l = B.length()/A.length();
//最多就是前面去了點(diǎn)，后面去了點(diǎn)但是中間不能去。所以是倍數(shù)+2
for(int i = 2;i<=l+2;i++){
sb.append(A);
if(i>=l && sb.indexOf(B)!=-1) return i;
}
return -1;
}
}
剩下的我直接去看人家的代碼吧，事先預(yù)測(cè)一下，性能好的應(yīng)該是用char操作?？纯搭A(yù)測(cè)的準(zhǔn)不準(zhǔn)：
好吧，我猜錯(cuò)了，人家也是用的字符串處理。直接上代碼：
class Solution {
public int repeatedStringMatch(String A, String B) {
int i = 1;
StringBuilder s = new StringBuilder(A);
int blength = B.length();
while(s.length() < blength){
s.append(A);
i++;
}
return s.lastIndexOf(B) == -1?((s.append(A)).lastIndexOf(B)==-1?-1:i+1):i;
}
}
感覺相似度百分之六十以上，邏輯相似百分之九十。為什么性能差這么多呢？我也是循環(huán)追加啊。奇了怪了。
emmm...找到問題了?。?！lastIndexOf比indexOf性能好！?。。∫粯右粯拥拇a換成lastIndexOf性能就上去了??！
我去看看這兩個(gè)方法的源碼：事實(shí)證明應(yīng)該是差不多的。而且我用了偽代碼測(cè)試，還是indexOf快，只能接收群友的說法：leetcode測(cè)試案例的問題。算了算了，這個(gè)問題過吧，下一題。
最長(zhǎng)同值路徑
題目：給定一個(gè)二叉樹，找到最長(zhǎng)的路徑，這個(gè)路徑中的每個(gè)節(jié)點(diǎn)具有相同值。 這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點(diǎn)。注意：兩個(gè)節(jié)點(diǎn)之間的路徑長(zhǎng)度由它們之間的邊數(shù)表示。
思路:總思路依然是遞歸。只不過除了參數(shù)樹以外應(yīng)該還傳一個(gè)參數(shù)：也就是當(dāng)前節(jié)點(diǎn)的值。然后我們?nèi)ヅ袛嘧庸?jié)點(diǎn)是值是不是等于根節(jié)點(diǎn)的值，如果是的話計(jì)數(shù)+1.另外應(yīng)該設(shè)置一個(gè)全局變量max，保證max是計(jì)數(shù)的最大值。暫時(shí)思路是這樣的，我去實(shí)現(xiàn)下試試。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int max;
public int longestUnivaluePath(TreeNode root) {
if(root==null) return 0;
getMax(root,root.val);
return max;
}
public int getMax(TreeNode root,int val){
if(root==null) return 0;
int l = getMax(root.left,root.val);
int r = getMax(root.right,root.val);
max = Math.max(max,l+r);
if(root.val==val) return l+r+1;
return 0;
}
}
第一版本的代碼?。?！錯(cuò)的老慘了?。。?br> 又是怪我審題不清，我以為是所有相連接的數(shù)值相同的路徑數(shù)。結(jié)果不是，是一條線。畫個(gè)圖比喻：
講真，一方面確實(shí)是我傻，沒理解題意，另一方面兩個(gè)例子太抽象了吧？非得用測(cè)試案例才能知道題目是啥意思。。。
呵！我去改了：
改完回來了，還好比較容易改，我上面代碼返回的是左邊+右邊+1的值，現(xiàn)在返回左邊右邊中較大值+1就行了。如下代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int max;
public int longestUnivaluePath(TreeNode root) {
if(root==null) return 0;
getMax(root,root.val);
return max;
}
public int getMax(TreeNode root,int val){
if(root==null) return 0;
int l = getMax(root.left,root.val);
int r = getMax(root.right,root.val);
max = Math.max(max,l+r);
if(root.val==val) return Math.max(l,r)+1;
return 0;
}
}
我覺得這道題最大的坑點(diǎn)就是題意。。剩下的就是常規(guī)遞歸。不過我這個(gè)性能不咋地，我去看看性能第一的代碼：
感覺代碼差別不大、我這里用了一個(gè)val的參數(shù)，方便判斷當(dāng)前節(jié)點(diǎn)是不是一段路徑。而人家的代碼沒有這個(gè)參數(shù)，通過判斷當(dāng)前節(jié)點(diǎn)和子節(jié)點(diǎn)是否相等從而判斷是不是有一段路徑。這個(gè)代碼處于能看懂的階段，但是自己想不出這么寫。
而且我就很奇怪，我是在return中+1.他這個(gè)是每個(gè)l和r都+1.明明應(yīng)該是我的運(yùn)算少，為啥還會(huì)我的性能低呢？
唯一的區(qū)別也就是我我這里一個(gè)if-ese，人家是兩個(gè)三目運(yùn)算吧？今天做題還算順利，但是讓性能搞得我頭疼。難不成是因?yàn)槲颐看味家嗯袛嘁粋€(gè)root==null？我去改動(dòng)試試。
一樣一樣的代碼，就是我變量名字不一樣和方法名字不一樣，結(jié)果我5ms運(yùn)行，人家2ms運(yùn)行？？？欺負(fù)人么？腦殼更疼了，下一題下一題吧。
員工的重要性
題目:給定一個(gè)保存員工信息的數(shù)據(jù)結(jié)構(gòu)，它包含了員工唯一的id，重要度 和 直系下屬的id。比如，員工1是員工2的領(lǐng)導(dǎo)，員工2是員工3的領(lǐng)導(dǎo)。他們相應(yīng)的重要度為15, 10, 5。那么員工1的數(shù)據(jù)結(jié)構(gòu)是[1, 15, [2]]，員工2的數(shù)據(jù)結(jié)構(gòu)是[2, 10, [3]]，員工3的數(shù)據(jù)結(jié)構(gòu)是[3, 5, []]。注意雖然員工3也是員工1的一個(gè)下屬，但是由于并不是直系下屬，因此沒有體現(xiàn)在員工1的數(shù)據(jù)結(jié)構(gòu)中。現(xiàn)在輸入一個(gè)公司的所有員工信息，以及單個(gè)員工id，返回這個(gè)員工和他所有下屬的重要度之和。
示例 1:
輸入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
輸出: 11
解釋:
員工1自身的重要度是5，他有兩個(gè)直系下屬2和3，而且2和3的重要度均為3。因此員工1的總重要度是 5 + 3 + 3 = 11。
注意:
一個(gè)員工最多有一個(gè)直系領(lǐng)導(dǎo)，但是可以有多個(gè)直系下屬
員工數(shù)量不超過2000。
思路：這個(gè)題要結(jié)合給的模板看，這個(gè)員工是一個(gè)對(duì)象。那就好找了，一層層往下找，知道下屬都為空被。我去做做試試！講真，我覺得這個(gè)要是一個(gè)sql題更加合適。。。
好了，第一版做出來了，思路沒問題，性能不能聊：
/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List<Integer> subordinates;
};
*/
class Solution {
int sum;
public int getImportance(List<Employee> employees, int id) {
List<Integer> list = null;
for(Employee e:employees){
if(e.id==id){
sum += e.importance;
list = e.subordinates;
break;
// employees.remove(e);
}
}
for(int i :list){
getImportance(employees,i);
}
return sum;
}
}
注意上面有一句被屏蔽的代碼:remove();因?yàn)檫@個(gè)在循環(huán)里，如果刪除會(huì)影響后續(xù)遍歷，從而報(bào)錯(cuò)，所以不能加上。后來發(fā)現(xiàn)直接移除break倒是可以，但是性能還不如之前呢，所以這句就沒算。
/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List<Integer> subordinates;
};
*/
class Solution {
int sum;
public int getImportance(List<Employee> employees, int id) {
for(Employee e:employees){
if(e.id==id){
sum += e.importance;
for(int i :e.subordinates){
getImportance(employees,i);
}
break;
}
}
return sum;
}
}
優(yōu)化再優(yōu)化，依然性能感人，我懷疑我是思路上的錯(cuò)誤！不是代碼編寫上的了。換個(gè)思路試試。
- 沒忍住看了排名第一的代碼，用了一個(gè)map中間集合來處理。其實(shí)想想也合理，畢竟map 的查找效率本來就比list強(qiáng)。。但是無緣無故突然多一個(gè)空間咋不說呢。。。哎，好吧，我就是在為我思路不開闊找借口。
附上代碼吧，其實(shí)邏輯差不多，只不過我是用list遍歷人家是用map。
/*
// Employee info
class Employee {
// It's the unique id of each node;
// unique id of this employee
public int id;
// the importance value of this employee
public int importance;
// the id of direct subordinates
public List<Integer> subordinates;
};
*/
class Solution {
Map<Integer,Employee> map;
int sum;
public int getImportance(List<Employee> employees, int id) {
map = new HashMap<Integer,Employee>();
for(Employee e:employees){
map.put(e.id,e);
}
getRes(id);
return sum;
}
public void getRes(int id){
Employee e = map.get(id);
sum += e.importance;
for(int i:e.subordinates){
getRes(i);
}
}
}
用了一層map性能頓時(shí)超過百分之九十八的人了，這道題其實(shí)不難，好了下一題吧。
交替位二進(jìn)制數(shù)
題目：給定一個(gè)正整數(shù)，檢查他是否為交替位二進(jìn)制數(shù)：換句話說，就是他的二進(jìn)制數(shù)相鄰的兩個(gè)位數(shù)永不相等。
示例 1:
輸入: 5
輸出: True
解釋:
5的二進(jìn)制數(shù)是: 101
示例 2:
輸入: 7
輸出: False
解釋:
7的二進(jìn)制數(shù)是: 111
示例 3:
輸入: 11
輸出: False
解釋:
11的二進(jìn)制數(shù)是: 1011
示例 4:
輸入: 10
輸出: True
解釋:
10的二進(jìn)制數(shù)是: 1010
思路：額反正目前為止我覺得這道題是一個(gè)送分題。不就是要判斷一個(gè)數(shù)的二進(jìn)制有沒有00或者11么？而且已經(jīng)說了正整數(shù)，簡(jiǎn)直？？？估計(jì)考的又是性能了。我不覺得單純解題上會(huì)有什么坑
我沒用最無腦的字符串判斷，用屁股想也知道肯定性能可憐的不行，而且用了一邊f(xié)lag標(biāo)記狀態(tài)，性能超過百分之八十多，直接貼代碼:
class Solution {
public boolean hasAlternatingBits(int n) {
boolean flag = (n%2==0?false:true);
while(n>0){
if(n%2==0){
if(flag) return false;
flag = true;
}else{
if(!flag) return false;
flag = false;
}
n=n/2;
}
return true;
}
}
其實(shí)一開始我想用0 1來表示，加加減減的，如果超過1說明連續(xù)了。但是發(fā)現(xiàn)6的測(cè)試案例 110 ，先減 再加 再加，最后也沒變化超過一，所以數(shù)字不能表示，然后換成布爾值了。
優(yōu)化點(diǎn)的話，我覺得可能能更直觀的判斷？直接判斷1，0吧，之前做的時(shí)候就有隱隱的想法，但是不確定0，1直接量會(huì)不會(huì)性能好啊，，
!!!!!!!!!我合理懷疑我被針對(duì)了，一樣一樣的代碼，人家運(yùn)行超過百分百(0ms)，我運(yùn)行就只超過百分之八十一(1ms)???這是要鬧哪樣?
首先說一下，人家的思路就是直接比較字面量。然后我反正運(yùn)行還是超過八十多，順便貼上代碼參考吧：
class Solution {
public boolean hasAlternatingBits(int n) {
int val = n%2;
n = n/2;
int temp = 0;
while(n!=0){
temp = n%2;
if(temp==val){
return false;
}
val = temp;
n=n/2;
}
return true;
}
}
反正就這樣了，下一題吧。
計(jì)數(shù)二進(jìn)制字串
題目：給定一個(gè)字符串 s，計(jì)算具有相同數(shù)量0和1的非空(連續(xù))子字符串的數(shù)量，并且這些子字符串中的所有0和所有1都是組合在一起的。重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)。
示例 1 :
輸入: "00110011"
輸出: 6
解釋: 有6個(gè)子串具有相同數(shù)量的連續(xù)1和0：“0011”，“01”，“1100”，“10”，“0011” 和 “01”。
請(qǐng)注意，一些重復(fù)出現(xiàn)的子串要計(jì)算它們出現(xiàn)的次數(shù)。
另外，“00110011”不是有效的子串，因?yàn)樗械?（和1）沒有組合在一起。
示例 2 :
輸入: "10101"
輸出: 4
解釋: 有4個(gè)子串：“10”，“01”，“10”，“01”，它們具有相同數(shù)量的連續(xù)1和0。
注意：
s.length 在1到50,000之間。
s 只包含“0”或“1”字符。
思路：其實(shí)可以這么看 0011 就包含兩組， 000111包含三組。00001111包含四組。所以可以把每一個(gè)分界點(diǎn)單提出來。
很好，一次通過，可喜可賀。
這里要說一下，我上面的思路可能只有我自己懂了，但是沒說清楚。
是這么個(gè)道理：比如 11100110。首先11100.三個(gè)1兩個(gè)0只能組成2組，一個(gè)是1100一個(gè)是10。然后往下判斷：0011能組成兩組 0011和01.再往下110能組成1組。判斷的依據(jù)就是挨著的相同元素的個(gè)數(shù)取少的那個(gè)。
然后我處理的第一步就是相同元素累加。我不用知道第一個(gè)元素是1還是0.反正是一種。第一種元素個(gè)數(shù)，第二種元素個(gè)數(shù)，第一種元素個(gè)數(shù)，第二種元素個(gè)數(shù)以此類推。比如11100011001010111
就變成了 3，3， 2，2，1，1，1，1，3（本來想畫個(gè)圖的，但是無奈我手殘）
反正思路就是如圖，接著上代碼:
class Solution {
public int countBinarySubstrings(String s) {
int[] c = new int[s.length()];
int n = 0;
int count = 1;
char[] arr = s.toCharArray();
for(int i = 0;i<arr.length-1;i++){
if(arr[i]==arr[i+1]){
count++;
}else{
c[n]=count;
n++;
count=1;
}
}
//最后一個(gè)元素類型個(gè)數(shù)肯定沒存呢，所以存進(jìn)去
c[n] = count;
int res =0;
for(int j = 0; j<n; j++){
res += Math.min(c[j],c[j+1]);
}
return res;
}
}
其實(shí)這道題的這種思路性能一般，但是我覺得應(yīng)該是我寫的問題，不是思路問題，才超過百分之七十多的人。也不太能想出優(yōu)化方案了，我直接看排行第一的代碼去吧。怎么說呢，一樣一樣的代碼我提交幾次就有幾次結(jié)果。從百分百到百分之七十多。。
不過我上面確實(shí)寫累贅了！其實(shí)這個(gè)數(shù)組我們保存再判斷可以，但是不保存數(shù)組直接算出來也ok，我貼一下新代碼（其實(shí)就是上個(gè)思路的進(jìn)化版）：
class Solution {
public int countBinarySubstrings(String s) {
int res =0;
int count = 1;
int last = 0;
char[] arr = s.toCharArray();
for(int i = 0;i<arr.length-1;i++){
if(arr[i]==arr[i+1]){
count++;
}else{
res +=(count>last?last:count);
last = count;
count=1;
}
}
res += Math.min(last,count);
return res;
}
}
另外注意下，兩個(gè)判斷我一個(gè)用三目運(yùn)算一個(gè)用的Math.min();其實(shí)本質(zhì)沒什么區(qū)別，我之所以這么寫只是為了測(cè)試性能。
然后今天的刷題記錄就到這里了，很開心今天沒遇到什么難題，然后刷了八道題，哈哈，給自己點(diǎn)贊！另外今天周五了，也祝大家周末愉快~~~~~如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注呦！我先去看講解動(dòng)態(tài)規(guī)劃的視頻去了，每天進(jìn)步一點(diǎn)點(diǎn)！
