第17天--算法（Leetcode 22,23,26）
22.括号生成
public List generateParenthesis(int n) {
char path[] = new char[n * 2];
List res = new ArrayList<>();
if(n == 0) {
return res;
}
process(path,0,0,n,res);
return res;
}
public void process(char path[],int index,int leftMinusRight,int restLeft,List res) {
if(index == path.length) {
res.add(String.valueOf(path));
}else {
if(restLeft > 0) {
path[index] = '(';
process(path,index + 1,leftMinusRight +1 ,restLeft - 1,res);
}
if(leftMinusRight > 0) {
path[index] = ')';
process(path,index + 1,leftMinusRight - 1,restLeft,res);
}
}
}
23.合并K个升序链表
public ListNode mergeKLists(ListNode[] lists) {
ListNode res = new ListNode();
if(lists == null || lists.length == 0) {
return null;
}
PriorityQueue priorityQueue = new PriorityQueue(new ListNodeComparator());
for(int i = 0;i < lists.length;i ++) {
if(lists[i] != null) {
priorityQueue.add(lists[i]);
}
}
if(priorityQueue.isEmpty()) {
return null;
}
ListNode cur = res;
while(!priorityQueue.isEmpty()) {
ListNode temp = priorityQueue.poll();
cur.next = new ListNode(temp.val);
cur = cur.next;
if(temp.next != null) {
priorityQueue.add(temp.next);
}
}
return res.next;
}
class ListNodeComparator implements Comparator {
@Override
public int compare(Object o1, Object o2) {
ListNode l1 = (ListNode) o1;
ListNode l2 = (ListNode) o2;
return l1.val - l2.val;
}
}
26.删除有序数组中的重复项
public int removeDuplicates(int[] nums) {
if(nums == null || nums.length == 0) {
return 0;
}
if(nums.length == 1) {
return 1;
}
int i = 0;
int j = 1;
for(;j < nums.length;) {
if(nums[i] == nums[j]) {
j ++;
}else {
int temp = nums[i + 1];
nums[i + 1] = nums[j];
nums[j] = temp;
i ++;
j ++;
}
}
return i + 1;
}