LeetCode(28) -- 690, 693, 696

P690. Employee Importance (Easy)

一个员工信息的list，第一项存员工ID， 第二项存员工的重要性，第三项存他的直接下属。求他所有下属和他自己的重要性之和。

我的思路

用一个HashMap记录下所有的员工，所有递归遍历就行了。

我的代码

public class E_690_EmployeeImportance {
    public int getImportance(List<Employee> employees, int id) {
        Employee[] employeeArray = new Employee[2000];
        for (Employee employee : employees) {
            employeeArray[employee.id] = employee;
        }
        return sum(id, employeeArray);
    }

    private int sum(int id, Employee[] employeeArray) {
        List<Integer> subs = employeeArray[id].subordinates;
        int ans = employeeArray[id].importance;
        if (subs == null || subs.size() == 0) {
            return ans;
        }
        for (Integer sub : subs) {
            ans += sum(sub, employeeArray);
        }
        return ans;
    }
}

100%

最优解

class Solution {
    int preSum = 0;
    public int getImportance(List<Employee> employees, int id) {
        Employee[] arr = new Employee[2000+1];
        for (Employee e: employees) arr[e.id] = e;
        helper(id, arr);
        return preSum;

    }
    void helper(int id, Employee[] arr){
        // System.out.println("id="+id + ", preSum=" + preSum);
        Employee employee = arr[id];
        preSum += arr[id].importance;
        for (int sid: arr[id].subordinates)
            helper(sid, arr);
        // return preSum;
    }
}

P693. Binary Number with Alternating Bits (Easy)

二进制数，判断它是否是1010交替的。

我的思路

一定是2的奇数次方的和。那么我只需要判断它是否是2的k+1次方减1再乘以2/3即可。整数的最大值就是2的32次方减1，最多32次一定能找到答案。

这只是一种可能。

答案

class Solution {
    public boolean hasAlternatingBits(int n) {
        int cur = n % 2;
        n /= 2;
        while (n > 0) {
            if (cur == n % 2) return false;
            cur = n % 2;
            n /= 2;
        }
        return true;
    }
}

每次都把除以2的余数记下来，然后除以2，然后跟下一次的余数对比，相同就false

P696. Count Binary Substrings (Easy)

连续的0和1个数相同的子数组的数量。

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.

我的思路

每次变化时，都跟上一次计数比较，较小的一个就积累。

我的代码

public class E_696_CountBinarySubstrings {
    public int countBinarySubstrings(String s) {
        int count1 = 0, count2 = 0, ans = 0;
        char[] chars = s.toCharArray();
        int curr = chars[0];
        int i;
        for (i = 0; i < chars.length; i++) {
            if (chars[i] == curr) {
                count1++;
            } else {
                curr = chars[i];
                break;
            }
        }
        while (i < chars.length) {
            if (chars[i] == curr) {
                count2++;
            } else {
                curr = chars[i];
                ans += Math.min(count1, count2);
                count1 = count2;
                count2 = 1;
            }
            i++;
        }
        ans += Math.min(count1, count2);
        return ans;
    }
}

97%

最优解

class Solution {
    public int countBinarySubstrings(String s) {
        char[] a = s.toCharArray();
        int currentcount = 1, prevcount = 0, ans = 0;
        for(int i = 1; i < a.length; i++) {
            if(a[i] == a[i - 1]) {
                currentcount++;
            } else {
                prevcount = currentcount;
                currentcount = 1;
            }
            if(prevcount >= currentcount) {
                ans++;
            }
        }
        return ans;
    }
}

并不用计数结束后再比较，随时就可以比较。