发表于 | 分类于

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
As long as a house is in the heaters' warm radius range, it can be warmed.
All the heaters follow your radius standard and the warm radius will the same.

Example 1:

1
2
3
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

1
2
3
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

解法1：

Array的题目需要总结一下常见的思路。
一般看到array想想：是否需要排序？可以使用双指针？是否可以dp?
这题的思路是，要覆盖所有的房子，那么每一个房子要知道离他最近的heater在哪里。
我们找出所有房子对应的最近的heater的距离，然后再取最大的距离就是我们所求的最小的radius。
我们可以对heaters排序，然后找寻对于每一个house最近的heaters，这里有一点greedy的思想，就是如果i…j对于房子A不是最近的heater，那么对于一个排在房子A之后的房子B，他们也一定不是最近的heaters。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(houses);
        Arrays.sort(heaters);
        int i = 0, res = 0;
        for (int house: houses) {
            while (i < heaters.length - 1 && Math.abs(heaters[i] - house) >= Math.abs(heaters[i + 1] - house)) {
                i++;
            }
            res = Math.max(res, Math.abs(heaters[i] - house));
        }
        return res;
    }
}

发表于 | 分类于

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

1
2
3
4
5
Input:
3
Output:
3

Example 2:

1
2
3
4
5
Input:
11
Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.

解法1：

不太喜欢这种风格的题。。。
基本思路是：
1 digit => 9 numbers
2 digits => 90 numbers
3 digits => 900 numbers
以此类推。

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 int findNthDigit(int m) {
        long n=m; // convert int to long
        long start=1,  len=1,  count=9;
        while(n>len*count){
            n=n-len*count;
            len++;
            count=count*10;
            start=start*10;
        }
        // identify the number
        start = start + (n-1)/len;
        // identify the digit
        return String.valueOf(start).charAt((int)((n-1)%len))-'0';
    }
}

发表于 | 分类于

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

1
2
Input: 16
Returns: True

Example 2:

1
2
Input: 14
Returns: False

解法1：

基本的binarySearch， 要用一个long来防止overflow.
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 boolean isPerfectSquare(int num) {
        if (num <= 0) {
            return false;
        }
        long start = 1, end = num;
        while (start + 1 < end) {
            long mid = start + (end - start) / 2;
            long temp = mid * mid;
            if (temp < num) {
                start = mid;
            } else if (temp > num) {
                end = mid;
            } else {
                return true;
            }
        }
        if (end * end == num || start * start == num) {
            return true;
        }
        return false;        
    }
}

发表于 | 分类于

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

For example,

1
2
3
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

解法1：

要注意一些细节。需要排除找到的数字不是自己，所以要统计每一个数字出现的次数。
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
public class TwoSum {
    /** Initialize your data structure here. */
    HashMap<Integer, Integer> map = null;
    public TwoSum() {
        map = new HashMap<Integer, Integer>();
    }
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        map.put(number, map.getOrDefault(number, 0) + 1);
    }
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (int key : map.keySet()) {
            int target = value - key;
            if (target == key && map.get(key) > 1 ) {
                return true;
            } else if (target != key && map.containsKey(target)) {
                return true;   
            }
        }
        return false;
    }
}
/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */

发表于 | 分类于

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

1
2
3
4
5
6
7
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB

解法1：

这题做起来有点拗，主要的点就在于那个n–
同时java里面char + integer是返回一个integer，所以需要用(char)去cast一下。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) {
            return "";
        }
        StringBuilder builder = new StringBuilder();
        while (n > 0) {
            n--;    // key to success!
            builder.append((char)('A' + n % 26));            
            n /= 26;
        }   
        return builder.reverse().toString();
    }
}

发表于 | 分类于

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:
1

Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:
2
Note:

Once you move the ball out of boundary, you cannot move it back.
The length and height of the grid is in range [1,50].
N is in range [0,50].

解法1：

