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

import java.util.*;

public class Main {
    public static void main (String[] args) {

        String s = "abcabcbb"; // 3
        // String s = "bbbb"; // 1
        String s = "pwwkew"; // 3
        int res = lengthOfLongestSubstring(s);
        System.out.println(res); 
    }


    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> hash = new HashMap<>();
        int res = 0;
        for (int j = 0, i = 0; i < s.length(); i ++) {
            // hash.put(s.charAt(i), hash.get(s.charAt(i)) + 1);
            hash.put(s.charAt(i), hash.getOrDefault(s.charAt(i), 0) + 1);
            while (hash.get(s.charAt(i)) > 1) {
                hash.put(s.charAt(j), hash.get(s.charAt(j)) - 1);
                j ++;
            }

            res = Math.max(res, i - j + 1);
        }

        return res;
    }

}

LC5. 最长回文子串

import java.util.*;

public class Main {
    public static void main (String[] args) {

        String s = "babad"; // bab
        // String s = "cbbd"; // bb
        // String s = "a"; // a
        String res = longestPalindrome(s);
        System.out.println(res); 
    }


    public static String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i ++) {
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l --; r ++;
            }
            if (res.length() < r - l - 1) res = s.substring(l + 1, r); // 注意：if内时r-l-1,不是r-l+1

            l = i; r = i + 1;

            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                l --; r ++;
            }

            if (res.length() < r - l - 1) res = s.substring(l + 1, r);
        }

        return res;
    }

}

LC8. 字符串转换整数 (atoi)

import java.util.*;

public class Main {
    public static void main (String[] args) {

        String s = "42"; // 42
        // String s = "-42"; // -42
        // String s = "4193 with words"; // 4193
        // String s = "words and 987"; // 0
        // String s = "-91283472332"; // -2147483648

        int res = myAtoi(s);
        System.out.println(res); 
    }


    public static int myAtoi(String s) {
        int k = 0;
        while (k < s.length() && s.charAt(k) == ' ') k ++;
        if (k == s.length()) return 0;

        int minus = 1;
        if (s.charAt(k) == '-') { minus = -1; k ++; }
        else if (s.charAt(k) == '+') k ++;


        long res = 0;
        while (k < s.length() && s.charAt(k) >= '0' && s.charAt(k) <= '9') {
            res = res * 10 + s.charAt(k ++) - '0';
            if (res > Integer.MAX_VALUE) break;
        }

        res *= minus;

        if (res > Integer.MAX_VALUE) res = Integer.MAX_VALUE;
        if (res < Integer.MIN_VALUE) res = Integer.MIN_VALUE;

        return (int)res;


        /*
        下面是 不用long类型，而是用int 
        int res = 0;
        while (k < s.length() && s.charAt(k) >= '0' && s.charAt(k) <= '9') {
            int x = s.charAt(k ++) - '0';
            if (minus > 0 && res > (Integer.MAX_VALUE - x) / 10) return Integer.MAX_VALUE;
            if (minus < 0 && -res < (Integer.MIN_VALUE + x) / 10) return Integer.MIN_VALUE;

            if (-res * 10 - x == Integer.MIN_VALUE) return Integer.MIN_VALUE;

            res = res * 10 + x;
        }

        res *= minus;
        return res;
        */
    }

}

LC14. 最长公共前缀

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String[] strs = {"flower", "flxx", "flight"};
        // String[] strs = {"dog","racecar","car"};
        System.out.println(longestCommonPrefix(strs)); // 输出fl
    }

    public static String longestCommonPrefix(String[] strs) {  
        if (strs.length == 0) return "";

        String s = strs[0];
        int size = s.length();

        int j = 0;
        for (int i = 0; i < strs.length; i ++) {
            for (j = 0; j < size; j ++) 
                if (s.charAt(j) != strs[i].charAt(j)) {
                    size = j;
                    break;
                }
        }

        return s.substring(0, j);
    }

}

