121、 Best Time to Buy and Sell Stock
三十一、題目
給出一個股票的價格序列，買入一次賣出一次，求能獲得最大利潤。其實就是求一個數組中，後面的數減去前面的數能得到的最大值。最容易想到的肯定是每次選一個數，周遊後面的數，求出直接的差然後和目前最大值進行比較，這樣時間複雜度為O(n*n)，不推薦。
思路：
找到目前周遊索引（包括目前索引）中的最小值min，然後用目前值減去這個最小值，最後跟我們一開始設定的maxProfit=0 進行比較取大的那一個，那麼最終的maxProfit一定大于0，要麼等于0。
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
package cn.hnu.leetcode.easy;
public class _121_MaxProfit {
public int maxProfit(int[] prices) {
//如果數組是空或者數組的長度小于2,說明數組裡面隻有一個或者根本沒有元素,直接傳回0
//因為不可能當天買當天就賣掉
if(prices == null||prices.length<2){
return 0;
}
//将最大利潤設定成0
int maxProfit = 0;
//整個數組中的最小值姑且就看成數組的第一個元素
int min = prices[0];
int len = prices.length;
//從數組的第二個元素開始周遊
for(int i = 1;i<len;i++){
//找到目前周遊的索引之前的最小的元素
min = Math.min(prices[i] , min);
//用目前的位置的元素減去上面獲得的"最小元素",然後跟上一次設定的最大利潤比較
//将最大利潤重新設定
maxProfit = Math.max(prices[i] - min , maxProfit);
}
//最後傳回
return maxProfit;
}
}
122、Best Time to Buy and Sell Stock II
三十二、題目
假設有一個數組，其中數組的第i個元素是第i天給定股票的價格。
設計算法以找到最大利潤。 假設可以根據需要完成盡可能多的交易（即，多次買入并賣出一股股票）。
注意：您不得同時進行多筆交易（即，必須在再次購買之前賣出股票）
思路：
因為可以連續買入或者賣出，是以隻要賣出點比買出點高，就可以賣出擷取利潤，将利潤累加即可。但給出的例子裡面有一個【1,2,3,4,5】擷取利潤是5-1=4，而不是（2-1）+（3-2）+（4-3）+（5-4）= 4.
Example 1:
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
package cn.hnu.leetcode.easy;
public class _122_MaxProfit {
public int maxProfit(int[] prices) {
int len = prices.length;
//如果數組的長度小于等于1,那麼也就沒有所謂的買入與賣出
if(len<=1){
return 0;
}
int i = 0;
int total = 0;
//使用局部最低點作為買入點,局部最高點為賣出點
while(i<len){
int buy,sell;
while(i+1<len&&prices[i+1]<prices[i]){
i++;
}
//設定買入點
buy = i;
//買入與賣出不能是同一天
i++;
//上面做了i++,那麼下面這個循環首先要判斷的是是否已經到了數組的最後
//這裡用數組【1 2 3 4】想
while(i<len&&prices[i]>=prices[i-1]){
i++;
}
//設定賣出點
sell = i-1;
//總利潤累加
total += prices[sell] - prices[buy];
}
return total;
}
}
125、Valid Palindrome
二十三、題目
給定一個字元串，确定它是否是回文，本題隻考慮字母和數字字元并忽略字母大小寫。
注意：空字元串定義為有效的回文。
思路：
将字元串中的字元全轉換成小寫，并将字元串轉換成字元數組，然後定義左右指針分别指向頭和尾，忽略字元數組中間不是0到1和a到z的字元，比較指針指向的字元是否相等，當left>right循環結束，還沒傳回false，那麼就是一個回文字元串。
Example 1:
Input: "A man, a plan, a canal: Panama"
Output: true
Example 2:
Input: "race a car"
Output: false
package cn.hnu.leetcode.easy;
public class _125_IsPalindrome {
public boolean isPalindrome(String s) {
//将給定字元串中的所有字母都改成小寫
char[] chars = s.toLowerCase().toCharArray();
//如果字元串為空或者字元串的長度等于1,則一定是回文字元串
if(s==null||s.length()==1){
return true;
}
//雙指針問題,一個指向頭,一個指向尾
int left = 0;
int right = chars.length-1;
//隻要左邊的指針位置小于右邊,那麼一直周遊
while(left<right){
//看看左邊,如果不在a-z或者0-9之間,左指針右移
if(!((chars[left]>='a'&&chars[left]<='z')||(chars[left]>='0'&&chars[left]<='9'))){
left++;
//看看右邊,如果不在a-z或者0-9之間,右指針左移
}else if(!((chars[right]>='a'&&chars[right]<='z')||(chars[right]>='0'&&chars[right]<='9'))){
right--;
//如果左指針指向的值等于右指針指向的值,左右指針分别右移和左移
}else if(chars[left]==chars[right]){
left++;
right--;
//否則的話就傳回false
}else{
return false;
}
}//end while
//while結束都沒傳回false,那麼就是回文字元串了
return true;
}
}
136、Single Number
二十四、題目
給定一個非空的整數數組，除了一個元素外，每個元素都會出現兩次。找到這個單一進制素
注意：
算法應具有線性運作時間複雜度，能不用額外的記憶體來實作嗎？
思路：
思路一：将數組中的元素以鍵值對的形式存在map裡面，然後數組中每出現相同的數，那麼鍵所對應的值就+1，最終隻要傳回map集合中值為1的那個key即可
思路二：利用異或操作，n ^ 0 = n ; n ^ n = 0 ；也就是說如果數組中出現同樣的數，那麼就傳回0，如果不存在那就傳回這個數；其實就是位運算，而且這個數組指明了除了其中一個數，其它數字都出現兩次，實際上就是讓用異或運算。而且異或運算滿足:
交換律：a ^ b = b ^ a
結合律：a ^ b ^ c = (a ^ b) ^ c = a ^ (b ^ c)
其它：a ^ b ^ a = b ; a ^ a = 0 ; a ^ 0 = 0； （就是因為隻有一個單數字，其它都是兩兩相同，那麼就可以利用上面的法則轉換成這種形式，得到那個最終的result）
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
方法一：
package cn.hnu.leetcode.easy;
import java.util.HashMap;
import java.util.Map;
public class _136_SingleNumber {
public int singleNumber(int[] nums) {
//建立一個map存儲鍵值對,鍵表示數組中出現的數字
HashMap<Integer, Integer> map = new HashMap<>();
//因為數組非空,是以如果是數組長度是1,直接傳回第一個元素即可
if(nums.length==1){
return nums[0];
}
int len = nums.length;
//周遊數組放入map集合中
for(int i = 0;i<len;i++){
Integer count = map.get(nums[i]);
if(count==null){
count = 0;
}
map.put(nums[i], count+1);
}
int result = -1;
//最終隻要擷取map中值為1的元素就完成了本題
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if(entry.getValue()==1){
result = entry.getKey();
break;
}
}
return result;
}
}
方法二：
package cn.hnu.leetcode.easy;
public class _136_SingleNumber {
public static void main(String[] args) {
int[] arr = new int[]{4,2,1,2,1};
System.out.println(singleNumber(arr));
}
public static int singleNumber(int[] nums) {
//如果數組為空或者數組長度小于1,傳回-1
if(nums==null||nums.length<1){
return -1;
}
int result = 0;
//利用異或操作,0 ^ n = n ; n ^ n = 0
for(int i = 0;i<nums.length;i++){
//System.out.println(result);
result = result ^ nums[i];
}
return result;
}
}
141、Linked List Cycle
二十五、題目
給定一個連結清單，确定它是否有一個循環。
思路：
本題看半天沒看懂題目意思，其實就是給定一個連結清單，也不知道這個連結清單長啥樣，問這個連結清單是不是有環，可以把連結清單想象成操場，有兩個孩子在圍着操場跑，一個速度慢一個速度快，如果操場是飛機場，那是直道，假設無限長，兩個小孩跑死也不會相遇，如果是環，那麼不管這個換多大，一個速度快，一個速度慢，總有一天會相遇，本題就是利用這種思想，快慢指針完成本題。詳見代碼。
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
package cn.hnu.leetcode.easy;
import cn.hnu.leetcode.easy.use_Class.ListNode;
public class _140_HasCycle {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
//前兩個條件好了解,最後一個是因為快指針每次移動兩步,我得知道是否為空
//如果為空,說明就是一個直鍊,沒有環路啦
while(fast!=null&&slow!=null&&fast.next!=null){
//快指針每次移動兩步(可以是任意,但是不同需要改變while循環條件)
fast = fast.next.next;
//慢指針每次移動一步
slow = slow.next;
//如果兩個指針相遇，說明有環,傳回true
if(fast == slow){
return true;
}
}//end while
//真個while結束無歡就無歡了，傳回false
return false;
}
}