刷题skill+编程cultivation+记录

AChris

02/28/2019 Day23

Leetcode 121. Best Time to Buy and Sell Stock
Importance【4】

解题思路：
做一次遍历就好了，注意在遍历price的过程中，随时更新price的最小值和profit

class Solution {
public int maxProfit(int[] prices) {
// time: O(n) 100%
// space: O(1) 97.21%
if (prices.length < 2) return 0;
int min = prices[0];
int profit = 0;
for (int price: prices) {
min = Math.min(min, price);
profit = Math.max(profit, price - min);
}
return profit;
}
}

复制代码

AChris

02/28/2019 Day23

Leetcode 136. Single Number
Importance【4】

解题思路：
这题主要是可以运用位运算 - 异或 - XOR 来计算，所以很巧妙。
异或有这样的性质：
（1） a ^ b = b ^ a
（2）a ^ b ^ b = a 如果一个数出现两次，和res运算，那么不影响结果
（3）0 ^ a = a 如果一个数只出现一次，和0运算，结果就是那个书本身

class Solution {
// method1:
public int singleNumber(int[] nums) {
// time: O(n)
// space: O(1)
// XOR ^: same return 0 else 1
// (1) XOR is commutative: a ^ b = b ^ a
// (2) So, if a number appear twice, it makes no change to the result.
// On the contrary, if a number is unique, 0 ^ a = a
int res = 0;
for (int num: nums) {
res ^= num;
}
return res;
}
// // method2:
// public int singleNumber(int[] nums) {
// // time: O(n) 35.82%
// // space: O(n) 30.99%
// Set<Integer> hs = new HashSet<> ();
// for (int num: nums) {
// if (hs.contains(num)) hs.remove(num);
// else hs.add(num);
// }
// return Integer.parseInt(hs.toArray()[0].toString());
// }
}

复制代码

AChris

03/01/2019 Day24

Leetcode 137. Single Number II
Importance【4】

解题思路：
还是一道很有trick的题。有两种方法，用HashMap的话就是暴力解决，没啥好说的。

第二种方法是用bitwise operation，比较方便，也很tricky。
主要是用一个ones，一个twos，表示第一次第二次遇到某个num。
                  ones twos
没有遇到       0    0
第一次遇到    1    0
第二次遇到    0    1
第三次遇到    0    0

具体的运算主要还是使用异或XOR，但是要注意。在第一次遇到的时候，ones赋值，twos不赋值，也就是twos不能和ones一样。
在第三次遇到的时候，ones不赋值，twos赋值，也就是ones不能和上一个twos一样。
为了不赋值，可以用 (ones ^ num) & ~b 来使得结果的数不是b。因为，b & ~b = 0

class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) return -1;
// time: O(n) 100%
// space: O(1) 86.53%
// 1. store the num in the ones
// 2. delete the num in the ones, store the num in the twos
// 3. delete num in the twos
// a & ~b to ensure the result of a is different from b (b & ~b = 0)
// & ~b is to ensure not setting b in first loop and not setting a in last loop
// ones twos
// first loop: ones = num, twos = 0 0->1 0->0
// second loop: ones = 0, twos = num 1->0 0->1
// third loop: ones = 0, twos = 0 0->0 1->0
int ones = 0, twos = 0;
for (int num : nums) {
ones = (ones ^ num) & ~twos;
twos = (twos ^ num) & ~ones;
}
return ones;
}
// public int singleNumber(int[] nums) {
// // time: O(n) 34.62%
// // space: O(n) 89.64
// if (nums == null || nums.length == 0) return -1;
// HashMap<Integer, Integer> map = new HashMap<> ();
// for (int num : nums) {
// if (map.containsKey(num)) {
// map.put(num, map.get(num) + 1);
// } else {
// map.put(num, 1);
// }
// }
// for (int key: map.keySet()) {
// if (map.get(key) == 1){
// return key;
// }
// }
// return -1;
// }
}

复制代码

AChris

03/02/2019 Day25

Leetcode 148. Sort List
Importance【4】

解题思路：
主要就是merge sort在linked list上的具体实现。
首先，要将linked list拆分成两个linked list，然后分别对他们sort再merge。
拆分的时候，记得要定义pre，主要用处是把 left和 right 从中间断开。
merge的时候，因为奇偶性，left和right最多相差一个，所以while循环的时候，需要他们都不为null。最后再if判断一下，left 和 right中是否有没有merge上去的元素。

技巧：
利用fast，slow两个node，fast一次两步，slow一次一步，知道fast==null || fast.next==null，最后得到的slow是中间偏左。

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// time: O(nlogn) 5.02%
// space: O(1) 17.26%
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode fast = head, slow = head, pre = null;
// in this way, we get slow as the (n odd) middle point or (n even) middle right
// fast go forward floor(n/2), slow's index is floor(n/2)
if (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
pre.next = null;
ListNode left = sortList(head);
ListNode right = sortList(slow);
return merge(left, right);
}
private ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode moving = dummy;
while (left != null && right != null) {
if (left.val < right.val) {
moving.next = left;
left = left.next;
} else {
moving.next = right;
right = right.next;
}
moving = moving.next;
}
if (left != null) moving.next = left;
if (right != null) moving.next = right;
return dummy.next;
}
}

复制代码

AChris

03/03/2019 Day26

Leetcode 141. Linked List Cycle
Importance【4】

解题思路：
主要是设置两个指针 fast 和slow对 linked list 进行遍历，fast一次走两步，slow一次走一步。
如果有循环的话，总有一天，fast会和slow重复，指向同一个点。
如果没有循环，fast在遍历完之后跳出循环，始终领先 slow。

