はじめに
今日ももくもくやっていきたいと思います。今回は、シンプルな問題が多かったです。
String to Integer (atoi)
Implement atoi which converts a string to an integer.
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
Only the space character ' ' is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Example 1:
Input: "42"
Output: 42
Example 2:
Input: " -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
Then take as many numerical digits as possible, which gets 42.
Example 3:
Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:
Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:
Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−231) is returned.
桁が変わる際の動作と、ASCII codeに注意して（'0'をマイナスするのを忘れずに。）解くだけです。
class Solution {
public int myAtoi(String str) {
// Remove whitespace character.
str = str.trim();
// Check length.
if (str.length() == 0) {
return 0;
}
int start = 0, sign = 1, len = str.length();
char head = str.charAt(0);
long sum = 0;
if (head == '+') {
sign = 1;
start++;
} else if (head == '-') {
sign = -1;
start++;
}
for (int i = start; i < len; i++ ) {
char c = str.charAt(i);
if (!Character.isDigit(c)) {
return (int) sum * sign;
}
// Be careful with ASCII code.
sum = sum * 10 + c - '0';
if (sign == 1 && sum > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (sign == -1 && (-1) * sum < Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
}
return (int) sum * sign;
}
}
Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
スタックを使いましょうという問題です。スタックのPopは$O(1)$なので、入力されたストリングをトラバースする$O(n)$が時間計算量です。
また、空間計算量は最大$O(n)$となります（例: '((((('）。
class Solution {
// Hash table that takes care of the mappings.
private HashMap<Character, Character> mappings;
// Initialize hash map with mappings.
public Solution() {
this.mappings = new HashMap<Character, Character>();
this.mappings.put(')', '(');
this.mappings.put('}', '{');
this.mappings.put(']', '[');
}
public boolean isValid(String s) {
if (s == null) {
return false;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (this.mappings.containsKey(c) && !stack.isEmpty()) {
if (stack.pop() != this.mappings.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.isEmpty();
}
}
Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
再帰を使ってパターンを探し出す方法を使って解きましたが、これだと再帰構造により時間計算量・空間計算量ともに$O(2^2n n)$かかってしまうのであまり上手な方法ではありません。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current))
result.add(new String(current));
} else {
current[pos] = '(';
generateAll(current, pos+1, result);
current[pos] = ')';
generateAll(current, pos+1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') balance++;
else balance--;
if (balance < 0) return false;
}
return (balance == 0);
}
}
別の方法として、カッコが閉じているか開いているかをバックトラッキングする方法を使ってこの問題を解いてみます。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, String cur,
int open, int close, int max) {
// Check if we use all parentheses.
if (cur.length() == max * 2) {
ans.add(cur);
return;
}
// Check if we don't use all parentheses.
if (open < max) {
backtrack(ans, cur + "(", open + 1, close, max);
}
// Check if we don't close the parentheses.
if (close < open) {
backtrack(ans, cur + ")", open, close + 1, max);
}
}
}
この記事にあるように、括弧の組み合わせによりカタラン数という漸化式が成り立ちます。(カタラン数は、$O(\frac{4^ n}{n\sqrt{n}})$に収束します。)
したがって、文字列の長さ$n$回分操作されるため、時間計算量は$O(\frac{4^ n}{\sqrt{n}})$となります。空間計算量も同様に$O(\frac{4^ n}{\sqrt{n}})$となります。
最後に同じ計算量でもっとシンプルな解答を載せておきます。こんなの思いつかないですよ、、、。カタラン数を基準となる括弧の中にどれだけ括弧が入るか、括弧の右にどれだけ括弧が来るのかという様に捉え直していますね。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
if (n == 0) {
ans.add("");
} else {
for (int c = 0; c < n; ++c)
for (String left: generateParenthesis(c))
for (String right: generateParenthesis(n-1-c))
ans.add("(" + left + ")" + right);
}
return ans;
}
}
Next Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
与えられた配列の要素を入れ替えることで、辞書順で大きい値を作れという問題です。すでに辞書順で最大の値が与えられている場合には、可能な限り最小の値へとソートさせます。
nums = [4, 1, 3, 7, 6, 5, 2]
という配列を例に考えていきます。
最初にnums[k] < nums[k + 1]という条件を満たす最大のk（配列を左から順に見た際に繰り上がる最初の値）を探します。
これを行うことで、配列の要素が既にどこまで逆順にソートされているか判定します。例を参照すると、nums[2] = 3 より後ろ([7, 6, 5, 4, 2])は要素が逆順にソートされているので、k = 2となります。
nums[k]が存在しない場合は、配列全体が逆順にソートされているので、全体を反転させたものが答えになります。
順列の次に来る配列を求めたいので、繰り上がる幅は、nums[k+1], nums[k+2], ..., nums[n-1]の中で、最小となるもの。つまり、nums[k]の次に大きい値になります。例においては、nums[5] = 5がその値となるので、nums[2] = 3とポジションを入れ替えます（nums = [4, 1, 5, 7, 6, 3, 2]）。
最後に、繰り上がった部分より右側が逆順になっているので、この部分を反転させて、辞書順で一番小さい順番にします。
例において、[7, 6, 3, 2]の部分が逆順のままなので、ここを反転すると nums = [4, 1, 5, 2, 3, 6, 7]となり、答えが得られます。
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i + 1] <= nums[i]) {
i--;
}
if (i >= 0) {
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j);
}
reverse(nums, i + 1);
}
private void reverse(int[] nums, int start) {
int i = start, j = nums.length - 1;
while (i < j) {
swap(nums, i, j);
i++;
j--;
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
時間計算量は$O(n)$、既に与えられた配列の要素を交換するため、空間計算量は$O(1)$となります。
おわりに
明日も頑張ります。