//思路：关键是如何去除空字符串，比如 ""、" " 和 "    " 等等。
public String reverseWords(String s) {
  if(s==null){
    return s;
  }
  String[] arr = s.trim().split(" ");

  Stack<String> stack = new Stack<>();
  for(String ss : arr){
    String str=ss.trim();
    if(str.length()!=0){ //去除空字符串
      stack.push(str);
    }
  }
  StringBuilder res = new StringBuilder();
  while (!stack.isEmpty()){
    res.append(stack.pop()).append(" ");
  }
  return res.toString().trim();
}

@Test
public void test(){
  //String s="the sky is blue";
  //String s="  hello world!  ";
  String s="a good   example";
  System.out.println(reverseWords(s));
}

public String reverseWords(String s) {
  StringBuilder res = new StringBuilder();

  String[] words =s.split(" ");
  for(String word : words){
    word=reverseWord(word);
    res.append(word).append(" ");
  }
  return res.toString().trim();
}

//翻转字符串
private String reverseWord(String word){
  char[] chs = word.toCharArray();
  int start =0,end=chs.length-1;
  while(start<end){
    swap(chs,start,end);
    start++;
    end--;
  }
  return new String(chs);
}

private void swap(char[] chs,int i,int j){
  char tmp = chs[i];
  chs[i] = chs[j];
  chs[j] = tmp;
}

@Test
public void test(){
  String s="Let's take LeetCode contest";
  System.out.println(reverseWords(s));
}

public int countSegments(String s) {
  if(s==null || s.length()==0){
    return 0;
  }

  int res=0;
  String[] words=s.trim().split(" ");
  for(String word:words){
    word = word.trim();
    if(word.length()!=0){
      res++;
    }
  }
  return res;
}

@Test
public void test(){
  String s="Hello, my name is John";
  System.out.println(countSegments(s));
}

//思路：从后向前相相加
public String addBinary(String a, String b) {
  StringBuilder res = new StringBuilder();

  char[] chsA = a.toCharArray();
  char[] chsB = b.toCharArray();

  int indexA=chsA.length-1;
  int indexB=chsB.length-1;

  int c=0;
  while(indexA>=0 || indexB>=0 || c==1){
    //TODO： c==1 判断条件是针对：a = "11", b = "1" 两数相加的情况的。
    c+=((indexA>=0)?chsA[indexA]-'0':0);
    c+=((indexB>=0)?chsB[indexB]-'0':0);
    res.append(c%2);
    c/=2; //作为下一次的值
    indexA--;
    indexB--;
  }
  return res.reverse().toString(); //注意是从后向前加的
}

@Test
public void test(){
  //String a = "11", b = "1";
  String a = "1010", b = "1011";
  System.out.println(addBinary(a,b));
}

public int firstUniqChar(String s) {
  char[] chs = s.toCharArray();

  int[] freq = new int[26];
  for(char ch : chs){
    freq[ch-'a']++;
  }

  for(int i=0;i<chs.length;i++){
    if(freq[chs[i]-'a']==1){
      return i;
    }
  }
  return -1;
}

//思路：
//由于字符串中只会出现'0'和'1'，并且要求是所有的'0'和'1'组合在一起
//统计一下每个连续 '0' 或者 '1'的个数,实际上就是连续子串的最大个数。
public int countBinarySubstrings(String s) {
  char[] chs = s.toCharArray();

  int[] count = new int[chs.length]; //统计一下每个连续 '0' 或者 '1'的个数

  int index=0; //新数组的下标，index<=chs.length;
  for(int i=0;i<chs.length-1;i++){
    count[index]++;
    if(chs[i]!= chs[i+1]){
      index++;
    }
  }
  count[index]++; //注意(i+1)<chs.length,所以需要统计最后一个字符

  // count[i] 就能表示子串数？
  // 举个例子："000111" 对应 count[0]=3、count[1]=3。
  // "000111" 的子串 --> 由内向外 "01"、"0011"和"000111"。
  int res=0;
  for(int i=0;i<index;i++){ //注意这里 i<index,因为后面存在（i+1）下标
    res+=Math.min(count[i],count[i+1]);
  }
  return res;
}

@Test
public void test(){
  String s="00110011";
  //String s="10101";
  System.out.println(countBinarySubstrings(s));
}

public int[] numberOfLines(int[] widths, String S) {
  char[] chs = S.toCharArray();

  int line =1;
  int width =0;
  for(int i=0;i<chs.length;i++){
    int index = chs[i]-'a';
    width += widths[index];
    if(width > 100){
      line++;
      i--; //TODO: i 元素不能写到 line 行了
      width = 0;
    }else if(width==100){
      line++;
      width =0;
    }
  }

  return new int[]{line,width};
}

@Test
public void test(){
  int[] widths = {4,10,10,10,10,10,10,10,10,10,10,10,
                  10,10,10,10,10,10,10,10,10,10,10,10,10,10};
  String S = "bbbcccdddaaa";
  //int [] widths = {10,10,10,10,10,10,10,10,10,10,10,
  //        10,10,10,10,10,10,10,10,10,10,10,10,10,10,10};
  //String S = "abcdefghijklmnopqrstuvwxyz";

  int[] res = numberOfLines(widths,S);
  for(int num : res){
    System.out.println(num);
  }
}

//思路：
//构成回文串的 2 种情况：
//1、字符出现次数为双数的组合
//2、字符出现次数为双数的组合 + 一个只出现一次的字符

//写法一：使用数组来统计
public int longestPalindrome(String s) {
  int[] cnts = new int[256];
  for (char c : s.toCharArray()) {
    cnts[c]++;
  }

  int res=0;
  //统计出现双数的次数，比如 "aaa" -> 3/2=1 (出现 1 次双数)
  for(int cnt : cnts){
    res+=(cnt/2)*2; // cnt/2 该字符能够有多少次双数
  }
  if(res < s.length()){
    res++;// res++，就是加上一个值出现一次的字符
  }
  return res;
}

@Test
public void test(){
  String s="abccccdd";
  System.out.println(longestPalindrome(s));
}

//写法二：使用 set 进行统计
public int longestPalindrome(String s) {
  int count =0; //用于统计字符出现次数为 2 的字符个数

  char[] chs = s.toCharArray();
  Set<Character> set=new HashSet<>(); //利用 set 存储的值不能相同的特性
  for(char ch:chs){
    if(!set.contains(ch)){
      set.add(ch);
    }else{ //说明 ch 出现次数是偶数
      set.remove(ch);
      count++;
    }
  }
  return set.isEmpty()?(2*count):(2*count+1);
}

@Test
public void test(){
  String s="abccccdd";
  System.out.println(longestPalindrome(s));
}