1.Two Sums

• 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, and you may not use the same element twice.

Example:

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

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Code:

javascript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var len = nums.length;
    var ar = [];
    var tmp = 0;
    for(var i = 0;i<len;i++){
        tmp = target - nums[i];
        if(ar[tmp] != undefined){
            return [ar[tmp],i]
        }
        ar[nums[i]] = i;
    }
};

Solution:

• 基本思路：array中兩數(shù)相加挟秤，等于一個(gè)數(shù)送淆，那么可以用個(gè)數(shù)組來(lái)存儲(chǔ)已經(jīng)遍歷過(guò)的數(shù) index為值 key為下標(biāo)生百，target-nums[i]如果新數(shù)組存在這個(gè)值的index 說(shuō)明兩個(gè)數(shù)已經(jīng)找到即[nums[tmp],i]

2.3SUM

• Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

• Note: The solution set must not contain duplicate triplets.

Example:

Given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

• 基本思路: 遍歷所有數(shù)字诸衔，取其3求和，題目要求去重图呢，所以可以先排序?qū)rray按大小排好识虚，然后在循環(huán)的時(shí)候判斷上次的值與當(dāng)前的值是否相等伤溉，相等則 ++ 或 -- ，因?yàn)?重循環(huán)會(huì)超時(shí)（O幾不知道）束倍，故需要降低時(shí)間復(fù)雜度被丧，目前是的代碼是O(n^2)，將低復(fù)雜度的方法是二分法绪妹，第二層循環(huán)的時(shí)候甥桂，設(shè)置2個(gè)下標(biāo)，start和end 如果和大于0 end -- 反之 start ++ 邮旷。

Code:

JavaScript:
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    var res = [];
    
    var len = nums.length;
    
    nums = bubbleSort(nums);//冒泡黄选，排序具體用什么無(wú)所謂，自定義

    
    for(var i = 0;i<len-2;){
        var start = i+1;
        var end = len-1;
        var sum = 0-nums[i];
        while(start<end){
            if(nums[start] + nums[end] == sum){
                res.push([nums[i],nums[start],nums[end]]);
                start++;
                while(nums[start] == nums[start-1] && start<end) start++;
                end--;
                
                while(nums[end] == nums[end+1] && start<end) end--;
                
            }else if(nums[start] + nums[end] > sum){
                
                end--;
                while(nums[end] == nums[end+1] && start<end) end--;
            }else {
                start++;
                while(nums[start] == nums[start-1] && start<end) start++;
            }
        
    }
        i++;
        while(nums[i] == nums[i-1])i++; 
}
    return res;
};

3.Add Two Numbers

• You are given two non-empty linked lists representing two non-negative integers. 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.
• You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution:

• 基本思路: 其實(shí)用隊(duì)列比較好實(shí)現(xiàn)這個(gè)簡(jiǎn)單的加法婶肩，因求和遇十進(jìn)位办陷，題中數(shù)和必然小于 20 則可以用 sum /=10 來(lái)獲取進(jìn)位值，那么該進(jìn)位值可以作為下個(gè)求和的參與值律歼。需要注意的是在最后的和中可能會(huì)出現(xiàn) 首位和大于10的情況民镜，需要特殊處理，輸入的兩個(gè)ListNode 長(zhǎng)度可能會(huì)不一樣 所以需要考慮到险毁。解法在于用一個(gè)隊(duì)列存儲(chǔ)每個(gè)node的和并將下個(gè)next的node.val定義成該node的余數(shù)制圈，進(jìn)位值在每次 求和前 取得即可。

Code:

Java:
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode p = new ListNode(0);
        ListNode sen = p;//新p 輸出用
        int sum = 0;
        while(l1 != null || l2 != null){
            sum /=10;// 取和的十位
            if(l1 != null){
                sum +=l1.val;
                l1 = l1.next;
            }
             if(l2 != null){
                sum +=l2.val;
                l2 = l2.next;
            }
            p.next = new ListNode(sum%10);//余數(shù)放到下個(gè)node
            p = p.next;
        }
        if(sum-10 >= 0) p.next = new ListNode(1);
        return sen.next;//第一個(gè)node沒用
    }
}

