考研算法辅导课总结

辅导课总结"/>

考研算法辅导课总结

这考研算法辅导课总结

• 建议根据大标题和题号来刷题
• • 排序和进位制
  • • 3375. 成绩排序
    • 3376. 成绩排序2
    • 3373. 进制转换
    • 3374.进制转换2
  • 链表和日期问题
  • • 66.两个链表的第一个公共节点
    • 3756.筛选链表
    • 3757.重排链表
    • 3607 打印日期
    • 3573.日期累加

本篇文章适用于考研和复试上机的同学，建议去ACWING买考研算法辅导课同步刷题，上岸的c++选手贼多，我都拿的是Java写的，有些拿c++写的，简单做法和最优做法基本都有，仅供参考！！！

建议根据大标题和题号来刷题

排序和进位制

3375. 成绩排序

import java.util.*;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int k = sc.nextInt();int[][] arr = new int[n][2];String[] s = new String[n];for(int i = 0; i < n; i++){s[i] = sc.next();arr[i][0] = i;arr[i][1]= sc.nextInt();}if(k == 1){Arrays.sort(arr,(o1,o2)->{return o1[1]-o2[1];});   }else{Arrays.sort(arr,(o1,o2)->{return o2[1]-o1[1];});   }for(int[] x: arr){System.out.print(s[x[0]]+" ");System.out.println(x[1]);}}
}

3376. 成绩排序2

import java.util.*;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[][] arr = new int[n][2];for(int i = 0; i < n; i++){arr[i][0] = sc.nextInt();arr[i][1] = sc.nextInt();}Arrays.sort(arr,(o1,o2)->{if(o1[1] != o2[1]){return o1[1] - o2[1];}return o1[0] - o2[0];});   for(int[] x: arr){System.out.print(x[0]+" ");System.out.println(x[1]);}}
}

3373. 进制转换

package Acwing;import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class AC3373_2 {static Deque<Integer> div(Queue<Integer> queue, int b){Deque<Integer> tmp = new LinkedList<>();int cnt = queue.size();int r = 0;while(cnt-- != 0){r = r * 10 + queue.poll();tmp.offer(r/b);r %=b;}while(tmp.size() != 0 && tmp.peek()==0){tmp.poll();}return tmp;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);while(sc.hasNext()){String x = sc.next();Deque<Integer> queue = new LinkedList<>();for(char c: x.toCharArray()){queue.offer(c-'0');}StringBuilder res = new StringBuilder();if("0".equals(x)){res.append("0");}else{while(!queue.isEmpty()){System.out.println(queue.peekLast());res.append(queue.peekLast()%2);queue =  div(queue,2);}}System.out.println(res.reverse());}}
}import java.util.*;
import java.math.BigInteger;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext()){BigInteger b = sc.nextBigInteger();System.out.println(b.toString(2));}}
}

3374.进制转换2

import java.util.*;
import java.math.BigInteger;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext()){int m = sc.nextInt();int n = sc.nextInt();BigInteger b = sc.nextBigInteger(m);System.out.println(b.toString(n));}}
}import java.util.*;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int a = sc.nextInt();int b = sc.nextInt();String s = sc.next();Deque<Integer> queue = new LinkedList<>();for(char c: s.toCharArray()){int x = 0;if(c>='A'){x = c-'A'+10;}else{x = c-'0';}queue.offer(x);}StringBuilder sb = new StringBuilder();if("0".equals(s)){sb.append("0");}else{while(!queue.isEmpty()){Deque<Integer> tmp = new LinkedList<>();int cnt = queue.size();int r = 0;for(int i = 0; i < cnt; i++){int t = queue.poll();//计算t的十进制t += r * a;//记录余数r= t%b;//记录除数t = t/b;tmp.offer(t);}while(!tmp.isEmpty() && tmp.peek()== 0){tmp.poll();}queue=tmp;if(r <10){sb.append(r);}else{sb.append((char)(r-10+'a'));}}System.out.println(sb.reverse());}}
}

链表和日期问题

66.两个链表的第一个公共节点

这个题有两种做法：

链表相加：
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
class Solution {public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {ListNode h1 = headA;ListNode h2 = headB;while(h1!=h2){h1 = h1!=null? h1.next:headB;h2 = h2!=null? h2.next:headA;}return h1;}
}
链表相减找后半段：
/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
class Solution {public ListNode findFirstCommonNode(ListNode headA, ListNode headB) {ListNode h1 = headA;ListNode h2 = headB;int len1 = 0;int len2 = 0;while(h1 != null){len1++;h1 = h1.next;}while(h2 != null){len2++;h2 = h2.next;}if(len1 <= len2){for(int i = 0; i < len2 - len1; i++){headB = headB.next;}}else{for(int i = 0; i < len1 - len2; i++){headA = headA.next;}}while(headA!=null&&headB!=null){if(headA.val==headB.val){return headA;}headA = headA.next;headB = headB.next;}return null;}
}作者：福尔摩DONG
链接：/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3756.筛选链表

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* filterList(ListNode* head) {bool st[10001] = {};ListNode *dummy = new ListNode(-1);ListNode *cur = dummy, *p = new ListNode(-1);while(head){int val = abs(head->val);if(!st[val]){cur->next = head;p = head;cur = cur->next;st[val] = true;}head = head->next;}p->next = NULL;return dummy->next;}
};

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode filterList(ListNode head) {HashSet<Integer> set = new HashSet<>();ListNode dummy = new ListNode(-1);ListNode cur = dummy,h1 = new ListNode(-1);while(head!=null){int x = Math.abs(head.val);if(!set.contains(x)){cur.next = head;h1 = head;cur = cur.next;set.add(x);} head = head.next;}h1.next = null;return dummy.next;}
}

