Code – 第246页

LeetCode 223. Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.

Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.

Rectangle Area
Assume that the total area is never beyond the maximum possible value of int.

class Solution {
public:
    int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int maxae = A > E ? A : E;
        int mincg = C > G ? G : C;
        int maxfb = F > B ? F : B;
        int minhd = H > D ? D : H;
        int overlap;
        if(maxae >= mincg || maxfb >= minhd)
            overlap = 0;
        else
            overlap = (mincg - maxae) * (minhd - maxfb);
        return (C - A) * (D - B) + (G - E) * (H - F) - overlap;
    }
};

class Solution {

public:

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {

int maxae = A > E ? A : E;

int mincg = C > G ? G : C;

int maxfb = F > B ? F : B;

int minhd = H > D ? D : H;

int overlap;

if(maxae >= mincg || maxfb >= minhd)

overlap = 0;

else

overlap = (mincg - maxae) * (minhd - maxfb);

return (C - A) * (D - B) + (G - E) * (H - F) - overlap;

}

};

LeetCode 219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        set<int> s;
        int t = 0;
        for(int i = 0; i < nums.size(); i++) {
            s.insert(nums[i]);
            if(s.size() == t) {
                for(int j = i - 1; j >= 0 && j >= i - k; j--) {
                    if(nums[i] == nums[j])
                        return true;
                }
            }
            t = s.size();
        }
        return false;
    }
};

class Solution {

public:

bool containsNearbyDuplicate(vector<int>& nums, int k) {

set<int> s;

int t = 0;

for(int i = 0; i < nums.size(); i++) {

s.insert(nums[i]);

if(s.size() == t) {

for(int j = i - 1; j >= 0 && j >= i - k; j--) {

if(nums[i] == nums[j])

return true;

}

t = s.size();

}

return false;

}

};

LeetCode 88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index = m + n - 1;
        int aindex = m - 1;
        int bindex = n - 1;
        while(aindex >= 0 && bindex >= 0) {
            if(nums1[aindex] > nums2[bindex]) {
                nums1[index--] = nums1[aindex--];
            } else {
                nums1[index--] = nums2[bindex--];
            }
        }
        while(bindex >= 0) {
            nums1[index--] = nums2[bindex--];
        }
    }
};

class Solution {

public:

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

int index = m + n - 1;

int aindex = m - 1;

int bindex = n - 1;

while(aindex >= 0 && bindex >= 0) {

if(nums1[aindex] > nums2[bindex]) {

nums1[index--] = nums1[aindex--];

} else {

nums1[index--] = nums2[bindex--];

}

while(bindex >= 0) {

nums1[index--] = nums2[bindex--];

}

};

LeetCode 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
begin to intersect at node c1.
Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getlength(ListNode *A) {
        int len = 0;
        while(A != NULL) {
            len++;
            A = A->next;
        }
        return len;
    }
    
    ListNode* func(ListNode *B, int movelen) {
        while(movelen--) {
            B = B->next;
        }
        return B;
    }
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == NULL || headB == NULL) {
            return NULL;
        }
        int lenA = getlength(headA);
        int lenB = getlength(headB);
        ListNode *p, *q;
        p = headA;
        q = headB;
        if(lenA > lenB) {
            p = func(headA, lenA - lenB);
        }
        if(lenA < lenB) {
            q = func(headB, lenB - lenA);
        }
        while(p != q && p != NULL && q != NULL) {
            p = p->next;
            q = q->next;
        }
        return p;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

int getlength(ListNode *A) {

int len = 0;

while(A != NULL) {

len++;

A = A->next;

}

return len;

}

ListNode* func(ListNode *B, int movelen) {

while(movelen--) {

B = B->next;

}

return B;

}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

if(headA == NULL || headB == NULL) {

return NULL;

}

int lenA = getlength(headA);

int lenB = getlength(headB);

ListNode *p, *q;

p = headA;

q = headB;

if(lenA > lenB) {

p = func(headA, lenA - lenB);

}