LC20. 有效的括号

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String s = "{[]}";
        System.out.println(isValid(s)); // 输出true
    }


   /*// 第一种写法(常规写法)
    public static boolean isValid(String s) {  
        Stack<Character> stk = new Stack<Character>();
        for (int i = 0; i < s.length(); i ++) {
            char t = s.charAt(i);
            if (t == '(' || t == '[' || t == '{') stk.push(t);
            else {
                if (stk.isEmpty()) return false;
                else if (t == ')' && stk.peek() == '(') stk.pop();
                else if (t == ']' && stk.peek() == '[') stk.pop();
                else if (t == '}' && stk.peek() == '{') stk.pop();
                else return false;
            }
        }

        return stk.isEmpty();
    }*/

    // 第二种写法（任意一对匹配的括号，他们的ASCII值相差<=2，所以可用此条件判断是否是一对括号）
     public static boolean isValid(String s) {  
        Stack<Character> stk = new Stack<Character>();
        for (int i = 0; i < s.length(); i ++) {
            char t = s.charAt(i);
            if (t == '(' || t == '[' || t == '{') stk.push(t);
            else {
                if (!stk.isEmpty() && Math.abs(stk.peek() - t) <= 2) stk.pop();
                else return false;
            }
        }
        return stk.isEmpty();
     }

}

LC22. 括号生成

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int n = 3;
        List<String> res = generateParenthesis(n);
        for (String r : res) {
            System.out.println(r);
            System.out.println();
        }
        /*
        ((()))

        (()())

        (())()

        ()(())

        ()()()
        */

    }

    public static List<String> res = new ArrayList<>();

    public static List<String> generateParenthesis(int n) {
        dfs(n, "", 0, 0);
        return res;
    }

    public static void dfs(int n, String path, int l, int r) {
        if (path.length() == n * 2) {
            res.add(path);
            return ;
        }

        if (l < n) dfs(n, path + "(", l + 1, r);
        if (r < n && r < l) dfs(n, path + ")", l, r + 1);
    }
}

LC76. 最小覆盖子串

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";

        String res = minWindow(s, t);
        System.out.println(res);
    }

    public static String minWindow(String s, String t) {
        HashMap<Character,Integer> hs = new HashMap<Character,Integer>();
        HashMap<Character,Integer> ht = new HashMap<Character,Integer>();

        for(int i = 0;i < t.length();i ++)
        {
            ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1);
        }

        String ans = "";
        int len = 0x3f3f3f3f;
        int cnt = 0;//有多少个元素符合
        for(int i = 0,j = 0;i < s.length();i ++)
        {
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if(ht.containsKey(s.charAt(i)) &&
                hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++;

            //维护双指针
            while(j < i && (!ht.containsKey(s.charAt(j)) || 
                hs.get(s.charAt(j)) > ht.get(s.charAt(j))))
            {
                int count = hs.get(s.charAt(j)) - 1;
                hs.put(s.charAt(j), count);
                j ++;
            }

            if(cnt == t.length() && i - j + 1 < len)
            {
                len = i - j + 1;
                ans = s.substring(j,i + 1);
            }
        }
        return ans;
    }
}

LC115. 不同的子序列

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        String s = "rabbbit", t = "rabbit"; // 3
        // String s = "babgbag", t = "bag"; // 5

        int res = numDistinct(s, t);
        System.out.println(res);
    }

    public static int numDistinct(String s, String t) {
        int n = s.length(), m = t.length();
        s = " " + s; t = " " + t;
        int[][] f = new int[n + 10][m + 10];

        for (int i = 0; i <= n; i ++) f[i][0] = 1;

        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++) {
                f[i][j] = f[i - 1][j];
                if (s.charAt(i) == t.charAt(j)) f[i][j] += f[i - 1][j - 1];
            }

        return f[n][m];
    }
}

LC125. 验证回文串

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama")); //true
        // System.out.println(isPalindrome("race a car")); //false

    }

    public static boolean isPalindrome(String s) {
        for (int i = 0, j = s.length() - 1; i < j; i ++, j --) {
            while (i < j && !check(s.charAt(i))) i ++;
            while (i < j && !check(s.charAt(j))) j --;
            if (i < j && Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
                return false;
        }
        return true;
    }

    public static boolean check(char c) {
        return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9';
    }

}

