Leetcode 題目
本文將不斷更新，主要內(nèi)容為解決Leetcode中的算法問題，有比較難的題目可能會單獨成文檔，所有代碼都將用Javascript編寫并且Accepted.標(biāo)題后面的百分號代表用JS寫的代碼中該答案比多少比例的答案快。
對于一些解法不高效的題，歡迎留言寫下你的答案。
最后編輯時間： 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ù)組起到了記錄其中一個數(shù)的位置和值的作用，每當(dāng)i探索新的數(shù)，如果該數(shù)無法和arr中的數(shù)相加成target，則將該數(shù)放進arr，直到找到能和arr中數(shù)組相加等于target的數(shù)。巧妙之處在于每次將i找到的數(shù)放進arr時，該數(shù)的值在arr中充當(dāng)了位置，該數(shù)的位置在arr中充當(dāng)了值，這種方法使用兩個arr達成了在數(shù)組中尋找是否存在一個數(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;
};
個人覺得這個答案很不錯了，但我不知道為什么還是只超過了46%。還可以改進的地方是這塊：
j=typeof sub[s.charAt(i)] != 'undefined'?Math.max(j,sub[s.charAt(i)]+1):j ;
如果能把這行代碼直接表示成一個j=多少的表達式，應(yīng)該速度能更快一些。但我不知道如何直接處理這里的'undefined'，能夠達到以下效果：當(dāng)在sub數(shù)組中找不到s.charAt(i)的值時，能直接用 -1 來取代返回的 'undefined'，如果能將返回值直接轉(zhuǎn)成-1 ,那么j就會直接取j的值，我們也不用先判斷再賦值了。
29/3/2017更新：重新安排一下做題順序，現(xiàn)在開始會分類做，而不是原計劃的按照題號做，先把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;
};
//在一個數(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ù)雜是因為加入了很多判斷，需要判斷很多特殊情況，比如數(shù)組為空的時候，實際上思路是很清晰的。因為要獲得兩個數(shù)組合并以后的中位數(shù)，無論合并以后排序如何，中位數(shù)的位置是不變的。當(dāng)兩個數(shù)組長度相加為奇數(shù)時，中位數(shù)永遠位于(m+n+1)/2，兩個數(shù)組長度相加為偶數(shù)時，中位數(shù)永遠是位于(m+n)/2和((m+n)/2)+1兩者的平均數(shù)。所以每次都比較兩個數(shù)組首位的大小，把小的去掉，然后再繼續(xù)比較，一直循環(huán)到中位數(shù)所在的位置，此時把中位數(shù)取出來即可。代碼寫的有點雜亂，有時間會把寫法改一下，思路本身的速度已經(jīng)不錯了。
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;
};
這個解法思路比較清晰，在數(shù)組的首尾分別安插一個指針然后往中間移直到遇到為止。移動過程中只需要明確一點:參照木桶原理，當(dāng)容器左邊的高度小于右邊的高度時，右邊的位置往左移動所產(chǎn)生的面積將永遠小于移動之前的面積；同理，當(dāng)容器右邊的高度小于左邊的高度時，右邊的位置不動，左邊的位置往右移動所產(chǎ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ù)組是排了序的??！
- 因為nums[i]是三個數(shù)中最左邊也是最小的數(shù)，所以最多只取到倒數(shù)第三位.
- left和right分別代表除了i以外另外兩個數(shù)的位置，nums[left]<nums[right].
- 如果left右邊的第一個數(shù)和現(xiàn)在的數(shù)相等，則直接往右跳過。
- 與上同理
- 現(xiàn)在left和right的位置已經(jīng)滿足
nums[left]+nums[right]=sum的情況，在接下來移動后獲得的數(shù)和現(xiàn)在不同的情況下，left往右跳一個位置或者right往左跳一個位置后nums[left]+nums[right]必定不可能依舊等于sum，因為left右邊的數(shù)必定更大，而right左邊的數(shù)必定比現(xiàn)在更小.所以,要left和right一起同時移動來尋找下一個可能的結(jié)果. - nums[left]+nums[right]<sum 等價于 nums[left]+nums[right]+nums[i]<0 ，i不變的情況下，需要將left往右移來尋找更大的nums[left],這樣才可能找到一個數(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)鍵的思路幾乎是一模一樣的，都是先確定一個數(shù)，然后再按照2sum的方法來探索剩下兩個數(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，因為效率很低。這里當(dāng)發(fā)現(xiàn)有一個數(shù)字和target相同時,直接把第一個數(shù)字的值覆蓋這個與target相同的值，然后將第一個數(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];
};
因為已經(jīng)排了序，找到左邊那個以后就直接從左邊的位置往后找就能找到右邊的target的位置了。理論上用二叉樹做更快，但不知道為什么，用二叉樹試了幾次都超時了，如果有網(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;
還是和上一題一樣，雖然使用了二叉樹，但效率似乎不高，不知道問題出在哪，做法和高票答案一模一樣。
