刷题skill+编程cultivation+记录

AChris

04/16/2019 Day41
LeetCode 53. Maximum Subarray
Importantce【4】

解题思路：
利用动态规划。
res 记录到目前为止最大值。
dp[i] 记录结尾是nums[i]可以得到的最大值

class Solution {
// method1:
public int maxSubArray(int[] nums) {
// time: O(n) 97.39%
// space: O(1) 90.84%
if (nums == null || nums.length == 0) return 0;
int maxIncludeCur = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
if (maxIncludeCur > 0) {
maxIncludeCur += nums[i];
} else {
maxIncludeCur = nums[i];
}
res = Math.max(maxIncludeCur, res);
}
return res;
}
// // method2:
// public int maxSubArray(int[] nums) {
// // time: O(n) 97.39%
// // space: O(n) 91.14%
// if (nums == null || nums.length == 0) return 0;
// int[] dp = new int[nums.length];
// dp[0] = nums[0];
// int res = dp[0];
// for (int i = 1; i < nums.length; i++) {
// dp[i] = nums[i] + (dp[i - 1] > 0? dp[i - 1] : 0);
// res = Math.max(dp[i], res);
// }
// return res;
// }
}

复制代码

AChris

04/17/2019 Day42
LeetCode 67. Add Binary
Importantce【3】

解题思路：
从后往前依次相加。i 表示 a 的位数。j 表示b的位数。
sb 依次 append

class Solution {
public String addBinary(String a, String b) {
// time: O(n) 99.93%
// space: O(n) 18.47%
StringBuilder sb = new StringBuilder();
int i = a.length() - 1;
int j = b.length() - 1;
int sum = 0;
while (i >= 0 || j >= 0) {
if (i >= 0) sum += a.charAt(i--) - '0';
if (j >= 0) sum += b.charAt(j--) - '0';
sb.append(sum % 2);
sum = sum / 2;
}
if (sum == 1) sb.append('1');
return sb.reverse().toString();
}
}

复制代码

AChris

04/19/2019 Day43
LeetCode 58. Length of the Last Word
Importantce【4】

解题思路：
trim后的长度减去最后一个空格的index 再减一

class Solution {
public int lengthOfLastWord(String s) {
// time: O(1) 100%
// space: O(1) 11.67%
return s.trim().length() - s.trim().lastIndexOf(" ") - 1;
}
}

复制代码

AChris

04/19/2019 Day43
LeetCode 80. Remove Duplicates from Sorted Array II
Importantce【4】

解题思路：
主要是count的时候，记住，count是即将要被赋值的位置，count - 2上不能重复的位置

class Solution {
public int removeDuplicates(int[] nums) {
      // time: O(n) 97.40%
      // space: O(1) 94.46%

      // nums = [ 1, 1, 1, 2, 2, 3, 3]
      //                      c
      //                         i
      //       [ 1, 1, 2, 2, 3, 3, 3]

      if (nums == null) return 0;
      if (nums.length <= 2) return nums.length;
      int count = 2;
      for (int i = 2; i < nums.length; i++) {
         if (nums[i] != nums[count-2]) {
            nums[count++] = nums[i];
         }
      }
      return count;
}
}

AChris

04/27/2019 Day44
LeetCode 37. Sudoku Solver
Importantce【5】

解题思路：
DFS搜索，注意在什么时候return false

