[每天两道题]坚持找到工作为止

adbase

125. Valid Palindrome
这题其实有点难度的，算是比较难的简单题。
当然若是语言好，可以用正则表达式来预处理字符串，否则就需要用双指针来跳过符号以及处理大小写。

class Solution {
public boolean isPalindrome(String s) {
s = s.replaceAll("[\\s*\\pP\\p{Punct}]", "").toLowerCase();
return s.equals(new StringBuilder().reverse().toString());
}
}

复制代码

adbase

word ladder II 实在太难写了，两天都没有写出来
128. Longest Consecutive Sequence
这道题我感觉不是很好，题目本意是不能排序，就是硬找。还要求线性时间。

所以方法就是扫一下用一个set存起来，存一下有什么数据。
然后遍历数组，每次遇到一个数字，用双指针开始找它两边的数字是否在set里存在，直到找到该数字左右最大边界，计算一下长度。
但是这么做不是线性时间，所以还要用一个set存一下已经检查过哪些数字，在之后的遍历的时候，若是已经检查过的数字就跳过不用检查。

这样可以保证，每一个数字只遍历过一次就可以找出最大的连续数字的长度。

class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num : nums) {
set.add(num);
}
int rs = 0;
int count = 0;
for(int num : nums) {
if(set.contains(num)){
int l = num - 1;
int r = num + 1;
while(set.contains(l) || set.contains(r)) {
if(set.contains(l)) {
set.remove(l);
l--;
}
if(set.contains(r)) {
set.remove(r);
r++;
}
}
//System.out.println(l + " " + r + " " + (r - l - 1 ));
rs = Math.max(rs, r - l - 1);
}
}
return rs;
}
}

复制代码

adbase

129. Sum Root to Leaf Numbers
这道题十分简单，应该是中等难度里偏简单的题。
还是dfs，遇到叶节点，就产生一个该路径的数字加到最终结果里。
某一个路径的数字也十分简单，每次我们把父节点传过来的值乘以10再加上本节点的值，就是当前路径产生的数字。

class Solution {
int sum = 0;
public int sumNumbers(TreeNode root) {
helper(root, 0);
return sum;
}
private void helper(TreeNode node, int curr) {
if(node == null) return;
if(node.left == null && node.right == null) {
sum += curr * 10 + node.val;
return;
}
helper(node.left, curr * 10 + node.val);
helper(node.right, curr * 10 + node.val);
}
}

复制代码

adbase

127. Word Ladder
相比于要求返回路径，这道题相对简单一些，就是bfs，遇到答案，就立刻返回结果。
这个题还有一个难度，就是如何找到只差一个字符的字符串，技巧比较多，我是最笨的办法，挨个比较字符串每一个位置的字符，看有多少个不一样。
还有的是替换元字符某一个位置的字母，看看wordlist有没有一样的，有的话，存到一个map里。

另外就是要用一个set，保存一下已经遇到过的字符串，否则会产生环。

这个题本质，其实就是建一个图，但是这个图是单向的，不能有环。最后产生的图的深度是最小。这个思路ii中也是一样的。只是本题只是找出深度，所以图的产生我们不用精确到每一个路径都准确，只要有一个路径是准确即可

class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Map<String, int[]> map = new HashMap<>();
Set<String> seen = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
seen.add(beginWord);
int level = 0;
while(!queue.isEmpty() && !seen.contains(endWord)) {
int size = queue.size();
for(int i = 0; i < size; i++) {
String s = queue.poll();
for(String us : wordList) {
// System.out.println(us + " " + s + " " + isNext(us, s));
if(isNext(us, s) && !seen.contains(us)) {
queue.offer(us);
seen.add(us);
}
}
}
level++;
System.out.println(queue);
}
return seen.contains(endWord) ? level + 1 : 0 ;
}
private boolean isNext(String s1, String s2) {
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int count = 0;
for(int i = 0; i < c1.length; i++) {
if(c1[i] != c2[i]) count++;
if(count > 1) return false;
}
return count == 1;
}
}

复制代码

adbase

130. Surrounded Regions
今天两道题都没看懂，所以耽误了很久。
一看题就知道肯定是dfs，但是一开始理解为是一个点。后来才看明白是不修改连接到边的点。
所以一下子反应过来，先在四个边找O，作为起点做dfs。dfs里面我们把这些O改成一个临时参数#。
都处理完之后，现在矩阵里，有X，有O，有#。

#就是我们要保留的O , 而依然存在的O就是我们要删除的点，也就是要改成X的O。所以我们再遍历一次矩阵，把#改成O，把O改成X即可得到答案

