Code – 第153页

LeetCode 143. Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

题目大意：按照L0→Ln→L1→Ln-1→L2→Ln-2→…重新排列链表～

分析：1.找到链表的中间结点mid——使用mid走一步、tail走两步的方式，直到tail走到链表尾部的时候，mid正好指向中间位置。2.从mid结点开始将后面的链表反转，返回反转后的头结点 3.p指向前面一段链表，q指向后面一段链表，将p和q合并：首先令a和b是p和q的临时结点，然后将pq分别向后移动一位，最后将a->next = b;b->next = p;

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *p = head, *a = head, *b = head;
        ListNode *mid = findMidNode(head);
        ListNode *q = reverseList(mid);
        while (p != NULL && q != NULL) {
            a = p;
            b = q;
            p = p->next;
            q = q->next;
            a->next = b;
            b->next = p;
        }
        if (q != NULL) b->next = q;
    }
    
    ListNode* findMidNode(ListNode* head) {
        ListNode *mid = head, *tail = head, *last = head;
        while (tail != NULL && tail->next != NULL) {
            last = mid;
            mid = mid->next;
            tail = tail->next->next;
        }
        if (last != NULL) last->next = NULL;
        return mid;
    }
    
    ListNode* reverseList(ListNode* head) {
        if (head == NULL) return head;
        ListNode *cur = head, *pre = NULL, *temp = NULL;
        while (cur != NULL) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

class Solution {

public:

void reorderList(ListNode* head) {

ListNode *p = head, *a = head, *b = head;

ListNode *mid = findMidNode(head);

ListNode *q = reverseList(mid);

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

a = p;

b = q;

p = p->next;

q = q->next;

a->next = b;

b->next = p;

}

if (q != NULL) b->next = q;

}

ListNode* findMidNode(ListNode* head) {

ListNode *mid = head, *tail = head, *last = head;

while (tail != NULL && tail->next != NULL) {

last = mid;

mid = mid->next;

tail = tail->next->next;

}

if (last != NULL) last->next = NULL;

return mid;

}

ListNode* reverseList(ListNode* head) {

if (head == NULL) return head;

ListNode *cur = head, *pre = NULL, *temp = NULL;

while (cur != NULL) {

temp = cur->next;

cur->next = pre;

pre = cur;

cur = temp;

}

return pre;

}

};

LeetCode 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

题目大意：给一个整型数组，求该数组中所有连续子数组的元素乘积的最大值～

分析：需要保存临时最大值和最小值，因为最大值乘以一个正数可能构成新的最大值，而最小值乘以负数也可能构成新的最大值。result是要求的结果，maxValue为nums[i]之前的，和nums[i]相邻的乘积的最大值，minValue为nums[i]之前的，和nums[i]相邻的乘积的最小值。首先令result、maxValue和minValue都为nums[0], i从nums[1]开始一直到结束，tempMax为考虑是否选择之前的maxValue与nums[i]相乘，如果相乘结果更大就保留，否则就选择nums[i]本身为最大。tempMin同理～然后maxValue和minValue比较tempMax/tempMin与minValue * nums[i]的大小关系，maxValue取较大值，minValue取较小值～而result是取所有maxValue中的最大值～最后返回result～

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        int result = nums[0], maxValue = nums[0], minValue = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int tempMax = max(nums[i], maxValue * nums[i]);
            int tempMin = min(nums[i], maxValue * nums[i]);
            maxValue = max(tempMax, minValue * nums[i]);
            minValue = min(tempMin, minValue * nums[i]);
            result = max(maxValue, result);
        }
        return result;
    }
};

class Solution {

public:

int maxProduct(vector<int>& nums) {

if (nums.size() == 0) return 0;

int result = nums[0], maxValue = nums[0], minValue = nums[0];

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

int tempMax = max(nums[i], maxValue * nums[i]);

int tempMin = min(nums[i], maxValue * nums[i]);

maxValue = max(tempMax, minValue * nums[i]);

minValue = min(tempMin, minValue * nums[i]);

result = max(maxValue, result);

}

return result;

}

};

LeetCode 501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than or equal to the node’s key.
The right subtree of a node contains only nodes with keys greater than or equal to the node’s key.
Both the left and right subtrees must also be binary search trees.
For example:
Given BST [1,null,2,2],
1
\
2
/
2
return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

题目大意：给一个二叉搜索树，求出现次数最多的数是哪个（哪些）～

分析：二叉搜索树的中序遍历的结果恰好是所有数的递增序列，根据中序遍历结果，对于当前遍历结点，标记maxCount为最大出现次数，tempCount为当前数字出现的次数，currentVal为当前保存的值。
首先，tempCount++表示当前的数字出现次数+1，如果当前结点的值不等于保存的值，就更新currentVal的值，并且将tempCount标记为1～
接下来，如果tempCount即当前数字出现的次数大于maxCount，就更新maxCount，并且将result数组清零，并将当前数字放入result数组中；如果tempCount只是等于maxCount，说明是出现次数一样的，则将当前数字直接放入result数组中～

class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        inorder(root);
        return result;
    }
