Given a positive 32-bit integer n, you need to find the smallest 32-bit integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive 32-bit integer exists, you need to return -1.
More …Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
More …Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note:
[1, 100].
public boolean checkValidString(String s) {
Deque<Integer> left = new ArrayDeque<>();
Deque<Integer> star = new ArrayDeque<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(c == '*') star.push(i);
else if(c == '(') left.push(i);
else {
if(left.isEmpty() && star.isEmpty()) return false;
if(!left.isEmpty())
left.poll();
else
star.poll();
}
}
if(left.size() > star.size()) return false;
while(!left.isEmpty()){
if(left.poll() > star.poll()) return false;
}
return true;
}
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
class NumArray {
private TreeNode root;
private int[] nums;
public NumArray(int[] nums) {
if(nums.length == 0) return;
root = new TreeNode(nums, 0, nums.length);
this.nums = nums;
}
public void update(int i, int val) {
int change = val - nums[i];
nums[i] = val;
TreeNode cur = root;
while(cur != null){
cur.sum += change;
if(cur.left != null && i >= cur.left.range[0] && i < cur.left.range[1]){
cur = cur.left;
} else if(cur.right != null && i >= cur.right.range[0] && i < cur.right.range[1]){
cur = cur.right;
} else
break;
}
}
public int sumRange(int i, int j) {
return sumRange(root, i, j + 1);
}
private int sumRange(TreeNode cur, int i, int j){
if(cur == null || i < cur.range[0] || j > cur.range[1])
return -1;
if(cur.range[0] == i && cur.range[1] == j)
return cur.sum;
int mid = (cur.range[0] + cur.range[1]) / 2;
if(j <= mid)
return sumRange(cur.left, i, j);
if(i >= mid)
return sumRange(cur.right, i, j);
return sumRange(cur.left, i, mid) + sumRange(cur.right, mid, j);
}
class TreeNode {
int[] range;
int sum;
TreeNode left;
TreeNode right;
TreeNode(int[] nums, int start, int end){
this.range = new int[]{start, end};
int mid = (start + end) / 2;
if(start < end - 1){
left = new TreeNode(nums, start, mid);
right = new TreeNode(nums, mid, end);
this.sum = left.sum + right.sum;
}else {
this.sum = nums[start];
}
}
}
}
A gene string can be represented by an 8-character long string, with choices from “A”, “C”, “G”, “T”.
Suppose we need to investigate about a mutation (mutation from “start” to “end”), where ONE mutation is defined as ONE single character changed in the gene string.
For example, “AACCGGTT” -> “AACCGGTA” is 1 mutation.
Also, there is a given gene “bank”, which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.
Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from “start” to “end”. If there is no such a mutation, return -1.
More …