1.22 problems solved.

lintcoder · lintcoder · commit f351cd2e6771 · 2017-03-04T19:38:18.000+08:00
diff --git a/100.cpp b/100.cpp
@@ -0,0 +1,12 @@
+bool isSameTree(TreeNode* p, TreeNode* q) {
+    if (p == NULL && q == NULL)
+        return true;
+    else if (p == NULL && q != NULL)
+        return false;
+    else if (p != NULL && q == NULL)
+        return false;
+    else
+    {
+        return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
+    }
+}
diff --git a/104.cpp b/104.cpp
@@ -0,0 +1,8 @@
+int maxDepth(TreeNode* root) {
+    if (root == 0)
+        return 0;
+    int leftdepth = maxDepth(root->left);
+    int rightdepth = maxDepth(root->right);
+
+    return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
+}
diff --git a/125.cpp b/125.cpp
@@ -0,0 +1,23 @@
+bool isPalindrome(string s) {
+    int len = s.size();
+    int i = 0, j = len - 1;
+    while (i < j)
+    {
+        while (i < j && !isalnum(s[i]))
+            ++i;
+        if (i == j)
+            return true;
+        while (i < j && !isalnum(s[j]))
+            --j;
+        if (i == j)
+            return true;
+        if (!(s[i] == s[j] || tolower(s[i]) == tolower(s[j])))
+            return false;
+        else
+        {
+            ++i;
+            --j;
+        }
+    }
+    return true;
+}
diff --git a/136.cpp b/136.cpp
@@ -0,0 +1,7 @@
+int singleNumber(vector<int>& nums) {
+    int res = nums[0];
+    int len = nums.size();
+    for (int i = 1; i < len; ++i)
+        res ^= nums[i];
+    return res;
+}
diff --git a/171.cpp b/171.cpp
@@ -0,0 +1,7 @@
+int titleToNumber(string s) {
+    int len = s.size();
+    int sum = 0;
+    for (int i = 0; i < len; ++i)
+        sum = sum * 26 + s[i] - 'A' + 1;
+    return sum;
+}
diff --git a/226.cpp b/226.cpp
@@ -0,0 +1,8 @@
+TreeNode* invertTree(TreeNode* root) {
+    if (root == NULL)
+        return NULL;
+    TreeNode* node = invertTree(root->left);
+    root->left = invertTree(root->right);
+    root->right = node;
+    return root;
+}
diff --git a/237.cpp b/237.cpp
@@ -0,0 +1,13 @@
+void deleteNode(ListNode* node) {
+    ListNode* p = node;
+    ListNode* q = node->next;
+    while (q->next != NULL)
+    {
+        p->val = q->val;
+        p = q;
+        q = q->next;
+    }
+    p->val = q->val;
+    delete q;
+    p->next = NULL;
+}
diff --git a/242.cpp b/242.cpp
@@ -0,0 +1,14 @@
+bool isAnagram(string s, string t) {
+    int alpha1[26] = {0};
+    int alpha2[26] = {0};
+    int len1 = s.size();
+    int len2 = t.size();
+    for (int i = 0; i < len1; ++i)
+        alpha1[s[i] - 'a']++;
+    for (int i = 0; i < len2; ++i)
+        alpha2[t[i] - 'a']++;
+    for (int i = 0; i < 26; ++i)
+        if(alpha1[i] != alpha2[i])
+            return false;
+    return true;
+}
diff --git a/258.cpp b/258.cpp
@@ -0,0 +1,5 @@
+int addDigits(int num) {
+    if (num == 0)
+        return 0;
+    return num % 9 == 0 ? 9 : num % 9;
+}
diff --git a/283.cpp b/283.cpp
@@ -0,0 +1,17 @@
+void moveZeroes(vector<int>& nums) {
+    int len = nums.size();
+    int i = 0, j = 0;
+    while (i < len && j < len)
+    {
+        while (i < len && nums[i] != 0 )
+            i++;
+        j = i + 1;
+        while (j < len && nums[j] == 0)
+            j++;
+        if (j >= len)
+            break;
+        swap(nums[i], nums[j]);
+        i++;
+        j++;
+    }
+}
diff --git a/292.cpp b/292.cpp
@@ -0,0 +1,3 @@
+bool canWinNim(int n) {
+    return n % 4 != 0;
+}
diff --git a/344.cpp b/344.cpp
@@ -0,0 +1,4 @@
+string reverseString(string s) {
+    reverse(s.begin(), s.end());
+    return s;
+}
diff --git a/349.cpp b/349.cpp
@@ -0,0 +1,21 @@
+vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
+    map<int, int> mp;
+    vector<int> res;
+    int len1 = nums1.size();
+    for (int i = 0; i < len1; ++i)
+        mp[nums1[i]]++;
+    sort(nums2.begin(), nums2.end());
+    int len2 = nums2.size();
+    int j = 0;
+    while (j < len2)
+    {
+        int val = nums2[j];
+        if (mp.find(val) != mp.end())
+        {
+            res.push_back(val);
+        }
+        while (j < len2 && nums2[j] == val)
+            ++j;
+    }
+    return res;
+}
diff --git a/371.cpp b/371.cpp
@@ -0,0 +1,9 @@
+int getSum(int a, int b) {
+    while (b != 0)
+    {
+        int tmp = a ^ b;
+        b = (a & b) << 1;
+        a = tmp;
+    }
+    return a;
+}
diff --git a/383.cpp b/383.cpp
@@ -0,0 +1,17 @@
+bool canConstruct(string ransomNote, string magazine) {
+    int alpha1[26] = {0};
+    int alpha2[26] = {0};
+    int len1 = ransomNote.size();
+    int len2 = magazine.size();
+    if (len1 > len2)
+        return false;
+    for (int i = 0; i < len1; ++i)
+        alpha1[ransomNote[i] - 'a']++;
+    for (int i = 0; i < len2; ++i)
+        alpha2[magazine[i] - 'a']++;
+    for (int i = 0; i < 26; ++i)
+        if (alpha1[i] > alpha2[i])
+            return false;
+
+    return true;
+}
diff --git a/387.cpp b/387.cpp
@@ -0,0 +1,10 @@
+int firstUniqChar(string s) {
+    int alpha[26] = {0};
+    int len = s.size();
+    for (int i = 0; i < len; ++i)
+        alpha[s[i] - 'a']++;
+    for (int i = 0; i < len; ++i)
+        if (alpha[s[i] - 'a'] == 1)
+            return i;
+    return -1;
+}
diff --git a/389.cpp b/389.cpp
@@ -0,0 +1,16 @@
+char findTheDifference(string s, string t) {
+    int alpha1[26] = {0};
+    int alpha2[26] = {0};
+
+    int len1 = s.size();
+    int len2 = t.size();
+    int i = 0;
+    for (i = 0; i < len1; ++i)
+        alpha1[s[i] - 'a']++;
+    for (i = 0; i < len2; ++i)
+        alpha2[t[i] - 'a']++;
+    for (i = 0; i < 26; ++i)
+        if (alpha1[i] < alpha2[i])
+            break;
+    return i + 'a';
+}
diff --git a/404.cpp b/404.cpp
@@ -0,0 +1,15 @@
+enum Side {LEFT, RIGHT};
+int sumOfLeftLeaves(TreeNode* root) {
+    if (root == NULL)
+        return 0;
+    return dosumOfLeftLeaves(root->left, LEFT) + dosumOfLeftLeaves(root->right, RIGHT);
+}
+int dosumOfLeftLeaves(TreeNode* node, enum Side side)
+{
+    if (node == NULL)
+        return 0;
+    else if (node->left == NULL && node->right == NULL)
+        return side == LEFT ? node->val : 0;
+    else
+        return dosumOfLeftLeaves(node->left, LEFT) + dosumOfLeftLeaves(node->right, RIGHT);
+}
diff --git a/412.cpp b/412.cpp
@@ -0,0 +1,27 @@
+vector<string> fizzBuzz(int n) {
+    vector<string> res;
+    for (int i = 1; i <= n; ++i)
+    {
+        if (i % 3 == 0 && i % 5 != 0)
+            res.push_back("Fizz");
+        else if (i % 3 != 0 && i % 5 == 0)
+            res.push_back("Buzz");
+        else if (i % 15 == 0)
+            res.push_back("FizzBuzz");
+        else
+            res.push_back(int2str(i));
+    }
+    return res;
+}
+
+string int2str(int n)
+{
+    string s;
+    while (n != 0)
+    {
+        s.push_back(n % 10 + '0');
+        n /= 10;
+    }
+    reverse(s.begin(), s.end());
+    return s;
+}
diff --git a/455.cpp b/455.cpp
@@ -0,0 +1,22 @@
+int findContentChildren(vector<int>& g, vector<int>& s) {
+    sort(g.begin(), g.end());
+    sort(s.begin(), s.end());
+
+    int len1 = g.size();
+    int len2 = s.size();
+
+    int i = 0, j = 0;
+    int total = 0;
+    while (i < len1)
+    {
+        while (j < len2 && s[j] < g[i])
+            ++j;
+        if (j == len2)
+            break;
+        ++total;
+        ++j;
+        ++i;
+    }
+
+    return total;
+}
diff --git a/463.cpp b/463.cpp
@@ -0,0 +1,26 @@
+int islandPerimeter(vector<vector<int>>& grid) {
+    int row = grid.size();
+    if (row == 0)
+        return 0;
+    int col = grid[0].size();
+
+    int sum = 0, cnt = 0;
+    for (int i = 0; i < row; ++i)
+    {
+        for (int j = 0; j < col; ++j)
+        {
+            if (grid[i][j] == 1)
+            {
+                ++sum;
+                if (j == 0 && i != row - 1)
+                    cnt += grid[i][j] == 1 && grid[i + 1][j] == 1;
+                else if (j != 0 && i == row - 1)
+                    cnt += grid[i][j] == 1 && grid[i][j - 1] == 1;
+                else if (j != 0 && i != row - 1)
+                    cnt += (grid[i][j] == 1 && grid[i][j - 1] == 1) + (grid[i][j] == 1 && grid[i + 1][j]);
+            }
+        }
+    }
+
+    return sum * 4 - cnt * 2;
+}
diff --git a/485.cpp b/485.cpp
@@ -0,0 +1,27 @@
+int findMaxConsecutiveOnes(vector<int>& nums) {
+    int len = nums.size();
+    int count = 0, subcount = 0;
+    int i = 0;
+    while (i < len)
+    {
+        while (i < len && nums[i] == 0)
+            ++i;
+        if (i == len)
+        {
+            if (subcount > count)
+                count = subcount;
+            break;
+        }
+        while (i < len && nums[i] == 1)
+        {
+            ++i;
+            ++subcount;
+        }
+        if (subcount > count)
+        {
+            count = subcount;
+        }
+        subcount = 0;
+    }
+    return count;
+}
