2. Add Two Numbers
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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int sum = ;
ListNode a();
ListNode* NODE = &a;
while(l1 || l2 || sum){
if(l1){
sum += l1->val;
l1 = l1->next;
}
if(l2){
sum += l2->val;
l2 = l2->next;
}
NODE->next = new ListNode(sum % );
NODE = NODE->next;
sum /= ;
}
return a.next;
}
};
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb"
, the answer is "abc"
, which the length is 3.
Given "bbbbb"
, the answer is "b"
, with the length of 1.
Given "pwwkew"
, the answer is "wke"
, with the length of 3. Note that the answer must be a substring, "pwke"
is a subsequence and not a substring.
c++:
暴力O(N2):Your runtime beats 24.22% of cpp submissions.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int repeat[], max = -, temp = ;
int len = s.size();
if(len == ) return ;
for(int i = ; i < len; i++){
temp = ;
for(int j = ; j < ; j++) repeat[j] = ;
for(int k = i; k < len; k++){
int l = s[k] - ' ';
//cout<< " l " << l << endl;
if(repeat[l] >= ) break;
if(repeat[l] == ) {temp++;repeat[l]++;}
}
//cout<< temp <<endl;
if(temp >= max) max = temp;
}
return max;
}
};
O(n):Your runtime beats 87.46% of cpp submissions.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int nmap[];
memset(nmap, -, sizeof(nmap));
int maxLength = , lastRepeatPosition = -, len = s.size();
for (int curPosition = ; curPosition != len; curPosition++) {
int position = nmap[s[curPosition]];
if (position > lastRepeatPosition)
lastRepeatPosition = position;
nmap[s[curPosition]] = curPosition;
maxLength = max(maxLength, curPosition - lastRepeatPosition);
}
return maxLength;
}
};
129. Sum Root to Leaf Numbers
- Total Accepted: 93320
- Total Submissions: 269426
- Difficulty: Medium
- Contributors: Admin
Given a binary tree containing digits from 0-9
only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3
which represents the number 123
.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2
represents the number 12
.
The root-to-leaf path 1->3
represents the number 13
.
Return the sum = 12 + 13 = 25
.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int sumNumbers(TreeNode* root) {
int sum_current = , total = ;
if(!root) return ;
return DFS(root, sum_current, total);
} int DFS(TreeNode* current, int sum, int total){
if(current == nullptr)
return ;
if(current != nullptr)
sum = sum * + current->val;
if(current->left == nullptr && current->right == nullptr){
total += sum;
return total;
}
return DFS(current->left, sum, total) + DFS(current->right, sum, total);
}
};