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中两数相加，等于一个数，那么可以用个数组来存储已经遍历过的数 index为值 key为下标，target-nums[i]如果新数组存在这个值的index 说明两个数已经找到即[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:
- 基本思路: 遍历所有数字，取其3求和，题目要求去重，所以可以先排序将array按大小排好，然后在循环的时候判断上次的值与当前的值是否相等，相等则 ++ 或 -- ，因为3重循环会超时（O几不知道），故需要降低时间复杂度，目前是的代码是O(n^2)，将低复杂度的方法是二分法，第二层循环的时候，设置2个下标，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);//冒泡，排序具体用什么无所谓，自定义
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:
- 基本思路: 其实用队列比较好实现这个简单的加法，因求和遇十进位，题中数和必然小于 20 则可以用
sum /=10来获取进位值，那么该进位值可以作为下个求和的参与值。需要注意的是在最后的和中可能会出现 首位和大于10的情况，需要特殊处理，输入的两个ListNode 长度可能会不一样 所以需要考虑到。解法在于用一个队列存储每个node的和并将下个next的node.val定义成该node的余数，进位值在每次 求和前 取得即可。
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);//余数放到下个node
p = p.next;
}
if(sum-10 >= 0) p.next = new ListNode(1);
return sen.next;//第一个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 字符长度很大，所以 只能是对应位数相乘，然后在对应位置求和。可以将每一位结果存在数组中然后再最后合并。 ps:还有一种方法，二维数组存储数据，将计算结果存在 [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;//个位
index = len1 - i - 1 + len2 - j - 1;
if(res[index] == undefined) res[index] = 0;
res[index] += dig;
var k = index;//判断加进位
while(res[k]>=10){
var tem = Math.floor(res[k] / 10);
res[k] = res[k]%10;//取余 其实也可以减去10 个位数相加必然小于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;//判断加进位
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"这类数
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:
- 罗马数字转数字这个相对比较简单，可以说是一道找规律的题目。基本思路： 以"MCMXCIV"为例，第一个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,简单地理解就是 CM = M - C ，所以就可以按这个思路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 这里简化了
sum = sum - 2 * ls + roman[i]
else:
sum = sum + roman[i]
ls = roman[i]
return sum