class Solution {
public void solve(char[][] board) {
int H = board.length;
int W = board[0].length;
for(int i = 0; i < W; i++) {
if(board[0][i] == 'O' )
helper(board, 0, i);
}
for(int i = 0; i < H; i++) {
if(board[i][0] == 'O' )
helper(board, i, 0);
}
for(int i = 0; i < W; i++) {
if(board[H - 1][i] == 'O' )
helper(board, H - 1, i);
}
for(int i = 0; i < H; i++) {
if(board[i][W - 1] == 'O' )
helper(board, i, W - 1);
}
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}else if(board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}
private void helper(char[][] board, int i, int j) {
if(i < 0 || j < 0
|| i > board.length - 1 || j > board[0].length - 1
|| board[i][j] == 'X' || board[i][j] == '#')
return;
board[i][j] = '#';
helper(board, i - 1, j);
helper(board, i + 1, j);
helper(board, i, j - 1);
helper(board, i, j + 1);
}
}

复制代码

adbase

131. Palindrome Partitioning
这道题一开始也没看懂，以为是取某一个子串。
后来才明白，是划分。划分的意思就是把原来的字符串掰成几段，每一段都是回文。

这种排列组合问题，方法当然就是回溯大法好了。
回溯的方法，是我们先把当前字符串拆两段，看看左边是不是回文，若是回文，那么我们就继续拆右边。
为了实现这个效果，我们定义一个start，表示拆的位置，比如s = aab, start = 1，那么就是拆第一个a，和后面的字符串ab。然后我们验证a是回文的，于是继续递归验证ab。然后ab我们继续拆，有两种拆法，a 和ab，然后验证，若是回文,比如又拆出一个a，剩下b，我们递归验证b。
那么什么时候结束呢？当然就是start走到了s.len的时候，也就是走到了没有右边的时候，递归就结束了。此时，前面拆出来的所有子串，就是一组答案。

至于如何判断回文，当然就很简单了，这里不做描述。

class Solution {
List<List<String>> rs = new ArrayList<>();
public List<List<String>> partition(String s) {
helper(s, 0, new ArrayList<>());
return rs;
}
private void helper(String s, int start, List<String> curr) {
if(start == s.length()) {
rs.add(new ArrayList<>(curr));
return;
}
for(int i = start + 1; i <= s.length(); i++) {
String sub = s.substring(start, i);
if(isPalin(sub)) {
curr.add(sub);
helper(s, i, curr);
curr.remove(curr.size() - 1);
}
}
}
private boolean isPalin(String s) {
return s.equals(new StringBuilder(s).reverse().toString());
}
}

复制代码

adbase

132. Palindrome Partitioning II

这道题一看，是找排列组合情况当中某一个特殊值，比如最大，最小，那么一定就是dp。
那么怎么假设dp呢，其实想一想上一道题，我们回溯的时候是先切一刀，若是切完之后，左边是回文，那么继续递归右边。在右边里面每一个位置继续试着切。

那么本题，显然，若是我在i的位置切了一刀，右边s[i,len]是回文，那么若是我知道了左边s[0, i -1]的最小切法，那么显然dp[len] = dp[i - 1] + 1。

也就是当字符串有j个字符，那么dp[j] = if s[i,j] is palin -> min( dp[i] + 1) 其中i = [0, j]; 也就是i就是切的位置。

这样问题就解决了，但是本题有个恶心的时间限制，我试着用stringbuilder判断回文的话，会超时。
所以它逼着你必须用dp去解决判断回文。

那么这个判断其实也不难，bolean dp[i][j] 表示s[i,j]这个字串是不是回文。若是 j - i <= 1 并且 s[i] == s[j]，显然是回文。同样若是j > i + 1，也就是要判断的字符串有两个以上的字符，我有s[i] == s[j] 并且 dp[i + 1]dp[j - 1] =true。也就是左右缩小一位还是回文，那么dp[i][j] = true;

那么我们就可以先初始化一下这个dp[][]二维矩阵，找出所有可能的回文子串之后，再用dp去统计最小切法。

最后，这两个过程是可以写道一个循环里的，代码非常简洁：

class Solution {
public int minCut(String s) {
int len = s.length();
int[] dp = new int[len];
dp[0] = 0;
boolean[][] dp2 = new boolean[len][len];
for(int i = 0; i < len; i++) {
dp[i] = i;
for(int j = 0; j <= i; j++) {
if(s.charAt(i) == s.charAt(j) && (i - j <= 1 || dp2[j+1][i-1])) {
dp2[j][i] = true;
if(j > 0)
dp[i] = Math.min(dp[i], dp[j - 1] + 1);
else dp[i] = 0;
}
}
}
return dp[len - 1];
}
}

复制代码

