文章目录

• 前言
• 一、两两交换链表中的节点（力扣24）【递归】
• 二、删除链表的倒数第N个节点（力扣19）
• 三、移除重复节点（面试题 02.01）【借助HashSet】
• 四、每日一题day70：和有限的最长子序列（力扣2389）【前缀和+二分】
• 五、每日一题day71：至少有 1 位重复的数字（力扣1012）【数位DP】
• 六、数字 1 的个数（力扣233）【数位DP】
• 七、2出现的次数（面试题 17.06）
• 八、每日一题day72：无矛盾的最佳球队（力扣1626）【动态规划】

前言

1、两两交换链表中的节点
2、删除链表的倒数第N个节点
3、移除重复节点
4、和有限的最长子序列
5、至少有 1 位重复的数字
6、数字 1 的个数
7、2出现的次数
8、无矛盾的最佳球队

一、两两交换链表中的节点（力扣24）【递归】

分析：
大佬题解

/*** 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 swapPairs(ListNode head) {if(head==null || head.next==null){return head;}ListNode temp = head.next;head.next = swapPairs(temp.next);temp.next = head;return temp;}
}

二、删除链表的倒数第N个节点（力扣19）

分析：
快慢指针：保证快指针和慢指针之间存在n个结点
之后一起++ 直到fast.next==null时，此时slow指针所指位置就是要删除结点的前一个结点

/*** 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 removeNthFromEnd(ListNode head, int n) {//快慢指针 快的先走n+1步 慢指针走1步 之后一起++ 直到快指针==null ListNode dummy = new ListNode(-1,head);if(head==null) return null;ListNode fast;ListNode slow;fast = dummy;slow = dummy;int index =0;//fast先走n步for(int i=0;ifast = fast.next;}//开始同步 说明找到了要删除指针的钱一个指针while(fast.next!=null ){fast=fast.next;slow = slow.next;}slow.next = slow.next.next;//删除指针return dummy.next;}
}

三、移除重复节点（面试题 02.01）【借助HashSet】

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode removeDuplicateNodes(ListNode head) {if(head==null) return head;ListNode current = head;HashSet set = new HashSet<>();set.add(current.val);while(current!=null && current.next!=null){if(set.contains(current.next.val)){current.next = current.next.next;}else{set.add(current.next.val);current = current.next;}}return head;}
}

四、每日一题day70：和有限的最长子序列（力扣2389）【前缀和+二分】

class Solution {public static int[] answerQueries(int[] nums, int[] queries) {int[] res = new int[queries.length];int[] pre = new int[nums.length];//前缀和+二分//1、先排序Arrays.sort(nums);int sum=0;//2、求前缀和for(int i=0;isum+=nums[i];pre[i] = sum;}//3、求结果 返回下标for(int i=0;iif(queries[i]res[i] =0;}else if(queries[i]>pre[pre.length-1]){res[i] =pre.length;}else {int left = 0;int right = pre.length - 1;int middle;int index = 0;//二分查找while (left <= right) {middle = (left + right) / 2;if (pre[middle] >queries[i]) {right = middle - 1;}if (pre[middle] <= queries[i]) {index = middle+1;left = middle + 1;}}res[i] = index;}}return res;}
}

五、每日一题day71：至少有 1 位重复的数字（力扣1012）【数位DP】

分析：
大佬题解

class Solution {char s[];int memo[][];public int numDupDigitsAtMostN(int n) {s = Integer.toString(n).toCharArray();int m = s.length;memo = new int[m][1<<10];for(int i=0;iArrays.fill(memo[i],-1);}return n-f(0,0,true,false);}int f(int i,int mask,boolean isLimited,boolean isNum){if(i==s.length) return isNum?1:0;if (!isLimited && isNum && memo[i][mask]!= -1)return memo[i][mask];int res = 0;if(!isNum){//表示可以跳过位res = f(i+1,mask,false,false);}//不跳过int up = isLimited?s[i]-'0':9;for(int d=isNum?0:1;d<=up;d++){if((mask>>d &1)==0){res+=f(i+1,mask|(1<memo[i][mask] = res;}return res;}
}

六、数字 1 的个数（力扣233）【数位DP】

分析
利用上一题模板 没有前导零不需要考虑isNum
只需要计算1出现的次数

class Solution {char[] s;int[][] dp;//mask:标志 此题中只需要找一 //isNum:需要注意前导零时，需要该标志位//isLimit：是否收到了限制public int countDigitOne(int n) {s = Integer.toString(n).toCharArray();var m = s.length;dp = new int[m][m];for(int i=0;iArrays.fill(dp[i],-1);}return f(0,0,true);}int f(int i,int mask,boolean isLimit){if(i==s.length) return mask;//无限制条件下结束if(!isLimit && dp[i][mask]>=0) return dp[i][mask];int res =0;int up = isLimit?s[i]-'0':9;for(int d = 0;d<=up;d++){res+=f(i+1,mask+(d==1?1:0),isLimit&d==up);}if(!isLimit) dp[i][mask] = res;return res;}
}

七、2出现的次数（面试题 17.06）

分析：
与上一题一摸一样

class Solution {char[] s;int[][] dp;public int numberOf2sInRange(int n) {s = Integer.toString(n).toCharArray();int m = s.length;dp = new int[m][m];for(int i=0;iArrays.fill(dp[i],-1);}return f(0,0,true);}int f(int i,int cnt,boolean isLimit){if(i==s.length) return cnt;if(!isLimit && dp[i][cnt]>=0) return dp[i][cnt];int res =0;int up = isLimit?s[i]-'0':9;for(int d=0;d<=up;d++){res += f(i+1,cnt+(d==2?1:0),isLimit&d==up);}if(!isLimit) dp[i][cnt] = res;return res;}
}

八、每日一题day72：无矛盾的最佳球队（力扣1626）【动态规划】

动规五部曲：
1、确定dp[]数组及下标含义

dp[i]：表示第i个（包含第i个）球员之前拿到的没有矛盾的最大分数

2、递推公式

dp[i] = Math.max(dp[i],dp[j])
//为了方便处理只有一个数据的情况
在循环外：
dp[i] += people[i][0];

3、初始化

dp[0] = people[0][0]

4、遍历顺序

从左到右

class Solution {public int bestTeamScore(int[] scores, int[] ages) {//动态规划int n = scores.length;int[][] people = new int[n][2];for(int i=0;ipeople[i][0] = scores[i];people[i][1] = ages[i];}int[] dp = new int[n];int res = 0;//按照分数递增排序 当分数相同时 按照年龄递增排序Arrays.sort(people,(a,b)->a[0]!=b[0]?a[0]-b[0]:a[1]-b[1]);for(int i=0;ifor(int j=i-1;j>=0;j--){if(people[i][1]>=people[j][1]){dp[i] = Math.max(dp[j],dp[i]);}}dp[i] +=people[i][0];res = Math.max(dp[i],res);}return res;}
}