LC127. 单词接龙

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        String beginWord = "hit", endWord = "cog";
        List<String> wordList = new ArrayList<>();
        wordList.add("hot");
        wordList.add("dot");
        wordList.add("dog");
        wordList.add("lot");
        wordList.add("log");
        wordList.add("cog");

        int res = ladderLength(beginWord, endWord, wordList);
        System.out.println(res); // 5
    }

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String,Integer> dist = new HashMap<>();
        HashSet<String> set = new HashSet<>();
        Queue<String> queue = new LinkedList<>();

        // 初始化
        dist.put(beginWord,1);
        queue.offer(beginWord);
        for(String s : wordList) set.add(s);

        // bfs求最短路径
        while(!queue.isEmpty()){
            // 取出队头元素
            String str = queue.poll();
            // 单词转换,枚举这个单词的每一位
            for(int i = 0;i < str.length();i++){
                // 存储当前单词
                StringBuilder sb = new StringBuilder(str);
                // 将每一位上的字母换成26个英文字母中的一个，
                //再转换成新的字符串，看是否在给定的wordList中
                for(char c = 'a';c <= 'z';c++){
                    // 转换当前位上的字母为变量c
                    sb.setCharAt(i,c);
                    // 将变完的单词转换为String
                    String new_str = sb.toString();
                    // 如果新的单词在给定的wordList中，
                    //并且该单词还没有出现过，说明这个单词还没有被搜索过
                    if(set.contains(new_str) && 
                        !dist.containsKey(new_str)){ //set用的是contains， map用的是containsKey
                        if(new_str.equals(endWord)) return dist.get(str) + 1;
                        // 将这个单词加到dist中，其路径长度为原单词路径长度+1
                        dist.put(new_str,dist.get(str) + 1);
                        // 将这个单词加到队列中，准备进行下一层bfs
                        queue.add(new_str);
                    }
                }
            }
        }
        return 0;
    }
}

LC131. 分割回文串

import java.util.*;

public class Main {
    public static int n;

    public static void main (String[] args) { 
        String s= "aab";

        List<List<String>> res = partition(s);

        for (List<String> r : res) {
            for (String t : r) {
                System.out.print(t);
                System.out.print(",");
            }
            System.out.println();
        }
    }

    public static boolean[][] f;

    public static List<List<String>> ans = new ArrayList<>();
    public static List<String> path = new ArrayList<>();

    public static void init(String s){
        int n = s.length();
        for(int j = 0; j < n; j ++){
            for(int i = 0; i <= j; i ++){
                if(i == j) f[i][j] = true;
                else if(s.charAt(i) == s.charAt(j)) {
                    if (i + 1 > j - 1 || f[i + 1][j - 1]) f[i][j] = true;
                }
            }
        }
    }

    public static void dfs(String s, int u) {
        if (u == s.length()) ans.add(new ArrayList<>(path)); //这里不能写成ans.add(path);
        else {
            for (int i = u; i < s.length(); i ++) {
                if (f[u][i]) {
                    path.add(s.substring(u, i + 1));
                    dfs(s, i + 1);
                    path.remove(path.size() - 1);
                }
            }
        }
    }

    public static List<List<String>> partition(String s) {
        ans.clear();
        int n = s.length();
        f = new boolean[n][n];
        init(s);
        dfs(s, 0);
        return ans;
    }
}

LC151. 翻转字符串里的单词

import java.util.*;

public class Main {
    public static int n;

    public static void main (String[] args) { 
        String s= "the sky is blue";
        // String s = "hello world  "; // world hello
        String res = reverseWords(s); 
        System.out.println(res); // blue is sky the
    }

    // 用的是库函数
    public static String reverseWords(String s) {
        String res = "";
        int n = s.length();

        for(int i = n-1, j = n-1; i >= 0; i = j){
            while(j >= 0 && s.charAt(j) != ' ') j--;
            String tmp = s.substring(j+1, i+1);
            res += tmp + " ";
            while(j >= 0 && s.charAt(j) == ' ') j--;
        }

        return res.trim();

    }
}

LC168. Excel表列名称

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(convertToTitle(28)); // AB

    }

    public static String convertToTitle(int num) {
        StringBuffer sb = new StringBuffer("");
        while (num > 0) {
            num --;
            sb.append((char)(num % 26 + 'A'));
            num /= 26;
        }

        return sb.reverse().toString();
    }

}

LC171. Excel表列序号

import java.util.*;

public class Main {
    public static void main (String[] args) {
        System.out.println(titleToNumber("ZY")); // 701
    }

    public static int titleToNumber(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i ++) {
            res = res * 26 + (s.charAt(i) - 'A' + 1);
        }

        return res;
    }

}

LC187. 重复的DNA序列

import java.util.*;

public class Main {
    public static int n;

    public static void main (String[] args) { 
        String s= "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT";
        List<String> res = findRepeatedDnaSequences(s); 
        for (String r : res) {
            System.out.println(r);  
        }
        /*
        AAAAACCCCC
        CCCCCAAAAA
        */
    }

    public static List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new ArrayList<String>();
        HashMap<String , Integer> cnt = new HashMap<>();

