0%

String-LEETCODE-100-DAY2

Posted on Edited on Valine:

186.reverse-words-in-a-string-ii)

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

1
2
输入: "the sky is blue"
输出: "blue is sky the"
  • 时间复杂度为O(n)，因为整体遍历和单个单词遍历的的复杂度都为n，r从0走到最右的复杂度也是n，这样就是3n的复杂度，忽略指数，即可得到O(n)
  • 空间复杂度为O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//先整体翻转，然后使用双指针法，将r指向单词后的空格部分，再逐一翻转单词
class Solution {
    public String reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        int r = 0;
        while (r < s.length) {
            int l = r;
            while (r < s.length && s[r] != ' ') {
                r++;
            }
            //因为r在空格上，所以要删除单词的话，就要前进一格。
            reverse(s, l, r - 1);
            r++;
        }

    }
    public void reverse(char[] s, int i, int j) {
        while (i < j) {
            char temp = s[i];
            s[i++] = s[j];
            s[j--] = temp;
        }
    }
}

151. Reverse Words in a String

trim去掉前后空格,split 中的\\s指所有的空格回车,+指有一个或者多个

Given an input string, reverse the string word by word.

Example 1:

1
2
Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

1
2
3
Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

1
2
3
Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// @lc code=start
class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        String[] words = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i--) {
            sb.append(words[i] + ' ');
        }
        return sb.toString().trim();
    }
}
// @lc code=end
// //先整体翻转，然后使用双指针法，将r指向单词后的空格部分，再逐一翻转单词
// class Solution {
//     public String reverseWords(char[] s) {
//         reverse(s, 0, s.length - 1);
//         int r = 0;
//         while (r < s.length) {
//             int l = r;
//             while (r < s.length && s[r] != ' ') {
//                 r++;
//             }
//             //因为r在空格上，所以要删除单词的话，就要前进一格。
//             reverse(s, l, r - 1);
//             r++;
//         }

//     }
//     public void reverse(char[] s, int i, int j) {
//         while (i < j) {
//             char temp = s[i];
//             s[i++] = s[j];
//             s[j--] = temp;
//         }
//     }
// }

345. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:

1
2
Input: "hello"
Output: "holle"

Example 2:

1
2
Input: "leetcode"
Output: "leotcede"

Note:
The vowels does not include the letter “y”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String reverseVowels(String s) {
        if (s == null || s.length() == 0) return s;
        String vowel = "aeiouAEIOU";
        char[] str = s.toCharArray();
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            //如果找不到，就前进
            while (left < right && vowel.indexOf(str[left]) == -1) {
                left++;
            }
            while (left < right && vowel.indexOf(str[right]) == -1) {
                right--;
            }
            char temp = str[left];
            str[left++] = str[right];
            str[right--] = temp;
        }
        return new String(str);
    }
}

13.Roman to Integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 首先将所有的组合可能性列出并添加到哈希表中
// 然后对字符串进行遍历，由于组合只有两种，一种是 1 个字符，一种是 2 个字符，其中 2 个字符优先于 1 个字符
// 先判断两个字符的组合在哈希表中是否存在，存在则将值取出加到结果 ans 中，并向后移2个字符。不存在则将判断当前 1 个字符是否存在，存在则将值取出加到结果 ans 中，并向后移 1 个字符
// 遍历结束返回结果 ans
class Solution {
    public int romanToInt(String s) {
        Map<String, Integer> map = new HashMap<>();
        map.put("I", 1);
        map.put("IV", 4);
        map.put("V", 5);
        map.put("IX", 9);
        map.put("X", 10);
        map.put("XL", 40);
        map.put("L", 50);
        map.put("XC", 90);
        map.put("C", 100);
        map.put("CD", 400);
        map.put("D", 500);
        map.put("CM", 900);
        map.put("M", 1000);
        int ans = 0;
        for(int i = 0;i < s.length();) {
            if (i + 1 < s.length() && map.containsKey(s.substring(i, i+2))) {
                ans += map.get(s.substring(i, i+2));
                i += 2;
            } else {
                ans += map.get(s.substring(i, i+1));
                i++;
            }
        }
        return ans;
    }

12. Integer to Roman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};    
        String[] strs = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < values.length; i++) {
            while (num >= values[i]) {
                num -= values[i];
                sb.append(strs[i]);
            }
        }
        return sb.toString();
    }
}

