杂题

杂题小记

剑指 Offer 57 - II. 和为s的连续正数序列

题目要求返回一个二维数组，且每行元素个数不定

无法由List<List>转变

可以由List<int[]>转变：

class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> res=new ArrayList<>();
        for(int i=1; i<=target/2; i++){
            backtracking(res,new ArrayList<>(),target,i);
        }
        return res.toArray(new int[res.size()][]); //List<int[]> 转变为int[][]
    }

    void backtracking(List<int[]> res, List<Integer> list, int target, int start){
        if(target<=0){
            if(target==0){
                //List<Integer>转变为int[]，无法直接toArray
                int[] arr=new int[list.size()];
                for(int i=0; i<arr.length; i++){
                    arr[i]=list.get(i);
                }
                res.add(arr);
            }
            return;
        }
        list.add(start);
        backtracking(res,list,target-start,start+1);
    }

}

49. Group Anagrams

法一：排序

注意注意注意：

• new String（）一般使用字符转码的时候,byte[]数组的时候
• toString（）将对象打印的时候使用

public class LeetCode49 {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map=new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String s = new String(chars);	//这样可以
            if(!map.containsKey(s)){
                map.put(s,new ArrayList<>());
            }
            map.get(s).add(str);
        }
        return new ArrayList(map.values());
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
            .collect(Collectors.groupingBy(str -> {
                // 返回 str 排序后的结果。
                // 按排序后的结果来grouping by，算子类似于 sql 里的 group by。
                char[] array = str.toCharArray();
                Arrays.sort(array);
                return new String(array);
            })).values());
    }
}

法二：计数

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        return new ArrayList<>(Arrays.stream(strs)
            .collect(Collectors.groupingBy(str -> {
                int[] counter = new int[26];
                for (int i = 0; i < str.length(); i++) {
                    counter[str.charAt(i) - 'a']++;
                }
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 26; i++) {
                    // 这里的 if 是可省略的，但是加上 if 以后，生成的 sb 更短，后续 groupingBy 会更快。
                    if (counter[i] != 0) {
                        sb.append((char) ('a' + i));
                        sb.append(counter[i]);
                    }
                }
                return sb.toString();
            })).values());
    }
}

71. Simplify Path

注意：

• /代表当前路径
• //代表根路径

public class LeetCode71 {
    public String simplifyPath(String path) {
        String[] split = path.split("/");
        LinkedList<String> list=new LinkedList<>();

        for (String s : split) {
            if(s.length()==0 || s.equals(".")){
                continue;
            }
            if(s.equals("..")){
                if(!list.isEmpty()){
                    list.removeLast();
                }
            }else{
                list.add(s);
            }
        }
        StringBuilder sb=new StringBuilder();
        int size=list.size();
        for (int i = 0; i < size; i++) {
            sb.append("/");
            sb.append(list.get(i));
        }
        String s=sb.toString();
        return s.length()==0 ? "/" : s;
    }
}