1. 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> twoSum(vector<int>& nums, int target)
{
    /*map*/ 
    umordered_map<int, int> hashtable;
    for(int i = 0; i < nums.size(); i++)
    {
        auto it = hashtable.find(target - nums[i]);
        if(it != hashtable.end())
            return {it->second, i};
        hashtable[nums[i]] = i;
    }
    return {};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/*先排序，再利用双指针遍历，初始i放首部，j放尾部，两数之和大于target的话j--，小于target的话i++，找到对应的i和j*/
vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> resV{ 0, 0 };
    vector<int> copyV = nums;
    int find;
    int hasFound = 0;
    sort(nums.begin(), nums.end());
    /* for(int k = 0; k < nums.size(); k++)*/
    /* {cout << nums[k] << " ";}*/
    int i = 0;
    int j = nums.size() - 1;
    while (i != j && hasFound == 0)
    {
        if (target > nums[i] + nums[j])
        {
            i++;
        }
        else if (target < nums[i] + nums[j])
        {
            j--;
        }
        else
        {
            /*找到i和j还没结束，要根据nums[i], nums[j]找到排序前的数组中对应的原始下标
            found1防止数组中有相同的值k使得k + k = target导致只能（进入下面的if）更新resV[0]的值
            这样，如果在原数组中找到第一个k值时进入if，之后继续找到第二个k值的时候便不会再进入if重复更新resV[0]而导致resV[j]不被更新*/
            int flag = 0, found1 = 0, label = 0;
            while (label != 2)
            {
                if (copyV[flag] == nums[i] && found1 == 0)
                {
                    label++;
                    resV[0] = flag;
                    found1 = 1;
                    flag++;
                }
                else if (copyV[flag] == nums[j])
                {
                    label++;
                    resV[1] = flag;
                    flag++;
                }
                else
                {
                    flag++;
                }
            }
            hasFound = 1;
        }
    }

    return resV;
}

2.两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
{
    ListNode *head = nullptr, *tail = nullptr;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val: 0;
        int n2 = l2 ? l2->val: 0;
        int sum = n1 + n2 + carry;
        if (!head) {
            head = tail = new ListNode(sum % 10);
        } else {
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        carry = sum / 10;
        if (l1) {
            l1 = l1->next;
        }
        if (l2) {
            l2 = l2->next;
        }
    }
    if (carry > 0) {
        tail->next = new ListNode(carry);
    }
    return head;
}

3. 无重复字符的最长字串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lengthOfLongestSubstring(string s)
{
    /* 滑动窗口 + set */
	unordered_set<char> st;
    int n = s.size();
    int right = 0, ret = 0;
    for(int left = 0; left < n; left++)
    {
        if(left != 0)
        {
            /* 每一轮循环首先舍弃窗口左端 */
            st.erase(s[left - 1]);
        }
        while(right < n && !st.count(s[right]))
        {
            st.insert(s[right]);
            right++;
        }
        /* 这里right - left 不用再加一，因为right从0而不是从-1开始，理解right的意义 */
        ret = max(ret, right - left);
    }
    return ret;
}

15. 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 排序然后双指针 */
vector<vector<int>> threeSum(vector<int>& nums)
{
    sort(nums.begin(), nums.end());
    vector<vector<int>> ret;
    int n = nums.size();
    if(n >= 3 && nums[n - 1] + nums[n - 2] + nums[n - 3] < 0) /* 剪枝 */
        return ret;
    for(int first = 0; first < n - 2; first++)
    {
        if(nums[first] + nums[first + 1] + nums[first + 2] > 0) /* 剪枝 */
            break;
        if(first > 0 && nums[first] == nums[first - 1])
            continue;
        int target = -nums[first];
        int third = n - 1;
        for(int second = first + 1; second < n - 1; second++)
        {
            if(second > first + 1 && nums[second] == nums[second - 1])
                continue;
            while(second < third && nums[second] + nums[third] > target)
                --third;
            if(second == third)
                break;
            if(nums[second] + nums[third] == target)
                ret.push_back({nums[first], nums[second], nums[third]});
        }
    }
    return ret;
}

84. 柱状图中的最大矩形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int largestRectangleArea(vector<int>& heights) {
    int ret = 0;
    int n = heights.size();
    vector<int> left(n), right(n, n);
    stack<int> monoStack;

    for(int i = 0; i < n; i++)
    {
        while(!monoStack.empty() && heights[monoStack.top()] >= heights[i])
        {
            right[monoStack.top()] = i; /* 终于遇到比stack中的top对应的柱低的柱了（之前可能是连续的比它高，所以无法确定矩形的宽，遇到比它低的时，就可以确定以它为高的矩形的右边界了）*/
            monoStack.pop();
        }
        left[i] = monoStack.empty() ? -1 : monoStack.top(); /* 检索到某下标时就可以确定以它为高的矩形的左边界 */
        monoStack.push(i);
    }
    for(int i = 0; i < n; i++)
    {
        ret = max(ret, (right[i] - left[i] -1) * heights[i]);
    }
    return ret;
}

