LeetCode(53) -- 1103, 1108, 1122, 1128, 1137, 1154,

P1103. Distribute Candies to People (Easy)

有一些糖果分给n个人，第一个人分一个，第二个人分两个。。。直到第n个人分n个。如果糖果还有剩余，再从第一个人开始，分n+1个，第二个人分n+2个。。。直到分完所有糖果。

我的思路

最简单的方法就是情景模拟，按题目要求实现代码即可。

我的代码

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] ans = new int[num_people];
        int count = 1;
        while (candies != 0) {
            for (int i = 0; i < num_people; i++) {
                if (candies - count >= 0) {
                    ans[i] += count;
                    candies -= count;
                    count++;
                } else {
                    ans[i] += candies;
                    candies = 0;
                    break;
                }
            }
        }
        return ans;
    }
}

92%

最优解

class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] res = new int[num_people];
        int turn = num_people * (num_people + 1) / 2;
        int nturn = 0;
        while (candies >= turn) {
            candies -= turn;
            turn += num_people * num_people;
            nturn++;
        }
        res[0] = nturn + (nturn - 1) * nturn / 2 * num_people;
        for (int i = 1; i < num_people; ++i) {
            res[i] = res[i - 1] + nturn;
        }
        int gift = nturn * num_people + 1;
        int i = 0;
        while (candies > 0) {
            if (candies >= gift) {
                res[i] += gift;
                candies -= gift;
                gift++;
            } else {
                res[i] += candies;
                candies = 0;
            }
            ++i;
        }
        return res;
    }
}

P1108. Defanging an IP Address (Easy)

IP地址，把所有的”.”都换成”[.]”

我的思路

不明白这题有什么意义。。。。

我的代码

class Solution {
    public String defangIPaddr(String address) {
        return address.replaceAll("\\.", "[.]");
    }
}

48%

class Solution {
    public String defangIPaddr(String address) {
        StringBuilder sb = new StringBuilder();
        for (char c : address.toCharArray()) {
            if (c == '.') {
                sb.append("[.]");
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

100%

最优解

class Solution {
    public String defangIPaddr(String address) {
        StringBuilder add = new StringBuilder(address.length() + 32);
    String search = ".";
    String replacement = "[.]";
    int start = 0;
    int found = address.indexOf(search, start);
    while (found != -1) {
        add.append(address.substring(start, found)).append(replacement);
        start = found + search.length();
        found = address.indexOf(search, start);
    }
    add.append(address.substring(start));
    return add.toString();
    }
}

有一点值得学习，indexOf可以设置起始点。其他没什么值得学的，用toCharArray即可。

P1122. Relative Sort Array (Easy)

两个整数数组arr1和arr2，arr2没有重复且arr1包含arr2中的所有数。现在要把arr1按照arr2中数字出现的顺序排序，剩下的没有在arr2中的数字按升序排序。

我的思路

用统计法非常容易就能做出来。

我的代码

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];
        for (int i : arr1) {
            count[i]++;
        }
        int[] ans = new int[arr1.length];
        int indexAns = 0;
        for (int i : arr2) {
            while (count[i] != 0) {
                ans[indexAns++] = i;
                count[i]--;
            }
        }
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                ans[indexAns++] = i;
                count[i]--;
            }
        }
        return ans;
    }
}

100%

最优解

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] counter = new int[1001];
        for(int i:arr1)
            counter[i]++;
        int[] result = new int[arr1.length];
        int index=0;
        for(int j:arr2){
            for(int i=0;i<counter[j];i++)
                result[index++]=j;
            counter[j]*=-1;
        }
        for(int j=0;j<1001;j++){
             for(int i=0;i<counter[j];i++)
                result[index++]=j;
            counter[j]*=-1;
        }
        return result;
    }
}

感觉我的代码更好。

P1128. Number of Equivalent Domino Pairs (Easy)

相等的多米诺骨牌对有多少

Input: dominoes = [[1,2],[2,1],[3,4],[5,6]]
Output: 1

我的思路

因为只有1到9，所以我就用两个二位数来表示一个骨牌。比如骨牌上是1和2，就用12和21来表示。

我的代码

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int[] hashTable = new int[100];
        int count = 0;
        for (int[] domino : dominoes) {
            int i1 = domino[0] * 10 + domino[1];
            int i2 = domino[1] * 10 + domino[0];
            count += hashTable[i1];
            hashTable[i1]++;
            if (i1 != i2) {
                hashTable[i2]++;
            }
        }
        return count;
    }
}

