LeetCode Week Contest

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

本周题目比较简单暴力。
1252. Cells with Odd Values in a Matrix
暴力模拟

class Solution {public int oddCells(int n, int m, int[][] indices) {int ans=0;int[][] chess=new int[n][m];for(int[] a:indices){for(int i=0;i<m;i++)chess[a[0]][i]+=1;for(int i=0;i<n;i++)chess[i][a[1]]+=1;}for(int i=0;i<n;i++){for(int j=0;j<m;j++){if((chess[i][j] & 1)==1)ans++;}}return ans;}
}

1253. Reconstruct a 2-Row Binary Matrix
暴力方法

class Solution {public List<List<Integer>> reconstructMatrix(int upper, int lower, int[] colsum) {int cols=colsum.length;int[][] nums=new int[2][cols];ArrayList<Integer> left=new ArrayList<>();int count=0;for(int i=0;i<cols;i++){if(colsum[i]==2){nums[0][i]=1;nums[1][i]=1;upper--;lower--;}if(colsum[i]==1){left.add(i);count++;}}if(count!=upper+lower)return new LinkedList<>();for(int i=0;i<left.size();i++){if(upper>lower){nums[0][left.get(i)]=1;upper--;}else{nums[1][left.get(i)]=1;lower--;}}if(upper==0 && lower==0){LinkedList<List<Integer>> ans=new LinkedList<>();for(int i=0;i<2;i++){LinkedList<Integer> tmp=new LinkedList<>();for(int j=0;j<cols;j++)tmp.add(nums[i][j]);ans.add(tmp);}return ans;}else{return new LinkedList<>();}}
}

1254. Number of Closed Islands
经典的BFS似曾相识

class Solution {static class Coordinate{int x,y; public Coordinate(int x,int y){this.x=x;this.y=y;}     }int[] dirsX={0,0,1,-1};int[] dirsY={-1,1,0,0};public int closedIsland(int[][] grid) {int ans=0;int m=grid.length,n=grid[0].length;boolean[][] visited=new boolean[m][n];for(int i=1;i<m-1;i++){for(int j=1;j<n-1;j++){if(grid[i][j]==0 && !visited[i][j]){boolean flag=false;Queue<Coordinate> q=new LinkedList<>();q.add(new Coordinate(i,j));while(!q.isEmpty()){Coordinate tmp=q.poll();int x=tmp.x,y=tmp.y;if(x==0 || x==m-1 || y==0 || y==n-1)flag=true;for(int k=0;k<4;k++){int x1=x+dirsX[k],y1=y+dirsY[k];if((x1>=0 && x1<m) && (y1>=0 && y1<n) && grid[x1][y1]==0 && !visited[x1][y1]){visited[x1][y1]=true;q.add(new Coordinate(x1,y1));   }}}if(!flag)ans++;}}}return ans;}
}

1255. Maximum Score Words Formed by Letters
经典的状态压缩动态规划似曾相识

