1.問題描述
統計字串中的單詞個數，這里的單詞指的是連續的不是空格的字符，
請注意，你可以假定字串里不包括任何不可列印的字符，
示例:
輸入: "Hello, my name is John"
輸出: 5
解釋: 這里的單詞是指連續的不是空格的字符，所以 "Hello," 算作 1 個單詞，
2.解題思路
統計單詞次數可以使用雙指標法
大雪菜老師給出的模板如下
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具體問題的邏輯
}
而對于本題的一個序列，用兩個指標維護一段區間，用i指標來對整個字串進行掃描，我們保證每次回圈的時候，i指向字串單詞的第一個位置，而j指標則從i指標的位置開始，找到字串單詞的最后一個位置，字串單詞的最后一個位置即找到str[i]==’ ’ 為止， 當我們本個單詞處理完之后，讓i=j,進行下一個單詞的處理
但是本題坑點比較多，可能兩個字串之間有多個空格，那么我們還需要一個回圈，讓j跨越中間的所有空格，
另外，字串的開頭也可能是空格，因此我們每次還需要判斷在j遇到空格退出這之間有沒有經過非空格的字符，
具體代碼如下：
3.實作代碼
class Solution {
public int countSegments(String s) {
int len=s.length();
int count=0; //單詞數
for(int i=0;i<len;i++){
int j=i;
//當遇到了空格即停止
while(j<len && s.charAt(j)!=' '){
j++;
}
if(j>i){ //表明有不為空格的字符存在，就可以組成一個單詞
count++;
}
//跨越中間可能存在的多個空格
while(j+1<len &&s.charAt(j+1)==' '){
j++;
}
if(j==len-1){
break;
}
i=j;
}
return count;
}
}
4.總結
雙指標演算法的核心思想是把從i,j兩重回圈中挖取某些性質，可以只讓我們列舉O(n)個狀態，把我們的時間復雜度從O(n2)變成O(n),
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/259512.html
標籤：其他