总的来说题目难度还行，题目有单选10道 多选10道 问答2题 编程题2题 压轴题1题 压轴题就问了个死锁
第一题
给一个数组，给一个k，问是否能够找到将数组分为k的子集，且每一个子集的和相等。
直接暴力搜索
boolean[] visited;
int K;
public boolean canPartitionKSubsets (int[] nums, int k) {
int sum=0;
for (int num:nums) {
sum+=num;
}
int n=nums.length;
K=k;
if (sum%k!=0) return false;
int avg=sum/k;
Arrays.sort(nums);
visited=new boolean[n];
return trace(nums,0,0,avg);
}
public boolean trace(int []nums,int count,int sum,int avg) {
if (count==K){
return true;
}
for (int i=0;i<nums.length;i++) {
if (visited[i]) continue;
if ((sum+nums[i])==avg) {
visited[i]=true;
if(trace(nums,count+1,0,avg)) return true;
visited[i]=false;
}else if ((sum+nums[i])>avg){
break;
}else{
visited[i]=true;
if(trace(nums,count,sum+nums[i],avg)) return true;
visited[i]=false;
}
}
return false;
}第二题
剑指Offer26题树的子结构的变种题
其他不变 子结构变成子树
public boolean isSubtree (TreeNode s, TreeNode t) {
if (t==null) return true;
if (s==null) return false;
if (s.val==t.val) {
return dfs(s,t);
}else {
return isSubtree(s.left,t)||isSubtree(s.right,t);
}
}
public boolean dfs(TreeNode s,TreeNode t) {
if (s==null&&t==null) return true;
if (s==null||t==null) return false;
if (s.val!=t.val) return false;
return dfs(s.left,t.left)&&dfs(s.right,t.right);
}评论 (5)