/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
// time: O(n) 100%
// space: O(1) 96.56%
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) return true;
}
return false;
}
}

复制代码

AChris

03/03/2019 Day26

Leetcode 142. Linked List Cycle II
Importance【4】

解题思路：
主要是设置两个指针 fast 和slow对 linked list 进行遍历，fast一次走两步，slow一次走一步。
如果没有循环，fast会最先遇到null，然后就可以return null了。

如果有循环的话，总有一天，fast会和slow重复，指向同一个点。这个点叫 z。
假设，循环长这样
   n_start -------------- n_cycle_start ---------------- n_meet --|
                                       |                                           |
                                       |--------------------------------------|

/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
// time: O(n) 100%
// space: O(1) 53.27%
if (head == null) return null;
ListNode slow = head, fast = head;
while (true) {
if (fast.next == null || fast.next.next == null) return null;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}

复制代码

AChris

03/03/2019 Day26

Leetcode 142. Linked List Cycle II
Importance【4】

解题思路：
主要是设置两个指针 fast 和slow对 linked list 进行遍历，fast一次走两步，slow一次走一步。
如果没有循环，fast会最先遇到null，然后就可以return null了。

如果有循环的话，总有一天，fast会和slow重复，指向同一个点。这个点叫 n_meet。
假设，循环长这样
   n_start -------(a)------- n_cycle_start --------(b)-------- n_meet --|
                                       |                                                    |
                                       |-------------------------(c)-----------------|

可以知道 slow 走过的距离 a+b，fast走过的距离 a +b + c + b。
所以，2 * (a + b) = a + b + c + b  -->  a = c
所以，我们只要把slow重新写设置成head，fast放在原来相遇的地方，然后让他们一次都走一步，一起走a/c步，这次相遇的地方就是cycle start

AChris

03/03/2019 Day26

Leetcode 142. Linked List Cycle II
Importance【4】

解题思路：
主要是设置两个指针 fast 和slow对 linked list 进行遍历，fast一次走两步，slow一次走一步。
如果没有循环，fast会最先遇到null，然后就可以return null了。

如果有循环的话，总有一天，fast会和slow重复，指向同一个点。这个点叫 n_meet。
假设，循环长这样
   n_start -------(a)------- n_cycle_start --------(b)-------- n_meet --|
                                       |                                                    |
                                       |-------------------------(c)-----------------|

可以知道 slow 走过的距离 a+b，fast走过的距离 a +b + c + b。
所以，2 * (a + b) = a + b + c + b  -->  a = c
所以，我们只要把slow重新写设置成head，fast放在原来相遇的地方，然后让他们一次都走一步，一起走a/c步，这次相遇的地方就是cycle start

/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
// time: O(n) 100%
// space: O(1) 53.27%
if (head == null) return null;
ListNode slow = head, fast = head;
while (true) {
if (fast.next == null || fast.next.next == null) return null;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}

复制代码

补充内容 (2019-3-4 00:21):
附一个写的比较好的讲解：https://www.cnblogs.com/hiddenfox/p/3408931.html

AChris

03/03/2019 Day26

Leetcode 152. Maximum Product Subarray
Importance【4】

解题思路：
解题的关键还在是设置变量上。
首先，因为有负数的存在，所以最大最小值随时可能相互转化，所以就要设置 curMax, curMin 两个变量记录最大最小值，并在每次遇到新的数之后更新curMax，curMin。
其次，因为array可能有0，在遇到0之后，curMax，curMin都会变成 0。所以说还要再增加一个max(max(..., ....), num[i]) 来引入num[ i ] 来重新restart

class Solution {
public int maxProduct(int[] nums) {
// time: O(n) 99.25%
// space: O(1) 79.57%
if (nums == null || nums.length == 0) return 0;
int curMax = nums[0];
int curMin = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
int temp = curMax;
// add A[i] in the last, since after encountering 0, curMax = curMin = 0, we need this nums[i] to restart
curMax = Math.max(Math.max(curMax * nums[i], curMin * nums[i]), nums[i]);
curMin = Math.min(Math.min(temp * nums[i], curMin * nums[i]), nums[i]);
res = Math.max(res, curMax);
}
return res;
}
}

复制代码

补充内容 (2019-3-5 01:27):
日期更正：03/04/2019 Day27

AChris

03/05/2019 Day28

Leetcode 206. Reverse Linked List
Importance【4】

解题思路：暴力解决
1.递归法：每次对nextNode进行reverse并返回newHead
2.遍历法：front用于链表的 next 一点一点往前走，mid 和 latter 用来设置新的结构关系

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// method1: recursive
public ListNode reverseList(ListNode head) {
// time: O(n) 100%
// space: O(n) 8.72%
if (head == null || head.next == null) return head;
ListNode nextNode = head.next;
ListNode newHead = reverseList(nextNode);
nextNode.next = head;
head.next = null;
return newHead;
}
// // method2: iterative
// public ListNode reverseList(ListNode head) {
// // time: O(n) 100%
// // space: O(1) 11.36%
// if (head == null || head.next == null) return head;
// ListNode front = head.next;
// ListNode mid = head;
// ListNode latter = null;
// while(front != null) {
// mid.next = latter;
// latter = mid;
// mid = front;
// front = front.next;
// }
// mid.next = latter;
// return mid;
// }
}

复制代码

刷题skill+编程cultivation+记录

浏览过的版块