LeetCode OJ – 第19页

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;

}

};

LeetCode 464. Can I Win

In the “100 game,” two players take turns adding, to a running total, any integer from 1..10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers of 1..15 without replacement until they reach a total >= 100.

Given an integer maxChoosableInteger and another integer desiredTotal, determine if the first player to move can force a win, assuming both players play optimally.

You can always assume that maxChoosableInteger will not be larger than 20 and desiredTotal will not be larger than 300.

Example

Input:
maxChoosableInteger = 10
desiredTotal = 11

Output:
false

Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.

题目大意：两个人玩游戏，从1～maxChoosableInteger中任选一个数字，第一个人先选，第二个人后选，每个人选过的数字就不能再选了～两个人谁先加起来总和超过desiredTotal谁就赢，问给出数字，第一个人能否赢得比赛～

分析：两个特殊情况：1.如果能够选的最大数字大于等于desiredTotal，第一个人又不傻肯定选最大的值～那样他就赢啦～即：
if(maxn >= desiredTotal) return true;
2.如果所有能够选的数字的总和都小于desiredTotal，再怎么选两个人都不可能赢，所以肯定输～：
总和就是首项加末项的和乘以项数除以2～：if((1 + maxn) * maxn / 2 < desiredTotal) return false;
然后建立一个canWin函数，需要用visited标记某个数字是否被选过～因为可选的数字最大不超过20，则可以用一个整型数组标记，因为整型有32位～如果1被选过就把第1位（不是第0位哦～当然也可以从0开始啦～）标记为1，如果2被选过就把第2位标记为1～这样保证所有数字不重复～
所以传入两个值，一个是想要达到（或者说超过，也就是大于等于啦）的目标数字target，另一个是visited数字标记哪些数字被选过了～
用map标记当前情况在map表中是否存在，存在的话结果保存在map里面～如果我们发现这个visited也就是这个数字选择的情况已经被保存过了，就直接返回在map里面保存的结果～
遍历i从1到maxn（maxn是可以选择的最大值，即maxChoosableInteger），表示考虑选择i的情况，用mask = 1 << i，如果mask和visited进行与运算，如果等于0说明当前的visited没有被访问过，就可以考虑这个i的情况，如果要选的这个i大于target，不傻的这个人就会选择i因为肯定能赢啦～还有种情况自己能赢，就是对方输了，即：canWin(target – i, mask | visited) == false，（mask | visited表示把i那位也标记为1～）这个时候把visited情况存起来并且return true，表示赢了～如果所有数字都遍历完还是没有return true，那就最后return false～return false之前不要忘记把当前状态存储起来～也就是m[visited] = false; ～
注意：调了两个小时的bug后来才发现！(mask & visited) == 0一开始忘记加括号了，写成了mask & visited == 0，但是&运算符比==优先级低，所以==会先运算。。所以就gg了～注意注意～号外号外～

class Solution {
private:
    int maxn;
    map<int, bool> m;
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        maxn = maxChoosableInteger;
        if(maxn >= desiredTotal) return true;
        if((1 + maxn) * maxn / 2 < desiredTotal) return false;
        return canWin(desiredTotal, 0);
    }
    bool canWin(int target, int visited) {
        if(m.find(visited) != m.end()) return m[visited];
        for(int i = 1; i <= maxn; i++) {
            int mask = (1 << i);
            if((mask & visited) == 0 && (i >= target || canWin(target - i, mask | visited) == false)) {
                m[visited] = true;
                return true;
            }
        }
        m[visited] = false;
        return false;
    }
};

class Solution {

private:

int maxn;

map<int, bool> m;

public:

bool canIWin(int maxChoosableInteger, int desiredTotal) {

maxn = maxChoosableInteger;

if(maxn >= desiredTotal) return true;

if((1 + maxn) * maxn / 2 < desiredTotal) return false;

return canWin(desiredTotal, 0);

}

bool canWin(int target, int visited) {

if(m.find(visited) != m.end()) return m[visited];

for(int i = 1; i <= maxn; i++) {

int mask = (1 << i);

if((mask & visited) == 0 && (i >= target || canWin(target - i, mask | visited) == false)) {

m[visited] = true;

return true;

}

m[visited] = false;

return false;

}

};

LeetCode 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.

题目大意：给一个二叉树，判断这个二叉树是不是合法的二叉搜索树～

分析：既然是二叉搜索树，那么按照左根右遍历后的结果一定是增序～所以只需要中序遍历一遍，判断遍历结果的数组是不是后面数一定大于前面数就可以了～

class Solution {
private:
    vector<int> v;
public:
    bool isValidBST(TreeNode* root) {
        if(root == NULL ||(root->left == NULL && root->right == NULL)) return true;
        inorder(root);
        for(int i = 1; i < v.size(); i++)
            if(v[i] <= v[i-1]) return false;
        return true;
    }
    void inorder(TreeNode* root) {
        if(root == NULL) return;
        inorder(root->left);
        v.push_back(root->val);
        inorder(root->right);
    }
};

class Solution {

private:

vector<int> v;

public:

bool isValidBST(TreeNode* root) {

if(root == NULL ||(root->left == NULL && root->right == NULL)) return true;

inorder(root);

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

if(v[i] <= v[i-1]) return false;

return true;

}

void inorder(TreeNode* root) {

if(root == NULL) return;

inorder(root->left);

v.push_back(root->val);

inorder(root->right);

}

};

LeetCode 220. Contains Duplicate III

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

题目大意：给一个整数数组，找到是否存在两个不同的下标i和j，使得nums[i]和nums[j]的差的绝对值不超过t并且i和j的差的绝对值不超过k～

分析：建立一个map，对应的是元素的值到元素的下标的映射。指针i将nums数组从头遍历到尾，j指针一开始指向0。i向右走的时候如果i和j之差大于k，且m中有nums[j]，就将nums[j]从m中移除，且j向前走一步～这样就保证了m中所有的元素满足第一个条件：i和j的差的绝对值不超过k～

接下来考虑nums[i]和nums[j]的差的绝对值不超过t，abs(num[i] – nums[j]) <= t 则 nums[j]的最小可能满足条件的值为>=nums[i] – t的，所以使用map中的lower_bound，寻找第一个大于等于nums[i] – t的地方，找到后标记为a，此时的a只是取到了可能满足的最小的a，但(a – nums[i])不一定满足，所以检验a是否存在于map中且是否abs(a->first – nums[i]) <= t。如果都满足说明可以return true～

为什么要循环的最后写map的插入呢，因为比较的是i之前的所有元素～为了防止找到的是nums[i]本身，然后让nums[i]自己本身和自己比较差值了，这样结果就不对了～
如果到最后都没有能够return true，则return false～

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        map<long, int> m;
        int j = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (i - j > k && m[nums[j]] == j) m.erase(nums[j++]);
            auto a = m.lower_bound((long)nums[i] - t);
            if (a != m.end() && abs(a->first - nums[i]) <= t) return true;
            m[nums[i]] = i;
        }
        return false;
    }
};

class Solution {

public:

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

map<long, int> m;

int j = 0;

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

if (i - j > k && m[nums[j]] == j) m.erase(nums[j++]);

auto a = m.lower_bound((long)nums[i] - t);

if (a != m.end() && abs(a->first - nums[i]) <= t) return true;

m[nums[i]] = i;

}

return false;

}

};