4.Multiply Strings

• Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution:

• 基本思路: 不能用 int 字符長(zhǎng)度很大畔况，所以 只能是對(duì)應(yīng)位數(shù)相乘离唐，然后在對(duì)應(yīng)位置求和∥是裕可以將每一位結(jié)果存在數(shù)組中然后再最后合并亥鬓。 ps:還有一種方法，二維數(shù)組存儲(chǔ)數(shù)據(jù)域庇，將計(jì)算結(jié)果存在 [i+j,i+j+1]上嵌戈，角度比較刁鉆。

Code:

JavaScript:
/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    var len1 = num1.length;
    var len2 = num2.length;
    var res = [];
    var add = 0;
    var index = 0;
    for (var i = 0;i<len1;i++)
        for (var j = 0;j<len2;j++){
            add = num1[i] * num2[j];
            var ten = Math.floor(add / 10);//拾位
            var dig = add % 10;//個(gè)位
            index = len1 - i - 1 + len2 - j - 1;
            if(res[index] == undefined) res[index] = 0;
            res[index] += dig;
            var k = index;//判斷加進(jìn)位
            while(res[k]>=10){
                var tem = Math.floor(res[k] / 10);
                res[k] = res[k]%10;//取余 其實(shí)也可以減去10 個(gè)位數(shù)相加必然小于20
                res[k+1] = (res[k+1] == undefined) ? tem : tem + res[k+1];
                k++;
            }
            
            if(ten != 0 && res[index+1] == undefined){
                res[index+1] = ten;
            }else if(ten != 0 ){
                res[index+1] += ten;
                   
            }
            k = index + 1;//判斷加進(jìn)位
                while(res[k]>=10){
                var tem = Math.floor(res[k] / 10);
                res[k] = res[k]%10;
                res[k+1] = (res[k+1] == undefined) ? tem : tem + res[k+1];
                k++;
            }
            
        }
  
    res.reverse();//逆序
    res = res.join('');
    if(res == 0) res = '0';//判斷非 字符"00000"這類數(shù)
    return res;
};

5. Roman to Integer

• Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

• For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

• Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.
  X can be placed before L (50) and C (100) to make 40 and 90.
  C can be placed before D (500) and M (1000) to make 400 and 900.
  Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3
Example 2:

Input: "IV"
Output: 4
Example 3:

Input: "IX"
Output: 9
Example 4:

Input: "LVIII"
Output: 58
Explanation: C = 100, L = 50, XXX = 30 and III = 3.
Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution:

• 羅馬數(shù)字轉(zhuǎn)數(shù)字這個(gè)相對(duì)比較簡(jiǎn)單听皿，可以說(shuō)是一道找規(guī)律的題目熟呛。基本思路： 以"MCMXCIV"為例尉姨，第一個(gè)M表示1000 CM表示900 = M(1000) - C(100) = 900, XC表示90 = C(100) - X(10) = 90 IV 表示4 = V(5) - I(1) = 4 所以"MCMXCIV" = 1000(M) + 900(CM) + 90(XC) + 4(IV) = 1994,簡(jiǎn)單地理解就是 CM = M - C 庵朝，所以就可以按這個(gè)思路coding了

Code:

Python3 :

class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1};
        sum = 0
        ls = 0
        lens = len(s)
        if lens == 0:
            return 0
        for i in s:
            if roman[i] > ls:
               //ps : sum = sum - ls + roman[i] - ls 這里簡(jiǎn)化了
                sum = sum - 2 * ls + roman[i]
            else:
                sum = sum + roman[i]
            ls = roman[i]
        return sum