        for(int i = 0;i + 10 <= s.length();i ++)
        {
            String t = s.substring(i, i + 10);
            cnt.put(t, cnt.getOrDefault(t, 0) + 1);
        }
        /*
            下面的for循环就相当于
            for (auto [s, c] : cnt) 
                if (c > 1) res.push_back(s);
        */
        for(Map.Entry<String, Integer> entry : cnt.entrySet())
        {
            if(entry.getValue() > 1)
                res.add(entry.getKey());
        }
        return res;
    }
}

AC23. 矩阵中的路径

import java.util.*;

public class Main {
    public static void main (String[] args) {
        char[][] matrix={
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String s = "BCCE"; // true 
        String s = "ASAE"; // false
        boolean res = hasPath(matrix, s);
        System.out.println(res);
    }

    public static boolean hasPath(char[][] matrix, String str) {
        for (int i = 0; i < matrix.length; i ++) 
            for (int j = 0; j < matrix[i].length; j ++)
                if (dfs(matrix, str, 0, i, j)) return true;
        return false;
    }

    public static boolean dfs(char[][] matrix, String str, int u, int x, int y) {
        if (matrix[x][y] != str.charAt(u)) return false;
        if (u == str.length() - 1) return true;
        int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
        char t = matrix[x][y];
        matrix[x][y] = '*';
        for (int i = 0; i < 4; i ++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < matrix.length && b >= 0 && b < matrix[a].length)
                if (dfs(matrix, str, u + 1, a, b)) return true;
        }

        matrix[x][y] = t;
        return false;
    }

}

AC51. 数字排列

import java.util.*;

public class Main {
    public static void main (String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> res = permutation(nums);
        for (List<Integer> r : res) {
            for (int x : r) {
                System.out.print(x);
                System.out.print(" ");
            }
            System.out.println();
        }
        /*
        1 2 3 
        1 3 2 
        2 1 3 
        2 3 1 
        3 1 2 
        3 2 1
        */
    }

    public static List<List<Integer>> permutation(int[] nums) {
        List<List<Integer>> ans =new ArrayList<>();
        Arrays.sort(nums);
        //回溯法
        dfs(ans, new ArrayList<>(), nums, new boolean[nums.length]);
        return ans;
    }

    private static void dfs(List<List<Integer>> ans, List<Integer> path, int[] nums, boolean[] st){
        if(path.size() == nums.length){
            ans.add(new ArrayList<>(path));
        } else {
            for (int i = 0; i < nums.length; i ++){
                if(st[i] || i > 0 && nums[i] == nums[i -  1] && !st[i - 1])
                    continue;

                st[i] = true;
                path.add(nums[i]);
                dfs(ans, path, nums, st);

                st[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

}

AC59. 把数字翻译成字符串

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String s = "12258";
        int res = getTranslationCount(s);

        System.out.println(res); // 5 
        // 12258  有 5 种不同的翻译，它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。
    }

    public static int getTranslationCount(String s) {
       int n = s.length();
       int[] f = new int[n + 1];
       f[0] = 1;
       f[1] = 1;
       for (int i = 2; i <= n; i ++) {
           f[i] = f[i - 1];
           int w = (s.charAt(i - 2) - '0' ) * 10 + s.charAt(i - 1) - '0';
           if (w >= 10 && w <= 25) f[i] += f[i - 2];
       }

       return f[n];
    }

}

AC61. 最长不含重复字符的子字符串

import java.util.*;

public class Main {
    public static void main (String[] args) {

        String s = "abcabcbb"; // 3
        // String s = "bbbb"; // 1
        String s = "pwwkew"; // 3
        int res = lengthOfLongestSubstring(s);
        System.out.println(res); 
    }


    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> hash = new HashMap<>();
        int res = 0;
        for (int j = 0, i = 0; i < s.length(); i ++) {
            // hash.put(s.charAt(i), hash.get(s.charAt(i)) + 1);
            hash.put(s.charAt(i), hash.getOrDefault(s.charAt(i), 0) + 1);
            while (hash.get(s.charAt(i)) > 1) {
                hash.put(s.charAt(j), hash.get(s.charAt(j)) - 1);
                j ++;
            }

            res = Math.max(res, i - j + 1);
        }

        return res;
    }

}

AC63. 字符串中第一个只出现一次的字符

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String s = "abaccdeff";
        char res = firstNotRepeatingChar(s);

