8000 update · wells70/leetcode-javascript@9fa7679 · GitHub
[go: up one dir, main page]
Skip to content

Commit 9fa7679

Browse files
author
Chihung Yu
committed
update
1 parent e406139 commit 9fa7679

File tree

3 files changed

+165
-0
lines changed

3 files changed

+165
-0
lines changed

‎[0001] Two Sum.js

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
// Given an array of integers, return indices of the two numbers such that they add up to a specific target.
2+
3+
// You may assume that each input would have exactly one solution.
4+
5+
// Example:
6+
// Given nums = [2, 7, 11, 15], target = 9,
7+
8+
// Because nums[0] + nums[1] = 2 + 7 = 9,
9+
// return [0, 1].
10+
// UPDATE (2016/2/13):
11+
// The return format had been changed to zero-based indices. Please read the above updated description carefully.
12+
13+
// Hide Company Tags LinkedIn Uber Airbnb Facebook Amazon Microsoft Apple Yahoo Dropbox Bloomberg Yelp Adobe
14+
// Hide Tags Array Hash Table
15+
// Hide Similar Problems (M) 3Sum (M) 4Sum (M) Two Sum II - Input array is sorted (E) Two Sum III - Data structure design
16+
17+
18+
19+
/**
20+
* @param {number[]} nums
21+
* @param {number} target
22+
* @return {number[]}
23+
*/
24+
var twoSum = function(nums, target) {
25+
var hash = {};
26+
27+
for(var i = 0; i < nums.length; i++) {
28+
var num = nums[i];
29+
if(hash[num] !== undefined) {
30+
return [hash[num], i]
31+
} else {
32+
hash[target - num] = i;
33+
}
34+
}
35+
36+
return [];
37+
};

‎[0002] Add Two Numbers.js

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
// 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.
2+
3+
// Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
4+
// Output: 7 -> 0 -> 8
5+
6+
// Amazon Microsoft Bloomberg Airbnb Adobe
7+
8+
/**
9+
* Definition for singly-linked list.
10+
* function ListNode(val) {
11+
* this.val = val;
12+
* this.next = null;
13+
* }
14+
*/
15+
/**
16+
* @param {ListNode} l1
17+
* @param {ListNode} l2
18+
* @return {ListNode}
19+
*/
20+
21+
22+
23+
// value reverse helps to asslign the first digit or both linklist
24+
var addTwoNumbers = function(l1, l2) {
25+
const answer = new ListNode(0);
26+
var node = answer;
27+
var carry = 0;
28+
while(l1 !== null || l2 !== null || carry !== 0) {
29+
var val = 0;
30+
if (carry !== 0) {
31+
val += carry;
32+
}
33+
carry = 0;
34+
if (l1 !== null) {
35+
val += l1.val;
36+
}
37+
if (l2 !== null) {
38+
val += l2.val;
39+
}
40+
if (val > 9) {
41+
val -= 10;
42+
carry = 1;
43+
}
44+
node.next = new ListNode(val);
45+
node = node.next;
46+
if (l1 !== null) {
47+
l1 = l1.next;
48+
}
49+
if (l2 !== null) {
50+
l2 = l2.next;
51+
}
52+
}
53+
54+
return answer.next;
55+
};

‎[0010] Regular Expresion Matching.js

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
// https://www.youtube.com/watch?v=l3hda49XcDE#t=211.113333
2+
3+
// Implement regular expression matching with support for '.' and '*'.
4+
5+
// '.' Matches any single character.
6+
// '*' Matches zero or more of the preceding element.
7+
8+
// The matching should cover the entire input string (not partial).
9+
10+
// The function prototype should be:
11+
// bool isMatch(const char *s, const char *p)
12+
13+
// Some examples:
14+
// isMatch("aa","a") → false
15+
// isMatch("aa","aa") → true
16+
// isMatch("aaa","aa") → false
17+
// isMatch("aa", "a*") → true
18+
// isMatch("aa", ".*") → true
19+
// isMatch("ab", ".*") → true
20+
// isMatch("aab", "c*a*b") → true
21+
22+
/**
23+
* @param {string} s
24+
* @param {string} p
25+
* @return {boolean}
26+
*/
27+
var isMatch = function(s, p) {
28+
var sLen = s.length;
29+
var pLen = p.length;
30+
var dp = [];
31+
32+
for(var i = 0; i <= sLen; i++) {
33+
var tmp = [];
34+
35+
for(var j = 0; j <= pLen; j++) {
36+
tmp.push(false);
37+
}
38+
39+
dp.push(tmp);
40+
}
41+
42+
dp[0][0] = true;
43+
44+
for(i = 0; i <= sLen; i++) {
45+
for(j = 0; j <= pLen; j++) {
46+
if(p[j - 1] !== '.' && p[j - 1] !== '*') {
47+
if(i > 0 && p[j - 1] === s[i - 1] && dp[i - 1][j - 1]) {
48+
dp[i][j] = true;
49+
}
50+
} else if(p[j - 1] === '.') {
51+
if(i > 0 && dp[i - 1][j - 1]) {
52+
dp[i][j] = true;
53+
}
54+
} else if(j > 1) { // '*' cannot be the first element
55+
if(dp[i][j - 2]) { // 0 occurance
56+
dp[i][j] = true;
57+
} else if(i > 0 && (p[j - 2] === s[i - 1] || p[j - 2] === '.') && dp[i - 1][j]) {
58+
59+
// example
60+
// xa and xa*
61+
// s[i-1] === a
62+
// p[j-2] === a
63+
// a === a
64+
// so we can now compare x, xa*
65+
// and x here is dp[i-1][j]
66+
dp[i][j] = true;
67+
}
68+
}
69+
}
70+
}
71+
72+
return dp[sLen][pLen];
73+
};

0 commit comments

Comments
 (0)
0