发表于 | 分类于

Given an m * n matrix M initialized with all 0’s and several update operations.

Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.

You need to count and return the number of maximum integers in the matrix after performing all the operations.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Input:
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation:
Initially, M =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]]
After performing [2,2], M =
[[1, 1, 0],
 [1, 1, 0],
 [0, 0, 0]]
After performing [3,3], M =
[[2, 2, 1],
 [2, 2, 1],
 [1, 1, 1]]
So the maximum integer in M is 2, and there are four of it in M. So return 4.

Note:

The range of m and n is [1,40000].
The range of a is [1,m], and the range of b is [1,n].
The range of operations size won't exceed 10,000.

解法1：

思想很巧妙，拥有最大值的数组一定是执行操作最多的。操作共享的最小范围就是row和col分别的最小值。
C++

1

Java

1

发表于 | 分类于

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

1
2
3
4
5
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

1
2
3
4
5
Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:

The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

解法1：

用一个hashtable记录每一个restaurant出现的位置，当出现之前出现过的string的时候更新答案。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        List<String> res = new ArrayList<String>();
        if (list1 == null || list2 == null || list1.length == 0 || list2.length == 0) {
            return new String[0];
        }
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < list1.length; i++) {
            map.put(list1[i], i);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if (map.containsKey(list2[i])) {
                int index = map.get(list2[i]);
                if (index + i == min) {
                    res.add(list2[i]);
                } else if (index + i < min) {
                    res.clear();
                    res.add(list2[i]);
                    min = index + i;
                }
            }
        }
        String[] array = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            array[i] = res.get(i);
        }
        return array;
    }
}

发表于 | 分类于

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

解法1：

两次dp, 每次只考虑头或者尾之中的一个, i.e. [0, n - 1]或者[1, n].
然后找出对应的最大的值就可以了
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];    // forward looking
        int res = dp[0];
        for (int i = 1; i < nums.length - 1; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + (i >= 2 ? dp[i - 2] : 0));
            res = Math.max(dp[i], res);
        }
        // backward looking
        dp = new int[nums.length];
        dp[nums.length - 1] = nums[nums.length - 1];
        res = Math.max(res, dp[nums.length - 1]);
        for (int i = nums.length - 2; i > 0; i--) {
            dp[i] = Math.max(dp[i + 1], nums[i] + (i < nums.length - 2 ? dp[i + 2] : 0));
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

发表于 | 分类于

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Example:

1
2
3
4
5
6
7
8
9
n = 10, I pick 8.
First round:  You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round:  You guess 9, I tell you that it's lower. You pay $9.
Game over. 8 is the number I picked.
You end up paying $5 + $7 + $9 = $21.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

解法1：

试着去选择每一个数作为猜测的答案，然后分为左边和右边分别考虑。
用一个dp记录子问题的结果，dp数组只需要按照对角线填充就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int getMoneyAmount(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 0;
        }
        int[][] dp = new int[n + 1][n + 1]; // dp[i][j] is [i,j] costs
        // Fill the upper triangle from mid to top right
        // len is the count of numbers in this range
        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int temp = Integer.MAX_VALUE;
                for (int pivot = start; pivot <= start + len - 1; pivot++) {
                    temp = Math.min(temp, pivot + Math.max(dp[start][pivot - 1], (pivot == start + len - 1 ? 0 : dp[pivot + 1][start + len - 1])));
                }
                dp[start][start + len - 1] = temp;
            }
        }
        return dp[1][n];      
    }
}

发表于 | 分类于

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

解法1：

一个排列组合的题目，注意一位的数有10种选择，而大于一位的数第一位只有9种。
用一个数组或者一个变量prev记录之前的结果简化运算。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return 10;
        }
        int sum = 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 10;
        dp[2] = 81;
        sum += dp[1] + dp[2];
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] * (9 - i + 2);           
            sum += dp[i];
        }
        return sum;
    }
}

发表于 | 分类于

Given a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
   1
    \
     3
    /
   2
Output:
1
Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

Note: There are at least two nodes in this BST.

解法1：