比较喜欢memorization的这个解法。
最直观的思路就是对于每一个位置，用递归像4个方向搜索是否能到边界之外。如果可以则返回1.
而每一个节点的数值是所有方向相加。但对于每一个位置(i,j)，和一定剩余的步数k, 这个组合在搜索的过程中会出现多次，所以用一个矩阵来记录下中间结果。

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
public class Solution {
    private int M=1000000007;
    public int findPaths(int m, int n, int N, int i, int j) {
        int[][][] memo = new int[m][n][N + 1];
        for (int k = 0; k < m; k++) {
            for (int l = 0; l < n; l++) {
                for (int p = 0; p <= N; p++) {
                    memo[k][l][p] = -1;
                }
            }
        }
        return helper(m, n, N, i, j, memo);
    }
    private int helper(int m, int n, int N, int i, int j, int[][][] memo) {
        if (i == m || j == n || i < 0 || j < 0) {
            return 1;
        }
        if (N == 0) {
            return 0;
        }
        if (memo[i][j][N] != -1) {
            return memo[i][j][N];
        }
        memo[i][j][N] = ((helper(m, n, N - 1, i + 1, j, memo) + helper(m, n, N - 1, i - 1, j, memo))%M + (helper(m, n, N - 1, i, j + 1, memo) + helper(m, n, N - 1, i, j - 1, memo))%M)%M;
        return memo[i][j][N];
    }
}

发表于 | 分类于

The API: int read4(char *buf) reads 4 characters at a time from a file.

The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.

By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.

Note:
The read function may be called multiple times.

解法1：

这题其实针对的是在I中的解法里的一个问题，就是多读的buf会被扔掉。
这里因为要call multiple times,那么不能扔掉多读的，而是要存起来。
存起来的办法就是建一个queue,先读queue里的数，如果有多的就放回到queue里。
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
/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */
public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    Queue<Character> queue = new LinkedList<>();
    public int read(char[] buf, int n) {
        int i = 0;
        while (i < n && !queue.isEmpty()) {
            buf[i++] = queue.poll();
        }
        // i points to the next inserting position
        while (i < n) {
            char[] buffer = new char[4];
            int len = read4(buffer);
            if (len == 0) {
                return i;
            }
            int j = 0;
            for (; j < len && i < n; j++) {
                buf[i++] = buffer[j];
            }
            while (j < len) {
                queue.offer(buffer[j++]);
            }
        }
        return i;        
    }
}

发表于 | 分类于

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly L characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
L: 16.

Return the formatted lines as:

[
“This is an”,
“example of text”,
“justification. “
]

Note: Each word is guaranteed not to exceed L in length.

解法1：

此题不难，也没有什么考点，可能就是考察编程能力和细心程度把。
思路大体就是先找出来每一行有哪些words,然后在分布空格。
分布空格的时候要从后往前分布，保证比较均匀且较多的空格在左面。
对于最后一行的处理要注意补齐空格。
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<String>();
        if (words.length == 0 || maxWidth < 0) {
            return res;
        }
        int i = 0;
        // coding skill and detail-oriented mindset
        int currentLen = 0;
        List<String> line = new ArrayList<String>();
        while (i < words.length) {
            // need to know if it is the start of a line
            if ((line.isEmpty() ) || currentLen + 1 + words[i].length() <= maxWidth)             {
                currentLen += (line.isEmpty() ? 0 : 1 ) + words[i].length();    // add a space
                line.add(words[i]);
                i++;
            } else {
                // Convert current line into a string and push into res
                res.add(justifyLine(line, maxWidth));
                line = new ArrayList<String>();
                currentLen = 0;
            }
        }
        // treat last line
        if (!line.isEmpty()) {
            String lastLine = String.join(" ", line);
            if (lastLine.length() < maxWidth) {
                int spaces = maxWidth - lastLine.length();
                for (i = 0; i < spaces; i++) {
                    lastLine += " ";
                }
            }
            res.add(lastLine);
        }
        return res;
    }
    private String justifyLine(List<String> words, int maxWidth) {
        StringBuilder builder = new StringBuilder();
        int len = 0;
        for (String s : words) {
            len += s.length();
        }
        int spaces = maxWidth - len;
        if (words.size() == 1) {
            builder.append(words.get(0));
            for (int i = 1; i <= spaces; i++) {
                builder.append(" ");
            }
        } else {
            // distribute evenly
            List<String> temp = new ArrayList<String>();
            for (int i = words.size() - 1; i > 0; i--) {
                int average = spaces / i;
                temp.add(words.get(i));
                for (int s = 0; s < average; s++) {
                    temp.add(" ");
                }
                spaces -= average;                
            }
            // append last word
            temp.add(words.get(0));
            for (int i = temp.size() - 1; i >= 0; i--) {
                builder.append(temp.get(i));
            }
        }
        return builder.toString();
    }    
}

