Emzie
4分钟前
import java.util.*;
import java.io.*;
public class Main {
     public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       String str = br.readLine();
       String[] s = br.readLine().split(" ");
       int n = Integer.valueOf(str);
       int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(s[i]);
        }
       quickSort(arr,0,n-1);
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i]+" ");

        }

    }
    public static void quickSort(int[] arr,int l,int r){
        if(l>=r) return;
        int x = arr[l];
        int i = l-1;
        int j = r+1;
        while(i<j){
            do i++; while(arr[i]<x);
            do j--; while(arr[j]>x);
            if(i<j) swap(arr,i,j);
        }
        quickSort(arr,l,j);
        quickSort(arr,j+1,r);
    }
    public static void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}



AnrolsP
21分钟前

思路分析:

QQ图片20200922152924.jpg

代码:

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 5010;
typedef pair<int , int >PII;
vector<PII> c;
int f[N];

int main()
{
    int n ; cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int s, north; cin >> s >> north; 
        c.push_back({s, north});
    }
    sort(c.begin(), c.end());
    //for(int i = 0; i < c.size(); ++i)cout << c[i].second <<" ";
    int res = 0;
    for(int i = 0; i < c.size(); ++i)
    {
        f[i] = 1;
        for(int j = 0; j < i; ++j)
            if(c[j].second < c[i].second)f[i] = max(f[i], f[j] + 1);
            res = max(f[i], res);
    }
    cout << res <<endl;
    return 0;
}



adamXu
40分钟前

