几个leetcode题型练练手
阿里云师兄说要补一个笔试,果然还是系统笔试只做出来一道太拉了吗:? 不过挺师兄的语气挺轻松:就是写两段代码。但是不打无准备之仗,还是几个类型的题找找手感先。
链表
剑指 Offer II 078. 合并排序链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int n = lists.length;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((o1,o2)->o1.val-o2.val);
for(int i=0;i<n;i++) {
if(lists[i]!=null) minHeap.add(lists[i]);
}
ListNode tmp;
ListNode fakeHead = new ListNode();
ListNode cur = fakeHead;
while(!minHeap.isEmpty()) {
tmp = minHeap.poll();
cur.next = tmp;
cur = cur.next;
if(tmp.next!=null) {
minHeap.add(tmp.next);
}
}
return fakeHead.next;
}
}
剑指 Offer II 077. 链表排序
链表快排
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
// 试一下链表快排
if(head==null || head.next==null) {
return head;
}
int n = 0;
ListNode t = head;
while(t!=null) {
n++;
t = t.next;
}
int c = new Random().nextInt(n);
ListNode p = head;
for(int i=0;i<c;i++) {
p = p.next;
}
ListNode cur = head;
ListNode middle = new ListNode();
ListNode curMiddle = middle;
ListNode left = new ListNode();
ListNode curLeft = left;
ListNode right = new ListNode();
ListNode curRight = right;
while(cur!=null) {
if(cur.val==p.val) {
curMiddle.next = cur;
curMiddle = curMiddle.next;
} else if(cur.val>p.val) {
curRight.next = cur;
curRight = curRight.next;
} else {
curLeft.next = cur;
curLeft = curLeft.next;
}
cur = cur.next;
}
curMiddle.next = null;
curLeft.next = null;
curRight.next = null;
ListNode resultFakeHead = new ListNode();
ListNode result = resultFakeHead;
ListNode ll = left.next;
left = sortList(left.next);
right = sortList(right.next);
result.next = left;
while(result.next!=null) {
result = result.next;
}
result.next = middle.next;
while(result.next!=null) {
result = result.next;
}
result.next = right;
while(result.next!=null) {
result = result.next;
}
result.next = null;
return resultFakeHead.next;
}
}
放入容器中排序
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null) {
return head;
}
List<ListNode> list = new ArrayList<>();
ListNode cur = head;
while(cur!=null) {
list.add(cur);
cur = cur.next;
}
Collections.sort(list,(o1,o2)->o1.val-o2.val);
ListNode fakeHead = new ListNode();
cur = fakeHead;
for(ListNode node:list) {
cur.next = node;
cur = cur.next;
}
cur.next = null;
return fakeHead.next;
}
}
字符串
1023. 驼峰式匹配
class Solution {
public List<Boolean> camelMatch(String[] queries, String pattern) {
List<Boolean> list = new ArrayList<>();
for(int k=0;k<queries.length;k++) {
String query = queries[k];
int pid = 0;
int i=0;
for(;i<query.length();i++) {
if(pid<pattern.length()) {
if(query.charAt(i)==pattern.charAt(pid)) {
pid++;
} else if(query.charAt(i)>='A'&&query.charAt(i)<='Z') {
break;
}
} else if(pid==pattern.length()) {
if(query.charAt(i)>='A'&&query.charAt(i)<='Z') {
break;
}
}
}
list.add(i==query.length()&&pid==pattern.length());
}
return list;
}
}
二叉树
95. 不同的二叉搜索树 II
回溯法(有重复解)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
List<TreeNode> result = new ArrayList<>();
Set<Integer> set = new HashSet<>();
for(int i=1;i<=n;i++) {
set.add(i);
}
Set<Integer> nextSet = new HashSet(set);
for(int r:set) {
TreeNode root = new TreeNode(r);
nextSet.remove(r);
generateTrees0(result,nextSet,root);
nextSet.add(r);
}
return result;
}
private TreeNode copy(TreeNode root) {
if(root==null) return null;
TreeNode result = new TreeNode(root.val);
result.left = copy(root.left);
result.right = copy(root.right);
return result;
}
public void generateTrees0(List<TreeNode> result,Set<Integer> set,TreeNode root) {
if(set.size()==0) result.add(copy(root));
Set<Integer> nextSet = new HashSet(set);
for(int r:set) {
TreeNode node = new TreeNode(r);
nextSet.remove(r);
TreeNode cur = root;
while(true) {
if(r>cur.val) {
if(cur.right==null) {
cur.right = node;
generateTrees0(result,nextSet,root);
cur.right = null;
break;
}
cur = cur.right;
} else {
if(cur.left==null) {
cur.left = node;
generateTrees0(result,nextSet,root);
cur.left = null;
break;
}
cur = cur.left;
}
}
nextSet.add(r);
}
}
}
递归分区
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
private List<TreeNode> result;
public List<TreeNode> generateTrees(int n) {
result = new ArrayList<>();
return generateTreesHelper(1,n);
}
private TreeNode copy(TreeNode root) {
if(root==null) return null;
TreeNode result = new TreeNode(root.val);
result.left = copy(root.left);
result.right = copy(root.right);
return result;
}
private List<TreeNode> generateTreesHelper(int start,int end) {
List<TreeNode> result = new ArrayList<>();
if(start>end) {
result.add(null);
return result;
}
for(int i=start;i<=end;i++) {
TreeNode cur = new TreeNode(i);
for(TreeNode node1:generateTreesHelper(start,i-1)) {
for(TreeNode node2:generateTreesHelper(i+1,end)) {
TreeNode ro = copy(cur);
ro.left = node1;
ro.right = node2;
result.add(ro);
}
}
}
return result;
}
}
动态规划
119. 杨辉三角 II
class Solution {
public List<Integer> getRow(int rowIndex) {
int[] before = new int[rowIndex+1];
int[] result = new int[rowIndex+1];
before[0] = 1;
for(int i=1;i<=rowIndex;i++) {
for(int j=0;j<=i;j++) {
if(j-1<0||j>=i) {
result[j] = 1;
} else {
result[j] = before[j-1]+before[j];
}
}
int[] tmp = before;
before = result;
result = tmp;
}
//System.out.println(Arrays.toString(before));
List<Integer> res = new ArrayList<>();
for(int i=0;i<=rowIndex;i++) {
res.add(before[i]);
}
return res;
}
}
二分查找
287. 寻找重复数
二分
class Solution {
public int findDuplicate(int[] nums) {
int start = 1;
int end = nums.length-1;
while(start<end) {
int mid = (start+end)/2;
int leftCount = 0;
int rightCount = 0;
for(int num:nums) {
if(num>=start&&num<=mid) {
leftCount++;
} else {
rightCount++;
}
}
if(leftCount>mid-start+1) {
end = mid;
} else {
start = mid+1;
}
}
return start;
}
}
环形链表。
多线程
FooBar
import java.util.*;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.Semaphore;
import java.util.stream.IntStream;
public class Main{
private Semaphore semaphoreFoo = new Semaphore(1);
private Semaphore semaphoreBar = new Semaphore(0);
public void printFoo() throws InterruptedException {
for(int i=0;i<100;i++) {
semaphoreFoo.acquire();
System.out.print("Foo");
semaphoreBar.release();
}
}
public void printBar() throws InterruptedException {
for(int i=0;i<100;i++) {
semaphoreBar.acquire();
System.out.println("Bar");
semaphoreFoo.release();
}
}
public static void main(String[] args) throws InterruptedException {
final Main inst = new Main();
final CountDownLatch latch = new CountDownLatch(2);
new Thread(new Runnable() {
@Override
public void run() {
try {
inst.printFoo();
} catch (InterruptedException e) {
e.printStackTrace();
}
latch.countDown();
}
}).start();
new Thread(new Runnable() {
@Override
public void run() {
try {
inst.printBar();
} catch (InterruptedException e) {
e.printStackTrace();
}
latch.countDown();
}
}).start();
latch.await();
}
}