class Solution {
public void solveSudoku(char[][] board) {
// time: unkown 43.48%
// space: unknown 100%
if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return;
solve(board);
}
private boolean solve (char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') {
for (char c = '1'; c <= '9'; c++) {
if (isValid(board, c, i, j)) {
board[i][j] = c;
if (solve(board)) {
return true;
} else {
board[i][j] = '.';
}
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, char c, int i, int j) {
for (int k = 0; k < 9; k++) {
if (board[i][k] == c) return false;
if (board[k][j] == c) return false;
if (board[i / 3 * 3 + k / 3][j / 3 * 3 + k % 3] == c) return false;
}
return true;
}
}

复制代码

AChris

04/27/2019 Day44
LeetCode 23. Merge k Sorted Lists
Importantce【5】

解题思路：
主要有两种方法。
第一种：divide and conquer
把整个问题化简成两个两个单独的list合并的问题

第二种：
利用 PriorityQueue，把每个list的头部的listnode加进去，然后每次都从queue中提取出最小的元素，并添加进去新的头部元素

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// // method 1: Divide and Conquer
// // time: O(nlogk) n = number of elements, k = lists.length 94.47%
// // space: O(n) 24.60%
// public ListNode mergeKLists(ListNode[] lists) {
// if (lists == null || lists.length == 0) return null;
// return sort(lists, 0, lists.length - 1);
// }
// private ListNode sort(ListNode[] lists, int low, int high) {
// // low <= high which can be proved by the mathematical induction
// if (low == high) return lists[low];
// int mid = low + (high - low) / 2;
// ListNode l1 = sort(lists, low, mid);
// ListNode l2 = sort(lists, mid + 1, high);
// return merge(l1, l2);
// }
// private ListNode merge(ListNode l1, ListNode l2) {
// if (l1 == null) return l2;
// if (l2 == null) return l1;
// if (l1.val < l2.val) {
// l1.next = merge(l1.next, l2);
// return l1;
// }
// l2.next = merge(l1, l2.next);
// return l2;
// }
// method 2: Priority Queue
// time: O(nlogk) n = number of elements, k = lists.length 40.52%
// space: O(n) 56.54%
public ListNode mergeKLists(ListNode[] lists) {
// boundary case
if (lists == null || lists.length == 0) return null;
// initilization
PriorityQueue<ListNode> queue = new PriorityQueue<> (lists.length, (a, b) -> a.val - b.val);
for (ListNode list: lists) {
if (list != null){
queue.add(list);
}
}
// sort
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (!queue.isEmpty()) {
cur.next = queue.poll();
cur = cur.next;
if (cur.next != null) {
queue.add(cur.next);
}
}
return dummy.next;
}
}

复制代码

AChris

04/27/2019 Day45
LeetCode 41. First Missing Positive
Importantce【5】

解题思路：
主要是利用count sort中的思想，如果1、2、3、。。。n所有的数都有的话，
理想的输出list应该是
index 0, 1, 2, 3, 4, ... i
num. 1, 2, 3, 4, 5, ... i+1
然后通过swap，争取依次把所有的数都swap到对应的位置上。
最后再loop一遍，检查有没有不符合要求的数并输出

class Solution {
public int firstMissingPositive(int[] nums) {
// time: O(n) 100%
// space: O(1) 89.70%
if (nums == null || nums.length == 0) return 1;
for (int i = 0; i < nums.length; i++) {
while (nums[i] >= 1 && nums[i] <= nums.length && nums[i] != nums[nums[i] - 1]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) return i + 1;
}
return nums.length + 1;
}
}

复制代码

AChris

04/28/2019 Day45
LeetCode 25. Reverse Nodes in k-Group
Importantce【5】

解题思路：
递归

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// time: O(n) 100%
// space: O(n) 95.02%
if (head == null || head.next == null) return head;
int count = 0;
ListNode cur = head;
while (count != k && cur!= null) {
cur = cur.next;
count++;
}
/* k = 2 count = 0
1 -> 2 -> 3
h cur
3
ht
2 -> 1.---^
c
*/
if (count == k) {
cur = reverseKGroup(cur, k);
while (count-- > 0) {
ListNode temp = head.next;
head.next = cur;
cur = head;
head = temp;
}
head = cur;
}
return head;
}
}

复制代码

AChris

04/28/2019 Day45
LeetCode 30. Substring with Concatenation of All Words
Importantce【5】

解题思路：
主要是建立一个map， map里面对应的是words中的string和所需要的个数。
然后从s的每一个位置开始遍历，看是否能将所有的words的单词找到对应，如果可以找到的话，就将这个加进结果。

class Solution {
public List<Integer> findSubstring(String s, String[] words) {
// time: O(n^2) 57.49%
// space: O(n) 39.37%
List<Integer> res = new ArrayList<> ();
if (s == null || s.length() == 0 || words == null || words.length == 0) return res;
// initilization
int nWords = words.length;
int wordLength = words[0].length();
HashMap<String, Integer> map = new HashMap<> ();
for (String word: words) {
map.put(word, map.getOrDefault(word, 0) + 1);
}
//search
for (int i = 0; i <= s.length() - nWords * wordLength; i++) {
HashMap<String, Integer> copy = new HashMap<> (map);
int left = nWords;
int j = i;
while (left > 0) {
String curWord = s.substring(j, j + wordLength);
if (!copy.containsKey(curWord) || copy.get(curWord) == 0) break;
copy.put(curWord, copy.get(curWord) - 1);
j += wordLength;
left--;
}
if (left == 0) res.add(i);
}
return res;
}
}

复制代码

AChris

04/28/2019 Day45
LeetCode 32. Longest Valid Parentheses
Importantce【5】

解题思路：
主要是利用stack，不停的把存在的（的位置push进stack里。然后看见）的话，在pop。
然后主要考虑）（）（）和（（））两种情况。

class Solution {
public int longestValidParentheses(String s) {
// time: O(n)
// space: O(n)
int res = 0;
if (s == null || s.length() == 0) return res;
Stack<Integer> stack = new Stack<> ();
int start = -1;
// we will use (start, i] to represent the valid substring
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
if (stack.isEmpty()) {
start = i;
} else {
stack.pop();
if (stack.isEmpty()) {
res = Math.max(res, i - start);
} else {
res = Math.max(res, i - stack.peek());
}
}
}
}
return res;
}
}

复制代码

刷题skill+编程cultivation+记录

浏览过的版块