private:
    vector<int> result;
    int maxCount = 0, currentVal, tempCount = 0;
    void inorder(TreeNode* root) {
        if (root == NULL) return;
        inorder(root->left);
        tempCount++;
        if (root->val != currentVal) {
            currentVal = root->val;
            tempCount = 1;
        }
        if (tempCount > maxCount) {
            maxCount = tempCount;
            result.clear();
            result.push_back(root->val);
        } else if (tempCount == maxCount) {
            result.push_back(root->val);
        }
        inorder(root->right);
    }
};

class Solution {

public:

vector<int> findMode(TreeNode* root) {

inorder(root);

return result;

}

private:

vector<int> result;

int maxCount = 0, currentVal, tempCount = 0;

void inorder(TreeNode* root) {

if (root == NULL) return;

inorder(root->left);

tempCount++;

if (root->val != currentVal) {

currentVal = root->val;

tempCount = 1;

}

if (tempCount > maxCount) {

maxCount = tempCount;

result.clear();

result.push_back(root->val);

} else if (tempCount == maxCount) {

result.push_back(root->val);

}

inorder(root->right);

}

};

LeetCode 71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = “/home/”, => “/home”
path = “/a/./b/../../c/”, => “/c”
click to show corner cases.

Corner Cases:
Did you consider the case where path = “/../”?
In this case, you should return “/”.
Another corner case is the path might contain multiple slashes ‘/’ together, such as “/home//foo/”.
In this case, you should ignore redundant slashes and return “/home/foo”.

题目大意：简化一个Unix风格的绝对路径，返回简化后的结果～

分析：以”/”为分隔，将所有不是”.”和”..”的字符串放入栈中。如果是”..”并且上一层不为空，就返回上一层，也就是弹栈；如果是”.”，不处理；如果有多个连续的”/”，则只认一个”/”：从头到尾遍历字符串，如果是”/”就不断跳过；当不是”/”的时候，将后面的字符串放入temp中，如果是”..”就弹栈，如果不是”..”和”.”就把temp压入栈中。最后将栈中所有的元素按照”/”分隔连接成result字符串～

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> s;
        string result = "", temp = "";
        int i = 0, len = path.length();
        while (i < len) {
            while (i < len && path[i] == '/') i++;
            temp = "";
            while (i < len && path[i] != '/') temp += path[i++];
            if (temp == ".." && !s.empty())
                s.pop();
            else if (temp != "" && temp != "." && temp != "..")
                s.push(temp);
        }
        if (s.empty()) return "/";
        while (!s.empty()) {
            result = "/" + s.top() + result;
            s.pop();
        }
        return result;
    }
};

class Solution {

public:

string simplifyPath(string path) {

stack<string> s;

string result = "", temp = "";

int i = 0, len = path.length();

while (i < len) {

while (i < len && path[i] == '/') i++;

temp = "";

while (i < len && path[i] != '/') temp += path[i++];

if (temp == ".." && !s.empty())

s.pop();

else if (temp != "" && temp != "." && temp != "..")

s.push(temp);

}

if (s.empty()) return "/";

while (!s.empty()) {

result = "/" + s.top() + result;

s.pop();

}

return result;

}

};

LeetCode 61. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

题目大意：将一个链表向右循环k次，返回这个链表～

分析：计算出整个链表的长度len，如果要向右循环k次，则新的head指针应该在往右移动len – k % len处。（如果向右移动的距离moveDistance == len，那么直接返回head即可），newhead之前的一个指针的next应为NULL。并且尾部NULL前的tail指针处，tail的next应该为原来的head，最后返回newhead～

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL) return head;
        int len = 0;
        ListNode *newhead = head, *tail = head, *p = head;
        while (p != NULL) {
            if (p->next == NULL)
                tail = p;
            len++;
            p = p->next;
        }
        int moveDistance = len - k % len;
        if (moveDistance == len) return head;
        for (int i = 0; i < moveDistance - 1; i++) {
            newhead = newhead->next;
        }
        ListNode *temp = newhead;
        newhead = newhead->next;
        temp->next = NULL;
        tail->next = head;
        return newhead;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

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

* };

class Solution {

public:

ListNode* rotateRight(ListNode* head, int k) {

if (head == NULL) return head;

int len = 0;

ListNode *newhead = head, *tail = head, *p = head;

while (p != NULL) {

if (p->next == NULL)

tail = p;

len++;

p = p->next;

}

int moveDistance = len - k % len;

if (moveDistance == len) return head;

for (int i = 0; i < moveDistance - 1; i++) {

newhead = newhead->next;

}

ListNode *temp = newhead;

newhead = newhead->next;

temp->next = NULL;

tail->next = head;

return newhead;

}

};

LeetCode 468. Validate IP Address

Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots (“.”), e.g.,172.16.254.1;

Besides, leading zeros in the IPv4 is invalid. For example, the address 172.16.254.01 is invalid.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (“:”). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a valid one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don’t replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, extra leading zeros in the IPv6 is also invalid. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is invalid.

Note: You may assume there is no extra space or special characters in the input string.

Example 1:
Input: “172.16.254.1”

Output: “IPv4”

