Moves in squared strings (I)


题目链接:https://www.codewars.com/kata/moves-in-squared-strings-i/train/objc

#import <Foundation/Foundation.h>

NSString *vertMirror(NSString *strng) {
    NSMutableString *res = [[NSMutableString alloc] init];
    NSArray *stringArray = [strng componentsSeparatedByString:@"\n"];
    for (NSString *tmpStr in stringArray) {
        NSMutableString * reverseString = [NSMutableString string];
        for(int i = 0 ; i < tmpStr.length; i ++){
            //倒序读取字符并且存到可变数组数组中
            unichar c = [tmpStr characterAtIndex:tmpStr.length- i -1];
            [reverseString appendFormat:@"%c",c];
        }
        
        if ([tmpStr isEqualToString:[stringArray lastObject]]) {
            [res appendString:reverseString];
            break;
        }
        
        [reverseString appendString:@"\n"];
        [res appendString:reverseString];
    }
    
    return res;
}

NSString *horMirror(NSString *strng) {
    NSMutableString *res = [[NSMutableString alloc] init];;
    NSArray *stringAry = [strng componentsSeparatedByString:@"\n"];
    for (int i = stringAry.count-1; i>=0; i--) {
        [res appendString:stringAry[i]];
        if (i==0) {
            break;
        }
        [res appendString:@"\n"];
    }
    return res;
}

NSString *oper(NSString *(*f)(NSString *), NSString *s) {
    return f(s);
}
2017/12/23 posted in  codeWars

Sum of many ints

题目链接:https://www.codewars.com/kata/moves-in-squared-strings-i/train/objc

注意long long类型。

#import <Foundation/Foundation.h>

long long f(long long n, long long m) {
    long long sum = 0;
    long long q = n/m;
    long long p = n%m;
    sum+= (m*(m-1)/2)*q;
    sum+= (p+1)*p/2;
    return sum;
}
2017/12/23 posted in  codeWars

 Longest Univalue Path

/**
 * 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 dfs(TreeNode* node, int& lup) {
        int l = node->left ? dfs(node->left, lup) : 0;
        int r = node->right ? dfs(node->right, lup) : 0;
        int resl = node->left && node->left->val == node->val ? l + 1 : 0;
        int resr = node->right && node->right->val == node->val ? r + 1 : 0;
        lup = max(lup, resl + resr);
        return max(resl, resr);
    }

    int longestUnivaluePath(TreeNode* root) {
        int lup = 0;
        if (root) dfs(root, lup);
        return lup;
    }
};
2017/12/22 posted in  leetcode

Isomorphic Strings

一开始写的代码,超时版本,用的集合。

bool isIsomorphic(string s, string t) {
    unordered_map<char, set<int>> Smap;
    unordered_map<char, vector<int>> Tmap;
    for (int i = 0; i<s.size(); i++) {
        Smap[s[i]].insert(i);
        Tmap[t[i]].push_back(i);
    }
    if (Smap.size()!=Tmap.size()) {
        return 0;
    }else{
        for (int j = 0; j<s.size(); j++) {
            vector<int> a = Tmap[t[j]];
            set<int> b = Smap[s[j]];
            int len = b.size();
            for (auto num : a) {
                b.insert(num);
                if (len!=b.size()) {
                    return 0;
                }
            }
        }
    }
    
    return 1;
}

修改后的版本。

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int m1[256] = {0}, m2[256] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) {
            if (m1[s[i]] != m2[t[i]]) return false;  //判断两个字符串i位置的字符上次出现的位置是否一样。
            m1[s[i]] = i + 1;   //记录上次该字符出现的位置
            m2[t[i]] = i + 1;   //记录上次该字符出现的位置
        }
        return true;
    }
};
2017/12/20 posted in  leetcode

Path Sum II

运用前序遍历

/**
 * 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:
    void findPaths(TreeNode* node, int sum, vector<int>& path, vector<vector<int> >& paths) {
        if (!node) return;
        path.push_back(node -> val);
        if (!(node -> left) && !(node -> right) && sum == node -> val)
            paths.push_back(path);
        findPaths(node -> left, sum - node -> val, path, paths);
        findPaths(node -> right, sum - node -> val, path, paths);
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int> > paths;
        vector<int> path;
        findPaths(root, sum, path, paths);
        return paths;
    }
};
2017/12/19 posted in  leetcode

Path Sum

/**
 * 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:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL) return false;
        if (root->val == sum && root->left ==  NULL && root->right == NULL) return true;
        
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
};
2017/12/19 posted in  leetcode