class Solution {public static boolean isChosen(int i,int j){if(((i>>j) & 1)==1)return true;elsereturn false;}public static boolean canDistribute(String word,int[] curCount){for(int i=0;i<word.length();i++){if(curCount[word.charAt(i)-'a']>=1)curCount[word.charAt(i)-'a']--;elsereturn false;    }return true;}public int maxScoreWords(String[] words, char[] letters, int[] score) {int n=words.length;//可选字母计数int[] count=new int[26];for(char c:letters){count[c-'a']++;}//候选单词得分int[] scores=new int[n];for(int j=0;j<words.length;j++){String word=words[j];for(int i=0;i<word.length();i++){scores[j]+=score[word.charAt(i)-'a'];}}int N=1<<n,ans=0;for(int i=0;i<N;i++){int curMax=0;int[] curCount=new int[26];for(int k=0;k<26;k++)curCount[k]=count[k];for(int j=0;j<n;j++){if(isChosen(i,j)){if(canDistribute(words[j],curCount))curMax+=scores[j];elsebreak;} }ans=Math.max(ans,curMax);}      return ans;}
}

1266. Minimum Time Visiting All Points
按顺序访问二维坐标点，每一步只能水平、竖直、正对角移动一个单元格，对于相邻点构成正方形的情况，所需步数为正方形的边长；对于矩形情况，也容易看出所需步数为矩形长边的长度。因此将两条规则统一：

class Solution {public int minTimeToVisitAllPoints(int[][] points) {int ans=0;for(int i=1;i<points.length;i++){ans+=Math.max(Math.abs(points[i][0]-points[i-1][0]),Math.abs(points[i][1]-points[i-1][1]));}return ans;}
}

1267. Count Servers that Communicate
能够通信的服务器必然在同一行或者同一列，也就是说在空十字线上的服务器被忽略，类似八皇后里面标记行列状态的技巧，需要用行数组和列数组来记录服务器的数量

class Solution {public int countServers(int[][] grid) {int[] recordRow=new int[250];int[] recordCol=new int[250];int m=grid.length;int n=grid[0].length;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]!=0){recordRow[i]++;recordCol[j]++;}}}int ans=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if( grid[i][j] == 1 && ( recordRow[i]>1 || recordCol[j]>1 )){//System.out.println(i+" "+j);ans++;}}}return ans;}
}

1268. Search Suggestions System
这个问题是Trie的加强（实现他的应用功能：拼写提示），这里原封不动拷贝Trie Implementation的代码，核心代码是对Trie的深度优先遍历操作，对于输入不断增加的字母，（新）前缀的搜索定位都需要从Trie根节点开始，这一步是相对冗余的操作，可以进一步优化。
算法一：

class Solution {public static int count = 0;public static int MAX = 3;public List<List<String>> suggestedProducts(String[] products, String searchWord) {List<List<String>> ans = new LinkedList<>();Trie trie = new Trie();for (int i = 0; i < products.length; i++) {trie.insert(products[i]);}for (int i = 0; i < searchWord.length(); i++) {count = 0;String prefix = searchWord.substring(0, i + 1);List<String> record = new LinkedList<>();TrieNode node = trie.searchPrefix(prefix);if(node!=null){if(node.isEnd){record.add(prefix);count++;}collect(prefix, node, record);}ans.add(record);}return ans;}public void collect(String cur, TrieNode node, List<String> record) {if (count == MAX)return;for (char c = 'a'; c <= 'z' && count<MAX; c++) {if (node.containsKey(c)) {String next = cur + c;if (node.get(c).isEnd) {record.add(next);count++;}collect(next, node.get(c), record);}}}class TrieNode {private TrieNode[] links;private final int R = 26;private boolean isEnd;public TrieNode() {links = new TrieNode[R];}public boolean containsKey(char c) {return links[c - 'a'] != null;}public TrieNode get(char c) {return links[c - 'a'];}public void put(char c, TrieNode node) {links[c - 'a'] = node;}public void setEnd() {isEnd = true;}}class Trie {private TrieNode root;/*** Initialize your data structure here.*/public Trie() {root = new TrieNode();}/*** Inserts a word into the trie.*/public void insert(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) {char curChar = word.charAt(i);if (!node.containsKey(curChar))node.put(curChar, new TrieNode());node = node.get(curChar);}node.setEnd();}/*返回以word为前缀的Trie节点*/private TrieNode searchPrefix(String word) {TrieNode node = root;for (int i = 0; i < word.length(); i++) {char curChar = word.charAt(i);if (node.containsKey(curChar))node = node.get(curChar);elsereturn null;}return node;}/*** Returns if the word is in the trie.*/public boolean search(String word) {TrieNode node = searchPrefix(word);return node != null && node.isEnd;}/*** Returns if there is any word in the trie that starts with the given prefix.*/public boolean startsWith(String prefix) {TrieNode node = searchPrefix(prefix);return node != null;}}/*public static void main(String[] args) {String[] strs = {"mobile", "mouse", "moneypot", "monitor", "mousepad"};String searchWord = "mouse";SearchSuggestions ss = new SearchSuggestions();List<List<String>> ans = ss.suggestedProducts(strs, searchWord);for (List<String> t : ans) {for (String s : t) {System.out.print(s + " ");}System.out.println();}}*/
}

