青训营-小R的城市稳定性挑战
问题描述
小R所在的国家有n个城市，每个城市的人口为 a_i。如果某个城市的人口不超过其他任何一个城市人口的两倍，那么这个城市就被认为是稳定的。国家可以对部分城市实施政策，从而改变它们的人口数量。你的任务是帮助小R找到最少需要对多少个城市进行人口修改，才能使所有城市都变得稳定。
例如：对于城市人口为 [1, 2, 3, 4] 的国家，最少需要对1个城市执行政策，才能使所有城市稳定。
测试样例样例1：
输入：n = 4 ,a = [1, 2, 3, 4]输出：1
样例2：
输入：n = 5 ,a = [1, 10, 20, 30, 40]输出：2
样例3：
输入：n = 3 ,a = [100, 50, 200]输出：1
思路每个城市的人口如果不超过其他城市人口的两倍，则这个城市是稳定的。换句话说，城市 i 的人口 a_i和城市j的人口a_j必须满足：
我们需要找出最少修改多少个城市的人口，才能使所有城市都满足这个条件。
滑动窗口：通过滑动窗口（或者双指针方法）来找到最长的稳定子数组。最长稳定子数组中的城市不需要修改，因此最少修改的城市数是 n - 最大稳定子数组长度 ...
青训营-小R的三的倍数分解
问题描述小R拿到了一些正整数，这些正整数都是3的倍数。他需要将每一个数$n$分解为三个3的倍数，并且每种分解方法的顺序不同也视为不同的分解方式。你的任务是帮助小R计算每个$n$可以分解成三个3的倍数的方法数。如果某个数无法分解，则返回0。需要注意的是，分解出的每个数都不能为0。
测试样例样例1：
输入：n = 9输出：1
样例2：
输入：n = 12输出：3
解答：123456789101112131415161718192021import mathdef solution(n: int) -> int: # 如果 n 不能被 3 整除，返回 0 if n % 3 != 0: return 0 # 计算 m = n / 3 m = n // 3 # 如果 m < 3，无法分解为三个正整数 3 的倍数 if m < 3: return 0 # 返回 C(m-1, 2)，即从 m-1 中选择 2 个 分割位置 return math.comb(m - 1, 2 ...
70. 爬楼梯
f(x) 表示爬到第 x 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下状态方程：
f(x)=f(x−1)+f(x−2)
记忆化搜索：
设置int[]dp数组，int[n]表示f(x)，n=1,2时直接返回。
1234567891011class Solution { public int climbStairs(int n) { if(n==1)return 1; if(n==2)return 2; int[]dp=new int[n+1]; dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++)dp[i]=dp[i-1]+dp[i-2]; return dp[n]; }}
19. 删除链表的倒数第 N 个结点
链表常见解法：使用前后指针, 前指针遍历完时后指针指向删除节点；
1234567891011121314151617181920212223242526/** * 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) { ListNode dummy=new ListNode(0,head); ...
2956.找到两个数组中的公共元素
把数组转成哈希集合，就可以 O(1) 判断元素是否在数组中了。
123456789101112131415161718192021222324class Solution { public int[] findIntersectionValues(int[] nums1, int[] nums2) { HashSet<Integer>set1=new HashSet<>(); for(int x:nums1){ set1.add(x); } HashSet<Integer>set2=new HashSet<>(); for(int x:nums2){ set2.add(x); } int n1=0,n2=0; for(int x:nums1) ...
206.反转链表
思路：
申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
1234567891011121314151617181920212223/** * 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 { ...
2.两数相加
创建哨兵节点在返回的链表节点之前，之后采用节点指针遍历，注意判断终止条件，如果有进位也要继续。
1234567891011121314151617181920212223242526/** * 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 addTwoNumbers(ListNode l1, ListNode l2) { ListNode head=new ListNo ...
1.两数之和
暴力：双循环
正解：
哈希表<值，下标>
先find找不到再insert，保证不会和自己匹配。
123456789101112class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; ++i) { if (hashtable.containsKey(target - nums[i])) { return new int[]{hashtable.get(target - nums[i]), i}; } hashtable.put(nums[i], i); } ...
数据投毒攻击
数据投毒攻击（Data Poisoning Attack）定义为攻击者在机器学习模型的训练阶段，通过向训练数据集中注入少量精心设计的恶意样本（也称为“毒化样本”），从而影响模型的学习过程。这些恶意样本利用模型的训练或微调（fine-tuning）过程，使得模型在测试阶段或部署后的预测阶段表现异常。数据投毒攻击的目的是破坏模型的可用性或完整性，导致模型对于特定的输入产生错误的输出，或者在更广泛的范围内降低模型的准确性和可靠性。
理论模型数据投毒的威胁模型可以根据攻击者的目标、知识水平和攻击方式来描述。攻击者的目标可以分为有目标和无目标两种。在无目标攻击中，攻击者旨在尽可能地产生模型错误预测，而有目标攻击则专注于特定的测试样本，试图改变模型对其分类结果。攻击者的知识水平对攻击的能力和战略至关重要。白盒攻击者了解目标机器学习系统的任务、算法、数据集和内部工作原理，可以直接访问训练数据和模型权重。黑盒攻击者无法直接访问受害模型和数据集，但可以利用替代数据集和模型来模拟原始系统。灰盒攻击者则对目标模型部分了解。攻击者可以通过修改数据的标签或内容来进行数据投毒。标签修改是指操纵数据的标签，例如将数 ...
知识蒸馏
知识蒸馏（Knowledge Distillation）是一种模型压缩技术，它允许一个大型、复杂的模型（称为“教师模型”）的知识被转移到一个更小、更简单的模型（称为“学生模型”）。这种方法的核心目的是在保持性能的同时减少模型的复杂性和计算资源需求，从而使得模型更适合在资源受限的环境下部署。[1]知识蒸馏的基本流程包括两个阶段：首先是训练一个复杂的教师模型，然后使用这个模型的输出或中间结果作为学生模型训练的监督信号来训练一个结构更简单、参数更少的学生模型。在知识蒸馏中，根据所使用的知识类型，可以将其分为几种不同的策略，每种策略利用教师模型的不同方面来指导学生模型的学习。以下是三种主要的知识蒸馏策略：基于响应的知识蒸馏，这种策略主要关注于教师模型的最后一层输出，即类别的logits（未经softmax层处理的原始输出）。学生模型的目标是模仿这些logits，而不是直接模仿softmax层后的概率分布。这种方法假设对数向量Z为全连接层的最后输出，学生模型的训练可以通过最小化学生模型的logits和教师模型的logits之间的差异来完成。这种差异通常通过KL散度（Kullback-Leible ...