第二遍写的

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        if (words == null || words.length == 0 || maxWidth < 0) {
            return res;
        }
        int start = 0;
        int len = 0;
        for (int i = 0; i < words.length; i++) {
            if (len == 0) len += words[i].length();
            else {
                len += (1 + words[i].length());
            }
            if (len > maxWidth) {
                // means the last step is the right interval to do a justify
                res.add(justify(words, start, i - 1, maxWidth, false));
                start = i;
                len = words[i].length();
            }
        }
        res.add(justify(words, start, words.length - 1, maxWidth, true));        
        return res;
    }
    /*
        Need to concate all words between start and end
    */
    private String justify(String[] words, int start, int end, int maxWidth, boolean lastLine) {
        StringBuilder builder = new StringBuilder();
        // left justify for the single word problem
        if (start == end) {
            builder.append(words[start]);
            for (int i = words[start].length() + 1; i <= maxWidth; i++) {
                builder.append(" ");
            }
            return builder.toString();
        }
        // Calculate the number of space between words
        if (lastLine) {
            int len = 0;
            for (int i = start; i < end; i++) {
                builder.append(words[i]);
                builder.append(" ");
                len += words[i].length() + 1;
            }
            builder.append(words[end]);
            len += words[end].length();
            while (len < maxWidth) {
                builder.append(" ");
                len++;
            }
            return builder.toString();
        }
        int totalLen = 0;
        for (int i = start; i <= end; i++) {
            totalLen += words[i].length();
        }
        int n = end - start + 1;
        /*
        Start filling the words into the sequence
        */
        int totalSpaces = maxWidth - totalLen;
        Stack<String> stack = new Stack<>();
        for (int i = end; i > start; i--) {
            stack.push(words[i]);
            int spaces = totalSpaces / (i - start);
            for (int j = 0; j < spaces; j++) {
                stack.push(" ");
            }
            totalSpaces -= spaces;
        }
        stack.push(words[start]);
        while (!stack.isEmpty()) {
            builder.append(stack.pop());
        }
        return builder.toString();        
    }
}

发表于 | 分类于

Implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char s, const char p)

Some examples:
isMatch(“aa”,”a”) ? false
isMatch(“aa”,”aa”) ? true
isMatch(“aaa”,”aa”) ? false
isMatch(“aa”, ““) ? true
isMatch(“aa”, “a“) ? true
isMatch(“ab”, “?“) ? true
isMatch(“aab”, “ca*b”) ? false

解法1：

这题的关键在于对于*的处理。
DP 不能过OJ
two pointers可以，关键思路是碰到＊先从match 0个字符开始，往后继续match，如果发现不match了那就试着match 1个字符，以此类推。
最后要注意是否pattern还只剩＊
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
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null && p == null) return true;
        if (s == null || p == null) return false;
        int ss = 0, pp = 0, starIndex = -1, match = 0;
        while (ss < s.length()) {
            if (pp < p.length() && (s.charAt(ss) == p.charAt(pp) || p.charAt(pp) == '?')) {
                ss++;
                pp++;
            } else if (pp < p.length() && p.charAt(pp) == '*') {
                starIndex = pp;
                match = ss;
                pp++;
            } else if (starIndex != -1) {
                pp = starIndex + 1;
                match++;
                ss = match;
            } else {
                return false;
            }
        }
        while (pp < p.length() && p.charAt(pp) == '*') {
            pp++;
        }
        return pp == p.length();
    }
}

发表于 | 分类于

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node's key.
The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
Both the left and right subtrees must also be binary search trees.

For example:
Given BST [1,null,2,2],

1
\
2
/
2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

解法1：In-order traversal

这题如果要求可以用extra space 的话很简单，用一个hashmap存储每一个出现的次数就可以了。
现在不能用extra space,那么根据bst的性质，一个中序遍历可以得到一个排序的数组。
对于这个排序数组，我们维护一个prev表示上一个节点，如果两个节点一样，我们更新count,如果不一样，则把当前的count和max相比，如果比max大则更新max并设置count为1.

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
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    TreeNode prev = null;
    int max = 1;
    int count = 1;
    public int[] findMode(TreeNode root) {
        int count = 0;
        TreeNode prev = null;
        ArrayList<Integer> res = new ArrayList<Integer>();
        traverse(root, res);
        int[] resArray = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resArray[i] = res.get(i);
        }
        return resArray;
    }
    private void traverse(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        traverse(root.left, res);
        if (prev != null) {
            if (root.val == prev.val) {
                count++;
            } else {
                count = 1;
            }
        }
        if (count > max) {
            res.clear();
            max = count;
            res.add(root.val);
        } else if (count == max) {
            res.add(root.val);
        }
        prev = root;
        traverse(root.right, res);        
    }
}