Nice post!
But in permutation,
if(tempList.contains(nums[i])) continue;
is O(n) complexity, right?
This makes the total complexity n^n instead of n! ?
Nice post!
But in permutation,
if(tempList.contains(nums[i])) continue;
is O(n) complexity, right?
This makes the total complexity n^n instead of n! ?
res ^= t.charAt(i) can compile while res = res ^ t.charAt(i) gets "incompatible types: possible lossy conversion from int to char" problem. Any reason?
The question is almost the same as 296 except that here we have obstacles. In 296 we simply calculate its median, while here we have to use bfs. Can we do something on the basis of median solution?
Use a list to store accumulated sum, where list[i] is the sum of nums[0] to nums[i]. Keep the list in ascending order, by finding insertion point using binary search and insert it into the correct position. The following is my code. However it gets a TLE. Can anyone tell me which part might have cost too much time?
public class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
int count = 0;
long acc = 0;
List<Long> list = new LinkedList<Long>();
list.add(acc);
for(int i = 0; i < nums.length; i++){
acc += nums[i];
for(int k = lower; k <= upper; k++){
long remain = acc - k;
int searchRes = search(list, remain);
count += searchRes;
}
int insertPos = Collections.binarySearch(list, acc);
insertPos = (insertPos < 0) ? (-insertPos - 1) : insertPos;
// Keep linkedlist in order.
list.add(insertPos,acc);
}
return count;
}
private int search(List<Long> list, long target){
int pos = Collections.binarySearch(list, target);
if(pos < 0) return 0;
else{
int left, right = 0;
left = (pos == 0) ? 0 : search(list.subList(0,pos),target);
right = (pos == list.size() - 1) ? 0 : search(list.subList(pos + 1, list.size()), target);
return 1 + left + right;
}
}
}
Assume the matrix is [[1,2,3],[1,2,3]], are the vals is treeset 1,3,6, 2,7,16? Assume k is 5, the sum of [2,3] in first and second row both satisfies. The [2,3] in first row is found by 6-1, but how is the [2,3] in the second row is found?
What does this statement mean? What will happen if it were removed?
if(!q.isEmpty() && q.peek().time==timestamp) {
q.peek().count += 1;
}
@ztq63830398 Yeah, that test case was not included. Good job!
public class Solution {
public int longestConsecutive(int[] nums) {
UF uf = new UF(nums.length);
Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // <value,index>
for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
continue;
}
map.put(nums[i],i);
if(map.containsKey(nums[i]+1)){
uf.union(i,map.get(nums[i]+1));
}
if(map.containsKey(nums[i]-1)){
uf.union(i,map.get(nums[i]-1));
}
}
return uf.maxUnion();
}
}
class UF{
private int[] list;
public UF(int n){
list = new int[n];
for(int i=0; i<n; i++){
list[i] = i;
}
}
private int root(int i){
while(i!=list[i]){
list[i] = list[list[i]];
i = list[i];
}
return i;
}
public boolean connected(int i, int j){
return root(i) == root(j);
}
public void union(int p, int q){
int i = root(p);
int j = root(q);
list[i] = j;
}
// returns the maxium size of union
public int maxUnion(){ // O(n)
int[] count = new int[list.length];
int max = 0;
for(int i=0; i<list.length; i++){
count[root(i)] ++;
max = Math.max(max, count[root(i)]);
}
return max;
}
}
delete from Person P where exists (select * from P, Person P2 where P.Id>P2.Id and P.Email=P2.Email);
Me too! What happens to leetcode? Is it I am wrong?