Peng Du pdu
pdu
/ leetcode_set_matrix_zeros.cpp
Created
January 27, 2013 06:51
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Follow up:
Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution? http://leetcode.com/onlineju…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| void setZeroes(vector<vector<int> > &matrix) { | |
| int n = matrix.size(); | |
| int m = matrix[0].size(); | |
| int firstrow = 0; | |
| int firstcol = 0; | |
| for (int i = 0; i < n; ++i) | |
| for (int j = 0; j < m; ++j) | |
| if (matrix[i][j] == 0) { |
pdu
/ leetcode_edit_distance.cpp
Created
January 27, 2013 07:05
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character
b) Delete a character
c) Replace a character http://leetcode.com/onlinejudge#question_72
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #define MAXN 500 | |
| int f[MAXN][MAXN]; | |
| int dp(int f[MAXN][MAXN], string& word1, string& word2, int n, int m, int k, int t) { | |
| if (k < 0) | |
| return t + 1; | |
| if (t < 0) | |
| return k + 1; | |
| if (f[k][t] != -1) |
pdu
/ leetcode_simplify_path.cpp
Created
January 28, 2013 13:44
Given an absolute path for a file (Unix-style), simplify it. For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c" http://leetcode.com/onlinejudge#question_71
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| void update(vector<string>& s, const string& t) { | |
| if (t == ".") | |
| ; | |
| else if (t == "..") { | |
| if (!s.empty()) | |
| s.pop_back(); | |
| } | |
| else | |
| s.push_back(t); | |
| } |
pdu
/ leetcode_climbing_stairs.cpp
Created
January 28, 2013 13:48
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? http://leetcode.com/onlinejudge#question_70
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int climbStairs(int n) { | |
| int f[3]; | |
| memset(f, 0, sizeof(f)); | |
| f[0] = 1; | |
| for (int i = 1; i <= n; ++i) { | |
| f[i % 3] = f[(i + 1) % 3] + f[(i + 2) % 3]; | |
| } | |
| return f[n % 3]; |
pdu
/ leetcode_sqrt_x.cpp
Created
January 28, 2013 13:53
Implement int sqrt(int x). Compute and return the square root of x. http://leetcode.com/onlinejudge#question_69
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| int sqrt(int x) { | |
| if (x <= 0) | |
| return 0; | |
| int ret = 1; | |
| int left = 1, right = x; | |
| while (left <= right) { | |
| int mid = (left + right) >> 1; | |
| if (mid <= x / mid) { |
pdu
/ leetcode_text_justification.cpp
Created
January 28, 2013 14:29
Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters. Extra spaces between w…
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<string> fullJustify(vector<string> &words, int L) { | |
| vector<string> ret; | |
| int n = words.size(); | |
| int pos = 0; | |
| while (pos < n) { | |
| int len = words[pos].length(); | |
| int next = -1; | |
| for (int i = pos + 1; i < n; ++i) { |
pdu
/ leetcode_plus_one.cpp
Created
January 28, 2013 14:42
Given a number represented as an array of digits, plus one to the number. http://leetcode.com/onlinejudge#question_66
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| vector<int> plusOne(vector<int> &digits) { | |
| int all9 = 1; | |
| for (int i = 0; i < digits.size(); ++i) | |
| if (digits[i] != 9) { | |
| all9 = 0; | |
| break; | |
| } | |
| int len = digits.size() + all9; |
pdu
/ leetcode_valid_number.cpp
Created
February 2, 2013 03:07
Validate if a given string is numeric. Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. http://leetcode.com/onlinejudge#question_65
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| bool isInt(const char* s, int len) { | |
| if (len == 0) | |
| return false; | |
| int st = 0; | |
| if (s[0] == '+' || s[0] == '-') | |
| st = 1; | |
| if (st == len) | |
| return false; |
pdu
/ leetcode_add_binary.cpp
Created
February 2, 2013 15:05
Given two binary strings, return their sum (also a binary string). For example,
a = "11"
b = "1"
Return "100". http://leetcode.com/onlinejudge#question_67
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| string addBinary(string a, string b) { | |
| string ret; | |
| int lena = a.length(); | |
| int lenb = b.length(); | |
| int t = 0; | |
| int i = lena - 1; | |
| int j = lenb - 1; | |
| while (i >= 0 || j >= 0) { |
pdu
/ leetcode_merge_two_sorted_list.cpp
Last active
December 13, 2015 19:08
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists. http://leetcode.com/onlinejudge#question_21
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Definition for singly-linked list. | |
| * struct ListNode { | |
| * int val; | |
| * ListNode *next; | |
| * ListNode(int x) : val(x), next(NULL) {} | |
| * }; | |
| */ | |
| class Solution { | |
| public: |