class Solution {
public:
    //思路,深搜加枚举吧,小技巧,坐标可以用数组来存放时间复杂度,dfs外n^2数量级,dfs内是3^k数量级
    //k为str.size()
    bool hasPath(vector<vector<char>>& matrix, string &str) {
        for (int i = 0;i < matrix.size();++i){
            for (int j = 0;j < matrix[0].size();++j){
                if(dfs(matrix,str,0,i,j))   return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>> &matrix,string &str,int u,int x,int y){
        if(str[u] != matrix[x][y]) return false;
        if(u == str.size() - 1) return true;
        int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
        //遍历各个坐标
        char t = matrix[x][y];
        matrix[x][y] = '*';
        for(int i = 0;i < 4;++i){
            int a = x + dx[i],b = y + dy[i];
            if(a >= 0 && a < matrix.size() && b >= 0 && b < matrix[a].size()){
                if(dfs(matrix,str,u + 1,a,b)) return true;
            }
        }
        matrix[x][y] = t;
        return false;
    }
};


新鲜事 原文

mojo
51分钟前
欢迎大家在22点以前进入我们的链接一起云刷题:https://meet.google.com/upp-jhen-nwu



皓首不倦
1小时前


'''
转换成最大闭合子图问题解决,
用户群为正权值点,中转站为负权值点,正权值点依赖于一些负权值点,负权值点没有对外依赖,
因此每一个选择方案都对应于原图的一个闭合子图,用最大流求闭合点集的最大权值和即可
'''

from typing import List
from collections import deque
import sys

class FortdFulkerson:
    # 输入图中所有边列表[(from1, to1, weight1), (form2, to2, weight2), ......]
    # 边可以有重边和自环边
    # souece_node 和 end_node 分别为源点和汇点
    # 所有节点从1开始连续编号, max_node_num是最大节点数,max_edge_nums是最大边数
    def __init__(self, edges, source_node, end_node, max_node_num, max_edge_num):
        self.edges = edges[::]
        self.source_node = source_node
        self.end_node = end_node
        self.max_edge_num = max_edge_num
        self.max_node_num = max_node_num

    # 返回整个图的最大流和每条边的流量以及容量,(max_flow, [(from1, to1, flow1, weight1), (from1, to1, flow1, weight1), ......])
    def getMaxFlow(self):
        e = [-1] * (self.max_edge_num * 2 + 1)  # e[idx]表示编号为idx残量图边的终点, idx//2 就是残量图边对应的原图边的编号
        f = [-1] * (self.max_edge_num * 2 + 1)  # f[idx]表示编号为idx的残量图边的流量
        ne = [-1] * (self.max_edge_num * 2 + 1)  # ne[idx]表示根编号为idx的边同一个起点的下一条边的编号
        h = [-1] * (self.max_node_num + 1)  # h[a]表示节点a为起点的所有边的链表头对应的边的编号
        dis = [-1] * (self.max_node_num + 1)  # dis[a]表示点a到源点的距离,用于记录分层图信息
        cur = [-1] * (self.max_node_num + 1)  # cur[a]表示节点a在dfs搜索中第一次开始搜索的边的下标,也称当前弧,用于优化dfs速度

        idx = 0
        for a, b, w in self.edges:
            e[idx], f[idx], ne[idx], h[a] = b, w, h[a], idx
            idx += 1
            e[idx], f[idx], ne[idx], h[b] = a, 0, h[b], idx
            idx += 1

        # bfs搜索有没有增广路
        def bfs() -> bool:
            for i in range(self.max_node_num + 1):
                dis[i] = -1

            que = deque()
            que.append(self.source_node)
            dis[self.source_node] = 0
            cur[self.source_node] = h[self.source_node]

            while len(que) > 0:
                cur_node = que.popleft()
                idx = h[cur_node]
                while idx != -1:
                    next_node = e[idx]
                    if dis[next_node] == -1 and f[idx] > 0:
                        dis[next_node] = dis[cur_node] + 1
                        cur[next_node] = h[next_node]
                        if next_node == self.end_node:
                            return True

                        que.append(next_node)

                    idx = ne[idx]

            return False

        # dfs查找增广路, 返回当前残量图上node节点能流入汇点的不超过limit的最大流量有多事少
        def dfs(node, limit) -> int:
            if node == self.end_node:
                return limit

            flow = 0
            idx = cur[node]  # 从节点的当前弧开始搜索下一个点
            while idx != -1 and flow < limit:
                # 当前弧优化,记录每一个节点最后走的一条边,只要limit还没有减成0,已经搜过的边的终点
                # 能够汇入汇点的流量就已经全部用完了,另外一条路径到同一个点时候没必要重复搜索已经不会
                # 再提供流量贡献的邻接点
                cur[node] = idx

                next_node = e[idx]
                if dis[next_node] == dis[node] + 1 and f[idx] > 0:
                    t = dfs(next_node, min(f[idx], limit - flow))
                    if t == 0:
                        # 已经无法提供流量的废点闪删除掉,不再参与搜索
                        dis[next_node] = -1

                    # 更新残量图边的流量
                    f[idx], f[idx ^ 1], flow = f[idx] - t, f[idx ^ 1] + t, flow + t

                idx = ne[idx]

            return flow

        max_flow = 0
        while bfs():
            # 只要还有增广路,就dfs把增广路都找到,把增广路上的流量加到可行流上
            max_flow += dfs(self.source_node, 0x7fffffff)
        return max_flow


n, m = map(int, input().split())
S, T = n+m + 1, n+m + 2
cost = list(map(int, input().split()))


edges = []
for i, p in enumerate(cost):
    edges.append((i+1, T, p))

ans = 0
for i in range(n+1, n+m+1):
    a, b, c = map(int, input().split())
    edges.append((i, a, 0x7fffffff))
    edges.append((i, b, 0x7fffffff))
    edges.append((S, i, c))
    ans += c

ans -= FortdFulkerson(edges, S, T, n+m+2, len(edges)).getMaxFlow()
print(ans)




题目描述

给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输出格式

输出一个整数,表示最短Hamilton路径的长度。

样例

输入样例:
5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0
输出样例:
18

算法1

(暴力枚举) $O(2nn^2)$

dp[i][j] = min{dp[i][j], dp[i - (1 << j)][k] + map[k][j]}
其中map数组为权值,map[k][j]是点k到点j的权值

dp[i][j]表示当前已经走过点的集合为i,移动到j。所以这个状态转移方程就是找一个中间点k,将已经走过点的集合i中去除掉j(表示j不在经过的点的集合中),然后再加上从k到j的权值

问题在于如何表达已经走过点的集合i,其实很简单,假如走过0,1,4这三个点,我们用二进制10011就可以表示,2,3没走过所以是0

那么走过点的集合i中去除掉点j也很容易表示i - (1 << j),比方说i是{0,1,4},j是1,那么i = 10011,(1 << j) = 10,i - (1 << j) = 10001

那么问题的答案就应该是dp[01....111][n-1],表示0~n-1都走过,且当前移动到n-1这个点

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<N;
int n;
int  w[N][N];
int f[M][N];
int main()
{
                  cin>>n;
           for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
               cin>>w[i][j];
             memset(f,0x3f,sizeof f);
              f[1][0]=0;
              for(int i=0;i<1<<n;i++)
                for(int j=0;j<n;j++)
                    if(i>>j &1)
                for(int k=0;k<n;k++)
                      if((i-(1<<j)) >> k &1)
                f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                    cout<<f[(1<<n)-1][n-1]<<endl;
                            return 0;
}

算法2

Fi,j表示点被经过的状态,且目前处于第j时的最短路径F[i,j]=min(F[i xor (1<<j),k]+weight[k][j]),因为点j只能恰好被经过一次,所以上一时刻“被经过的状态”对应的二进制数的J位为0,而上一时刻位置位于i xor(k<<j)中的任意一个是1的数位k,即加上weight[k][j];

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=20,M=1<<N;
int n;
int w[N][N];
int f[M][N];
int main()
{
            cin>>n;
      for(int i=0;i<n;i++)
       for(int j=0;j<n;j++)
           cin>>w[i][j];
          memset(f,0x3f,sizeof f); 
                f[1][0]=0;
            for(int i=0;i<1<<n;i++)
             {for(int j=0;j<n;j++){
                  if(i>>j & 1)
              for(int k=0;k<n;k++)
                 if(i >> k & 1)
               f[i][j]=min(f[i][j],f[i^1<<j][k]+w[k][j]);
                }
             }

             cout<<f[(1<<n)-1][n-1]<<endl;
                    return 0;
}



新鲜事 原文

hyc_noi
2小时前
费用流的总结出来啦 https://blog.csdn.net/weixin_44043668/article/details/108738212



adamXu
2小时前
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size() - 1;
        if(n < 0) return -1;
        //去掉最后与a[0]相等相等的一段使其数组满足二分性质,即分界点左边都大于等于a[0],右边小于
        //a[0],值得注意的是,如果数组已经单调,即未旋转的情况下,此时直接返回a[0]

        while(n > 0 && nums[n] == nums[0]) n--;
        if(nums[0] < nums[n]) return nums[0];   //注意单调情况
        int l = 0,r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        return nums[r];
    }
};