273. Integer to English Words

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    String[] less20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    String[] tens = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    String[] thousands  = {"", "Thousand", "Million", "Billion"};
    public String numberToWords(int num) {
        if (num == 0) return "Zero";
        String res = "";
        int i = 0;
        while (num > 0) {
            if (num % 1000 != 0) {
                res = helper(num % 1000)+ thousands[i] + " " + res;
            }
            num /= 1000;
            i++;
        }
        return res.trim();          
    }
    public String helper(int num) {
        if (num == 0) return "";
        if (num < 20) {
            return less20[num % 20] + " ";
        } else if (num < 100) {
            return tens[num / 10] + " " + helper(num % 10);
        } else {
            return less20[num / 100] + " Hundred " + helper(num % 100);
        }
    }
}

1.Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly\ one solution, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if(map.containsKey(complement)) {
                return new int[] {map.get(complement), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}
        // for (int i = 0; i < nums.length; ++i) {
        //     for (int j = i + 1; j < nums.length; ++j) {
        //         if (nums[j] == target - nums[i]) {
        //             return new int[] {i, j};
        //         }
        //     }
        // }
        // throw new IllegalArgumentException("No solution");

15.Three Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if (nums == null || len < 3) return ans;
        Arrays.sort(nums);// 排序
        for (int i = 0; i < len; i++) {
            if(nums[i] > 0) break;// 如果当前数字大于0，则三数之和一定大于0，所以结束循环
            if (i > 0 && nums[i] == nums[i-1]) continue;// 去重
            int L = i + 1;
            int R = len - 1;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0) {
                    ans.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    while (L < R && nums[L] == nums[L+1]) L++;// 去重
                    while (L < R && nums[R] == nums[R-1]) R--;// 去重
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }
        return ans;
    }
}

16. 3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

1
2
3
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

  • 3 <= nums.length <= 10^3

  • -10^3 <= nums[i] <= 10^3

  • -10^4 <= target <= 10^4

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    // @lc code=start
    //只有在从小到大排序后，才能移动left和right（因为排序是为了去重）
    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            int res = nums[0] + nums[1] + nums[nums.length - 1];
            Arrays.sort(nums);
            for(int i = 0; i < nums.length - 2; i++) {
                int start = i + 1, end = nums.length - 1;
                while (start < end) {
                    int sum = nums[i] + nums[start] + nums[end];
                    if (sum > target) {
                        end--;
                    } else {
                        start++;
                    }
                    if(Math.abs(sum - target) < Math.abs(res - target)) {
                        //绝对值偏小,说明更接近
                        res = sum;
                    }
                }
            }
            return res;
        }
    }

