CONY的世界

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequenceand not a substring.
 
這題不是用DP，因為一但遇到重疊的基本上counting是直接歸零
看解答也是用two pointer 掃過所有可能，l 負責記錄開頭，r 負責記錄結尾，
用兩個紀錄的好處是當要清除重複的字元時，前面非重複字元其實也要從set清除掉，
所以 l 可以幫助紀錄到底需要清掉哪些字元，中間過程中我們會掃過所有可能的不重複字串，
所以要有一個int 去記錄這之中最長的字串在最後return

360. Sort Transformed Array
注意這題之所以變難是因為O(n)，因為不能用sorting，不然會變成O(nlogn)
用到的概念是數學的概念拋物線

通常用來detect loop，判斷從哪段開始有loop 
解法可以想像是龜兔賽跑，兔子兩倍速，烏龜一倍速前進
 
假設c是起點距離loop的距離，k是起點距離第一次相遇點的距離，loop 長度是L

 
162. Find Peak Element

A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

211. Add and Search Word - Data structure design

Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)

在研究為什麼 List<List<Integer>> res = new ArrayList<>(); 
 為什麼可以這樣初始，然後研究到這個
 

442. Find All Duplicates in an Array
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
 
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
 Success: 

134. Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
 
紀錄這題我一開始想到的就是想找扣最多當最後，然後向後找正值當起頭
結果很難寫.....就去解答了
這題用到蠻重要的一個觀念
When sum(i, j) < 0, start = i + 1

134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
 
紀錄這題我一開始想到的就是想找扣最多當最後，然後向後找正值當起頭
結果很難寫.....就去解答了
這題用到蠻重要的一個觀念
When sum(i, j) < 0, start = i + 1

71. Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"