        System.out.println(res); // 'b'
    }

    public static char firstNotRepeatingChar(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int n = s.length();

        for(int i = 0; i < n; i ++) {
            char ch = s.charAt(i);
            if(map.containsKey(ch)) {
               int count = map.get(ch) + 1;
               map.put(ch, count);
            } else map.put(ch, 1);
        }

        //遍历s 来保证拿到的是第一个出现次数为1的
        for(int i = 0; i < n; i ++)
           if(map.get(s.charAt(i)) == 1)
               return s.charAt(i);

        // for (Map.Entry<Character, Integer> entry : map.entrySet()) {
        //   if(entry.getValue()==1){
        //       return entry.getKey();
        //   }
        // }
        return '#';

    }

}

AC64. 字符流中第一个只出现一次的字符(没有Java版本的，可以看题解)

AC77. 翻转单词顺序

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String s = "I am a student.";
        String res = reverseWords(s);

        System.out.println(res); // student. a am I
    }

    //使用java的API
    public static String reverseWords(String s){
        String []str = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = str.length - 1; i >= 0; i --){
            sb.append(str[i]);
            sb.append(" ");
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }

    /*
    public static String reverseWords(String s){
    // 反转整个字符串
        char[] chars = s.toCharArray();
        reverse(chars,0, chars.length-1);
        // 反转每个单词
        int index = 0;
        for(int i = 0; i< chars.length; i++){
            // 检测到' '就执行翻转
            if(chars[i] == ' '){
                reverse(chars, index, i-1);
                index = i+1;
            }
            // 处理最后一个字符
            if(i == chars.length-1){
                reverse(chars, index, i);
            }
        }
        return new String(chars);
    }

    private static void reverse(char[] s, int l, int r) {
        for (int i = l, j = r; i < j; i++, j--) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
    */
}

AC78. 左旋转字符串

import java.util.*;

public class Main {
    public static void main (String[] args) {
        String s = "abcdefg";
        int n = 2;
        String res = leftRotateString(s, n);

        System.out.println(res);  //cdefgab
    }

    /*  
    public static String leftRotateString(String str, int n) {
        return str.substring(n) + str.substring(0, n );
    }
    */

    /*    
    public static String leftRotateString(String str, int n) {
        String res = "";
        for (int i = n; i < str.length(); i ++) res += str.charAt(i);
        for (int i = 0; i < n; i ++) res += str.charAt(i);
        return res;
    }
    */

    public static String leftRotateString(String str, int n) {
        char[] s = str.toCharArray();
        reverse(s, 0, n - 1);
        reverse(s, n, s.length - 1);
        reverse(s, 0, s.length - 1);
        return new String(s);
    }

    private  static void reverse (char[] str, int start, int end) {
        while (start < end) {
            char tmp = str[start];
            str[start] = str[end];
            str[end] = tmp;
            start ++;
            end --;
        }
    }
}

AC87. 把字符串转换成整数

import java.util.*;

public class Main {
    public static void main (String[] args) {

        String s = "42"; // 42
        // String s = "-42"; // -42
        // String s = "4193 with words"; // 4193
        // String s = "words and 987"; // 0
        // String s = "-91283472332"; // -2147483648

        int res = myAtoi(s);
        System.out.println(res); 
    }


    public static int myAtoi(String s) {
        int k = 0;
        while (k < s.length() && s.charAt(k) == ' ') k ++;
        if (k == s.length()) return 0;

        int minus = 1;
        if (s.charAt(k) == '-') { minus = -1; k ++; }
        else if (s.charAt(k) == '+') k ++;


        long res = 0;
        while (k < s.length() && s.charAt(k) >= '0' && s.charAt(k) <= '9') {
            res = res * 10 + s.charAt(k ++) - '0';
            if (res > Integer.MAX_VALUE) break;
        }

        res *= minus;

        if (res > Integer.MAX_VALUE) res = Integer.MAX_VALUE;
        if (res < Integer.MIN_VALUE) res = Integer.MIN_VALUE;

        return (int)res;


        /*
        下面是 不用long类型，而是用int 
        int res = 0;
        while (k < s.length() && s.charAt(k) >= '0' && s.charAt(k) <= '9') {
            int x = s.charAt(k ++) - '0';
            if (minus > 0 && res > (Integer.MAX_VALUE - x) / 10) return Integer.MAX_VALUE;
            if (minus < 0 && -res < (Integer.MIN_VALUE + x) / 10) return Integer.MIN_VALUE;

            if (-res * 10 - x == Integer.MIN_VALUE) return Integer.MIN_VALUE;

            res = res * 10 + x;
        }

        res *= minus;
        return res;
        */
    }

}