中级农民
- 积分
- 115
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2019-12-7
- 最后登录
- 1970-1-1
|
补昨天:
8月10日打卡第十天 刷题第十天
1.Leetcode 3
Longest Substring Without Repeating Characters
Assumption:
All characters are from 'a' - 'z'
High level:
use two pointers slow and fast to maintain a variable sliding window;
use a HashSet to record all unique characters in the sliding window which consist of the current substring.
record the length of current substring and compare with historical longest;
return the longest one;
Details:
the slow pointer represent the startIndex of substring and the right pointer
represent the endIndex of the current substring;
use an int variable longest to record the historical longest substring, waited to be compared
traverse the string and use a hashSet to store unique characters we had ever met;
as long as the upcoming character hasn't shown before, put it into the hashset;
If the character, eg: c, is already in the hashSet, move the slow pointer and remove
s.charAt(slow), until c can be added into the hashset, compare its current length with
historical longest, update the longest(if applicable)
After the process of traversing has finished, we can return longest.
2. find an element and return its index in a sorted unknown sized array;
-double size the searching range from slow index == 0 and fast index == 1;
-when we fix the searching range, shall we use the classical binary search to find out its index or return -1;
3. Leetcode 2 Generate Parentheses
Approach One:
- use DFS with a stringBuilder to generate all parentheses and put into the list
- until index hit the bottom so we can return the list;
Approach two:
- instead of using a StringBuilder, use a char array and replace each character when necessary;
- for example: if the left brackets still remain, put left brackets into the char; if the right brackets has more remains than left brackets, put right brackets into the char.
疫情持久战,更要努力💪💪💪期待下个十天! |
|