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;
}
}
思路分析：
代码：
#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;
}
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;
}
};
'''
转换成最大闭合子图问题解决，
用户群为正权值点，中转站为负权值点，正权值点依赖于一些负权值点，负权值点没有对外依赖，
因此每一个选择方案都对应于原图的一个闭合子图，用最大流求闭合点集的最大权值和即可
'''
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;
}
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.反问环节
题目描述
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，
两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，
那么将他们的值相加作为节点合并后的新值，
否则不为 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;
}
};
