c++刷leetcode

刷题目的: 熟练使用c++语法、STL组件的用法

1. 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        unordered_map<int,int>pos_map;
        for (int i = 0; i < nums.size();++i)
        {
            if (pos_map.count(target-nums[i]))
            {
                ret.push_back(i);
                ret.push_back(pos_map[target-nums[i]]);
                return ret;
            }
            
            pos_map[nums[i]] = i;
        }
        return ret;
    }
};

**思路: **我们遍历数组nums，借助unordered_map做数组元素和其在数组中的位置的映射，每当我们遍历到一个数组成员，我们先查找unordered_map中是否存在与该元素相加，构成要求的target的元素，如果存在的话，那说明我们已经找到这两个元素，所以我们就可以通过他们的键得到他们的值，也即是他们在数组中的位置。

STL

unordered_map

1. unordered_map 比map块，因为它不需要排序。尽管他们的范围遍历都是比较低效的。

2. Unordered maps 可通过运算符[]来使用键key，直接访问其映射的 == > mp[key] = value;

3. std::unordered_map::count ( )

   搜索unordered_map容器中key=k的成员的个数，由于unordered_map容器键是唯一的，所以在这个key存在的基础上，这个返回值永远为1.

15. 三数之和

C语言：

int compare(void *a,void *b)
{
    return *((int *)a) - *((int *)b);
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    int **ret = NULL;
    int count = 0;
    int *retcol = NULL;
	
    (*returnSize) = count;
    (*returnColumnSizes) = retcol;

    if (!nums || numsSize <= 2)
    {
        return ret;
    }

	qsort(nums,numsSize,sizeof(int),(void *)compare);

	ret = (int **)realloc(ret,sizeof(int *)*numsSize*numsSize);
    retcol = (int *)realloc(retcol,sizeof(int)*numsSize*numsSize);

    for (int i = 0; i < numsSize-2;++i)
    {
        if (nums[i] > 0)
        {
            break;
        }
		
        if (i > 0 && nums[i] == nums[i-1] )
        {
            continue;
        }
		
        int head = i+1;
        int tail = numsSize-1;
        
        while (head < tail)
        {
            int target = nums[head] + nums[tail] + nums[i];
            if (target == 0)
            {
                #if 0
                在内部逐步扩展指针数组，会导致超时,真操蛋！
                ret = (int **)realloc(ret,sizeof(int *)*(count+1));
                retcol = (int *)realloc(retcol,sizeof(int)*(count+1));
                #endif
                
                retcol[count] = 3;
                ret[count] = (int *)malloc(sizeof(int)*3);
                
                ret[count][0] = nums[i];
                ret[count][1] = nums[head];
                ret[count][2] = nums[tail];

                ++count;

                while (head < tail && nums[head] == nums[head+1])
                {
                    ++head;
                }

                while (head < tail && nums[tail] == nums[tail - 1])
                {
                    --tail;
                }

                ++head;
                --tail;
            }
            else if (target < 0)
            {
                ++head;
            }
            else
            {
                --tail;
            }
        }
    }

    (*returnSize) = count;
    (*returnColumnSizes) = retcol;

    return ret;
}

c++:

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        const int size = (int)nums.size();
        vector<vector<int>> ret;

        if (size < 3)
        {
            return ret;
        }
        
        sort(nums.begin(),nums.end());

        for (int i = 0; i < size -2;++i)
        {
            if (nums[i] > 0)
            {
                break;
            }

            if (i > 0 && nums[i] == nums[i-1])
            {
                continue;
            }

            int head = i+1;
            int tail = size-1;

            while (head < tail)
            {
                int target = nums[i] + nums[head] + nums[tail];
                if (target == 0)
                {
                    ret.push_back({nums[i],nums[head],nums[tail]});

                    while (head < tail && nums[head] == nums[head+1])
                    {
                        ++head;
                    }

                    while (head < tail && nums[tail] == nums[tail-1])
                    {
                        --tail;
                    }

                    ++head;
                    --tail;
                }
                else if (target < 0)
                {
                    ++head;
                }
                else 
                {
                    --tail;
                }
            }
        }

        return ret;
    }
};

16. 最接近的三数之和

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        const int size = (int)nums.size();
        int mostequal = nums[0] + nums[1] + nums[2];
        int diff = abs(mostequal - target);

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

        for (int i = 0; i < size -2;++i)
        {
            int head = i+1;
            int tail = size-1;

            while (head < tail)
            {
                int tmp = nums[i] + nums[head] + nums[tail];
                int tmpdiff = abs(target - tmp);
                if (diff > tmpdiff)
                {
                    diff = tmpdiff;
                    mostequal = tmp;
                }

                if (tmp < target)
                {
                    ++head;
                }
                else 
                {
                    --tail;
                }
            }
        }

        return mostequal;
    }
};

589. N 叉树的前序遍历

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ret;
        if (!root)
        {
            return ret;
        }
        stack<Node *>auxstack;
        auxstack.push(root);
        while (!auxstack.empty())
        {
            Node *ptmp = auxstack.top();
            ret.push_back(ptmp->val);
            auxstack.pop();
            
            for (auto itr = ptmp->children.rbegin();itr != ptmp->children.rend();++itr)
            {
                auxstack.push(*itr);
            }
        }

        return ret;
    }
};

STL

stack

47. 全排列 II

难度中等709收藏分享切换为英文接收动态反馈

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

as

STL

istream

(1) 从输入流is获取string,直到遇到字符delim
istream& getline (istream& is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);

(2) 和（1）相比，默认delim为换行符’\n’
istream& getline (istream& is, string& str);
istream& getline (istream&& is, string& str);

注意事项：

1.delim字符并不作为输入保存

2.若执行getline之前，str中有内容，则将被is的输入所替换。

3.若is达到了文件结束状态，那么getline也会停止。

set

1. set<int> var_set({1,2,3,4,5});var_set.find(2)返回的是指向这个元素的指针，var_set.count(2)是计算次数。set中的所有元素都是唯一的，所以count(key)的返回值只有0或1两种状态。

124. 二叉树中的最大路径和

难度困难1066
路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int ret = -1001;
        helper(root,ret);
        return ret;
    }

    int helper(TreeNode *node,int& res)
    {
        if (!node)
            return 0;
        int left = max(helper(node->left,res),0); //孩子值可能为负数，所以和0做对比，避免无用的“负”担
        int right = max(helper(node->right,res),0);     

        res = max(res,left+right+node->val);//此节点为根节点时构成的路径和若是超过当前最大路劲和res,那么就替换res为当前最大路径和。
        return max(left,right) + node->val;//node不为根节点时，其必须和其左右孩子节点中的一个在同一个路径上,那么当然是值不为0且更大的那一个，但是两个孩子可能都为负数，此时就抛弃孩子不让其参与到路径中
    }
};

思路：

某个点，有可能以它为根节点，与其左右子树构成最大路径和，也有可能该节点只是最大路径和上的一个旁节点。如下的node A;

所以，我们在递归的过程中，要计算这两种情况，对于第一种情况，因为我们的回溯是从叶子节点向上的，所以当遍历到某个节点，我们不会再往下，那么我们就可以直接计算其为根节点时的路径和，并与当前最大路径和比较。

 res = max(res,left+right+node->val);

同时，我们是从下到上的，那万一上面有一个节点F为根节点，与当前在其分支上的节点A其构成题目要求的最大路径和呢？所以在从下到上的回溯过程中我们要返回这种情况时的最大值，即A非根节点时其只能和其左右子树C和B中的最大者构成路径；又或者由于C、B（为根）的都是部分路径和为负数，此时只将A单独参与到最大路径的构成上去。