一面

1.自我介绍
2.介绍自己项目
3.项目方案设计的思路,怎么入手
4.路由器和交换机的区别
5.数据库事务,ACID
6.static关键字
7.tcp连接
8.说说智能指针
9.函数指针
10.sizeof 和 strlen区别
11.多态
12.map,set
13.kmp算法原理
14.反转k个一组的链表
15.程序编译预处理阶段做了什么
16.进程和线程的同步方式
18.进程状态
19.七层模型,每层列举协议
20.设计模式
21.单例模式的懒汉式和饿汉式
22.OPP面向对象原则
23.工厂模式和装饰者模式使用业务

反问环节

手撕算法:链表快排

二面

1.自我介绍
2.介绍项目
3.结构体和类区别
4.知道些什么锁
5.介绍自旋锁,互斥锁,自旋锁
6.指针和引用区别
7.数据库事务
8.虚函数
9.纯虚函数
10.构造函数可以是纯虚函数吗
11.c++怎么定义常量,存放区域
12.说说STL,map,set
13.进程和线程
14.并发和并行
15.https协议
16.死锁
17.GDB调试
18.tcp和udp区别
19.get和post区别
20.数据库索引
21.left join 业务场景
22.B树和B+树
23.知道哪些加密算法
24.大型项目怎么判断内存泄漏
25.判断内存泄漏的工具

反问环节

手撕算法:LC179最大数,给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

三面

1.自我介绍
2.聊聊项目
3.聊聊家常
4.聊聊人生
5.期望薪资
6.期望工作地点
7.反问环节




itdef
2小时前

题目描述

给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,
两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,
那么将他们的值相加作为节点合并后的新值,
否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

输入: 
    Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
         3
        / \
       4   5
      / \   \ 
     5   4   7
注意: 合并必须从两个树的根节点开始。


算法1

还是使用树的遍历
如果两边均有节点 则节点值相加
如果只有一个节点 记录到答案中
(这里在递归遍历中返回处理结果会比较好,由于我采取的是答案直接放到第一颗树,导致使用了丑陋的指向指针的指针,仅做演示,不做推荐)
如果两边都没节点了 回溯

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:


void dfs(TreeNode** t1, TreeNode** t2) {
    //t1作为答案返回
    if (*t1 == NULL && *t2 == NULL) return;

    if (*t1 != NULL && *t2 == NULL) return;
    //t1没有节点 t2有 转移到t1上
    if (*t1 == NULL && *t2 != NULL) { *t1 = *t2; return; }

    if (*t1 != NULL && *t2 != NULL) {
        (*t1)->val += (*t2)->val;
    }
    dfs(&((*t1)->left), &((*t2)->left));
    dfs(&((*t1)->right), &((*t2)->right));
}

void printTree(TreeNode* t1)
{
    if (t1 == NULL) return;

    cout << t1->val << " ";

    printTree(t1->left);
    printTree(t1->right);
}


TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    dfs(&t1,&t2);

    printTree(t1);

    return t1;
}


};