算法—-字符串

算法之路

链表

树

数组

1 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

leetcode-cn.com/problems/la…

    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }
        String[] strAtr = new String[nums.length];
        for (int i = 0; i < strAtr.length; i++) {
            strAtr[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(strAtr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        StringBuilder sb = new StringBuilder();
        for (String aStrArr : strAtr) {
            sb.append(aStrArr);
        }
        String result = sb.toString();
        if ('0' == result.charAt(0)) {
            result = "0";
        }
        return result;
    }
}
复制代码

2 有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。
对于 nums[3]=2 存在一个比它小的数字：（1）。
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/ho…

    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n=nums.length;
		int []res=new int[n];
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(i==j)continue;
				if(nums[j]<nums[i]) {
					res[i]++;
				}
			}
		}
		return res;
    }
}
复制代码

3 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

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

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/zu…

 public int lengthOfLongestSubstring(String s) {
        if (s.length() <= 0) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int length = 0;

        HashSet<Character> hashSet = new HashSet<>();
        while (right < s.length()) {
            if (hashSet.contains(s.charAt(right))) {
                hashSet.remove(s.charAt(left));
                left++;
            } else {
                hashSet.add(s.charAt(right));
                right++;
            }
            length = hashSet.size() > length ? hashSet.size() : length;
        }
        return length;
    }
复制代码

4 无重复字符的最长子串

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

示例 1:

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

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

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/lo…

 public int lengthOfLongestSubstring(String args) {
         if (args.length() <= 0) {
            return 0;
        }

        int left = 0;
        int right = 0;
        int length = 0;
        HashSet<Character> hashSet = new HashSet<>();
        while (right < args.length()) {
            if (hashSet.contains(args.charAt(right))) {
                hashSet.remove(args.charAt(left++));
            } else {
                hashSet.add(args.charAt(right++));
            }
            length = hashSet.size() > length ? hashSet.size() : length;
        }
        return length;
    }
复制代码

5 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”
示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/lo…

public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String s = strs[0];
        for (String str : strs) {
            while (!str.startsWith(s)) {
                s = s.substring(0, s.length() - 1);
            }
        }
        return s;
    }
复制代码

6 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：”abbaca”
输出：”ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/re…

 public String removeDuplicates(String s) {
        if (s.length() <=0){
            return s;
        }
        return removeHelper(new StringBuilder(s)).toString();
    }

    static StringBuilder removeHelper(StringBuilder sb) {
        for (int i = 0; i + 1 < sb.length(); i++) {
            if (sb.charAt(i) == sb.charAt(i + 1)) {
                sb.delete(i, i + 2);
                return removeHelper(sb);
            }
        }
        return sb;
    }
复制代码