騰訊?？嫉氖浪惴}

完整代碼如下：

classSolution{
publicStringlongestPalindrome(Strings){

if(s==null||s.length()<2){
?????????????returns;
}

Stringresult="";
for(inti=0;ir2.length()?r1:r2;
result=tempMax.length()>result.length()?tempMax:result;

}
returnresult;

}

privateStringsubLongestPalindrome(Strings,intl,intr){
while(l>=0&&rreturns.substring(l+1,r);
}
}

6.全排列

給定一個不含重復數(shù)字的數(shù)組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1：

輸入：nums =[1,2,3]
輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

輸入：nums =[0,1]
輸出：[[0,1],[1,0]]

這道題可以用回溯算法解決，完整代碼如下：

classSolution{
//全排列，即所有路徑集合
List>allPath=newLinkedList<>();

publicList>permute(int[]nums){
//當前路徑，入口路徑，path是空的
Listpath=newLinkedList<>();
//遞歸函數(shù)入口，可做選擇是nums數(shù)組
backTrace(nums,path);
returnallPath;
}

publicvoidbackTrace(int[]nums,Listpath){
//已走路徑path的數(shù)組長度等于nums的長度,表示走到葉子節(jié)點，所以加到全排列集合
if(nums.length==path.size()){
allPath.add(newLinkedList(path));
return;
}

for(inti=0;iif(path.contains(nums[i])){
continue;
}
//做選擇，加到當前路徑
path.add(nums[i]);
//遞歸，進入下一層的決策
backTrace(nums,path);
//取消選擇
path.remove(path.size()-1);
}
}
}

大家可以看下之前我寫的這篇回溯文章哈，有回溯算法的框架套用。

面試必備：回溯算法詳解

7. LRU 緩存

請你設計并實現(xiàn)一個滿足 LRU (最近最少使用) 緩存 約束的數(shù)據(jù)結構。

實現(xiàn) LRUCache 類：

• LRUCache(int capacity) 以 正整數(shù) 作為容量capacity 初始化 LRU 緩存
• int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
• void put(int key, int value)如果關鍵字 key 已經存在，則變更其數(shù)據(jù)值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數(shù)量超過 capacity ，則應該 逐出 最久未使用的關鍵字。

函數(shù) get 和 put 必須以O(1)的平均時間復雜度運行。

示例：

輸入
["LRUCache","put","put","get","put","get","put","get","get","get"]
[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
輸出
[null,null,null,1,null,-1,null,-1,3,4]

解釋
LRUCachelRUCache=newLRUCache(2);
lRUCache.put(1,1);//緩存是{1=1}
lRUCache.put(2,2);//緩存是{1=1,2=2}
lRUCache.get(1);//返回1
lRUCache.put(3,3);//該操作會使得關鍵字2作廢，緩存是{1=1,3=3}
lRUCache.get(2);//返回-1(未找到)
lRUCache.put(4,4);//該操作會使得關鍵字1作廢，緩存是{4=4,3=3}
lRUCache.get(1);//返回-1(未找到)
lRUCache.get(3);//返回3
lRUCache.get(4);//返回4

這道題，出現(xiàn)的頻率還是挺高的，很多小伙伴在面試時，都反饋自己遇到過原題。

LRU，Least Recently Used，即最近使用過的數(shù)據(jù)是有用的，可以使用雙鏈表+Hashmap解答，雙鏈表用于存儲LRUCache的數(shù)據(jù)，Hashmap實現(xiàn)O（1）的平均時間復雜度。

• 每次從鏈表尾部添加元素，靠尾的元素就是最近使用過
• 某個key可以通過哈希表快速定位到節(jié)點。

對于雙鏈表，需要做哪些事呢。

• 首先是鏈表初始化，為了方便處理i，虛擬一個頭節(jié)點和尾結點。
• 添加元素時，放到鏈表的尾部，表示該元素最近使用過
• 刪除雙向鏈表的某個節(jié)點
• 刪除并返回頭節(jié)點，表示刪除最久未使用的元素
• 返回鏈表當前長度

LRU緩存有哪些方法

• 構造函數(shù)初始化方法
• get和put方法
• makeRecently 設置某個元素最近使用過的方法，哈希表已經有該元素
• addRecently 添加最近使用過的元素，同時更新map
• deleteKey 刪除某個key對應的元素,同時刪除map上的節(jié)點
• removeLeastRecently 刪除最久未使用的元素

完整代碼如下：

classNode{

intkey,val;
Nodenext,prev;
publicNode(intkey,intval){
this.key=key;
this.val=val;
}
}

classDoubleList{
//虛擬出頭節(jié)點和尾結點
privateNodehead,tail;
privateintsize;

//初始化雙鏈表
publicDoubleList(){
//虛擬頭結點
head=newNode(0,0);
//虛擬頭結點
tail=newNode(0,0);
head.next=tail;
tail.prev=head;
size=0;
}

//要加到鏈表尾部，且越靠近鏈表尾部，越表示最近使用過
publicvoidaddLast(Nodex){
//比如當前鏈表為：head <-> 1 <-> tail，加入結點x = 2
x.prev=tail.prev;
//完成結點2指向兩端的箭頭head<->1<-?2?->tail;此時tail.pre=結點1還未斷開
x.next=tail;
//head<->1<->2->tail;
tail.prev.next=x;
//head<->1<->2<->tail;
tail.prev=x;
//更新鏈表長度
size++;
}

//刪除指定結點
publicvoidremove(Nodex){
x.prev.next=x.next;
x.next.prev=x.prev;
size--;
}

//刪除并返回頭結點
publicNoderemoveHead(){
if(head.next==tail){
returnnull;
}
Nodefirst=head.next;
//size在remove中更新了
remove(first);
//用作在哈希表中移除最久未使用的數(shù)據(jù)值
returnfirst;
}

//獲取鏈表長度
publicintgetSize(){
returnsize;
}
}

publicclassLRUCache{

privateMapmap;
privateDoubleListdoubleList;
privateintcap;

publicLRUCache(intcapacity){
this.map=newHashMap<>();
this.doubleList=newDoubleList();
this.cap=capacity;
}

publicintget(intkey){
if(map.containsKey(key)){
//先將key標記為最近使用，再返回value
makeRecently(key);
returnmap.get(key).val;
}else{
return-1;
}
}

publicvoidput(intkey,intvalue){
if(map.containsKey(key)){
deleteKey(key);//從原map中移除該key
addRecently(key,value);//更新最近使用
return;
}

intsize=doubleList.getSize();
if(size==cap){//說明需要移除最久未使用的元素了
removeLeastRecently();
}
addRecently(key,value);//添加新的元素進來
}


publicvoidmakeRecently(intkey){//將某個key標記為最近使用的元素（map中已存在的）
Nodex=map.get(key);
doubleList.remove(x);//先從雙鏈表刪除
doubleList.addLast(x);//再添加到鏈表末尾，因為尾部是最近使用過的元素
}

publicvoidaddRecently(intkey,intvalue){//添加最近使用過的元素
Nodex=newNode(key,value);
doubleList.addLast(x);
map.put(key,x);//更新map
}

publicvoiddeleteKey(intkey){
Nodex=map.get(key);
map.remove(key);
doubleList.remove(x);//在map中和cache中同時刪除
}

//刪除最久未使用的元素
publicvoidremoveLeastRecently(){
//最久未使用的一定在鏈表頭部
NodeoldNode=doubleList.removeHead();
intoldKey=oldNode.key;
map.remove(oldKey);
}
}

8. 合并K個升序鏈表

給你一個鏈表數(shù)組，每個鏈表都已經按升序排列。請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例 1：

輸入：lists =[[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數(shù)組如下：
[
1->4->5,
1->3->4,
2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

合并兩個有序鏈表，是比較簡單的，相信大家都會做。那么如何合并K個有序鏈表呢？其實道理是一樣的，我們可以借用優(yōu)先級隊列找出最小節(jié)點，完整代碼如下：

classSolution{


publicListNodemergeKLists(ListNode[]lists){

if(lists.length==0){
returnnull;
}
//虛擬節(jié)點
ListNodehead=newListNode(0);
ListNodetail=head;
//優(yōu)先隊列
PriorityQueuequeue=newPriorityQueue<>(lists.length,(a,b)->(a.val-b.val));

//將K個鏈表頭節(jié)點合并最小堆
for(ListNodenode:lists){
if(node!=null){
queue.add(node);
}
}

while(!queue.isEmpty()){
//獲取最小節(jié)點，放到結果鏈表中
ListNodenode=queue.poll();
tail.next=node;

if(node.next!=null){
queue.add(node.next);
}
//指針鏈表一直往前
tail=tail.next;
}
returnhead.next;
}
}

9. 無重復字符的最長子串

給定一個字符串 s ，請你找出其中不含有重復字符的 最長子串 的長度。

示例 1:

輸入:s="abcabcbb"
輸出:3
解釋:因為無重復字符的最長子串是"abc"，所以其長度為 3。

示例 2:

輸入:s="bbbbb"
輸出:1
解釋:因為無重復字符的最長子串是"b"，所以其長度為 1。

這道題可以使用滑動窗口來實現(xiàn)?；瑒哟翱诰褪蔷S護一個窗口，不斷滑動，然后更新答案。

滑動窗口的大致邏輯框架，偽代碼如下：

intleft=0，right=0;
while(rightwhile(windowneedsshrink){
//縮小窗口
window.remove(s[left]);
left++;
}
}

解法流程如下：

• 首先呢，就是獲取原字符串的長度。
• 接著維護一個窗口（數(shù)組、哈希、隊列）
• 窗口一步一步向右擴展
• 窗口在向右擴展滑動過程，需要判斷左邊是否需要縮減
• 最后比較更新答案

完整代碼如下：

intlengthOfLongestSubstring(Strings){
//獲取原字符串的長度
intlen=s.length();
//維護一個哈希集合的窗口
Setwindows=newHashSet<>();
intleft=0,right=0;
intres=0;

while(rightwhile(windows.contains(c)){
windows.remove(s.charAt(left));
left++;
}
windows.add(c);
//比較更新答案
res=Math.max(res,windows.size());
}
returnres;
}

之前寫過一篇滑動窗口解析，大家有興趣可以看下哈：

leetcode必備算法：聊聊滑動窗口

10.刪除鏈表的倒數(shù)第 N 個結點

給你一個鏈表，刪除鏈表的倒數(shù)第 n 個結點，并且返回鏈表的頭結點。

示例 ：

輸入：head =[1,2,3,4,5], n = 2
輸出：[1,2,3,5]

這道題可以使用雙指針解決。既然我們要找到倒數(shù)第n個節(jié)點，我們可以使用兩個指針first 和 second同時對鏈表進行遍歷，并且first 比second超前n個節(jié)點。當first遍歷到鏈表的末尾時，second就恰好處于倒數(shù)第n個節(jié)點。

classSolution{
publicListNoderemoveNthFromEnd(ListNodehead,intn){
ListNodedummy=newListNode(0,head);
ListNodefirst=head;
ListNodesecond=dummy;
//first比second先走n個節(jié)點
for(inti=0;iwhile(first!=null){
first=first.next;
second=second.next;
}
//刪除節(jié)點
second.next=second.next.next;
ListNodeans=dummy.next;
returnans;
}
}