98% 出的bug是如果两个数字是一样的，只需要加一次。

最优解

class Solution {
    public int numEquivDominoPairs(int[][] dominoes) {
        int output = 0;

        int[][] table = new int[10][10];

        for (int i = 0; i < dominoes.length; i++) {
            table[dominoes[i][0]][dominoes[i][1]]++;
        }

        for (int i = 1; i < 10; i++) {
            for (int j = 1; j < 10; j++) {
                int n = 0;
                if (i != j) {
                    n = Math.max(table[i][j] + table[j][i] - 1, 0);
                } else {
                    n = Math.max(table[i][j] - 1, 0);
                }

                output += n*(n + 1)/2;
                table[i][j] = 0;
                table[j][i] = 0;
            }
        }
        return output;
    }
}

用一个二维数组，把出现的次数记下来，然后求每一个数以及它颠倒后出现次数的最大值。 然后求1到n的和，就是pair的个数。

P1137. N-th Tribonacci Number (Easy)

斐波那契数列的变体，每个数都是前三个数相加的结果。

我的思路

斐波那契数列就有很多种方法，怎么做都可以，只要别搞成3^n就行了。

我的代码

class Solution {
    public int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;
        int[] tri = new int[n+1];
        tri[0] = 0;
        tri[1] = 1;
        tri[2] = 1;
        for (int i = 3; i < n + 1; i++) {
            tri[i] = tri[i - 1] + tri[i - 2] + tri[i - 3];
        }
        return tri[n];
    }
}

100%

P1154. Day of the Year (Easy)

给一个”YYYY-MM-DD”格式的日期，返回这一天是当年的第几天。

我的思路

用某人函数应该可以返回日期的差。或者按每个月的天数数一下，注意闰年的问题。（鉴于闰年比较麻烦，还是尽量用内置的函数吧。。。）

最优解

class Solution {
    public int dayOfYear(String date) {
        int[] dpm = new int[] {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};

        int day = (date.charAt(8) - '0') * 10 + date.charAt(9) - '0';
        int month = (date.charAt(5) - '0') * 10 + date.charAt(6) - '0';
        int year = (((date.charAt(0) - '0') * 10 + date.charAt(1) - '0') * 10 + date.charAt(2) - '0') * 10 + date.charAt(3) - '0';

        int leapYear = (month > 2 && (year % 4 == 0) && (year % 100 != 0 || year % 400 == 0)) ? 1 : 0;

        return dpm[month - 1] + day + leapYear;
    }
}

P1160. Find Words That Can Be Formed by Characters (Easy)

给一些单词和一个字符串chars。一个单词是“好”的如果它能用chars里的字母构成，每个字母只能使用一次。

我的思路

把chars的所有字母统计在一个table里，然后每个单词用一个字母就消耗一次，一旦消耗完，就说明不是good

我的代码

class Solution {
    public int countCharacters(String[] words, String chars) {
        int[] table = new int[26];
        for (char c : chars.toCharArray()) {
            table[c - 'a']++;
        }
        int sum = 0;
        for (String word : words) {
            int[] clone = table.clone();
            int i;
            for (i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (clone[c - 'a'] == 0) {
                    break;
                }
                clone[c - 'a']--;
            }
            if (i == word.length()) {
                sum += word.length();
            }
        }
        return sum;
    }
}

80%

最优解

class Solution
{
    public int countCharacters(String[] words, String chars)
    {
        // Array that counts the frequency
        int[] char_counts = new int[26];
        for (char c : chars.toCharArray())
        {
            char_counts[c - 'a']++;
        }

        int count = 0;
        // Iterate through the words and
        for (String word : words)
        {
            // If we can form the word, then add to string
            if (is_valid(word, char_counts))
            {
                count += word.length();
            }
        }

        return count;
    }
    // Function checks if we can make the word w/ count
    boolean is_valid(String word, int[] count)
    {
        // Word Frequency
        int[] used = new int[26];
        for (char c : word.toCharArray())
        {
            used[c - 'a']++;
            // returns false if we use more than we have
            if (used[c - 'a'] > count[c - 'a']) return false;
        }

        return true;
    }
}

感觉跟我的差不多。

P1170. Compare Strings by Frequency of the Smallest Character (Easy)

一个函数f(s)，返回一个字符串中，最小的字母出现的次数。最小的字母是指最靠前的，比如a < b, b < c。

