[刷题笔记]LeetCode3. Longest Substring Without Repeating Characters

发表于 2018-03-13 | 分类于 LeetCode

Descripition

Given a string, find the length of the longest substring without repeating characters.
给定一个字符串，找出不包含重复字符的最长子串

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

分析

看完题目比较直观的想法，是在遍历字符串的时候，记录从当前位置往前看所能组成非重复子串的最大长度，然后动态更新全局的最大子串长度。

这就需要设置两个指针start和end，用来记录子串的两个端点位置，遍历过程中不断右移end指针，同时更新start指针的位置，使其包含的部分符合非重复子串的定义，每走一步就与全局最大子串长度比较一次，这样达到更新全局最大子串长度的目的。

这就涉及到一个问题，start指针在何时更新，如何更新？

很自然能想到使用一个map来记录每个字符出现的位置，当end指针扫描到的字符在map中存在记录时（假设对应位置为pos），表示符合条件的子串必定包含在pos和end之间，此时可以取start = pos + 1，以使子串长度最大化。不过这里要注意一个问题，start指针是不能向左更新的，因为start指针左移就意味着将之前步骤已经排除在外的部分又重新包含到当前子串中了。

举个例子：考虑字符串abba，起始时start和end都指向第一个字符a；当end扫描到第三个字符b时，此时start仍指向第一个位置，map中已经存储了两个记录map[a]=0和map[b]=1，此时发现b的位置记录1，因此将start指向1+1=2的位置，并更新map[b]=2；end继续扫描到第四个字符a时，再次发现a的位置记录0，此时若直接将start更新为0+1=1，会造成start和end包含的子串bba中出现重复的字符b。

So，综合起来就是end一直往后扫，当发现end指针所指向的内容在map中存在位置记录pos，并且pos >= start时，将start更新为pos+1，每遍历一步就记录一下map的最新内容，同时获得当前子串的长度s = end - start + 1，对比一下maxlen和s的大小并更新maxlen = max(maxlen, s)就行了。哎，说得有点绕，还是写代码清晰啊

该方法只需遍历一次字符串，但须要额外资源存储下标记录，因此时间复杂度和空间复杂度均为O(n)。

C++ Code:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxlen = 0;                     // 记录最大子串长度
        int start = 0, end = 0;             // 记录子串两个端点位置
        unordered_map<char, int> pos_map;   // 记录字符最新位置
        
        for (; end < s.size(); ++end)
        {
            char c = s[end];
            if ((pos_map.find(c) != pos_map.end()) &&
                (pos_map[c] >= start))              
            {   // 仅当重复字符的位置在原start右边时才需要更新
                start = pos_map[c] + 1;
            }
            maxlen = max(maxlen, end - start + 1);  // 更新最大长度
            pos_map[c] = end;                       // 记录字符最新位置
        }
        return maxlen;
    }
};

[刷题笔记]LeetCode2. Add Two Numbers

发表于 2018-03-12 | 分类于 LeetCode

Descripition

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
给定两个非空链表，分别表示两个逆序排列的非负整数，每个节点包含一个单一数字，求得两个整数的和并返回响应的链表表示。
假设给定的整数不会包含前导0，除非整数就是0本身。

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

分析

同时遍历两个整数链表，使用尾插法更新结果链表，新节点值为当前两节点值与前一轮进位和的个位结果，同时更新当前轮次的进位标记。

Tips：

因两整数链表长度不一定相等，为方便操作，当遍历到某个链表节点为空时，可假定其取值为0
当遍历到两个链表节点均为空时，还需检查最后的进位标志

时间复杂度和空间复杂度均为O(max(n, m))，n和m分表代表两个链表的长度。

C++ Code：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 为方便操作, 为结果链表构建头结点
        ListNode* L = new ListNode(-1);
        ListNode* p = L;
        
        int ca = 0;    // 进位标志
        int v1, v2, sum, unit;
        while (l1 || l2) {
            v1 = l1 ? l1->val : 0;
            v2 = l2 ? l2->val : 0;
            
            sum = v1 + v2 + ca;
            unit = sum % 10;
            ca = sum / 10;
            
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
            p->next = new ListNode(unit);
            p = p->next;
        }
        
        if (ca > 0) {
            p->next = new ListNode(ca);
        }
        
        return L->next;
    }
};

[刷题笔记]LeetCode1. Two Sum

发表于 2018-03-12 | 分类于 LeetCode

Descripition

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
给定一个整形数组，返回相加等于指定目标数字的元素下标，
假设每组输入恰好只有一种可能的解，并且同一元素不能使用两次。

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析

遍历一遍数组，遍历的同时，用一个map记录经过的数字与下标，每遇到一个新的元素，查找目标值与该元素的差是否存于在map中，若存在则返回对应下标，否则继续遍历。

最坏情况需一次遍历和正比数组长度的额外空间，因此时间复杂度和空间复杂度均为O(n)。

C++ Code:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> rev;
        unordered_map<int, int> mapping;
        int size = nums.size();
        for (int i = 0; i < size; ++i) {
            int a = target - nums[i];
            if (mapping.find(a) != mapping.end()) {
                rev.push_back(mapping.at(a));
                rev.push_back(i);
                return rev;
            }
            mapping[nums[i]] = i;
        }
        return rev;
    }
};

Git命令笔记

发表于 2018-03-11 | 分类于 Git

日常使用Git时经常记不住相关操作，故将常用的命令记录以便翻查

基本操作

git init 初始化仓库
git clone [url] 克隆远程仓库到本地
git add [file] 添加指定文件到缓存区
git add . 添加所有文件到缓存区
git status 查看仓库当前状态
git diff 对比缓存器与工作区的差异
git pull [remote] [branch] 拉取远程仓库, 并与本地分支合并
git push [remote] [branch] 推送本地指定分支到远程仓库
git push [remote] --force 强制推送当前分支到远程仓库
git push [remote] --all 推送所有分支到远程仓库
git commit -m [message] 将缓存区内容提交到仓库
git reset HEAD 还原工作区与缓存区到上一次提交状态
git reset [file] 还原缓存区中指定文件, 工作区不变
git rm 删除仓库中指定文件
git mv 移动/重命名仓库中的文件

分支

git branch 列出所有本地分支
git branch -r 列出所有远程分支
git branch -a 列出所有本地和远程分支
git branch [branch-name] 新建分支
git checkout -b [branch-name] 新建并切换分支
git checkout [branch-name] 切换分支
git merge [branch-name] 合并指定分支到当前分支
git branch -d [branch-name] 删除分支

日志

git log 显示当前分支的提交历史
git log --stat 显示每次提交的变更
git log -S [keyword] 根据关键词搜索提交历史

远程仓库

git remote add [name] [url] 新建远程仓库
git remote -v 显示所有远程仓库信息
git remote show [name] 显示指定远程仓库信息

还原

git checkout [file] 还原缓存区指定文件到工作区
git checkout [commit] [file] 还原指定commit的指定文件到缓存区和工作区
git checkout . 还原缓存区所有文件到工作区
git reset --hard 还原缓存区和工作区与上一次commit一致
git reset [commit] 当前分支HEAD变为指定commit, 同时重置缓存区, 但工作区不变
git reset --hard [commit] 当前分支HEAD变为指定commit, 同时重置缓存区和工作区
get reset --keep [commit] 重置当前分支HEAD为指定commit, 但缓存区和工作区都保持不变

常用组合命令

新建远程仓库连接origin，并首次推送

1 2	git remote add origin git@github:xxx/xxx.git git push -u origin -all

强制pull远程仓库覆盖本地文件

1
2
3

git fetch --all
git reset --hard origin/master
git pull