18. 4 Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class Solution {
    public List<List<Integer>> fourSum(int[] nums,int target){
        /*定义一个返回值*/
        List<List<Integer>> result=new ArrayList<>();
        /*当数组为null或元素小于4个时，直接返回*/
        if(nums==null||nums.length<4){
            return result;
        }
        /*对数组进行从小到大排序*/
        Arrays.sort(nums);
        /*数组长度*/
        int length=nums.length;
        /*定义4个指针k，i，j，h  k从0开始遍历，i从k+1开始遍历，留下j和h，j指向i+1，h指向数组最大值*/
        for(int k=0;k<length-3;k++){
            /*当k的值与前面的值相等时忽略*/
            if(k>0&&nums[k]==nums[k-1]){
                continue;
            }
            /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/
            int min1=nums[k]+nums[k+1]+nums[k+2]+nums[k+3];
            if(min1>target){
                break;
            }
            /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
            int max1=nums[k]+nums[length-1]+nums[length-2]+nums[length-3];
            if(max1<target){
                continue;
            }
            /*第二层循环i，初始值指向k+1*/
            for(int i=k+1;i<length-2;i++){
                /*当i的值与前面的值相等时忽略*/
                if(i>k+1&&nums[i]==nums[i-1]){
                    continue;
                }
                /*定义指针j指向i+1*/
                int j=i+1;
                /*定义指针h指向数组末尾*/
                int h=length-1;
                /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏，忽略*/
                int min=nums[k]+nums[i]+nums[j]+nums[j+1];
                if(min>target){
                    continue;
                }
                /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
                int max=nums[k]+nums[i]+nums[h]+nums[h-1];
                if(max<target){
                    continue;
                }
                /*开始j指针和h指针的表演，计算当前和，如果等于目标值，j++并去重，h--并去重，当当前和大于目标值时h--，当当前和小于目标值时j++*/
                while (j<h){
                    int curr=nums[k]+nums[i]+nums[j]+nums[h];
                    if(curr==target){
                        result.add(Arrays.asList(nums[k],nums[i],nums[j],nums[h]));
                        j++;
                        while(j<h&&nums[j]==nums[j-1]){
                            j++;
                        }
                        h--;
                        while(j<h&&i<h&&nums[h]==nums[h+1]){
                            h--;
                        }
                    }else if(curr>target){
                        h--;
                    }else {
                       j++;
                    }
                }
            }
        }
        return result;
    }
}

242. Valid Anagram

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2
Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] count = new int[26];
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int num : count) {
            if (num != 0) return false;
        }
        return true;
    }
}

49. Group Anagrams

Given an array of strings, group anagrams together.

Example:

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.HashMap;
import java.util.List;
import java.util.*;

/*
 * @lc app=leetcode.cn id=49 lang=java
 *
 * [49] 字母异位词分组
 */

// @lc code=start
//time:O（m + n） m:strs长度 n:strs中最大String的长度
//space: O（n）级别
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        //counting为key, 字符串为value
        //讲aabbc和ababc存入a2b2c1
        HashMap<String, List<String>> map = new HashMap<>();
        for(String str : strs) {
            //对当前的单个单词进行counting sort
            int[] count = new int[26];
            for(Character ch : str.toCharArray()) {
                count[ch - 'a']++;
            }
            //设置基准
            String s = "";
            for(int i = 0; i < count.length; i++) {
                //等于0，说明字母没有出现，在这里只数出现过的字母
                if(count[i] != 0) {
                    //valueOf将字母出现的次数从Int型转换成String类型
                    s += String.valueOf(count[i]) + String.valueOf((char)(i + 'a'));
                    //之前减去a,现在加上a，就恢复到了a
                }
            }
            if (map.containsKey(s)) {
                //如果已经包含了，就取出来，然后加进去
                List<String> list = map.get(s);
                list.add(str);
            } else {
                //如果第一次出现
                List<String> list = new ArrayList<>();//初始化List
                list.add(str);//将2a2b1c和aabbc加入到list中
                map.put(s, list);
            }
        }
        return new ArrayList<>(map.values());
    }
}
// @lc code=end

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

1
2
Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * @lc app=leetcode.cn id=14 lang=java
 *
 * [14] 最长公共前缀
 */

// @lc code=start
class Solution {
    public String longestCommonPrefix(String[] strs) {
       if(strs.length == 0) {
           return "";
       }
       String ans = strs[0];
       for(int i = 1; i < strs.length; i++) {
           int j = 0;
           for(;j < ans.length() && j < strs[i].length();j++) {
               if(ans.charAt(j) != strs[i].charAt(j))
                    break;
           }
           ans = ans.substring(0, j);
           if(ans.equals(""))
                return ans;
       }
            return ans;

    }
}