算法二：有点暴力匹配的意思，算法比较直观，先按字典序排序，然后，枚举可能的前缀与产品名一一匹配。看着复杂度比较大，实际运行起来速度挺快。

public List<List<String>> suggestedProducts(String[] products, String searchWord) {List<List<String>> results = new ArrayList<>();if(products == null || products.length == 0) return results;// sort the products lexicographicallyArrays.sort(products);for(int i = 1; i <= searchWord.length(); i++) {List<String> temp = new ArrayList<>();int count = 0;for(String product : products) {if(product.length() >= i && product.substring(0, i).equals(searchWord.substring(0, i))) {temp.add(product);count++;if(count >= 3) {break;}}}results.add(temp);}return results;
}

1269. Number of Ways to Stay in the Same Place After Some Steps
状态转移方程：
$$\begin{gathered} dp[i,j]表示花费i步到达位置j所需的步数。 \\ dp[i,j]=dp[i-1,j-1]+dp[i-1,j]+dp[i-1,j+1] \end{gathered}$$

class Solution {public static int MOD=1000000007;public int numWays(int steps, int arrLen) {int[] dp1=new int[arrLen+2];dp1[1]=1;int[] dp2=new int[arrLen+2];int n=Math.min(steps,arrLen);for(int i=0;i<steps;i++){for(int j=1;j<n+1;j++)dp2[j]=((dp1[j-1]+dp1[j])%MOD+dp1[j+1])%MOD;int[] tmp=dp1;dp1=dp2;dp2=tmp;}return dp1[1]; }
}

万年第四道不会，这该怎么提高呀！！！
1184. Distance Between Bus Stops

class Solution {public int distanceBetweenBusStops(int[] distance, int start, int destination) {int dist=0,dist1=0;if(start>destination){int tmp=start;start=destination;destination=tmp;}for(int i=0;i<distance.length;i++){dist+=distance[i];if(i>=start && i<destination){dist1+=distance[i];}}return Math.min(dist-dist1,dist1);}
}

1185. Day of the Week

class Solution {public static int[][] monthLength={{31,28,31,30,31,30,31,31,30,31,30,31},{31,29,31,30,31,30,31,31,30,31,30,31}};public static String[] symbols={"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};public static boolean isleap(int year){if(year%4==0&&year%100!=0||year%400==0)return true;elsereturn false;}public String dayOfTheWeek(int day, int month, int year) {int sum=0,cur=0;for(int i=1971;i<year;i++){sum+=isleap(i)?366:365;}if(isleap(year)){     //29天for(int i=0;i<month-1;i++){cur+=monthLength[1][i];}}else{for(int i=0;i<month-1;i++){cur+=monthLength[0][i];}}sum+=cur+day;return symbols[(5+(sum-1)%7)%7];}
}

1186. Maximum Subarray Sum with One Deletion

class Solution {public int maximumSum(int[] arr) {int n=arr.length;int[] endHere=new int[n];endHere[0]=arr[0];int max=arr[0];for(int i=1;i<n;i++){endHere[i]=Math.max(endHere[i-1]+arr[i],arr[i]);max=Math.max(max,endHere[i]);}int[] startHere=new int[n];startHere[n-1]=arr[n-1];for(int i=n-2;i>=0;i--){startHere[i]=Math.max(startHere[i+1]+arr[i],arr[i]);max=Math.max(max,startHere[i]);}for(int i=1;i<n-1;i++){max=Math.max(max,endHere[i-1]+startHere[i+1]);}return max;  }
}

1187. Make Array Strictly Increasing

这篇关于LeetCode Week Contest的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---