本文主要是介绍LeetCode Contest 130，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LeetCode第130周周赛问题基本不难。
1017. Convert to Base -2
这个问题类似于十进制求二进制表达的过程，但因为是负数，需要做一些处理，数学证明这里不赘述，参考
class Solution {public String baseNeg2(int N) {int remainder=N%(-2);N/=(-2);if(remainder<0){remainder+=2;N++;}if(N==0)return String.valueOf(remainder);return baseNeg2(N)+String.valueOf(remainder);}
}
更为一般的结论代码：
public static String toNegativeBase(int n, int negBase)
{ // If n is zero then in any base it will be 0 only int remainder=N%(negBase);N/=(negBase);if(remainder<0){remainder-=negBase;N++;}if(N==0)return String.valueOf(remainder);return toNegativeBase(N)+String.valueOf(remainder);
}
1018. Binary Prefix Divisible By 5
这个问题不大，就是利用余数性质来避免整数溢出
class Solution {public List<Boolean> prefixesDivBy5(int[] A) {LinkedList<Boolean> ret=new LinkedList<>();int tmp=0;for(int i=0;i<A.length;i++){tmp=(tmp<<1 | A[i])%5;if(tmp%5==0)ret.add(true);elseret.add(false);}return ret;}
}
1019. Next Greater Node In Linked List
我用的解法很一般，十分暴力。
class Solution {public int[] nextLargerNodes(ListNode head) {ArrayList<Integer> ret=new ArrayList<>();ListNode p=head;while(p!=null){ListNode q=p.next;while(q!=null && q.val<=p.val)q=q.next;if(q==null)ret.add(0);elseret.add(q.val);p=p.next;}int[] res=new int[ret.size()];for(int i=0;i<ret.size();i++)res[i]=ret.get(i);return res;}
}
看到一种很妙的解法，链表递归加栈真的很强，时间复杂度仅为O(N)：
class Solution {public static Stack<Integer> stack;public static int[] ret;public int[] nextLargerNodes(ListNode head) {stack=new Stack<>();recursive(head,0);return ret;}public static void recursive(ListNode node,int idx){if(node==null){ret=new int[idx];return;}recursive(node.next,idx+1);while(!stack.isEmpty() && stack.peek()<=node.val)stack.pop();if(stack.isEmpty())ret[idx]=0;elseret[idx]=stack.peek();stack.push(node.val);}
}
1020. Number of Enclaves
这一问中规中矩，正常的格网递归搜索即可
class Solution {public static int n_row;public static int n_col;public int numEnclaves(int[][] A) {int ret=0;n_row=A.length;n_col=A[0].length;for(int j=0;j<n_col;j++){if(A[0][j]==1){dfs(0,j,A);} if(A[n_row-1][j]==1){dfs(n_row-1,j,A);}}for(int i=0;i<n_row;i++){if(A[i][0]==1){dfs(i,0,A);}if(A[i][n_col-1]==1){dfs(i,n_col-1,A);}}for(int i=0;i<n_row;i++){for(int j=0;j<n_col;j++){if(A[i][j]==1)ret++;}}return ret;}public static void dfs(int i,int j,int[][] grid){grid[i][j]=-1;for(int dx=-1;dx<=1;dx++){for(int dy=-1;dy<=1;dy++){if(Math.abs(dx+dy)==1 && validPos(i+dx,j+dy,grid))dfs(i+dx,j+dy,grid);}}}public static boolean validPos(int i,int j,int[][] grid){if(i<0 || i>=n_row || j<0 || j>=n_col || grid[i][j]!=1)return false;return true;}
}
这篇关于LeetCode Contest 130的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