给一个字符串数组words，以及另一个字符串数组queries。对于query 中的每一个单词，问在words中有多少单词的函数值大于该单词的函数值。

我的思路

先写出来这个函数，然后把words中的每个单词都求出来对应的函数值，放在一个新数组中。然后遍历queries，看每个单词的函数值，在words中有多少数比它大。

我的代码

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] ans = new int[queries.length];
        int[] word_f = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            word_f[i] = f(words[i]);
        }
        Arrays.sort(word_f);
        for (int i = 0; i < queries.length; i++) {
            int target = f(queries[i]);
            ans[i] = binarySearch(word_f, target);
        }
        return ans;
    }

    private int f(String s) {
        int count = 0;
        char smallest = 'z';
        for (char c : s.toCharArray()) {
            if (c < smallest) {
                count = 1;
                smallest = c;
            } else if (c == smallest) {
                count++;
            }
        }
        return count;
    }

    private int binarySearch(int[] word_f, int target) {
        if (word_f.length == 1) {
            if (word_f[0] > target) {
                return 1;
            } else {
                return 0;
            }
        }
        int l = 0;
        int r = word_f.length - 1;
        while (l <= r) {
            if (l == r) {
                return word_f.length - l - 1;
            }
            int mid = l + (r - l) / 2;
            if (target >= word_f[mid] && target < word_f[mid + 1]) {
                return word_f.length - mid - 1;
            }
            if (target < word_f[mid]) {
                if (mid == 0) {
                    return word_f.length;
                }
                r = mid - 1;
            } else if (target >= word_f[mid+1]) {
                l = mid + 1;
            }
        }
        return 0;
    }
}

89%，这个binary search 居然写了好几个小时才算终于没bug了。。。

最优解

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {

	   //running sum of number of words with f(W)>=index
		int[] counts = new int[12];
		for (String word : words) counts[f(word)]++;
        for (int i=10; i>=0; i--) counts[i] += counts[i+1];

        int[] ans = new int[queries.length];
		for (int i=0; i<queries.length; i++) ans[i]=counts[f(queries[i])+1];
        return ans;
    }

    private int f(String s) {
        char minChar = Character.MAX_VALUE;
        int freq = 0;
        for (int i=0; i< s.length(); i++) {
            char ch = s.charAt(i);
            if (ch<minChar) {
                freq=1;
                minChar=ch;
            }
            else if (ch==minChar) freq++;
        }
        return freq;
    }
}

函数值最多就是10，所以存成counts，然后从后往前累加，其结果就是有多少个数比这个数大。

P1175. Prime Arrangements (Easy)

我的思路

我的代码

class Solution {
    public int numPrimeArrangements(int n) {
        int prime = countPrimes(n + 1);
        long ans = 1;
        for (int i = 1; i <= prime; i++) {
            ans *= i;
            ans = ans % 1000000007;
        }
        for (int i = 1; i <= n - prime; i++) {
            ans *= i;
            ans = ans % 1000000007;
        }
        return (int)ans;
    }

    private int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        boolean[] f = new boolean[n];
        int count = n / 2;
        for (int i = 3; i * i < n; i += 2) {
            if (f[i]) {
                continue;
            }
            for (int j = i * i; j < n; j += 2 * i) {
                if (!f[j]) {
                    count--;
                    f[j] = true;
                }
            }
        }
        return count;
    }
}

100%

最优解

class Solution {
    public int numPrimeArrangements(int n) {
        if(n <= 2) {
            return 1;
        }
        int count = countPrime(n);
        long sum = 1;
        for(int i = 2; i <= count; i++) {
            sum = (sum * i) % 1000000007;
        }
        for(int i = n - count; i >= 2; i--) {
            sum = (sum * i) % 1000000007;
        }
        return (int)(sum % 1000000007);
    }

    private int countPrime(int n) {
        int count = 0;
        boolean[] v = new boolean[n + 1];
        for(int i = 2; i * i <= n; i++) {
            for(int j = 2; j * i <= n; j++) {
                v[i * j] = true;
            }
        }
        for(int i = 2; i <= n; i++) {
            if(!v[i] && isPrime(i)) {
                count++;
            }
        }
        return count;
    }

    private boolean isPrime(int val) {
        for(int i = 2; i * i <= val; i++) {
            if(val % i == 0) {
                return false;
            }
        }
        return true;
    }
}