给一个数组, 给一个操作: 删除一个数字, 然后得到这个数字的分数, 并且必须删除这个数字-1和+1的所有数字, 求最大的分数.

这题就是dp+贪心, 因为要得到最高的分数, 所以肯定要删大的先, 找到最大的删后, 就不用担心这个数字有+1的数字被删掉了. 然而只是贪心不够的, 因为如果是按照排序的数删除的话, 会有[10,8,8,8,8,8]这类情况, 所以还是要dp.

那么设dp[i]为删到大小为i的时候最大的分数. 那么dp[0] = 0, dp[1] = {all 1}, dp[2] = max{all 2 + dp[0], dp[1]}. dp[3] = max{all 3 + dp[1], dp[2]}

dp[i] = {dp[i-2] + sum[i], dp[i-1]}意义是: 两种选法儿, 第一种是选i-2的最佳答案,并且加上sum[i], 因为隔了一个, 所以是能选的. 第二种选法是选上一个的最佳答案, 这次的不要了

class Solution {
    int N = 100001;
    public int deleteAndEarn(int[] nums) {
        int[] sum = new int[N];
        int[] dp = new int[N];
        for(int n : nums)
            sum[n] += n;
        dp[0] = 0;
        dp[1] = sum[1];
        for(int i = 2; i < N; i++)
        {
            dp[i] = Math.max(dp[i - 2] + sum[i], dp[i - 1]);
        }
        //dp[0] = 0
        //dp[1] = sum[1]; all 1's score, because 0 has 0 score.
        //dp[2] = max(dp[0] + sum[2],dp[1])
        return dp[N - 1];
    }
}

给一个string表示数字, 求n次数字位求和后的结果.

class Solution {
    public int getLucky(String s, int k) {
        StringBuilder sb = new StringBuilder();
        for(char c : s.toCharArray())
            sb.append((c - 'a') + 1);
        s = sb.toString();
        while(k != 0)
        { 
            int sum = 0;
            for(char c : s.toCharArray())
            {
                sum += c - '0';
            }
            s = sum + "";
            k--;
        }
        return Integer.valueOf(s);
    }
}

给一个数字n, 求n是否有三个约数.

这个就求一下约数个数即可, 数到3就不数了.

class Solution {
    public boolean isThree(int n) {
        int count = 0;
        for(int i = 1; i <= n; i++)
        {
            if(n % i == 0)
                count++;
            if(count > 3)
                break;
        }
        return count == 3;
    }
}

删除一个字符串里所有三连相同的字符.

class Solution {
    public String makeFancyString(String s) {
        StringBuilder sb = new StringBuilder(s);
        for(int i = 1; i < sb.length() - 1;)
        { 
            if(sb.charAt(i - 1) == sb.charAt(i) && sb.charAt(i) == sb.charAt(i + 1))
                sb.deleteCharAt(i);
            else
                i++;
        }
        return sb.toString();
        
    }
}

给一个字符串s和一个字符串组, 求这个字符串组所组成的prefix字符串有没有s.

class Solution {
    public boolean isPrefixString(String s, String[] words) {
        Set<String> set = new HashSet<>();
        int n = words.length;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++)
        { 
            sb.append(words[i]);
            set.add(sb.toString());
        }
        return set.contains(s);
    }
}

查一个字符串是不是所有出现过的字符的字频都一样

class Solution {
    public boolean areOccurrencesEqual(String s) {
        int[] count = new int[26];
        for(char c : s.toCharArray())
            count[c - 'a']++;
        Integer j = null;
        for(int c : count)
            if(c != 0){
                if(j == null)
                    j = c;
                else
                    if(c != j)
                        return false;
            }
        return true;
    }
}

给一个sorted array组, 求所有的lcs.

这题都sorted了, 所以顺序不再重要, 所以就是查这几个array有几个重复的元素.

class Solution {
    public List<Integer> longestCommomSubsequence(int[][] arrays) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < arrays[0].length; i++)
        {
            set.add(arrays[0][i]);
        }
        for(int i = 1; i < arrays.length; i++)
        {
            Set<Integer> set1 = new HashSet<>(); 
            for(int j = 0; j < arrays[i].length; j++)
            {
                set1.add(arrays[i][j]);
            }
            set.retainAll(set1);
        }
        return new ArrayList<>(set);
    }
}

这个就拓扑查环,没啥说的

class Solution {
    public boolean canFinish(int n, int[][] p) {
        int[] into = new int[n];
        for(int[] pp : p)
            into[pp[0]]++;
         for(int k = 0; k < n; k++)
        {
            int i = 0;
            while(i < n)
            {
                if(into[i] == 0)
                    break;
                i++;
            }
            if(i == n)
                return false;
            into[i] = -1; //visited
            for(int[] pp : p)
                if(pp[1] == i)
                    into[pp[0]]--;
        }
        return true;
    }
}

BFS 方法, 通过入度判断环.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        int[] ind = new int[numCourses]; 
        for(int[] p : prerequisites){
            if(!map.containsKey(p[1]))
                map.put(p[1], new HashSet<Integer>());
            map.get(p[1]).add(p[0]); 
            ind[p[0]]++;
        }  
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        for(int i = 0; i < numCourses; i++)
            if(ind[i] == 0)
                queue.add(i);  
        while(!queue.isEmpty()){
            int n = queue.poll();
            count++;
            for(int nn : map.getOrDefault(n, new HashSet<Integer>())){
                ind[nn]--;
                if(ind[nn] == 0)
                    queue.add(nn);
            }
        }
        return count == numCourses;
    }
}

拓扑排序. 求排序后的结果.

我用的是in-degree数组做法, 一共运行n次, 每次都查找是否有in-degree为0 的点, 如果有, 标记-1(visited), 然后更新相关的边. 用一个into数组, 记录into边的数量, 即可知道是否当前访问的点的所有边都搜索过了. 这个做法简练, 而且不用dfs/bfs什么的那么多数据结构.

class Solution {
    public int[] findOrder(int n, int[][] p) {
        int[] into = new int[n];
        for(int[] pp : p)
            into[pp[0]]++;
        int[] res = new int[n];
        int k = 0;
        for(int i = 0; i < n; i++)
        {
            int j = 0; 
            while(j < n)
            {
                if(into[j] == 0)
                    break;
                j++;
            }
            if(j == n)
                return new int[0]; 
            res[k++] = j;
            into[j] = -1;
            for(int[] pp : p)
                if(pp[1] == j)
                {
                    into[pp[0]]--;
                }
            
        }
        return res;
    }
}

给一个字符串组,由一个空格和domain组成, 求所有subdomain的count.

这题就是分割一下字符串即可. 注意用\\.分割点号

class Solution {
    public List<String> subdomainVisits(String[] cpdomains) {
        List<String> res = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for(String d : cpdomains)
        {
            String[] s = d.split(" ");
            int count = Integer.valueOf(s[0]);
            String[] ss = s[1].split("\\.");
            String tmp = "";
            for(int i = ss.length - 1; i >= 0; i--)
            {
                if(i != ss.length - 1)
                {
                    tmp = "." + tmp;
                }
                tmp = ss[i] + tmp; 
                map.put(tmp, map.getOrDefault(tmp, 0) + count);
            }
        }
        for(Map.Entry<String, Integer> entry : map.entrySet())
        {
            res.add(entry.getValue() + " " + entry.getKey());
        }
        return res;
    }
}