LeetCodeWeeklyContest-177

本文主要是介绍LeetCodeWeeklyContest-177，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第 177 场周赛
rank:1381 / 2985
AC: 1/4

日期之间隔几天

给定两个yyyy-MM-DD格式的字符串,计算两者之间差多少天

java日期类之前写的很少,想起来用然后导了半天的包,还得抛异常…还是不熟

import java.util.Date;
import java.text.SimpleDateFormat;class Solution {public int daysBetweenDates(String date1, String date2) {SimpleDateFormat sdf = new  SimpleDateFormat("yyyy-MM-dd");try{long days = Math.abs(sdf.parse(date1).getTime() - sdf.parse(date2).getTime()) ;return (int)(days/ (1000*3600*24));}catch(Exception e){return 0;}}
};

验证二叉树

解法1:dfs,利用vis统计多次访问的,返回false,有不止一个连通分量的返回false

int vis[100005];
bool dfs(int x,vector<int>& l, vector<int>& r){if(x==-1) return true;if(vis[x]) return false;vis[x]=1;return  dfs(l[x],l,r) && dfs(r[x],l,r);
}
class Solution {
public:bool validateBinaryTreeNodes(int n, vector<int>& l, vector<int>& r) {memset(vis,0,sizeof(vis));if(!dfs(0,l,r)) return false;for(int i=0;i<n;i++) {if(!vis[i]) return false;}return true;}
};

解法2: 利用图论的知识,-1的个数等于结点个数加1时为二叉树

class Solution {
public:bool validateBinaryTreeNodes(int n, vector<int>& l, vector<int>& r) {int count = 0;for(int i=0;i<n;i++){if(l[i]==-1) count ++;if(r[i]==-1) count ++;}return count==n+1;}
};

最接近的因数

直接从sqrt(num+2)到0进行遍历,然后判断

class Solution {
public:vector<int> closestDivisors(int num) {vector<int> v;int sq = (int)sqrt(num+2);int mind = 1000000000;for(int i=sq;i>0;i--){int j1 = (num+1)/i,j2 = (num+2)/i;if(i*j1==num+1){if(abs(i-j1)<mind){mind = abs(i-j1);v.clear();v.push_back(i);v.push_back(j1);}}else if(i*j2==num+2){if(abs(i-j1)<mind){mind = abs(i-j2);v.clear();v.push_back(i);v.push_back(j2);}}}return v;}  
};

形成三的最大倍数

参考: c++ 去掉最小值 8ms

能被三整除的数,它的各个位上的数加起来的和sum也能被三整除,如果sum%3==1,那可以删去一个对三取余为1的数,也可以删去两个对三取余为2的数.如果sum%3==2,那可以删去一个对三取余为2的数,也可以删去两个对三取余为1的数.删除的时候要从小往大删,这里面体现了贪心的思想.

class Solution {int cnt[10];string res="";int del(int x){for(int i=x;i<=9;i+=3) if(cnt[i]) {cnt[i]--;return 1;}return 0;}
public:string largestMultipleOfThree(vector<int>& digits) {memset(cnt,0,sizeof(cnt));int n = digits.size(),sum=0;for(int i=0;i<n;i++){cnt[digits[i]]++;sum += digits[i];}if(cnt[0]==n) return "0";if(sum%3==1)  if(!del(1)) {del(2);del(2);}if(sum%3==2) if(!del(2)) {del(1);del(1);}for(int i=9;i>=0;i--){while(cnt[i]--) res += i+'0';}return res;}
};