adbase

133. Clone Graph
这个题很基础，但是我图没有学号，答得不好。最重要的是，要用一个map存储已经产生好的新node，下次再添加孩子的时候，若是孩子节点之前已经产生好了，也就是环，那么我们直接从map里面取出结果，否则，我们就递归地产生这个孩子节点。

这个题我要背诵，以后是要用到的。

class Solution {
Map<Integer, Node> map = new HashMap<>();
public Node cloneGraph(Node node) {
if(node == null) return null;
if(map.containsKey(node.val)) return map.get(node.val);
Node root = new Node(node.val);
map.put(node.val, root);
List<Node> oldNei = node.neighbors;
for(int i = 0; i < oldNei.size(); i++) {
Node oldN = oldNei.get(i);
if(map.containsKey(oldN.val)) {
root.neighbors.add(map.get(oldN.val));
}else{
root.neighbors.add(cloneGraph(oldN));
}
}
return root;
}
}

复制代码

adbase

134. Gas Station
也是经典题了，这道题其实是一个数学定理：一个总和为非负的数列环，一定可以找到一个起点，使得它的累积和也都是非负的。

那么这道题就利用了这一点：
首先，我们要找到可以作为起点的位置，也就是gas[i] - cost[i] >=0 的点，然后我们用一个start记录这个点，然后我们开始往后走，每次到了一个新的点，我们都重新计算邮箱里剩余的油耗tank += gas[i] - cost[i]。若是到了某一个点 k ，tank < 0了，说明前面的起点start走不通。
其实不仅仅是start走不通，而[start, k]里的点都走不通。为什么呢？因为start后面的点相当于带着start点的剩余的油，最后依然走不通，所以若是不从start开始，而是从后面某一个点开始，它的油只会更少，到了后面也一定会走不通的。

所以，此时我们就把start ＝ k + 1，tank = 0。从下一个点从新开始计算。直到我们走到数列的结尾，此时start就是我们要找的起点。

但是这里可能还会有问题，为什么说到了数列终点，start点就一定是答案呢？凭什么说[start, len]走得通，那么转回去[0, start]也走得通呢？这里我也想了很久，后面大概想明白了，若是[start, len]走得通，那么它剩余的油，也就是gas[i] - cost[i] 的累加（其中start<= i < len），一定比[0, start]的gas[j] - cost[j]更大，至少是相等，否则就意味着整个数列没有答案。
当然，其实这道题也的确有没有答案的情况，所以我也的确要计算[0,len]的total = gas - cost。若是此时total 小于0那么就是无论如何都走不通的。返回-1。

所以代码就是

class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0, sum = 0, start = 0, len = gas.length;
for(int i = 0; i < len; i++) {
total += gas[i] - cost[i];
sum += gas[i] - cost[i];
if(sum < 0) {
sum = 0;
start = i + 1;
}
}
return total < 0 ? -1 : start;
}
}

复制代码

adbase

135. Candy
这道题为hard应该是它不是一个常规的思路题，我至今没太搞清楚这个题是什么类型的问题。官方的标签是greedy，贪心法。
此题解法比较多，我选择了一个最容易懂的思路。
首先是初始化一个数列，都设置为1，表示每一个小朋友都有一个糖。
然后我们先处理每一个小朋友的左手边，也就是从i =1到len遍历数组。每次我们比较一下权重，若是当前小朋友权重更大，我们就把当前小朋友的糖数设定为比左手边多一个 children[i] = children[i - 1] + 1 。
然后我们返回来看右手边，也就是从后往前遍历数字，同一看到当前小朋友权重比右手边更大，那么就是右手边数量＋1。但是此时注意，可能当前小朋友的糖已经比右手边更多了，那么我们就不用更新了。也就是更新的条件是权重更大，但是数量小于或者等于。

那么会不会两个循环有矛盾呢？是不会的，因为不可能两个小朋友，右边看左边，说我权重更大，返回来左边看右边也出现权重更大的情况。

所以代码就是

class Solution {
public int candy(int[] ratings) {
int[] arr = new int[ratings.length];
Arrays.fill(arr, 1);
for(int i = 1; i < ratings.length; i++) {
if(ratings[i] > ratings[i - 1]) {
arr[i] = arr[i - 1] + 1;
}
}
for(int i = ratings.length - 2; i >=0; i--) {
if(ratings[i] > ratings[i + 1] && arr[i] <= arr[i + 1]) {
arr[i] = arr[i + 1] + 1;
}
}
//System.out.println(Arrays.toString(arr));
int rs = 0;
for(int n : arr) rs+= n;
return rs;
}
}

复制代码

[每天两道题]坚持找到工作为止

浏览过的版块