93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

---

本题需要给一个数字字符串添加点号，使其成为一个合法的IP地址。
递归求解。首先设置两个数组kMinLen和kMaxLen，表示剩余字符串的最小/大长度，比如开始时step=0，则字符串的长度范围应该是[4,12]。

const vector<int> kMinLen = { 4, 3, 2, 1 };
const vector<int> kMaxLen = { 12, 9, 6, 3 };

然后递归的切当前字符串最多前3个字符，转成int，看是否<=255，如果是，则继续递归。直到step==4且没有剩余字符时，得到一个合法的IP地址。

完整代码如下：

const vector<int> kMinLen = { 4, 3, 2, 1 };
const vector<int> kMaxLen = { 12, 9, 6, 3 };
class Solution {
public:
    void work(vector<string>& ans, string cand, string left, int step)
    {
        if (step == 4) {
            if (left.size() == 0) {
                ans.push_back(cand);
            }
            return;
        }
        if (left.size() >= kMinLen[step] && left.size() <= kMaxLen[step]) {
            int border = min(3, int(left.size()));
            for (int l = 1; l <= border; l++) {
                string part_str = left.substr(0, l);
                if (part_str != "0" && part_str[0] == ‘0’)
                    continue; // 防止"010"这样的leading zero
                int part_int = atoi(part_str.c_str());
                if (part_int <= 255) {
                    string tmp = cand + left.substr(0, l);
                    if (step < 3)
                        tmp += ".";
                    work(ans, tmp, left.substr(l), step + 1);
                }
            }
        }
    }
    vector<string> restoreIpAddresses(string s)
    {
        vector<string> ans;
        string cand = "";
        work(ans, cand, s, 0);
        return ans;
    }
};

本代码提交AC，用时3MS。

二刷。使用数组保存ip地址更方便，代码如下：

class Solution {
public:
	void dfs(vector<string>& ans,vector<string>& cand, string &s, int idx) {
		if (cand.size() == 4 && idx == s.size()) {
			string ip = "";
			for (int i = 0; i < cand.size(); ++i) {
				ip = ip + cand[i] + ".";
			}
			ans.push_back(ip.substr(0, ip.size() - 1));
			return;
		}
		if (cand.size() == 4 && idx < s.size())return;
		if (cand.size() < 4 && idx >= s.size())return;
		for (int i = idx; i < s.size() && i < idx + 3; ++i) {
			string part = s.substr(idx, i - idx + 1);
			if (part[0] == '0'&&part.size() > 1)continue;
			int val = stoi(part);
			if (val <= 255) {
				cand.push_back(part);
				dfs(ans, cand, s, i + 1);
				cand.pop_back();
			}
		}
	}
	vector<string> restoreIpAddresses(string s) {
		vector<string> ans;
		vector<string> cand;
		dfs(ans, cand, s, 0);
		return ans;
	}
};

本代码提交AC，用时0MS。

92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

---

本题需要把链表中[m,n]之间的节点逆序，算是LeetCode Reverse Linked List的升级版，也是链表逆序的通用代码了。
思路简单，首先找到第m个节点，然后和LeetCode Reverse Linked List类似，用头插法把接下来的n-m+1个节点逆序就好了。
因为m可能等于1，为了统一代码，我们先在head前添加一个0号节点，这样操作起来更方便~然后开始找第m个节点，找到之后，把prior和tail切开，从tail开始往后把n-m+1个节点用头插法逆序。
有一个地方需要注意，就像样例一样，当把2~4逆序之后，我们还需要把最后节点5接到逆序之后的链表末尾，为了不再遍历链表，我们在找到第m个节点的时候，事先保存tail节点，也就是先保存2号节点，当逆序完之后，直接2->next=5就好了。
完整代码如下：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n)
    {
        if (head == NULL || head->next == NULL || m == n)
            return head;
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode *prior = new_head, *tail = head, *mid_head, *tmp;
        int offset = 1;
        while (offset < m) {
            prior = prior->next;
            tail = tail->next;
            offset++;
        }
        mid_head = prior; // 需要逆序的前一个节点
        tmp = tail; // 保留已逆序的最后一个节点，也就是需要逆序的第一个节点
        while (offset <= n) {
            prior = tail;
            tail = tail->next;
            prior->next = mid_head->next;
            mid_head->next = prior;
            offset++;
        }
        tmp->next = tail; // 已逆序最后一个节点接上后续节点
        return new_head->next;
    }
};

本代码提交AC，用时3MS。这代码居然一遍写完AC，都没有经过调试，我觉得边界条件处理还是要比较细心。

206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

---

本题要将一个链表反转。简单题，分为迭代法和递归法，迭代法比较容易想到，依次把链表当前的头结点断开，然后用头插法插到新链表的开头。算法如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* new_head = new ListNode(0);
        while (head != NULL) {
            ListNode* prior = head;
            head = head->next;
            prior->next = new_head->next;
            new_head->next = prior;
        }
        return new_head->next;
    }
};

