常见的手撕算法题
链表
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
return true;
}
}
return false;
}
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
if(fast==slow){
ListNode cur = head;
while(cur!=slow){
cur = cur.next;
slow = slow.next;
}
return cur;
}
}
return null;
}
public int kthToLast(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
for(int i=0;i<k;i++){
fast = fast.next;
}
while(fast!=null){
fast = fast.next;
slow = slow.next;
}
return slow.val;
}
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for(int i=0;i<=n;i++){
fast = fast.next;
}
while(fast!=null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while(curr!=null){
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head==null||head.next==null) return head;
pre = pre.next;
ListNode dummy = new ListNode(0);
dummy.next = head;
for(int i=1;i<left;i++){
ListNode pre = dummy;
}
ListNode curr = pre.next;
for(int i=0;i<right-left;i++){
ListNode next = curr.next;
curr.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
先找到left的前一个节点作为pre，反转的更新步骤为
next = curr.next
curr.next = next.next;
next.next = pre.next;
pre.next = next;
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
curr.next = list1;
list1 = list1.next;
}else{
curr.next = list2;
list2 = list2.next;
}
curr = curr.next;
}
curr.next = list1!=null?list1:list2;
return dummy.next;
}
public ListNode sortList(ListNode head){
if(head==null||head.next==null) return head;
ListNode mid = getMid(head);
ListNode l = sortList(head);
ListNode r = sortList(mid);
return merge(l,r);
}
public ListNode getMid(ListNode head){
ListNode fast = head.next;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
return mid;
}
public ListNode merge(ListNode l1,ListNode l2){
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
curr.next = l1;
l1 = l1.next;
}else{
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1!=null?l1:l2;
return dummy.next;
}
采用归并排序算法的思想，先找出中点，再递归，最后组合。
验证回文链表 先找中点，反转后一部分，验证是否相等。
public boolean isPalindrome(ListNode head) {
if(head==null||head.next==null) return true;
ListNode res= getMid(head);
ListNode mid = reverse(res);
ListNode curr = head;
while(mid!=null){
if(mid.val!=curr.val){
return false;
}
mid = mid.next;
curr = curr.next;
}
return true;
}
public ListNode getMid(ListNode head){
ListNode fast = head.next;
ListNode slow = head;
while(fast!=null&&fast.next!=null){
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
return mid;
}
private ListNode reverse(ListNode head){
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
字符串
public boolean isPalindrome(String s) {
s = s.toLowerCase().replaceAll("[^a-z0-9]","");
int l=0,r=s.length()-1;
while(l<=r){
if(s.charAt(l)!=(s.charAt(r))){
return false;
}
l++;
r--;
}
return true;
}
s = s.toLowerCase().replaceAll("[^a-z0-9]","");
toLowerCase()将字符转换成小写，replaceAll("[^a-z0-9]","")表示移除字符串中所有非字母数字字符（即只保留小写字母和数字）
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m+1][n+1];
for(int i=0;i<=m;i++){
for(int j=0;j<=n;j++){
if(i==0||j==0){
dp[i][j]=0;
}
else if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1]+1;
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[m][n];
}
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left=0,ans=0;
for(int i=0;i<s.length();i++){
while(set.contains(s.charAt(i))){
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(i));
ans = Math.max(ans,i-left+1);
}
return ans;
}
二叉树
List<Integer> result;
public List<Integer> preorderTraversal(TreeNode root) {
result = new ArrayList<>();
preorder(root);
return result;
}
public void preorder(TreeNode root){
if(root==null) return;
result.add(root.val);
preorder(root.left);
preorder(root.right);
}
List<Integer> res;
public List<Integer> postorderTraversal(TreeNode root) {
res = new ArrayList<>();
postorder(root);
return res;
}
public void postorder(TreeNode root){
if(root==null) return;
postorder(root.left);
postorder(root.right);
res.add(root.val);
}
List<Integer> res;
public List<Integer> inorderTraversal(TreeNode root) {
res = new ArrayList<>();
inorder(root);
return res;
}
public void inorder(TreeNode root){
if(root==null) return;
inorder(root.left);
res.add(root.val);
inorder(root.right);
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()){
int s = q.size();
List<Integer> ans = new ArrayList<>();
for(int i=0;i<s;i++){
TreeNode node = q.poll();
ans.add(node.val);
if(node.left!=null) q.offer(node.left);
if(node.right!=null) q.offer(node.right);
}
res.add(ans);
}
return res;
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||p==root||q==root){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left!=null&&right!=null) return root;
return left!=null?left:right;
}
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left,right)+1;
}
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
return buildBST(head,null);
}
private TreeNode buildBST(ListNode left, ListNode right) {
if (left == right) return null;
ListNode mid = getMid(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = buildBST(left, mid);
root.right = buildBST(mid.next, right);
return root;
}
public ListNode getMid(ListNode head,ListNode right){
ListNode fast = head;
ListNode slow = head;
while(fast!=right&&fast.next!=right){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public int search(int[] nums, int target) {
int l=0,r=nums.length-1;
while(l<=r){
int mid = l+(r-l)/2;
if(target==nums[mid]) return mid;
else if(target<nums[mid]) r=mid-1;
else l=mid+1;
}
return -1;
}
Stack<Integer> a,b;
public MyQueue() {
a = new Stack<>();
b = new Stack<>();
}
public void push(int x) {
a.push(x);
}
public int pop() {
int peek = peek();
b.pop();
return peek;
}
public int peek() {
if(!b.isEmpty()) return b.peek();
if(a.isEmpty()) return a.peek();
while(!a.isEmpty()){
b.push(a.pop());
}
return b.peek();
}
public boolean empty() {
return a.isEmpty()&&b.isEmpty();
}
Queue<Integer> a,b;
public MyStack() {
a = new LinkedList<>();
b = new LinkedList<>();
}
public void push(int x) {
b.offer(x);
while(!a.isEmpty()){
b.offer(a.poll());
}
Queue<Integer> tmp = a;
a=b;
b=tmp;
}
public int pop() {
return a.poll();
}
public int top() {
return a.peek();
}
public boolean empty() {
return a.isEmpty();
}
public int climbStairs(int n) {
if(n<3) return n;
int dp1=1;
int dp2=2;
for(int i=3;i<=n;i++){
int dp3 = dp1+dp2;
dp1 = dp2;
dp2 = dp3;
}
return dp2;
}
public int findMinArrowShots(int[][] points) {
if(points == null||points.length==0){
return 0;
}
Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
int arrows=1;
int arrowend=points[0][1];
for(int i=1;i<points.length;i++){
if(points[i][0]>arrowend){
arrows++;
arrowend = points[i][1];
}
}
return arrows;
}
排序数组 快速排序、选择排序、归并排序等