Leetcode 題目
本文將不斷更新，主要內(nèi)容為解決Leetcode中的算法問題，有比較難的題目可能會(huì)單獨(dú)成文檔橄务，所有代碼都將用Javascript編寫并且Accepted.標(biāo)題后面的百分號(hào)代表用JS寫的代碼中該答案比多少比例的答案快难礼。
對于一些解法不高效的題，歡迎留言寫下你的答案蔫慧。
最后編輯時(shí)間： 8/4/2017
<h5><a id="problem1" >1.Two Sum </a> (96%) </h5>
var twoSum=function(nums,target){
var arr=new Array();
for(var i=0;i<nums.length;i++){
var j=target-nums[i];
if(typeof arr[j]!='undefined'){
return [arr[j],i];
}else{
arr[nums[i]]=i;
}
}
};
這里arr數(shù)組起到了記錄其中一個(gè)數(shù)的位置和值的作用睡毒，每當(dāng)i探索新的數(shù)登馒，如果該數(shù)無法和arr中的數(shù)相加成target，則將該數(shù)放進(jìn)arr，直到找到能和arr中數(shù)組相加等于target的數(shù)溉卓。巧妙之處在于每次將i找到的數(shù)放進(jìn)arr時(shí)，該數(shù)的值在arr中充當(dāng)了位置严肪，該數(shù)的位置在arr中充當(dāng)了值键思，這種方法使用兩個(gè)arr達(dá)成了在數(shù)組中尋找是否存在一個(gè)數(shù)的效果，而無需使用map阐枣。
2.Add Two Numbers(71%)
function ListNode(val) {
this.val = val;
this.next = null;
}
var addTwoNumbers=function(l1,l2){
if(l1===null) return l2;
if(l2===null) return l1;
return helper(l1,l2,0);
};
var helper=function(l1,l2,temp){
if(l1===null&&l2===null){
if(temp==0){
return null;
}else{
return new ListNode(temp);
}
}
if(l1===null&&l2!==null){
l1=new ListNode(0);
}
if(l1!==null&&l2===null){
l2=new ListNode(0);
}
var sum=l1.val+l2.val+temp;
var l3=new ListNode(sum%10);
l3.next=helper(l1.next,l2.next,parseInt(sum/10));
return l3;
};
3. Longest Substring Without Repeating Characters
我的答案 （容易理解但效率不高） （15%）
var lengthOfLongestSubstring = function(s) {
if(s.length<2) return s.length;
var maxCount=0;
var sub=[];
for(var i=0;i<s.length;i++){
var judge=isExist(sub,s[i]);
if(judge==-1){
sub.push(s[i]);
}else{
i=i-sub.length+judge;
var sub=[];
}
if(sub.length>maxCount){
maxCount=sub.length;
}
}
return maxCount;
};
var isExist=function(arr,num){
for(var i=0;i<arr.length;i++){
if(num==arr[i]){
return i;
}
}
return -1;
};
由第一題延伸出的另一種思路,由該題高分java答案改編而來马靠。（48%）
var lengthOfLongestSubstring = function(s) {
if(s.length<2) return s.length;
var max=0;
var sub=[];
for(var i=0,j=0;i<s.length;i++){
j= typeof sub[s.charAt(i)] != 'undefined'?Math.max(j,sub[s.charAt(i)]+1):j ;
sub[s.charAt(i)]=i;
max=Math.max(max,i-j+1);
}
return max;
};
個(gè)人覺得這個(gè)答案很不錯(cuò)了，但我不知道為什么還是只超過了46%蔼两。還可以改進(jìn)的地方是這塊：
j=typeof sub[s.charAt(i)] != 'undefined'?Math.max(j,sub[s.charAt(i)]+1):j ;
如果能把這行代碼直接表示成一個(gè)j=多少的表達(dá)式甩鳄，應(yīng)該速度能更快一些。但我不知道如何直接處理這里的'undefined'额划，能夠達(dá)到以下效果：當(dāng)在sub數(shù)組中找不到s.charAt(i)的值時(shí)妙啃，能直接用 -1 來取代返回的 'undefined'，如果能將返回值直接轉(zhuǎn)成-1 ,那么j就會(huì)直接取j的值俊戳，我們也不用先判斷再賦值了揖赴。
29/3/2017更新：重新安排一下做題順序，現(xiàn)在開始會(huì)分類做抑胎，而不是原計(jì)劃的按照題號(hào)做储笑，先把Array部分做完
Tag: Array
1.Two Sum (96%)
4. Median of Two Sorted Arrays (88%) (該題前幾天在同學(xué)的阿里面試中被問到)
var findMedianSortedArrays = function(nums1,nums2) {
var median=0;
var m=nums1.length; //m,n代表數(shù)組長度
var n=nums2.length;
var i=0;
if(isNull(nums1)){
return findMedianOneArray(nums2);
}
if(isNull(nums2)){
return findMedianOneArray(nums1);
}
if((m+n)%2==0){
while(i<(m+n)/2-1){
if(isNull(nums1)){
nums2.shift();
}else if(isNull(nums2)){
nums1.shift()
}else {
nums1[0]<nums2[0]? nums1.shift():nums2.shift() ;
}
i++;
}
var left,right;
if(isNull(nums1)){
left=nums2.shift();
}else if(isNull(nums2)){
left=nums1.shift();
}else {
left=nums1[0]<nums2[0]? nums1.shift():nums2.shift() ;
}
if(isNull(nums1)){
right=nums2.shift();
}else if(isNull(nums2)){
right=nums1.shift();
}else {
right=nums1[0]<nums2[0]? nums1.shift():nums2.shift() ;
}
median=(left+right)/2;
}else{
while(i<(m+n-1)/2){
if(isNull(nums1)){
nums2.shift();
}else if(isNull(nums2)){
nums1.shift();
}else {
nums1[0]<nums2[0]? nums1.shift():nums2.shift();
}
i++;
}
if(isNull(nums1)){
median=nums2.shift();
}else if(isNull(nums2)){
median=nums1.shift();
}else {
median=nums1[0]<nums2[0]? nums1.shift():nums2.shift() ;
}
}
return median;
};
//在一個(gè)數(shù)組內(nèi)尋找中位數(shù)
var findMedianOneArray=function(num){
var l=num.length;
if(l==0){
return null;
}
if(l%2==0){
return (num[l/2-1]+num[l/2])/2;
}else{
return num[(l-1)/2];
}
};
//判斷數(shù)組是否為空
var isNull=function(num){
if(num.length>0){
return false;
}else {
return true;
}
};
上面的代碼看起來比較復(fù)雜是因?yàn)榧尤肓撕芏嗯袛啵枰袛嗪芏嗵厥馇闆r圆恤，比如數(shù)組為空的時(shí)候突倍，實(shí)際上思路是很清晰的。因?yàn)橐@得兩個(gè)數(shù)組合并以后的中位數(shù)盆昙，無論合并以后排序如何羽历，中位數(shù)的位置是不變的。當(dāng)兩個(gè)數(shù)組長度相加為奇數(shù)時(shí)淡喜，中位數(shù)永遠(yuǎn)位于(m+n+1)/2秕磷，兩個(gè)數(shù)組長度相加為偶數(shù)時(shí)，中位數(shù)永遠(yuǎn)是位于(m+n)/2和((m+n)/2)+1兩者的平均數(shù)炼团。所以每次都比較兩個(gè)數(shù)組首位的大小澎嚣，把小的去掉疏尿，然后再繼續(xù)比較，一直循環(huán)到中位數(shù)所在的位置易桃，此時(shí)把中位數(shù)取出來即可褥琐。代碼寫的有點(diǎn)雜亂，有時(shí)間會(huì)把寫法改一下晤郑，思路本身的速度已經(jīng)不錯(cuò)了敌呈。
11. Container With Most Water (74%)
var maxArea = function(height) {
var left=0;
var right=height.length-1;
var maxSize=0;
while(left<right){
var size=height[left]<height[right]? height[left]*(right-left) : height[right]*(right-left) ;
if(size>maxSize){
maxSize=size;
}
if(height[left]<height[right]){
left++;
}else{
right--;
}
}
return maxSize;
};
這個(gè)解法思路比較清晰，在數(shù)組的首尾分別安插一個(gè)指針然后往中間移直到遇到為止造寝。移動(dòng)過程中只需要明確一點(diǎn):參照木桶原理磕洪，當(dāng)容器左邊的高度小于右邊的高度時(shí)，右邊的位置往左移動(dòng)所產(chǎn)生的面積將永遠(yuǎn)小于移動(dòng)之前的面積诫龙；同理析显，當(dāng)容器右邊的高度小于左邊的高度時(shí)，右邊的位置不動(dòng)签赃，左邊的位置往右移動(dòng)所產(chǎn)生的面積將永遠(yuǎn)小于移動(dòng)之前的面積谷异。只要理解這一點(diǎn)，就理解了這道題姊舵。
15. 3Sum (68%)
答案改編自高分java答案
var threeSum = function(nums) {
nums.sort(function(a,b){
return a-b;
});
//將算法從小到大排序
var result=new Array();
for(var i=0;i<nums.length-2;i++){ //1
if(i==0||(i>0&&nums[i]!=nums[i-1])){
var left=i+1; //2
var right=nums.length-1;
var sum=0-nums[i];
while(left<right){
if(nums[left]+nums[right]==sum){
result.push([nums[i],nums[left],nums[right]]);
while(left<right&&nums[left]==nums[left+1]) { //3
left++;
}
while(left<right&&nums[right]==nums[right-1]){ //4
right--;
}
left++;
right--; //5
}else if(nums[left]+nums[right]<sum){
left++; //6
}else{
right--; //7
}
}
}
}
return result;
}
首先記住數(shù)組是排了序的Ｎ铩寓落！
- 因?yàn)閚ums[i]是三個(gè)數(shù)中最左邊也是最小的數(shù)括丁，所以最多只取到倒數(shù)第三位.
- left和right分別代表除了i以外另外兩個(gè)數(shù)的位置，nums[left]<nums[right].
- 如果left右邊的第一個(gè)數(shù)和現(xiàn)在的數(shù)相等伶选，則直接往右跳過史飞。
- 與上同理
- 現(xiàn)在left和right的位置已經(jīng)滿足
nums[left]+nums[right]=sum的情況，在接下來移動(dòng)后獲得的數(shù)和現(xiàn)在不同的情況下仰税，left往右跳一個(gè)位置或者right往左跳一個(gè)位置后nums[left]+nums[right]必定不可能依舊等于sum构资，因?yàn)閘eft右邊的數(shù)必定更大，而right左邊的數(shù)必定比現(xiàn)在更小.所以,要left和right一起同時(shí)移動(dòng)來尋找下一個(gè)可能的結(jié)果. - nums[left]+nums[right]<sum 等價(jià)于 nums[left]+nums[right]+nums[i]<0 陨簇，i不變的情況下吐绵，需要將left往右移來尋找更大的nums[left],這樣才可能找到一個(gè)數(shù)使nums[left]+nums[right]+nums[i]=0
- 與上同理
16. 3Sum Closest (90%)
var threeSumClosest = function(nums, target) {
nums.sort(function(a,b){
return a-b;
})
var result;
var minDiff=10000;
for(var i=0;i<nums.length-2;i++){
var left=i+1;
var right=nums.length-1;
while(left<right){
var sum=nums[i]+nums[left]+nums[right];
if(Math.abs(target-sum)<minDiff){
result=sum;
minDiff=Math.abs(target-sum);
if(minDiff==0){
return result;
}
}
target<sum? right--:left++;
}
}
return result;
};
這道題和上一題有異曲同工之妙，最關(guān)鍵的思路幾乎是一模一樣的河绽，都是先確定一個(gè)數(shù)己单，然后再按照2sum的方法來探索剩下兩個(gè)數(shù)“沂危可以用這道題來檢測一下自己對上一題的思路是否真正理解纹笼。如果對于這道題還是有不明白的地方可以留言。
18. 4Sum (63%)
var fourSum = function(nums, target) {
nums.sort(function(a,b){
return a-b;
})
var result=new Array();
for(var i=0;i<nums.length-3;i++){
if(i>0&&nums[i]==nums[i-1]) continue;
for(var j=i+1;j<nums.length-2;j++){
if(j>i+1&&nums[j]==nums[j-1]) continue;
var left=j+1;
var right=nums.length-1;
var sum=target-nums[i]-nums[j];
while(left<right){
if(nums[left]+nums[right]==sum){
result.push([nums[i],nums[j],nums[left],nums[right]]);
while(left<right&&nums[left]==nums[left+1]) {
left++;
}
while(left<right&&nums[right]==nums[right-1]){
right--;
}
left++;
right--;
}else if(nums[left]+nums[right]<sum){
left++;
}else{
right--;
}
}
}
}
return result;
};
這道題的解法也是跟隨了3sum的解法苟跪，建議上面3題一起看廷痘。
26. Remove Duplicates from Sorted Array(33%）
var removeDuplicates = function(nums) {
for(var i=0;i<nums.length;i++){
if(nums[i]==nums[i+1]){
nums.splice(i,1);
i--;
}
}
};
27. Remove Element (87%)
var removeElement = function(nums, target) {
for(var i=0;i<nums.length;i++){
if(nums[i]==target){
nums[i]=nums[0];
nums.shift();
i--;
}
}
};
這里我沒用splice蔓涧，因?yàn)樾屎艿汀＿@里當(dāng)發(fā)現(xiàn)有一個(gè)數(shù)字和target相同時(shí),直接把第一個(gè)數(shù)字的值覆蓋這個(gè)與target相同的值笋额，然后將第一個(gè)數(shù)字刪掉元暴。
34. Search for a Range (61%)
var searchRange = function(nums, target) {
var left=0;
var right=nums.length-1;
var i=-1;
var j=-1;
while(left<=right&&(i==-1||j==-1)){
nums[left]==target?i=left:left++;
if(i!=-1){
j=i+1;
while(nums[j]==target){
j++;
}
}
}
return j==-1?[i,j]:[i,j-1];
};
因?yàn)橐呀?jīng)排了序，找到左邊那個(gè)以后就直接從左邊的位置往后找就能找到右邊的target的位置了鳞陨。理論上用二叉樹做更快昨寞，但不知道為什么，用二叉樹試了幾次都超時(shí)了厦滤，如果有網(wǎng)友能有js的二叉樹解法援岩，歡迎留言。
35. Search Insert Position (13%)
var searchInsert = function(nums, target) {
var left = 0;
var right = nums.length - 1;
while (left <= right) {
mid = Math.round((left + right) / 2);
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
還是和上一題一樣掏导，雖然使用了二叉樹享怀，但效率似乎不高，不知道問題出在哪趟咆，做法和高票答案一模一樣添瓷。
