/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
std::vector<int> quickSelect(std::vector<int>& nums, int left, int right, int k) {
int i = partition(nums, left, right);
/* 下标转换
要找的是最小的前 k 个元素，也就是下标 [0 ... k - 1]
当 i == k - 1，[0, i] 正好是前 k 小的元素
*/
if (i + 1 == k) {
return std::vector<int>(nums.begin(), nums.begin() + k);
}
if (i + 1 > k) {
// i > k-1, 左边已经包含了超过 k 个最小数，继续在左半边查找。
return quickSelect(nums, 0, i - 1, k);
} else {
// i < k - 1, 左边不够 k 个最小数，还需要从右侧补足，在右半边递归找剩下的 k - (i + 1) 个数
return quickSelect(nums, i + 1, right, k);
}
return {};
}
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}
nums[right] = pivot;
return right;
}
class Solution {
public:
int jewelleryValue(vector<vector>& frame) {
int m = frame.size();
if (m 0) return 0; // 处理空矩阵
int n = frame[0].size();
vector<vector> dp(m, vector(n, 0));
class Solution {
public:
int m,n,cnt;
vector<vector> visit;
int wardrobeFinishing(int m, int n, int cnt) {
this->m=m;
this->n=n;
this->cnt=cnt;
visit.resize(m, vector(n, false));
return dfs(0,0);
}
int dfs(int i, int j) {
if(i<0 || i>=m || j<0 || j>=n || digit(i)+digit(j)>cnt || visit[i][j]) {
return 0;
}
class Solution {
int m; // 棋盘的行数
int n; // 棋盘的列数
int k; // 位数和的限制
boolean[][] visited; // 用于记录每个格子是否被访问过
// 主方法，计算机器人能够到达的格子数量
public int movingCount(int m, int n, int k) {
this.m = m; // 初始化棋盘的行数
this.n = n; // 初始化棋盘的列数
this.k = k; // 初始化位数和的限制
visited = new boolean[m][n]; // 初始化访问记录数组，初始值为 false
return dfs(0, 0); // 从左上角 (0,0) 开始深度优先搜索
}
// 深度优先搜索方法
int dfs(int i, int j) {
// 判断当前格子是否在棋盘范围内、是否未被访问过、位数和是否小于等于 k
if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k < sum(i) + sum(j)) {
return 0; // 如果不满足条件，返回 0
}
// 遍历board的每一个位置，尝试从每个位置开始搜索
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果从位置(i, j)开始能够找到单词，则返回true
if (dsf(board, i, j, word, 0)) {
return true;
}
}
}
// 如果遍历完所有位置都没有找到单词，则返回false
return false;
}
// 深度优先搜索函数，从位置(i, j)开始，尝试匹配word的第k个字符
boolean dsf(char[][] board, int i, int j, String word, int k) {
// 判断是否越界，或者当前位置的字符与目标字符不匹配
if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != word.charAt(k)) {
return false;
}
// 如果已经匹配到目标单词的最后一个字符，说明找到了单词
if (k == len - 1) {
return true;
}
// 从当前位置向四个方向（上下左右）继续搜索
boolean res = dsf(board, i, j + 1, word, k + 1) || // 向右搜索
dsf(board, i + 1, j, word, k + 1) || // 向下搜索
dsf(board, i, j - 1, word, k + 1) || // 向左搜索
dsf(board, i - 1, j, word, k + 1); // 向上搜索
class MedianFinder {
Queue min, max; // 定义两个优先队列，分别用于存储数据
/**
* 初始化数据结构
*/
public MedianFinder() {
min = new PriorityQueue<>();
// 小根堆，用于存储较大的一半数据
max = new PriorityQueue<>((x, y) -> (y - x));
// 大根堆，用于存储较小的一半数据
}
public static void main(String[] args) {
int[] arr = new int[]{1, 2,3,3,3,4,5,5,7};
int target = 3;
int index = floor_lower(arr, target);
System.out.println("index = "+ index + ", value = " + arr[index]);
}
//1.寻找第一个大于 target 的元素的下标，案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
public static int upper(int[] arr, int target){
// 二分查找需要想清楚的点
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[r] <= target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
int mid = (r - l) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid;
} else if(arr[mid] == target){
l = mid + 1;
}else {//arr[mid] < target
l = mid + 1;
}
}
return l;
}
//2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
// 如果不存在，则返回第一个大于 target 的元素下标
//案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
public static int floor_upper(int[] arr, int target){
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[r] < target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
int mid = (r - l) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid;
} else if(arr[mid] == target){
l = mid + 1;
}else {//arr[mid] < target
l = mid + 1;
}
}
只在堆上分配应该是将默认构造函数删除或者设置为私有，然后提供create方法进行new操作
这个思路太牛了
禁止指令重排序（有序性）：volatile 会通过内存屏障（Memory Barrier）防止编译器和 CPU 对代码进行指令重排序。可理解为，volatile 修饰的变量写时，像设置了一个完成的标志一样，保证前面的读写操作已经完成，但不保证原子性，多步操作可能出现问题，如i=i+1,包括读i的原值，改算i+1的值，写i的值，三步分开。volatile 修饰的变量读时，像检查一个完成标志一样，保证之后所有的读都能读取到前面的最新值
spring的ThreadLocal,自动清理线程对象
一个是普通对象的共享，一个线程对象的共享
与static的区别
多级反馈队列描述不对，应该是某个进程如果长时间运行，用完时间片后会降优先级
/**
* 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 {
Map<Integer,Integer> map = new HashMap<>();
public TreeNode deduceTree(int[] preorder, int[] inorder) {
if(preorder null || preorder.length <= 0){
return null;
}
for(int i = 0; i < preorder.length ; i++){
map.put(inorder[i],i);
}
TreeNode root = f(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
return root;
}TreeNode f(int[] preorder , int l1 , int r1 , int[] inorder , int l2, int r2){
if(l1 > r1 || l2 > r2){
return null;
}
TreeNode root = new TreeNode(preorder[l1]);
int i = map.get(preorder[l1]);
root.left = f(preorder,l1+1,l1+i-l2,inorder,l2,i-1);
root.right = f(preorder,l1+i-l2+1,r1,inorder,i+1,r2);
return root;
}
}代码
// 先删除较大的索引（因为删除后数组会左移，先删大的不会影响小的索引位置）
for (int i = inx1; i < a.length-1; i++) {
a[i] = a[i+1]; // 将后面的元素前移，覆盖要删除的元素
}
// 再删除较小的索引（此时数组长度已减1，但a.length没变）
for (int i = inx2; i < a.length-1; i++) {
a[i] = a[i+1]; // 再次前移元素
}
“垂直分表：将一个大的表分割成多个小表，可以是同一个数据库中的多个表，也可以是跨库的。例如，订单表按时间范围进行分割，每年一个表。”这句话有问题吧，给出的示例好像是水平分表
手机端新改版的页面交互：点最下测的题目跳转后定位到了最下面的题目，希望跳转后定位到页面顶部
7.14-7.20
1.牛客网项目目前完成了两个功能模块，分页查询以及注册页面的功能逻辑，两个功能还挺复杂的，需要多多回顾；
2.jvm虚拟机看了两小节，地哥写的通俗易懂，但是看的有些少了，下个星期争取看5篇左右，并且需要不断地回顾加深印象；
3.算法题刷了两道，层序遍历基础和加强版，加强版那个开始不知道如何统计每一层的结点个数，学到了可以采用当前队列的长度进行统计，下一周争取刷5道哈哈，先刷树专题
你好
牛
已看
已看
已看
0-25已看
const int x = 10;
int* y = const_cast<int*>(&x); // 去除const，允许修改
*y = 20; // 修改x的值，虽然它是const的，但这里直接通过指针修改
这里的指针y并不能改变x的值把，编译器会对其进行优化，x本身是常量不可以改变
class MedianFinder {
private:
std::priority_queue<int, std::vector, std::less> mMax; // 大根堆，保存较小的一半
std::priority_queue<int, std::vector, std::greater> mMin; // 小根堆，保存较大的一半
public:
MedianFinder() {
}/*这套逻辑背后的本质是：
保持一个平衡的“左右两半”
左边是最大堆，右边是最小堆
插入时保证：
数值上：左边的最大值 ≤ 右边的最小值
数量上：左边 ≥ 右边（最多多一个）
这样才可以快速地、始终正确地返回中位数。*/
void addNum(int num) {
/*保证下面两个不变量（invariants）始终成立：
数值顺序不变量：maxHeap.top() ≤ minHeap.top()
即最大的小数 ≤ 最小的大数 → 这样合并两个堆就是有序的
数量平衡不变量：maxHeap.size() == minHeap.size() 或 maxHeap.size() == minHeap.size() + 1
即保证两个堆的大小差距最多为1，并且 maxHeap 元素个数不小于 minHeap*/
//保证所有数都优先进入“较小的一半”maxHeap，先默认是“小的”。
mMax.push(num);
//把 maxHeap 的最大值（可能是刚刚插入的）移动到 minHeap
// 这样保证了最终 maxHeap里的值 ≤ minHeap里的值，维护了值的正确划分。
mMin.push(mMax.top());
mMax.pop();
//如果 maxHeap 元素比 minHeap 少，就从 minHeap 抽一个回来
if (mMax.size() < mMin.size()) {
mMax.push(mMin.top());
mMin.pop();
}
}
double findMedian() {
if (mMax.size() == mMin.size()) {
return (mMax.top() + mMin.top()) / 2.0;
} else {
return mMax.top();
}
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
QuickSelect算法class Solution {
public:
/最小的K个数：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。/
vector inventoryManagement(vector& stock, int cnt) {
auto& nums = stock;
if (nums.empty() || cnt <= 0) {
return {};
}
return quickSelect(nums, 0, nums.size() - 1, cnt);}
std::vector<int> quickSelect(std::vector<int>& nums, int left, int right, int k) {
int i = partition(nums, left, right);
/* 下标转换
要找的是最小的前 k 个元素，也就是下标 [0 ... k - 1]
当 i == k - 1，[0, i] 正好是前 k 小的元素
*/
if (i + 1 == k) {
return std::vector<int>(nums.begin(), nums.begin() + k);
}
if (i + 1 > k) {
// i > k-1, 左边已经包含了超过 k 个最小数，继续在左半边查找。
return quickSelect(nums, 0, i - 1, k);
} else {
// i < k - 1, 左边不够 k 个最小数，还需要从右侧补足，在右半边递归找剩下的 k - (i + 1) 个数
return quickSelect(nums, i + 1, right, k);
}
return {};
}
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[left];
while (left < right) {
while (left < right && nums[right] >= pivot) {
right--;
}
nums[left] = nums[right];
while (left < right && nums[left] <= pivot) {
left++;
}
nums[right] = nums[left];
}
nums[right] = pivot;
return right;
}
};
class Solution {
public:
int dismantlingAction(string arr) {
if(arr.empty()) {
return 0;
}
unordered_map<char,int> hash;
int i=-1,j=0,len=arr.size();
vector dp(len,0);
for(j=0;j<len;j++) {
if(hash.find(arr[j]) != hash.end()) {
i=max(i,hash.find(arr[j])->second);
}
hash[arr[j]]=j;
if(j0) {
dp[0]=1;
}else{
dp[j]=max(dp[j-1],j-i);
}
}
return dp[len-1];
}
};O(N)
时间复杂度
class Solution {
public:
int jewelleryValue(vector<vector>& frame) {
int m = frame.size();
if (m 0) return 0; // 处理空矩阵
int n = frame[0].size();
vector<vector> dp(m, vector(n, 0));
// 初始化起点dp[0][0] = frame[0][0];
// 初始化第一行：只能从左侧到达
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j-1] + frame[0][j];
}
// 初始化第一列：只能从上方到达
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i-1][0] + frame[i][0];
}
// 填充剩余格子：可以从上方或左侧到达
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i][j];
}
}
return dp[m-1][n-1];
}
};
class Solution {
public:
int bestTiming(vector& prices) {
int minprice=numeric_limits::max(),maxprofit=0;
for(int price:prices) {
maxprofit=max(maxprofit,price-minprice);
minprice=min(minprice,price);
}
return maxprofit;
}
};时间复杂度O(N)
class Solution {
public:
int maxSales(vector& sales) {
int pre=0,maxone=sales[0];
for(int i:sales) {
pre=max(pre+i,i);
maxone=max(pre,maxone);
}
return maxone;
}
};时间复杂度O(N)
class Solution {
public:
vector goodsOrder(string goods) {
vector res;
sort(goods.begin(),goods.end());
do{
res.push_back(goods);
}while(next_permutation(goods.begin(),goods.end()));
return res;
}
};时间复杂度O(N!)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector> res;
vector path;
vector<vector> pathTarget(TreeNode root, int target) {
preOrderTraversal(root,target);
return res;
}
void preOrderTraversal(TreeNode* root, int target) {
if(root==nullptr) return;
path.push_back(root->val);
target-=root->val;
if(target==0 && root->left==nullptr && root->right==nullptr) {
res.push_back(path);
}
preOrderTraversal(root->left,target);
preOrderTraversal(root->right,target);
path.pop_back();
}
};
时间复杂度O(N)
class Solution {
public:
int m,n,cnt;
vector<vector> visit;
int wardrobeFinishing(int m, int n, int cnt) {
this->m=m;
this->n=n;
this->cnt=cnt;
visit.resize(m, vector(n, false));
return dfs(0,0);
}
int dfs(int i, int j) {if(i<0 || i>=m || j<0 || j>=n || digit(i)+digit(j)>cnt || visit[i][j]) {
return 0;
}
visit[i][j]=true;
return 1+dfs(i+1,j)+dfs(i,j+1);
}
int digit(int num) {
int res=0;
while(num!=0) {
res+=num%10;
num/=10;
}
return res;
}
};
时间复杂度O(M∗N)
class Solution {
public:
int n, m, len;
vector<vector> visit;
bool wordPuzzle(vector<vector>& grid, string target) {
this->n = grid.size(), this->m = grid[0].size(), this->len = target.size();
visit.resize(n, vector(m, false)); // 初始化visit数组
for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {
if(dfs(grid, i, j, target, 0)) {
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& grid, int i, int j, string target, int k) {
if(i < 0 || i >= n || j < 0 || j >= m || grid[i][j] != target[k] || visit[i][j]) {
return false;
}
if(k == len - 1) {
return true;
}
visit[i][j] = true;
bool res = (dfs(grid, i + 1, j, target, k + 1) ||
dfs(grid, i - 1, j, target, k + 1) ||
dfs(grid, i, j + 1, target, k + 1) ||
dfs(grid, i, j - 1, target, k + 1) );
visit[i][j] = false;
return res;
}
};
class Solution {
// 用于存储所有满足条件的路径
List<List> res;
// 用于临时存储当前路径
List tmp;
// 主函数：寻找所有从根节点到叶子节点的路径，使得路径上节点的值之和等于目标值public List<List<Integer>> pathSum(TreeNode root, int target) {
// 初始化结果列表和临时路径
res = new ArrayList<>();
tmp = new ArrayList<>();
// 调用深度优先搜索函数
dsf(root, target);
// 返回最终结果
return res;
}
// 深度优先搜索辅助函数
void dsf(TreeNode root, int target) {
// 如果当前节点为空，直接返回
if (root == null) {
return;
}
// 将当前节点的值加入临时路径
tmp.add(root.val);
// 更新目标值：减去当前节点的值
target = target - root.val;
// 如果当前节点是叶子节点，并且目标值为 0
if (root.left == null && root.right == null && target == 0) {
// 将当前路径加入结果列表（注意需要创建一个新的 ArrayList，避免后续修改影响结果）
res.add(new ArrayList<>(tmp));
}
// 递归处理左子树
dsf(root.left, target);
// 递归处理右子树
dsf(root.right, target);
// 回溯：移除当前节点的值，恢复临时路径的状态
tmp.remove(tmp.size() - 1);
}
}
时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
int m; // 棋盘的行数
int n; // 棋盘的列数
int k; // 位数和的限制
boolean[][] visited; // 用于记录每个格子是否被访问过
// 主方法，计算机器人能够到达的格子数量public int movingCount(int m, int n, int k) {
this.m = m; // 初始化棋盘的行数
this.n = n; // 初始化棋盘的列数
this.k = k; // 初始化位数和的限制
visited = new boolean[m][n]; // 初始化访问记录数组，初始值为 false
return dfs(0, 0); // 从左上角 (0,0) 开始深度优先搜索
}
// 深度优先搜索方法
int dfs(int i, int j) {
// 判断当前格子是否在棋盘范围内、是否未被访问过、位数和是否小于等于 k
if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k < sum(i) + sum(j)) {
return 0; // 如果不满足条件，返回 0
}
visited[i][j] = true; // 标记当前格子为已访问
// 递归计算向右和向下移动的结果，并加 1 表示当前格子
return 1 + dfs(i + 1, j) + dfs(i, j + 1);
}
// 计算一个数字的位数和
int sum(int x) {
int res = 0; // 初始化结果为 0
while (x != 0) {
res = res + x % 10; // 取出最低位并累加
x = x / 10; // 去掉最低位
}
return res; // 返回位数和
}
}
时间复杂度：O(mn)
空间复杂度：O(mn)
class Solution {
int n; // board的行数
int m; // board的列数
int len; // word的长度
boolean[][] visited; // 标记数组，记录某个位置是否被访问过
// 主函数，判断单词是否存在于board中public boolean exist(char[][] board, String word) {
this.n = board.length; // 获取board的行数
this.m = board[0].length; // 获取board的列数
this.len = word.length(); // 获取目标单词的长度
visited = new boolean[n][m]; // 初始化visited数组
// 遍历board的每一个位置，尝试从每个位置开始搜索
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// 如果从位置(i, j)开始能够找到单词，则返回true
if (dsf(board, i, j, word, 0)) {
return true;
}
}
}
// 如果遍历完所有位置都没有找到单词，则返回false
return false;
}
// 深度优先搜索函数，从位置(i, j)开始，尝试匹配word的第k个字符
boolean dsf(char[][] board, int i, int j, String word, int k) {
// 判断是否越界，或者当前位置的字符与目标字符不匹配
if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != word.charAt(k)) {
return false;
}
// 如果已经匹配到目标单词的最后一个字符，说明找到了单词
if (k == len - 1) {
return true;
}
// 标记当前位置为已访问，避免重复访问
// visited[i][j] = true;
board[i][j] = 'n'; // 通过修改字符为'n'来标记已访问
// 从当前位置向四个方向（上下左右）继续搜索
boolean res = dsf(board, i, j + 1, word, k + 1) || // 向右搜索
dsf(board, i + 1, j, word, k + 1) || // 向下搜索
dsf(board, i, j - 1, word, k + 1) || // 向左搜索
dsf(board, i - 1, j, word, k + 1); // 向上搜索
// 恢复当前位置的字符，以便后续搜索使用
board[i][j] = word.charAt(k);
return res; // 返回搜索结果
}
}
时间复杂度：O(3^K * MN) ： 最差情况下，需要遍历矩阵中长度为 KK 字符串的所有方案，时间复杂度为 O(3^K)；矩阵中共有 MN 个起点，时间复杂度为 O(MN)
空间复杂度：O(k)
class Solution {
/**
* 主函数，用于计算数组中的逆序对数量
* @param nums 输入数组
* @return 逆序对的数量
*/
public int reversePairs(int[] nums) {
if (nums null || nums.length <= 1) {
return 0; // 如果数组为空或只有一个元素，没有逆序对
}
return mergeSort(nums, 0, nums.length – 1); // 调用归并排序函数
}
/*** 归并排序函数，递归地将数组分成两部分，并计算逆序对数量
* @param nums 输入数组
* @param left 当前区间的左边界
* @param right 当前区间的右边界
* @return 当前区间内的逆序对数量
*/
int mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return 0; // 如果区间只有一个元素，没有逆序对
}
int mid = (right - left) / 2 + left; // 计算中间索引
int x1 = mergeSort(nums, left, mid); // 递归处理左半部分
int x2 = mergeSort(nums, mid + 1, right); // 递归处理右半部分
int x3 = merge(nums, left, mid, mid + 1, right); // 合并两个有序数组并计算逆序对
return x1 + x2 + x3; // 返回总逆序对数量
}
/**
* 合并函数，用于合并两个有序数组，并计算跨区间的逆序对数量
* @param nums 输入数组
* @param l1 左半部分的左边界
* @param r1 左半部分的右边界
* @param l2 右半部分的左边界
* @param r2 右半部分的右边界
* @return 跨区间的逆序对数量
*/
int merge(int[] nums, int l1, int r1, int l2, int r2) {
int[] temp = new int[r2 - l1 + 1]; // 创建临时数组用于合并
int count = 0; // 用于记录逆序对数量
int i = l1, j = l2, k = 0; // 初始化指针
// 合并两个有序数组
while (i <= r1 && j <= r2) {
if (nums[i] > nums[j]) {
// 如果左半部分的当前元素大于右半部分的当前元素
count = count + (r1 - i + 1); // 计算逆序对数量
temp[k++] = nums[j++]; // 将右半部分的元素加入临时数组
} else {
temp[k++] = nums[i++]; // 将左半部分的元素加入临时数组
}
}
// 处理左半部分剩余的元素
while (i <= r1) {
temp[k++] = nums[i++];
}
// 处理右半部分剩余的元素
while (j <= r2) {
temp[k++] = nums[j++];
}
// 将临时数组的内容复制回原数组
k = 0;
for (i = l1; i <= r2; i++) {
nums[i] = temp[k++];
}
return count; // 返回逆序对数量
}
}
复杂度和归并排序一样
时间：O(nlogn)
空间:O(n)
class MedianFinder {
Queue min, max; // 定义两个优先队列，分别用于存储数据
/*** 初始化数据结构
*/
public MedianFinder() {
min = new PriorityQueue<>();
// 小根堆，用于存储较大的一半数据
max = new PriorityQueue<>((x, y) -> (y - x));
// 大根堆，用于存储较小的一半数据
}
/**
* 向数据结构中添加一个数字
* @param num 要添加的数字
*/
public void addNum(int num) {
// 如果两个堆的大小相等（即当前数据总数为偶数）
if (min.size() == max.size()) {
// 先将数字加入到小根堆min中
min.add(num);
// 然后将min的堆顶元素（即当前较大的一半中的最小值）弹出
// 并加入到大根堆max中
max.add(min.poll());
} else {
// 如果两个堆的大小不相等（即当前数据总数为奇数）
// 先将数字加入到大根堆max中
max.add(num);
// 然后将max的堆顶元素（即当前较小的一半中的最大值）弹出
// 并加入到小根堆min中
min.add(max.poll());
}
}
/**
* 返回当前数据的中位数
* @return 中位数
*/
public double findMedian() {
// 如果两个堆的大小相等（即数据总数为偶数）
if (min.size() == max.size()) {
// 中位数是两个堆顶元素的平均值
return (min.peek() + max.peek()) / 2.0;
} else {
// 如果两个堆的大小不相等（即数据总数为奇数）
// 中位数是大根堆max的堆顶元素
return max.peek() * 1.0;
}
}
}
时间复杂度：1. 查找中位数 O(1)， 2. 插入元素：O(logn)
空间复杂度：O(n)
p22已看
1-14已看
阅
阅
归并排序
class Solution {
public:
int reversePairs(vector& record) {
if(record.empty()) return 0;
int cnt=0;
cnt=mergesort(record,0,record.size()-1);
return cnt;
}
private:
int mergesort(vector& record,int left,int right) {
int mid=0,cnt=0;
if(left<right) {
mid=(right-left)/2+left;
cnt+=mergesort(record,left,mid);
cnt+=mergesort(record,mid+1,right);
cnt+=merge(record,left,mid,right);
}
return cnt;
}
int merge(vector<int>& record,int left,int mid,int right) {
int m=mid-left+1,n=right-mid;
vector<int> L(m),R(n);
int i,j,k,cnt=0;
for (int i = 0; i < m; ++i) {
L[i] = record[left + i];
}
for (int j = 0; j < n; ++j) {
R[j] = record[mid + 1 + j];
}
i=0,j=0,k=left;
while(i<m && j<n) {
if(L[i] <= R[j]) {
record[k++]=L[i++];
}else {
record[k++]=R[j++];
cnt+=m-i;
}
}
while(i < m) {
record[k++]=L[i++];
}
while(j < n) {
record[k++]=R[j++];
}
return cnt;
}
};
阅
阅
阅
阅
快排：
class Solution {
public:
vector inventoryManagement(vector& stock, int cnt) {
if(stock.empty()||cnt0) return {};
return quickFind(stock,0,stock.size()-1,cnt);
}
private:
vector quickFind(vector& stock, int left,int right,int cnt) {
int i=patition(stock,left,right);
if(i+1cnt) {
vector find(stock.begin(),stock.begin()+cnt);
return find;
}else if(i+1>cnt) {
return quickFind(stock,left,i-1,cnt);
}else {
return quickFind(stock,i+1,right,cnt);
}
}
int patition(vector<int>& stock, int left,int right) {
int pivot=stock[left];
int i=left,j=right;
while(i<j) {
while(i<=j && pivot >= stock[i]) i++;
while(i<=j && pivot < stock[j]) j--;
if(i>=j) break;
swap(stock[i],stock[j]);
}
swap(stock[j],stock[left]);
return j;
}
};
2.堆排序
class Solution {
public:
vector inventoryManagement(vector& stock, int cnt) {
vector vec;
if(stock.empty() || cnt0) return vec;
priority_queue maxHeap;
for(int i=0;i<cnt;i++) {
maxHeap.push(stock[i]);
}
for(int i=cnt;i<(int)stock.size(); i++){
if(stock[i] < maxHeap.top()) {
maxHeap.pop();
maxHeap.push(stock[i]);
}
}
for(int i=0;i<cnt;i++) {
vec.push_back(maxHeap.top());
maxHeap.pop();
}
return vec;
}
};
应该是这个吧，find()和binary_search()有什么区别？
class Solution {
public:
string crackPassword(vector& password) {
vector strs;
for(int num : password) {
strs.push_back(to_string(num));
}
quicksort(strs, 0, strs.size() – 1);
string complete;
for(string s : strs) {
complete.append(s);
}
return complete;
}
private:
void quicksort(vector& strs, int left, int right) {
if(left >= right) return;
int pivot = partition(strs, left, right);
quicksort(strs, left, pivot – 1);
quicksort(strs, pivot + 1, right);
}
int partition(vector<string>& strs, int left, int right) {
string pivot = strs[left];
int i = left, j = right;
while (i < j) {
// 从右向左找第一个比基准小的元素
while (i < j && (strs[j] + pivot >= pivot + strs[j])) {
j--;
}
// 从左向右找第一个比基准大的元素
while (i < j && (strs[i] + pivot <= pivot + strs[i])) {
i++;
}
if (i < j) {
swap(strs[i], strs[j]);
}
}
swap(strs[left], strs[j]);
return j;
}
};
// 自底向上
public static boolean isBalanced(TreeNode root) {
return dfs(root) != -1;
}
public static int dfs(TreeNode root) {if (root == null) {
return 0;
}
int count_left = dfs(root.left);
if (count_left == -1) {
return -1;
}
int count_right = dfs(root.right);
// 若在向上归的过程中发现了某个子树不平衡, 则层层向上返回-1, 无需再去递归另一边的某个(大)子树
if (count_right == -1 || Math.abs(count_left - count_right) > 1) {
return -1;
}
// 层层向上返回子树的深度
return Math.max(count_left, count_right) + 1;
}
package sort;
public class BanarySort {
public static void main(String[] args) {int[] arr = new int[]{1, 2,3,3,3,4,5,5,7};
int target = 3;
int index = floor_lower(arr, target);
System.out.println("index = "+ index + ", value = " + arr[index]);
}
//1.寻找第一个大于 target 的元素的下标，案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
public static int upper(int[] arr, int target){
// 二分查找需要想清楚的点
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[r] <= target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
int mid = (r - l) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid;
} else if(arr[mid] == target){
l = mid + 1;
}else {//arr[mid] < target
l = mid + 1;
}
}
return l;
}
//2.如果数组中存在元素等于 target，则返回最后一个等于target 的元素下标，
// 如果不存在，则返回第一个大于 target 的元素下标
//案例：arr[1, 2,3,3,3,4,5,5,7], target = 3。
public static int floor_upper(int[] arr, int target){
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[r] < target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
int mid = (r - l) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid;
} else if(arr[mid] == target){
l = mid + 1;
}else {//arr[mid] < target
l = mid + 1;
}
}
if(l - 1 >= 0 && arr[l - 1] == target){
return l -1;
}
return l;
}
//3.寻找最后一个小于 target 的元素的下标
// [1, 2,3,3,3,4,5,5,7],target = 3;
public static int lower(int[] arr, int target){
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[l] >= target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
// r = 1,l = 0,mid = 0
int mid = (r - l + 1) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid - 1;
} else if(arr[mid] == target){
r = mid - 1;
}else {//arr[mid] < target
l = mid;
}
}
//
return l;
}
// 4.如果数组中存在元素等于 target，则返回第一个等于target 的下标，
// 如果不存在，则返回最后一个小于 target 的元素的下标
//[1, 2,3,3,3,4,5,5,7],target = 3;
public static int floor_lower(int[] arr, int target){
int l = 0;
int r = arr.length - 1;
// 判断特殊情况
if(arr[l] > target){
return -1;
}
//[l,r],，在我们二分查找的过程中，不断缩小我们的查找范围，直到范围里面只有一个元素，那个就是我们要找的元素了
while(l < r){
// r = 1,l = 0,mid = 0
int mid = (r - l + 1) / 2 + l;
if(arr[mid] > target){
//[l ,mid, r]
r = mid - 1;
} else if(arr[mid] == target){
r = mid - 1;
}else {//arr[mid] < target
l = mid;
}
}
//
if(l + 1 < arr.length && arr[l + 1] == target){
return l + 1;
}
return l;
}
}