image.png

38. 外观数列

难度简单649
给定一个正整数 n ，输出外观数列的第 n 项。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。
你可以将其视作是由递归公式定义的数字字符串序列：

  • countAndSay(1) = "1"
  • countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221"
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。
例如，数字字符串 "3322251" 的描述如下图：
字符串处理 - 图2


示例 1：
输入：n = 1
输出：“1”
解释：这是一个基本样例。

示例 2：
输入：n = 4
输出：“1211”
解释：
countAndSay(1) = “1”
countAndSay(2) = 读 “1” = 一 个 1 = “11”
countAndSay(3) = 读 “11” = 二 个 1 = “21”
countAndSay(4) = 读 “21” = 一 个 2 + 一 个 1 = “12” + “11” = “1211”

  1. /*class Solution {
  2.     public String countAndSay(int n) {
  3.         String s="1";
  4.         char[] S=s.toCharArray();//这个应该放到for的里面
  5.         for(int i=0;i<n-1;i++){//生成第n个，只需要递推n-1次
  6.             StringBuffer ns = new StringBuffer();
  7.             for(int j=0;j<s.length();j++){
  8.                 int k=j;
  9.                 while(k<s.length()&&S[k]==S[j]) k++;//用来判断几个重复的
  10.                 ns.append(k-j);
  11.                 ns.append(S[j]);
  12.                 j=k-1;//更新j
  13.             }
  14.             s=ns.toString();;
  15.     }
  16.     return s;
  17. }
  18. }*//
  19. class Solution {
  20.     public String countAndSay(int n) {
  21.         String s="1";
  22.         for(int i=0;i<n-1;i++){
  23.             char[] S=s.toCharArray();
  24.             StringBuffer ns = new StringBuffer();
  25.             for(int j=0;j<s.length();j++){
  26.                 int k=j;
  27.                 while(k<s.length()&&S[k]==S[j]) k++;
  28.                 ns.append(k-j);
  29.                 ns.append(S[j]);
  30.                 j=k-1;
  31.             }
  32.             s=ns.toString();;
  33.     }
  34.     return s;
  35. }
  36. }

49. 字母异位词分组

难度中等660
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for(String s:strs){
            char[] key=s.toCharArray();
            Arrays.sort(key);
            String skey = new String(key);
            List<String> list = map.getOrDefault(skey, new ArrayList<String>());//返回指定键映射到的值，如果此映射不包含键的映射，则返回 defaultValue 。
            list.add(s);
            map.put(skey,list);
        }
        return new ArrayList<List<String>>(map.values());//map.values(),返回此映射中包含的值的Collection视图。
    }
}

5. 最长回文子串

难度中等3303
给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

示例 3：
输入：s = “a”
输出：“a”

示例 4：
输入：s = “ac”
输出：“a”

class Solution {
    public String longestPalindrome(String s) {
        String res="";
        char[] S=s.toCharArray();
        for(int i=0;i<s.length();i++){
            for(int j=i,k=i;j>=0&&k<s.length()&&S[j]==S[k];j--,k++)
            if(res.length()<k-j+1)
                res=s.substring(j,k+1);
            for(int j=i,k=i+1;j>=0&&k<s.length()&&S[j]==S[k];j--,k++)
            if(res.length()<k-j+1)
                res=s.substring(j,k+1);
    }
    return res;
}
}

3. 无重复字符的最长子串

难度中等5079
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:
输入: s = “”
输出: 0

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] arr = new int[128];
        int res=0;
        char[] str=s.toCharArray();
        for(int i=0,j=0;i<s.length();i++){
            arr[str[i]]++;
            while(arr[str[i]]>1) arr[str[j++]]--;
            res=Math.max(res,i-j+1);
        }
        return res;
}
}

208. 实现 Trie (前缀树)

难度中等547
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true

class Trie {
    private Trie[] next = new Trie[26];
    private boolean isEnd=false;

    /** Initialize your data structure here. */
    public Trie() {
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie p=this;
        for(char c:word.toCharArray()){
            int u=c-'a';
            if(p.next[u]==null) p.next[u]=new Trie();
            p=p.next[u];
        }
        p.isEnd=true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie p=this;
        for(char c:word.toCharArray()){
            int u=c-'a';
            if(p.next[u]==null) return false;
            p=p.next[u];
        }
        return p.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        Trie p=this;
        for(char c:prefix.toCharArray()){
            int u=c-'a';
            if(p.next[u]==null) return false;
            p=p.next[u];
        }
        return true;
    }
}