本代码提交AC，用时9MS。 本题还要求实现递归法。比如链表1->2->3->4，递归的时候把头结点1断开，假设我们能得到2->3->4的反转链表4->3->2，则还需要把1接在之前反转链表的末尾。但是我们得到的4->3->2只返回了头结点，怎么得到尾节点2呢，唯一的方法就是开始我们不断开1，这样我们就可以用1->next得到2，然后把1->next->next=1，最后把1->next置为NULL。算法如下：

class Solution {
public:
    ListNode* reverseList(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* reversed_list = reverseList(head->next);
        head->next->next = head; // 重点
        head->next = NULL;
        return reversed_list;
    }
};

本代码提交AC，用时6MS。

二刷。更好理解的递归方法，比如链表1->2->3->4，先把2->3->4逆序变成4->3->2，注意此时1后面还是连着2，也就是说我们可以通过1找到2->3->4逆序的尾巴，然后把1接到尾巴即可。完整代码如下：

class Solution {
public:
	ListNode* reverseList(ListNode* head) {
		if (head == NULL)return NULL;
		if (head->next == NULL)return head;
		ListNode* tail = head->next;
		ListNode *rev_head = reverseList(head->next);
		tail->next = head;
		head->next = NULL;
		return rev_head;
	}
};

本代码提交AC，用时4MS。

LeetCode Sum of Two Integers Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -. Example: Given a = 1 and b = 2, return 3.

---

不使用加减法实现两个整数之和。这其实就是用位运算实现加法，我还清楚的记得本科面搜狐实习的时候被问到这个问题，当时还没有答上来。。。 用基本位运算实现加减乘除和位运算 实现加法这两篇博客介绍得很详细，可以参考之。 简单讲，对于两个二进制数a,b，异或运算（a^b）可以得到两数不加进位的和，与运算（a&b）可以得到两数每一位上的进位。所以还需要把每一位的进位依次加到之前的和里面。完整代码如下： [cpp] class Solution { public: int getSum(int a, int b) { int sum = a^b, carry = a&b; while (carry) { int tmp_a = sum; // 把和当作新的被加数a int tmp_b = carry << 1; // 把进位当作新的加数b sum = tmp_a^tmp_b; // 新的和 carry = tmp_a&tmp_b; // 新的进位 } return sum; } }; [/cpp] 本代码提交AC，用时0MS。 //负数也可以通过上述代码 如果要用位运算实现减法，通过简单的转换就能变成加法：a-b=a+(-b)。负数在计算机中的表示是补码，负数的补码等于正数的原码（正数的原码、反码和补码相等）取反加1。得到(-b)的表示之后，就可以调用上面的加法函数了。]]>

90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

---

求一个“集合”的所有子集，和LeetCode Subsets的区别是本题中，原始“集合”可能包含重复元素，和LeetCode Permutations II很类似。
只需在LeetCode Subsets的基础上增加一个判断，如果在递归的时候发现某个元素和上一个元素相同，则不添加，即不再以该元素独立新开一个递归下去。
举个例子，样例中的{1,2,2}，第一次递归的时候，我们会尝试分别以1,2和2递归，但是发现第二个2和前一个元素2相同，所以我们不再以第二个2开一个新的递归下去。但是我们在以第一个2开递归的时候，发现后面有一个2时，并不阻止这个2加到原有的集合中去，也就是子集{2,2}还是会产生的。
完整代码如下：

class Solution {
public:
    void work(vector<vector<int> >& ans, vector<int>& cand, vector<int>& nums, int step)
    {
        ans.push_back(cand);
        for (int i = step; i < nums.size(); i++) {
            if (i != step && nums[i] == nums[i – 1]) { // caution:i != step
                continue;
            }
            cand.push_back(nums[i]);
            work(ans, cand, nums, i + 1);
            cand.pop_back();
        }
    }
    vector<vector<int> > subsetsWithDup(vector<int>& nums)
    {
        vector<vector<int> > ans;
        vector<int> cand;
        sort(nums.begin(), nums.end()); // 先对原数组排序
        work(ans, cand, nums, 0);
        return ans;
    }
};

注意判断的条件是i!=step，而不是i!=0，因为如果是i!=0，则{2,2}这种情况也会被禁止掉。
本代码提交AC，用时6MS。

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Return the linked list sorted as well.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

---

把已排序链表中有重复元素的节点删掉，只保留出现一次的节点，看样例就可以知道这是怎么回事了。 此题有两个步骤，第一是找到新的头结点，第二是删掉后续的重复节点。 找新头结点时，维护一个head和tail指针，如果tail的val和head的val相同，则更新head和tail， 直到tail为空或者遇到一个distinct的head。 删掉后续重复节点时，维护一个sub_head、prior和tail，如果prior和tail的val相同，则把所有相同的节点都删掉，方法是直接把sub_head的next指向所有相同元素的下一个元素，同时更新prior和tail。 完整代码如下：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* tail = head->next;
        while (tail != NULL) { // find new head
            int cnt = 0;
            while (tail != NULL && tail->val == head->val) {
                tail = tail->next;
                cnt++;
            }
            if (tail == NULL)
                return NULL;
            if (cnt == 0)
                break;
            else {
                head = tail;
                tail = head->next;
            }
        }
        ListNode *sub_head = head, *prior = sub_head->next;
        while (prior != NULL) { // delete all duplicate nodes
            tail = prior->next;
            int cnt = 0;
            while (tail != NULL && tail->val == prior->val) {
                tail = tail->next;
                cnt++;
            }
            //if (tail == NULL)break;
            if (cnt == 0) {
                sub_head = prior;
                prior = prior->next;
            }
            else {
                sub_head->next = tail;
                prior = tail;
            }
        }
        return head;
    }
};

本代码提交AC，用时9MS。

二刷。完全不记得一刷的解法了。二刷参考https://discuss.leetcode.com/topic/29849/c-8ms-iterative-naive-but-easy-to-implement，很好理解的一个方法。
设置一个标签to_be_added，为true表明这个节点unique，需要添加到结果链表中，否则重复，需要删除。直接判断head和head->next的值是否相等，如果相等，则需要把所有等于head的节点删掉，比如说样例[1,1,1,2,3]，head=1,head->next=1，相等，则把head删掉；接着，head到了第二个1，发现等于第三个1，所以把第二个1删掉；接着head走到第三个1，此时head->next->val != head-val，跳出循环，但是因为to_be_added=false，说明1这个数重复了，所以还是需要把head删掉。只有to_be_added=true才会加入到结果链表中。
最后记得把tail->next=NULL置空，并且所有该删除的节点真的要delete掉。
完整代码如下：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* dummy = new ListNode(0 == head->val ? 1 : 0);
        ListNode *tail = dummy, *delete_node;
        bool to_be_added = true;
        while (head) {
            while (head->next && head->val == head->next->val) {
                delete_node = head;
                head = head->next;
                delete delete_node;
                to_be_added = false;
            }
            if (to_be_added) {
                tail->next = head;
                tail = tail->next;
                head = head->next;
            }
            else {
                delete_node = head;
                head = head->next;
                delete delete_node;
            }
            to_be_added = true; // reset
        }
        tail->next = NULL;
        delete_node = dummy;
        dummy = dummy->next;
        delete delete_node;
        return dummy;
    }
};