if(lenA < lenB) {

q = func(headB, lenB - lenA);

}

while(p != q && p != NULL && q != NULL) {

p = p->next;

q = q->next;

}

return p;

}

};

LeetCode 36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles – The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int book[10];
        memset(book, 0, sizeof(int)*10);
        //每一列
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[i][j] == '.') continue;
                if(book[board[i][j] - '0'] == 0)
                    book[board[i][j] - '0'] = 1;
                else
                    return false;
            }
            memset(book, 0, sizeof(int) * 10);
        }
        //每一行
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                if(board[j][i] == '.') continue;
                if(book[board[j][i] - '0'] == 0)
                    book[board[j][i] - '0'] = 1;
                else
                    return false;
            }
            memset(book, 0, sizeof(int) * 10);
        }
        //每个小九宫格
        for(int m = 0; m <= 6; m = m + 3) {
            for(int i = 0; i <= 8; i++) {
                if(i % 3 == 0)
                     memset(book, 0, sizeof(int) * 10);
                for(int j = 0; j <= 2; j++) {
                    if(board[i][j + m] == '.') continue;
                    if(book[board[i][j + m] - '0'] == 0)
                        book[board[i][j + m] - '0'] = 1;
                    else
                        return false;
                }
            }
        }
        return true;
    }
};

class Solution {

public:

bool isValidSudoku(vector<vector<char>>& board) {

int book[10];

memset(book, 0, sizeof(int)*10);

//每一列

for(int i = 0; i < 9; i++) {

for(int j = 0; j < 9; j++) {

if(board[i][j] == '.') continue;

if(book[board[i][j] - '0'] == 0)

book[board[i][j] - '0'] = 1;

else

return false;

}

memset(book, 0, sizeof(int) * 10);

}

//每一行

for(int i = 0; i < 9; i++) {

for(int j = 0; j < 9; j++) {

if(board[j][i] == '.') continue;

if(book[board[j][i] - '0'] == 0)

book[board[j][i] - '0'] = 1;

else

return false;

}

memset(book, 0, sizeof(int) * 10);

}

//每个小九宫格

for(int m = 0; m <= 6; m = m + 3) {

for(int i = 0; i <= 8; i++) {

if(i % 3 == 0)

memset(book, 0, sizeof(int) * 10);

for(int j = 0; j <= 2; j++) {

if(board[i][j + m] == '.') continue;

if(book[board[i][j + m] - '0'] == 0)

book[board[i][j + m] - '0'] = 1;

else

return false;

}

return true;

}

};

LeetCode 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

递归方法：
/**
 * 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->left == NULL && root->right == NULL && sum == root->val)
                return true;
        if(hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))
            return true;
        else
            return false;
    }
};


非递归法
/**
 * 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) {
        queue<TreeNode *> q;
        if(root == NULL)
            return false;
        q.push(root);
        TreeNode *temp;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                temp = q.front();
                q.pop();
                if(temp->left != NULL) {
                    q.push(temp->left);
                    temp->left->val += temp->val;
                }
                if(temp->right != NULL) {
                    q.push(temp->right);
                    temp->right->val += temp->val;
                }
                if(temp->left == NULL && temp->right == NULL && (temp->val == sum || temp->val == sum)) {
                        return true;
                }
            }
        }
        return false;
    }
};

递归方法：

/**

* 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->left == NULL && root->right == NULL && sum == root->val)

return true;

if(hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val))

return true;

else

return false;

}

};

非递归法

/**

* 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) {

queue<TreeNode *> q;

if(root == NULL)

return false;

q.push(root);

TreeNode *temp;

while(!q.empty()) {

int size = q.size();

while(size--) {

temp = q.front();

q.pop();

if(temp->left != NULL) {

q.push(temp->left);

temp->left->val += temp->val;

}

if(temp->right != NULL) {

q.push(temp->right);

temp->right->val += temp->val;

}

if(temp->left == NULL && temp->right == NULL && (temp->val == sum || temp->val == sum)) {

return true;

}

return false;

}

};