85. 最大矩形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int largestRectangleArea(vector<int>& heights)
{
    int ret = 0;
    int n = heights.size();
    vector<int> left(n), right(n, n);
    stack<int> monoStack;
    for(int i = 0; i < n; i++)
    {
        while(!monoStack.empty() && heights[monoStack.top()] >= heights[i])
        {
            right[monoStack.top()] = i;
            monoStack.pop();
        }
        left[i] = monoStack.empty() ? -1 : monoStack.top();
        monoStack.push(i);
    }
    for(int i = 0; i < n; i++)
    {
        ret = max(ret, (right[i] - left[i] - 1) * heights[i]);
    }
    return ret;
}

int maximalRectangle(vector<vector<char>>& matrix) {
    int ret = 0;
    int m = matrix.size();
    if(m == 0) /*要写在n的定义之前，因为matrix[0]不一定存在*/
        return 0;
    int n = matrix[0].size();
    vector<int> dp (n, 0);
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            dp[j] = matrix[i][j] == '0' ? 0 : dp[j] + 1; /* 这个叠加是根据上一行的dp进行的，比如上方是2，下一行如果为‘1’，相应的柱状图加1的长度变为3（即在原dp数组基础上进行修改）*/
        }
        ret = max(ret, largestRectangleArea(dp));
    }
    return ret;
}

114. 二叉树（原地）展开为链表（顺着右子节点连）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* 还可以用前序遍历存到数组，再改节点结构；或者（只能用迭代法）同时存到数组并改节点结构，以上两种方法空间复杂度O(n)，下面是第三种方法不用前序遍历，直接改结构，空间复杂度为O(1) */
void flatten(TreeNode* root)
{
    TreeNode* cur = root;
    while(cur)
    {
        if(cur->left)
        {
            auto next = cur->left;
            auto predecessor = next;
            while(predecessor->right)
                predecessor = predecessor->right;
            /* predecessor为当前节点的左子树的最右节点，连到当前节点cur的右子节点 */
            predecessor->right = cur->right;
            /* 更新当前节点的左右子节点 */
            cur->left = nullptr;
            cur->right = next;
		}
        cur = cur->right;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxGain(TreeNode* root, int& maxSum)
{
    if(root)
        /* 空节点的最大贡献值等于0 */
    	return 0;
    int left = max(maxGain(root->left), 0);
    int right = max(maxGain(root->right), 0);
    /* 当前子树中的最大路径和为当前节点值加上两个子节点的最大贡献值 */
    int curMaxSum = root->val + left + right;
    maxSum = max(maxSum, curMaxSum);
    /* 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和 */
    return root->val + max(left, right);
}
int maxPathSum(TreeNode* root)
{
    int maxSum = INT_MIN;
    maxGain(root, maxSum);
    return maxSum;
}

128. （无序数组中能找出的）最长连续序列（需要O(n)时间复杂度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int longestConsecutive(vector<int>& nums)
{
    /* 怎么也该想到用哈希表存来减少时间复杂度 */
    unordered_set<int> st;
    int longestSeq = 0;
    for(int num : nums)
        st.insert(num);
    for(int s : st)
    {
        /* 灵魂的一步剪枝，怎么确定是否检查从某一个数字开始的序列？看set中是否存在num-1，如果存在，则跳过，以此避免查询序列中间的数字 */
        if(!st.count(s - 1))
        {
            int curSeq = 1;
            int curNum = s;
            while(st.count(curNum + 1))
            {
                curSeq++;
                curNum++;
            }
            longestSeq = max(longestSeq, curSeq);
        }
	}
    return longestSeq;
}

139. 单词（是否可以）拆分（成字符串数组中的元素） 4min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool wordBreak(string s, vector<string>& wordDict)
{
    unordered_set<string> st;
    for(string word : wordDict)
        st.insert(word);
    vector<bool> dp(s.size() + 1);
    dp[0] = true;
    /* 这里的i可以理解为字符串s的前i个字符 */
    for(int i = 1; i <= s.size();i++)
    {
        for(int j = 0; j < i; j++)
            /* 字符串的匹配使用的是s的子串和集合中存的string元素比较 */
            if(dp[j] && st.find(s.substr(j, i - j)) != st.end())
            {
                dp[i] = true;
                break;
            }
    }
    return dp[s.size()];
}

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 你走过我走的路，我走过你走的路，我们殊途同归 */
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if(!headA || !headB) return NULL;
    ListNode *p, *q, *pp, *qq;
    p = headA; q = headB;
    while(p != q)
    {
        pp = p; qq = q;
        p = (!p -> next && qq -> next) ? headB : p -> next;
        /* 用pp的作用体现出来了，经过上面的步骤，p可能已经变为p->next*/
        q = (!q -> next && pp -> next) ? headA : q -> next;
    }
    return p;
}

739. 每日温度（每天找下一个比今天更高的温度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 又是单调栈，相关题目还有84，85 */
vector<int> dailyTemperature(vector<int>& T)
{
    int n = T.size();
    vector<int> ret(n);
    stack<int> stk;
    for(int i = 0; i < n; i++)
    {
        while(!stk.empty() && T[i] > T[stk.top()])
        {
            int prevIndex = stk.top();
            ret[prevIndex] = i - prevIndex;
            stk.pop();
        }
        stk.push(i);
    }
	return ret;
}