Leetcode 刷題計劃 - myprogram－IT工程師數位筆記本

文章出處

Two Sum 21.4% Medium

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

給定一個數組，找到數組中的兩個值，使其和為n，假定數組中一定存在這樣一組解。

常規的思路是兩次循環，如果了解哈希表的話，我們可以用哈希表來記錄遍歷過的節點，找到當前節點和(n-i)節點所在的位置即可。這樣可以在O(n)的時間復雜度里面解決這個問題。

Add Two Numbers 22.3% Medium

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

大數字的加法，把兩個數字都表示成鏈表的形式。

Longest Substring Without Repeating Characters 21.6% Medium

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

由于是字符串，這樣的話遞歸或者多次循環都會導致超時。技巧還是用hash的方法來記錄遍歷過的字符，另外一個就是如何減少遍歷個數。

Median of Two Sorted Arrays 18.2% Hard

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

從兩個已經排序的數組a[m],b[n]中找到中間的數，如果m+n為偶數，則返回中間兩個數的平均值，要求時間復雜度log(m+n)

如果寫一個時間復雜度是o(m+n)/2 的方法，思路上就簡單了，只需要實現即可。既然要求時間復雜度是log(m+n)，意味著需要二分法。這道題可以轉換成求第k大元素所在的位置，假設第k大元素在a[m]中的index為x，那么b[n]中的索引為k-x,我們通過二分法找x所在的位置，滿足 a[x],b[k-x]中較大的一個元素同時小于a[x+1],b[k-x+1]即可。

Longest Palindromic Substring 22.6% Medium

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

回文可以理解成對稱子串，如aaaa,abc,abba,abcba都是回文，由于此題中假設了前提字符串長度不超過1000，那就意味著我們可以使用遞歸，不會出現堆棧溢出的情況。每一個回文都一定有一個中軸，因此找最長回文就轉化為找中軸的問題，如果回文長度為奇數，中軸為1個元素，回文長度為偶數中軸為2個元素。尋找中軸需要一次循環，每一個中軸尋找對稱字符串大概小于2n，因此時間復雜度為 n^2.

有人說更牛逼的解法是后綴樹，目前還沒有找到相關的材料。

上述問題的參考代碼：

https://github.com/cuicheng11165/myleetcode/tree/master/leetcode/leetcode

文章列表