20190324leetcode周赛
首先,原谅我这个菜狗子用的中文版。紧接着上题目。
这是一道easy的题目。一开始,我还是很懵逼的。用两个指针,分别指向两端,向中间移动。对应的左边和与右边和相等时,查看中间部分的情况即可。很显然结果是没通过。所以当时就简单暴力了一下。哎,暴力出真知啊。
class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int threeSum=0;
for (int i=0;i<A.length;i++) {
threeSum+=A[i];
}
int sum=threeSum/3;
if (threeSum%3!=0) {
return false;
}
int count=0;int temp=0;
for (int i=0;i<A.length;i++) {
temp+=A[i];
if (temp==sum) {
count++;
temp=0;
}
}
return count==3;
}
}
这道题我当时没a出来,看的第一名的结果。其实大神们都是很暴力的。我有一点疑问就是我用while循环没通过,对应输入为17的时候,超时。。。首先,对应的k为偶数或者是5的倍数的时候,结果应当是-1。对于给定的K,对应的N不断地增大,来尝试能否被整除。
class Solution {
public int smallestRepunitDivByK(int K) {
if(K%2==0||K%5==0){
return -1;
}
int length=0;
int N=0;
for(int i=1;i<1e6;i++){
N=(N*10+1)%K;
length++;
if(N==0){
return length;
}
}
return -1;
}
}
这道题,一开始我用两层for循环来解决这个问题,毕竟状态转移方程已经给出。结果是超时。仔细分析后,状态方程可以转化为(A[i]+i)+(A[j]-j),这里的i作为起始位置,j是向后移动的。可以通过这个方程的转化,可以减少一层for循环。这是以后我应该多多练习的题目。
import java.util.*;
class Solution {
public int maxScoreSightseeingPair(int[] A) {
int goal=0;
int maxScore=A[0];
for(int i=1;i<A.length;i++){
if(A[i]+maxScore-i>goal) {
goal=A[i]+maxScore-i;
}
if(maxScore<A[i]+i){
maxScore=A[i]+i;
}
}
return goal;
}
}
这道题,是暴力出来的。一方面,考查移位操作与构造字符串,暴力就过了。从这道题,我找到了自己字符串方面的操作是真的菜,真的菜。
class Solution {
public boolean queryString(String S, int N) {
for(int i=0;i<=N;i++){
if(!S.contains(findSubstring(i))){
return false;
}
}
return true;
}
public static String findSubstring(int N){
String res="";
int k=N;
while(k>0) {
if((k&1)!=0){
res+="1";
}
else { res+="0";}
k=k>>1;
}
res=new StringBuilder(res).reverse().toString();
return res;
}
}