本代码提交AC，用时6MS。

三刷。简洁版代码，新建一个链表，把原链表中没有重复值的节点接到新链表中，代码如下：

class Solution {
public:
	ListNode* deleteDuplicates(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *new_head = new ListNode(0);
		ListNode *l0=new_head, *l1 = head, *l2 = head->next;
		while (l2) {
			l2 = l1->next;
			int count = 0;
			while (l2 != NULL && l2->val == l1->val) {
				l2 = l2->next;
				++count;
			}
			if (count == 0) {
				l0->next = l1;
				l0 = l0->next;
			}
			l1 = l2;
		}
		l0->next = NULL;
		return new_head->next;
	}
};

本代码提交AC，用时12MS。

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

---

删除已排序链表中的重复元素。简单，直接遍历，发现后面元素(tail)和前面元素(head)的值相同时，则删除后面元素，直到链表结束。 完整代码如下：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* new_head = head;
        ListNode *prior = head, *tail = prior->next;
        while (tail != NULL) {
            while (tail != NULL && tail->val == prior->val) {
                prior->next = tail->next;
                tail = prior->next;
            }
            if (tail == NULL)
                break;
            if (tail->val != prior->val) {
                prior = tail;
                tail = prior->next;
            }
        }
        return new_head;
    }
};

本代码提交AC，用时19MS。

下面提供一个由数组生成链表以及打印链表的函数，方便调试。

// 根据数组生成链表
ListNode* GenList(vector<int>& nums)
{
    if (nums.size() == 0)
        return NULL;
    ListNode* head = new ListNode(nums[0]);
    ListNode* tail = head;
    for (int i = 1; i < nums.size(); i++) {
        ListNode* node = new ListNode(nums[i]);
        tail->next = node;
        tail = tail->next;
    }
    return head;
}
// 打印链表
void PrintList(ListNode* head)
{
    while (head != NULL) {
        cout << head->val << endl;
        head = head->next;
    }
}

二刷。简洁代码：

class Solution {
public:
	ListNode* deleteDuplicates(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *l1 = head, *l2 = head->next;
		while (l2) {
			while (l2&&l2->val == l1->val) {
				//ListNode *tmp = l2;
				l2 = l2->next;
				//delete tmp;
			}
			l1->next = l2;
			l1 = l2;
		}
		return head;
	}
};

本代码提交AC，用时16MS。