Explanation: This is a valid IPv4 address, return “IPv4”.
Example 2:
Input: “2001:0db8:85a3:0:0:8A2E:0370:7334”

Output: “IPv6”

Explanation: This is a valid IPv6 address, return “IPv6”.
Example 3:
Input: “256.256.256.256”

Output: “Neither”

Explanation: This is neither a IPv4 address nor a IPv6 address.

题目大意：给一个字符串，判断它是不是IP地址，如果是IPv4地址，就返回IPv4；如果是IPv6地址，就返回IPv6；都不是的话返回Neither～

分析：首先根据地址中是否包含.或者:判断是IPv4还是IPv6的范畴～
如果是IPv4，则需要满足：
1.一共有3个”.”
2.每个点之间的内容为数字，不能为空，且这个数字是0～255
3.没有前导的0，即不会出现001这样的数字（小技巧是字符串转化为数字再转化为字符串，看看和原来字符串是否一致）
如果是IPv6，则需要满足：
1.一共有7个”:”
2.每个标点之间的内容为16进制数字，不能为空即只能包含数字、字母(a~f、A~F)

class Solution {
public:
    string validIPAddress(string IP) {
		for (int i = 0; i < IP.length(); i++) {
			if (IP[i] == '.')
				return isIPv4(IP) ? "IPv4" : "Neither";
			else if (IP[i] == ':')
				return isIPv6(IP) ? "IPv6" : "Neither";
		}
		return "Neither";
    }
private:
	bool isIPv4(string IP) {
		int dotcnt = 0;
		for (int i = 0; i < IP.length(); i++) {
			if (IP[i] == '.')
				dotcnt++;
		}
		if (dotcnt != 3) return false;
		string temp = "";
		for (int i = 0; i < IP.length(); i++) {
		    if (IP[i] != '.')
		        temp += IP[i];
		    if (IP[i] == '.' || i == IP.length() - 1) {
		        if (temp.length() == 0 || temp.length() > 3) return false;
		        for (int j = 0; j < temp.length(); j++) {
		            if (!isdigit(temp[j])) return false;
		        }
		        int tempInt = stoi(temp);
		        if (tempInt > 255 || tempInt < 0) return false;
		        string convertString = to_string(tempInt);
		        if (convertString != temp) return false;
		        temp = "";
		    }
		}
		if (IP[IP.length()-1] == '.') return false;
		return true;
	}

	bool isIPv6(string IP) {
		int dotcnt = 0;
		for (int i = 0; i < IP.length(); i++) {
			if(IP[i] == ':')
				dotcnt++;
		}
		if (dotcnt != 7) return false;
		string temp = "";
		for (int i = 0; i < IP.length(); i++) {
		    if (IP[i] != ':')
		        temp += IP[i];
		    if (IP[i] == ':' || i == IP.length() - 1) {
		        if (temp.length() == 0 || temp.length() > 4) return false;
		        for (int j = 0; j < temp.length(); j++) {
		            if (!(isdigit(temp[j]) || (temp[j] >= 'a' && temp[j] <= 'f') || (temp[j] >= 'A' && temp[j] <= 'F'))) return false;
		        }
		        temp = "";
		    }
		}
		if (IP[IP.length()-1] == ':') return false;
		return true;
	}
};

class Solution {

public:

string validIPAddress(string IP) {

for (int i = 0; i < IP.length(); i++) {

if (IP[i] == '.')

return isIPv4(IP) ? "IPv4" : "Neither";

else if (IP[i] == ':')

return isIPv6(IP) ? "IPv6" : "Neither";

}

return "Neither";

}

private:

bool isIPv4(string IP) {

int dotcnt = 0;

for (int i = 0; i < IP.length(); i++) {

if (IP[i] == '.')

dotcnt++;

}

if (dotcnt != 3) return false;

string temp = "";

for (int i = 0; i < IP.length(); i++) {

if (IP[i] != '.')

temp += IP[i];

if (IP[i] == '.' || i == IP.length() - 1) {

if (temp.length() == 0 || temp.length() > 3) return false;

for (int j = 0; j < temp.length(); j++) {

if (!isdigit(temp[j])) return false;

}

int tempInt = stoi(temp);

if (tempInt > 255 || tempInt < 0) return false;

string convertString = to_string(tempInt);

if (convertString != temp) return false;

temp = "";

}

if (IP[IP.length()-1] == '.') return false;

return true;

}

bool isIPv6(string IP) {

int dotcnt = 0;

for (int i = 0; i < IP.length(); i++) {

if(IP[i] == ':')

dotcnt++;

}

if (dotcnt != 7) return false;

string temp = "";

for (int i = 0; i < IP.length(); i++) {

if (IP[i] != ':')

temp += IP[i];

if (IP[i] == ':' || i == IP.length() - 1) {

if (temp.length() == 0 || temp.length() > 4) return false;

for (int j = 0; j < temp.length(); j++) {

if (!(isdigit(temp[j]) || (temp[j] >= 'a' && temp[j] <= 'f') || (temp[j] >= 'A' && temp[j] <= 'F'))) return false;

}

temp = "";

}

if (IP[IP.length()-1] == ':') return false;

return true;

}

};