我只是做了代码裁缝的角色罢了
目录
试题地址
https://leetcode.cn/contest/sf-tech/
1
DFS判定有向图是否有环
class Solution:
def __init__(self): #初始化方法
self.color=[0 for _ in range(105)]
self.haveCycle=False
self.m=-1
def hasCycle(self, graph: str) -> bool:
b=list(graph.split(","))
b=list(map( lambda x:list(map(int,x.split("->"))) ,b))
a=[[0 for i in range(105)]for j in range(105)]
for tmp_list in b:
From=tmp_list[0]
To=tmp_list[1]
self.m=max(self.m,From)
self.m=max(self.m,To)
a[From][To]=1
def DFS(i):
self.color[i]=1;
for j in range(1,self.m+1,1):
if a[i][j]!=0:
if self.color[j]==1:
self.haveCycle=True
break
elif self.color[j]==-1:
continue
else:
DFS(j)
self.color[i]=-1
for i in range(1,self.m+1,1):
if self.color[i]==-1:
continue
else:
DFS(i)
return self.haveCycle
//C#
public class Solution {
int m=-1;
bool haveCycle=false;
int [] color=new int[105];
public bool HasCycle(string graph) {
var b=graph.Split(',');
int [,] a=new int [105,105];
foreach (var tmp in b){
var tmp1=tmp.Split(new string[]{"->"},System.StringSplitOptions.RemoveEmptyEntries);
int From=int.Parse(tmp1[0]);
int To=int.Parse(tmp1[1]);
m=Math.Max(m,From);
m=Math.Max(m,To);
a[From,To]=1;
}
void DFS(int i){
color[i]=1;
for(int j=1;j<m+1;j++){
if(a[i,j]!=0){
if(color[j]==1){
haveCycle=true;
}
else if(color[j]==1){
continue;
}
else{
DFS(j);
}
}
}
color[i]=-1;
}
for(int i=1;i<=m;i++){
if(color[i]==-1){
continue;
}
else{
DFS(i);
}
}
return haveCycle;
}
}
2
问你背包最多装多少件物品？
背包九讲看过没？
class Solution {
public:
int minRemainingSpace(vector<int>& N, int V) {
int n = N.size();
vector<int> dp(V + 1, 0);
for (int i = 0; i < n; ++i)
for (int j = V; j >= N[i]; --j)
dp[j] = max(dp[j], dp[j - N[i]] + N[i]);
return V - dp[V];
}
};
作者：silenceneo
链接：https://leetcode.cn/circle/discuss/7w4iT0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。//C#
public class Solution {
public int MinRemainingSpace(int[] N, int V) {
int n=N.GetLength(0);
int[] dp=new int [V+1];
for(int i=0;i<n;i++){
for(int j=V;j>=N[i];j--){
dp[j] = Math.Max(dp[j], dp[j - N[i]] + N[i]);
}
}
return V - dp[V];
}
}
3
最长连续递增序列
class Solution:
def LIS_lis(self,nums):
n = len(nums)
dp = [1] * n
for j in range(1, n):
if nums[j] > nums[j-1]:
dp[j] = max(dp[j], dp[j-1]+1)
return max(dp)
def findMaxCI(self, nums: List[int]) -> int:
return (self.LIS_lis(nums))
# 300. 最长递增子序列 & 674. 最长连续递增序列 - 早起Statistics的文章 - 知乎
# https://zhuanlan.zhihu.com/p/465484573
//C#
public class Solution {
public int LIS(int[] nums){
int n=nums.GetLength(0);
int [] dp=new int[n];
// foreach(int ele in dp){
// ele=1;
// }
for(int i=0;i<=n-1;i++) dp[i]=1;
for(int j=1;j<n;j++){
if(nums[j]>nums[j-1]){
dp[j]=Math.Max(dp[j],dp[j-1]+1);
}
}
return dp.Max();
}
public int FindMaxCI(int[] nums) {
return LIS(nums);
}
}
4
判断点是否在多边形内？
有哪几种算法？
using namespace std;
typedef long long ll;
const double eps = 1e-6;
const double PI = acos(-1);
int n;
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
//向量+
Point operator +(const Point &b)const
{
return Point(x+b.x,y+b.y);
}
//向量-
Point operator -(const Point &b)const
{
return Point(x-b.x,y-b.y);
}
//点积
double operator *(const Point &b)const
{
return x*b.x + y*b.y;
}
//叉积
//P^Q>0,P在Q的顺时针方向；<0，P在Q的逆时针方向；=0，P，Q共线，可能同向或反向
double operator ^(const Point &b)const
{
return x*b.y - b.x*y;
}
}polygon[105];
typedef Point Vector;
//三态函数，判断两个double在eps精度下的大小关系
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
else
return x<0?-1:1;
}
//判断点Q是否在P1和P2的线段上
bool OnSegment(Point P1,Point P2,Point Q)
{
return dcmp((P1-Q)^(P2-Q))==0&&dcmp((P1-Q)*(P2-Q))<=0;
}
//判断点P在多边形内-射线法
bool InPolygon(Point P)
{
bool flag = false;
Point P1,P2; //多边形一条边的两个顶点
for(int i=1,j=n;i<=n;j=i++)
{
P1 = polygon[i];
P2 = polygon[j];
if(OnSegment(P1,P2,P)) return true; //点在多边形一条边上
if( (dcmp(P1.y-P.y)>0 != dcmp(P2.y-P.y)>0) && dcmp(P.x - (P.y-P1.y)*(P1.x-P2.x)/(P1.y-P2.y)-P1.x)<0)
flag = !flag;
}
return flag;
}
class Solution {
public:
bool isPointInPolygon(double x, double y, vector<double>& coords) {
n=coords.size()/2;
for(int i=0;i<=n-1;i+=1){
polygon[i].x=coords[2*i];
polygon[i].y=coords[2*i+1];
}
// for(auto &p :polygon ){
// cout<<p.x<<" "<<p.y<<endl;
// }
return InPolygon(Point(x,y));
}
};
5
并查集模板题
class UnionFindSet(object):
def __init__(self, data_list):
self.parent = {}
self.rank = {}
self.sets_count=len(data_list) # 判断并查集里共有几个集合, 初始化默认互相独立
for d in data_list:
self.parent[d] = d # 初始化节点的父节点为自身
self.rank[d] = 1 # 初始化rank为1
def find(self, d):
"""使用递归的方式来查找根节点
路径压缩：在查找父节点的时候，顺便把当前节点移动到父节点下面
"""
father = self.parent[d]
if(d != father):
father = self.find(father)
self.parent[d] = father
return father
def is_same_set(self, a,b):
"""查看两个节点是不是在一个集合里面"""
return self.find(a) == self.find(b)
def union(self, a, b):
"""将两个集合合并在一起"""
a_head = self.find(a)
b_head = self.find(b)
if(a_head != b_head):
a_rank = self.rank[a_head]
b_rank = self.rank[b_head]
if a_rank >= b_rank:
self.parent[b_head] = a_head
if a_rank==b_rank:
self.rank[a_rank]+=1
else:
self.parent[a_head] = b_head
self.sets_count-=1
class Solution:
def isCompliance(self, d: List[List[int]], n: int) -> bool:
# distance是对称矩阵
m=len(d)
ufs = UnionFindSet(list(range(m)))
for i in range(0,m,1):
for j in range(i+1,m,1):
if d[i][j]<=2:
ufs.union(i,j)
# print(ufs.parent)
# print(ufs.sets_count)
ust=set()
for i in range(m):
ust.add(ufs.find(i))
print(len(ust))
return ufs.sets_count<=n
# return len(ust)<=n