in-order的traversal是一个排序过后的数组，用一个prev记录上一次访问过的node，然后相邻的比较一下。
用一个global variable寄存
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int min = Integer.MAX_VALUE;
    TreeNode prev = null;
    public int getMinimumDifference(TreeNode root) {
        // bst in order traversal is a sorted array
        // Record the prev node and current node
        // Calculate the difference and compare with global min
        inorder(root);
        return min;        
    }
    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        if (prev != null) {
            min = Math.min(min, Math.abs(prev.val - root.val));
        }
        prev = root;
        inorder(root.right);
    }
}

发表于 | 分类于

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.
Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

1
2
3
Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)

解法1：

每一个divisor都有对应的另外一个divisor， 每次找到一个小的divisor之后对应的大的divisor就成为了新的边界，因为不会再出现比大的divisor再大的没遇见的divisor。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public boolean checkPerfectNumber(int num) {
        int sum = 1;
        int i = 2;
        int right = num;
        while ( i < right) {
            if (num % i == 0) {
                sum += i;
                sum += (num / i);   // the other side,
            }
            right = num / i;
            i++;
        }
        return sum == num && num != 1;
    }
}

发表于 | 分类于

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

1
2
3
4
5
    1
   / \
  2   3
 / \     
4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

解法1：

用一个function计算每一个node的max path， 然后对每一个node更新最大的diameter，每一个node的diameter是left + right。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int diameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        int temp = helper(root);
        return diameter;
    }
    private int helper(TreeNode root) {
        // Use this function to calculate the longest path rooted at "root"
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        // Update the longest path
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;   // Update the longest path rooted at root
    }
}

发表于 | 分类于

Given a binary tree, return the tilt of the whole tree.

The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.

The tilt of the whole tree is defined as the sum of all nodes’ tilt.

Example:

1
2
3
4
5
6
7
8
9
10
Input:
         1
       /   \
      2     3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

Note:

The sum of node values in any subtree won't exceed the range of 32-bit integer.
All the tilt values won't exceed the range of 32-bit integer.

解法1：

对每一个node计算一个total sum,同时也计算出当前node的sum，然后再把这个sum加入到结果中就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int totalTilt = 0;
    public int findTilt(TreeNode root) {
        int temp = helper(root);
        return totalTilt;
    }
    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        totalTilt += Math.abs(left - right);    // update the total tilt
        return left + right + root.val; // return total sum
    }
}

发表于 | 分类于

Find the largest palindrome made from the product of two n-digit numbers.

Since the result could be very large, you should return the largest palindrome mod 1337.

Example:

Input: 2

Output: 987

Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note:

The range of n is [1,8].

解法1：

这题不认为是简单题。。。
主要的思路是，对于一个n位的数字，最大的数字就是pow(10, n) - 1, 那么可以从这个数字开始，计算出最大的可能的乘积。
这就确定了我们搜索的上边界，那么如果把这个数分成左右两半，我们可以把左面的数看成是乘积左面的上边界然后遍历他，直到左面的数小于n个数字。
然后每次对左面的数减1，看是否能构造成两个满足是palindrome的数。
对于拆分成左右两个数，用到了left = prod / mod 和right = prod % mod的办法，其中mod = pow(10, n)
也就是说，对于2位的数，最大可能乘积为4位，那么pow(10,2) = 100，4位的 mod 100可以得到后面两位，左面同理。
对于每一个left的数，构造出一个palindrome的数，然后去看是否满足这个数能被其中一个数整除（范围是[i, prod/i]),其中i从maxNumber开始。

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        int base = 1337;
        int mod = (int)Math.pow(10, n);
        int maxNumber = (int)Math.pow(10, n) - 1;   // Start from maxNumber and traverse until a result is found
        long prod = (long)maxNumber * (long)maxNumber;
        // To split prod into left half and right half
        int left = (int)(prod / mod);  
        int right = (int)(prod % mod);
        if (left == reverse(right)) return (int)(prod % base);
        left--;
        prod = (long)left * (long)mod + (long)reverse(left);
        // Traverse from left to min
        while (left != mod / 10) {
            for (int i = maxNumber; i > prod / i; i--) {
                if (prod % i == 0) {
                    return (int)(prod % base);
                }
            }
            left--;
            prod = (long)left * (long)mod + (long)reverse(left);
        }
        return (int)(prod % base);
    }
    private int reverse(int n) {
        int x = n;
        int res = 0;
        while (x != 0) {
            res = res * 10 + (x % 10);
            x /= 10;
        }
        return res;
    }
}