472-82（22、165、39、剑指 Offer II 078、48. 旋转图像）

22. 括号生成

class Solution {
    
private:
    vector<string> res;

public:
    void dfs(int n, int left, int right, string seq)
    {
    
        if (left == n && right == n)
        {
    
            res.push_back(seq);
            return;
        }

        if(left < n)    dfs(n, left+1, right, seq + '(');
        if (right < n && left > right)    dfs(n, left, right + 1, seq + ')');
    }


public:
    vector<string> generateParenthesis(int n) {
    
        dfs(n, 0, 0, "");
        return res;
    }


};

165. 比较版本号

class Solution {
    
public:
    int compareVersion(string version1, string version2) {
    
        int i = 0, j = 0;

        while (i < version1.size() || j < version2.size())
        {
    
            unsigned int num1 = 0, num2 = 0;

            while (i < version1.size() && version1[i] != '.')
            {
    
                num1 = num1 * 10 + version1[i] - '0';
                i++;
            }

            while (j < version2.size() && version2[j] != '.')
            {
    
                num2 = num2 * 10 + version2[j] - '0';
                j++;
            }

            if (num1 > num2)
            {
    
                return 1;
            }
            else if (num1 < num2)
            {
    
                return -1;
            }

            i++, j++;
        }
        return 0;
    }
};

39. 组合总和

class Solution {
    
private:
    vector<vector<int>> res;
    vector<int> path;

private:
    void back_tracking(vector<int>& candidates, int target, int sum, int start_index)
    {
    
        if (sum == target)
        {
    
            res.push_back(path);
            return;
        }

        for (int i = start_index; i < candidates.size() && sum + candidates[i] <= target; i++)
        {
    
            sum += candidates[i];
            path.push_back(candidates[i]);
            back_tracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    
        res.clear();
        path.clear();

        if (candidates.size() == 0)  return res;
        sort(candidates.begin(), candidates.end());
        back_tracking(candidates, target, 0, 0);

        return res;
    }
};

剑指 Offer II 078. 合并排序链表

class Solution {
    
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
    
        vector<int> temp;

        for (const auto& list : lists)
        {
    
            ListNode* cur = list;
            while (cur != nullptr)
            {
    
                temp.push_back(cur->val);
                cur = cur->next;
            }
        }

        sort(temp.begin(), temp.end());

        ListNode* dummy_node = new ListNode(0);
        ListNode* cur = dummy_node;
        
        for (int i = 0; i < temp.size(); i++)
        {
    
            ListNode* node = new ListNode(temp[i]);
            cur->next = node;
            cur = cur->next;
        }

        return dummy_node->next;
    }
};

48. 旋转图像

class Solution {
    
public:
    void rotate(vector<vector<int>>& matrix) {
    
        int n = matrix.size();

        for (int i = 0; i < n; i++)//先沿对角线反转
        {
    
            for (int j = 0; j < i; j++)
            {
    
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        for (int i = 0; i < n; i++)//沿中线反转
        {
    
            for (int j = 0, k = n - 1; j < k; j++, k--)//类似于双指针
            {
    
                swap(matrix[i][j], matrix[i][k]);
            }
        }

    }
};