344. Reverse String

stringにまつわるコーディング試験を行うことになったのでやってみる。

class Solution {
public:
    void reverseString(vector<char>& s) {
        vector<char> reverseS;
        for(int i = s.size()-1; i>=0; i-- )
        {
            reverseS.push_back(s[i]);
        }
        s= reverseS;
    }
};

Runtime: 53 ms

Memory Usage: 23.4 MB

class Solution {
public:
    void reverseString(vector<char>& s) {
        int start= 0;
        int end = s.size()-1;
        
        while(start<end){
          swap(s[start], s[end]); 
            start++;
            end--;
        }      

    }
};

Runtime: 34 ms

Memory Usage: 23.3 MB

283. Move Zeroes

nums[i]が0でないときに、nums[i]より前にある0といれかえる

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int swapObj=0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i])
            {
                swap(nums[i], nums[swapObj]);
                next++;
            }
        }           
    }
};

112. Path Sum

targetSumの値からtreeの値をrootから引いていく。0になったときにその下にノードがなければtrue。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr){
            return false;
        }
        
        targetSum = targetSum-root->val;
        if(targetSum == 0 && root->left == NULL && root->right == NULL ){
            return true;
        }
        bool leftResult = hasPathSum(root->left, targetSum);
        bool rightResult = hasPathSum(root->right, targetSum);
        
        return leftResult || rightResult;
    }
};

108. Convert Sorted Array to Binary Search Tree

1. 与えられた配列の中心をルートにする
2. 左側にルートより小さい値、右側に大きな値の枝を作る
3. 1-2を繰り返す

参考1

https://qiita.com/mhiro216/items/49d244dd9da1d6e6f70d

参考2

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/616527/C%2B%2B-solution

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()== 0)
        {
            return nullptr;
        }
        
        int leftSide = 0;
        int rightSide = nums.size()-1;
        return constrcutTree(nums, leftSide, rightSide);
    }
    
    TreeNode* constrcutTree(vector<int>&nums, int leftSide, int rightSide){
        if(leftSide> rightSide){
            return nullptr;
        }
        
        int mid = (leftSide + rightSide)/2;
        
        TreeNode* node = new TreeNode(nums[mid]);
        node->left = constrcutTree(nums, leftSide, mid-1);
        node->right = constrcutTree(nums, mid+1, rightSide);
        return node;        
    }
};

121. Best Time to Buy and Sell Stock

kadane algorithmの応用で行けました

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxPro = INT_MIN;
        int temPro = 0;
        int minBuyPrice =INT_MAX;
        for(int i= 0; i <prices.size(); i++)
        {
            minBuyPrice = min(prices[i], minBuyPrice);
            temPro=max(temPro, prices[i]-minBuyPrice);
            if(temPro>maxPro)
            {
                maxPro= temPro;
            }
        }
        return maxPro;
    }
};

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/ 与えられた値を1つずつ足していき、最も大きな値を選ぶ総当りは思いついたが、O(ｎ²)で遅い。

部分配列をO(ｎ)で計算するKadane Algorithm というアルゴリズムがあるようでした。

Kadaneのアルゴリズム—（動的計画法）—どのようにそしてなぜそれが機能するのか？

総当り

class Solution {
public:
    int max_sum = INT_MIN;
    int maxSubArray(vector<int>& nums) {
        for(int i = 0; nums.size() > i; i++){
            int currrent_sum = 0;
            for(int j=i; nums.size() > j; j++){
                currrent_sum += nums[j];
                max_sum = max(max_sum, currrent_sum);
            }
        }
        
        return max_sum;
    }
};

Kaneda Algorithm

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int max_sum = INT_MIN;
        int tmpSum = 0;
        for(int i =0; i < nums.size(); i++){
            tmpSum = max(nums[i], nums[i] + tmpSum);
            if(tmpSum > max_sum){
                max_sum = tmpSum;
            }
        }
        return max_sum;
    }
};

617. Merge Two Binary Trees

root1,2のどちらかが存在しない場合はもう一方のTreeNodeを返し、両方のTreeNodeが存在しない場合は0を、そして両方のTreeNodeが存在する場合は数値を足す

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(!root1 && !root2){
            return 0;
        }
        if(!root1 ){
            return root2;
        }
        if(!root2 ){
            return root1;
        }
        root1->val += root2->val;
        
        root1->left = mergeTrees(root1->left,root2->left);
        root1->right = mergeTrees(root1->right,root2->right);
        return root1;        
    }
};