3757.重排链表

ListNode在 = 赋值的时候，传递的是地址。前半段要记得终止，就要是的a->next = null，而在遍历的时候使用的是指针。地址是全局的。相当于链表的最后一个肯定要指向空/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public void rearrangedList(ListNode head) {//计算链表长度ListNode p = head;int len = 0;while(p!=null){len++;p = p.next;}int left = (len+1)/2;ListNode a = head;for(int i = 0; i < left-1; i++){a = a.next;}ListNode b = a.next;a.next = null;ListNode pre = null;while(b!=null){ListNode c = b.next;b.next = pre;pre = b;b = c;}while(pre!=null){ListNode ta = head.next, tb = pre.next;head.next = pre;pre.next = ta;head = ta;pre = tb;}}
}

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:void rearrangedList(ListNode* head) {ListNode *h = head;int len = 0;while(h){len++;h = h->next;}int left = (len+1)/2;ListNode *l = head;for(int i = 0; i < left-1; i++){l = l->next;}ListNode *r = l->next;l->next = NULL;ListNode *pre = NULL;while(r){ListNode *ne = r ->next;r->next = pre;pre = r;r = ne;}while(pre){ListNode *l1 = head->next;ListNode *r1 = pre->next;head ->next =pre;pre->next = l1;head = l1;pre = r1;}}
};

3607 打印日期

一年中的天数为

1,3,5,7,8,10,12为31天，2月的话闰年为29天，平年为28天。

闰年的话分为普通闰年和世纪闰年，4年一闰，百年不闰或400年一闰。

这个比较恶心的是yyyy-mm-dd，

可以用prinf试试，卧槽，printf可以补前导0，绝了，以前不知道，一直特判，人傻了。。。

import java.util.*;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int[] arr1 = {31,28,31,30,31,30,31,31,30,31,30,31};int[] arr2 = {31,29,31,30,31,30,31,31,30,31,30,31};while(sc.hasNext()){int x = sc.nextInt();int y = sc.nextInt();  if((x%4==0&&x%100!=0)||(x%400==0)){for(int i = 1; i <= 12; i++){y = y - arr2[i-1];if(y<=0){System.out.printf("%04d-%02d-%02d\n",x,i,(y+arr2[i-1]));break;}}}else{for(int i = 1; i <= 12; i++){y = y - arr1[i-1];if(y<=0){System.out.printf("%04d-%02d-%02d\n",x,i,(y+arr1[i-1]));break;}}}}}
}

import java.util.*;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int[] arr1 = {31,28,31,30,31,30,31,31,30,31,30,31};int[] arr2 = {31,29,31,30,31,30,31,31,30,31,30,31};while(sc.hasNext()){int x = sc.nextInt();int y = sc.nextInt();  String xx = String.valueOf(x);if(xx.length()<4){for(int i = 0; i < 4-xx.length();i++){xx = "0"+xx;}}if((x%4==0&&x%100!=0)||(x%400==0)){for(int i = 1; i <= 12; i++){y = y - arr2[i-1];if(y<=0){System.out.println(xx+"-"+(i<10?"0":"")+i+"-"+(arr2[i-1]+y<10?"0":"")+(arr2[i-1]+y));break;}}}else{for(int i = 1; i <= 12; i++){y = y - arr1[i-1];if(y<=0){System.out.println(xx+"-"+(i<10?"0":"")+i+"-"+(arr1[i-1]+y<10?"0":"")+(arr1[i-1]+y));break;}}}}}
}

3573.日期累加

import java.util.*;
class Main{//日期问题三板斧static int[] month = {0,31,28,31,30,31,30,31,31,30,31,30,31};static int is_leap(int year){if((year %4 == 0&& year %100 !=0)||(year % 400 == 0)){return 1;}return 0;}static int get_month(int y ,int m){if(m == 2){//获得月份天数return month[m]+is_leap(y);}return month[m];}public static void main(String[]args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();while(n-- != 0){int y = sc.nextInt();int m = sc.nextInt();int d = sc.nextInt();int a = sc.nextInt();int sum = 0;//算总数从一年的开始开始算        for(int i = 1; i < m; i++){sum +=get_month(y,i);}sum+=d+a;//然后按年算while(sum > 365+is_leap(y)){sum -= 365+is_leap(y);y++;}m = 1;//按月算while(sum > get_month(y,m)){sum -=get_month(y,m);m++;}//最后剩下的就是天数System.out.printf("%04d-%02d-%02d\n",y,m,sum);}}
}