liuchuo – 第155页 – 我不管，反正我最萌～

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;

}

};

LeetCode 127. Word Ladder

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

题目大意：给出beginWord、endWord和一个字典，找到从beginWord到endWord的最短转换序列，转换要求是：1.每次只能改变一个字母～ 2.变换过程中的中间单词必须在字典中出现～（第一个beginWord不需要出现，最后一个endWord需要在字典中出现～）

分析：用广度优先搜索～先将beginWord放入队列中，然后将队列中的每一个单词从头到尾换26个字母一遍～如果换后的单词在字典中能找到～而且没有被访问过～（如果每次都找访问过的就死循环啦，不停的变来变去变同一个咋办～）那就将这个单词放入队列中继续变换～直到有一次发现在字典中找到单词的时候，这个单词恰好是endWord为止～
因为要返回路径长度～所以在队列中放一个string和int组成的pair一对～这样的话用string表示单词，int表示变换到当前单词的路径～比如startWord就是1～之后每次加1～因为题目给的是vector～把他们所有单词先放到dict的set集合中查找单词会方便很多～visit标记当前单词是否被访问过～

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        set<string> dict, visit;
        for(int i = 0; i < wordList.size(); i++)
            dict.insert(wordList[i]);
        queue<pair<string, int>> q;
        q.push(make_pair(beginWord, 1));
        while(!q.empty()) {
            pair<string, int> temp = q.front();
            q.pop();
            string word = temp.first;
            for(int i = 0; i < word.length(); i++) {
                string newword = word;
                for(int j = 0; j < 26; j++) {
                    newword[i] = 'a' + j;
                    if(dict.find(newword) != dict.end() && visit.find(newword) == visit.end()) {
                        if(newword == endWord)
                            return temp.second + 1;
                        visit.insert(newword);
                        q.push(make_pair(newword, temp.second + 1));
                    }
                }
            }
        }
        return 0;
    }
};

class Solution {

public:

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {

set<string> dict, visit;

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

dict.insert(wordList[i]);

queue<pair<string, int>> q;

q.push(make_pair(beginWord, 1));

while(!q.empty()) {

pair<string, int> temp = q.front();

q.pop();

string word = temp.first;

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

string newword = word;

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

newword[i] = 'a' + j;

if(dict.find(newword) != dict.end() && visit.find(newword) == visit.end()) {

if(newword == endWord)

return temp.second + 1;

visit.insert(newword);

q.push(make_pair(newword, temp.second + 1));

}

return 0;

}

};

LeetCode 307. Range Sum Query – Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

题目大意：给一个整型数组，当调用sumRange(i, j)的时候返回i～j之间的元素的总和，当调用update(i, val)的时候将nums[i]的值更新为val

分析：本来想用sum[]数组标记和，然后更新sum[]直接返回的，结果还是意料之中的超时了。。用树状数组的方法可以解决～

解释：树状数组本质上是按照二分对数组进行分组，维护和查询都是O(lgn)的复杂度
树状数组与线段树：树状数组和线段树很像，但能用树状数组解决的问题，基本上都能用线段树解决，而线段树能解决的树状数组不一定能解决。相比较而言，树状数组效率要高很多～关于lowbit：lowbit = x & (-x), lowbit(x)也可以理解为能整除x的最大的2的幂次，如果要求[x, y]之内的数的和，可以转换成getsum(y) – getsum(x – 1)来解决～

class NumArray {
public:
    NumArray(vector<int> nums) {
       size = nums.size();
       num = vector<int>(size + 1, 0);
       sum = vector<int>(size + 1, 0);
       for(int i = 0;i < size; i++)
           update(i, nums[i]); 
    }
    
    void update(int i, int val) {
        int old = num[i+1];
        for(int j = i + 1;j <= size; j += (j & (-j)))
            sum[j] = sum[j] - old + val;
        num[i+1] = val;
    }
    
    int sumRange(int i, int j) {
        return getSum(j + 1) - getSum(i);
    }
private:
    int getSum(int k) {
        int result = 0;
        for(int i = k;i > 0;i -= (i & (-i)))
            result += sum[i];
        return result;
    }
    int size;
    vector<int> sum, num;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

class NumArray {

public:

NumArray(vector<int> nums) {

size = nums.size();

num = vector<int>(size + 1, 0);

sum = vector<int>(size + 1, 0);

for(int i = 0;i < size; i++)

update(i, nums[i]);

}

void update(int i, int val) {

int old = num[i+1];

for(int j = i + 1;j <= size; j += (j & (-j)))

sum[j] = sum[j] - old + val;

num[i+1] = val;

}

int sumRange(int i, int j) {

return getSum(j + 1) - getSum(i);

}

private:

int getSum(int k) {

int result = 0;

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

result += sum[i];

return result;

}

int size;

vector<int> sum, num;

};

/**

* Your NumArray object will be instantiated and called as such:

* NumArray obj = new NumArray(nums);

* obj.update(i,val);

* int param_2 = obj.sumRange(i,j);

LeetCode 130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

题目大意：给一个地图，X表示围墙，找出所有被X围墙包围的O，并且把被包围的O替换成X～

分析：我的方法是与其找被包围的O，不如反过来寻找没有被包围的O～从地图的外围一圈开始寻找～如果当前位置是O～那就找他的上下左右～把与这个O联通的所有O都标记为”*”～标记为*后，所有没有被标记为*的O就是被包围的O～那就将所有剩余的O标记为X，把所有*标记为O～返回这张地图就可以了～

class Solution {
private:
    int m, n;
public:
    void solve(vector<vector<char>>& board) {
        if(board.size() == 0) return ;
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++) {
            dfs(i, 0, board);
            dfs(i, n - 1, board);
        }
        for(int j = 0; j < n; j++) {
            dfs(0, j, board);
            dfs(m - 1, j, board);
        }
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == '*')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
    void dfs(int row, int col, vector<vector<char>>& board) {
        if(board[row][col] != 'O') return;
        board[row][col] = '*';
        if(row - 1 > 0) dfs(row - 1, col, board);
        if(col - 1 > 0) dfs(row, col - 1, board);
        if(row + 1 < m) dfs(row + 1, col, board);
        if(col + 1 < n) dfs(row, col + 1, board);
    }
};

class Solution {

private:

int m, n;

public:

void solve(vector<vector<char>>& board) {

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

m = board.size(), n = board[0].size();

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

dfs(i, 0, board);

dfs(i, n - 1, board);

}

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

dfs(0, j, board);

dfs(m - 1, j, board);

}

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

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

if(board[i][j] == '*')

board[i][j] = 'O';

else if(board[i][j] == 'O')

board[i][j] = 'X';

}

void dfs(int row, int col, vector<vector<char>>& board) {

if(board[row][col] != 'O') return;

board[row][col] = '*';

if(row - 1 > 0) dfs(row - 1, col, board);

if(col - 1 > 0) dfs(row, col - 1, board);

if(row + 1 < m) dfs(row + 1, col, board);

if(col + 1 < n) dfs(row, col + 1, board);

}

};

LeetCode 166. Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

For example,

Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.
Hint:

No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

题目大意：给定两个整型数分子和分母，以小数的形式返回它们的结果，当有循环小数时，将循环的部分用括号括起来～

分析：先忽略符号，为了防止溢出，转换为long型的a和b，以绝对值形式求a/b的结果：a/b的结果是结果的整数部分，如果余数r = a % b不等于0，说明还有小数部分～
用map标记余数r应该在string result的哪个位置，如果map[r]不为0说明出现过，那么就在m[r]（出现的位置）的前面添加一个(，在result结尾添加一个)，表示这部分会循环～

注意点：1.如果除数等于0，直接返回0，为了避免出现返回-0的情况～2.如果(numerator < 0) ^ (denominator < 0)等于1，说明他们一正一负，结果是负数，所以要在result的第一位添加一个“-”。3.如果一开始的r不等于0，说明有小数部分，则在计算小数部分之前添加一个”.”

class Solution {
public:
    string fractionToDecimal(int numerator, int denominator) {
        if(numerator == 0) return "0";
        string result = "";
        if(((numerator < 0) ^ (denominator < 0)) == 1)
            result += '-';
        long a = abs((long)numerator), b = abs((long)denominator);
        result += to_string(a / b);
        long r = a % b;
        if(r != 0) result += '.';
        map<int, int> m;
        while(r != 0) {
            if(m[r] != 0) {
                result.insert(m[r], 1, '(');
                result += ')';
                break;
            }
            m[r] = result.size();
            r = r * 10;
            result += to_string(r / b);
            r = r % b;
        }
        return result;
        
    }
};

class Solution {

public:

string fractionToDecimal(int numerator, int denominator) {

if(numerator == 0) return "0";

string result = "";

if(((numerator < 0) ^ (denominator < 0)) == 1)

result += '-';

long a = abs((long)numerator), b = abs((long)denominator);

result += to_string(a / b);

long r = a % b;

if(r != 0) result += '.';

map<int, int> m;

while(r != 0) {

if(m[r] != 0) {

result.insert(m[r], 1, '(');

result += ')';

break;

}

m[r] = result.size();

r = r * 10;

result += to_string(r / b);

r = r % b;

}

return result;

}

};

LeetCode 29. Divide Two Integers

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题目大意：不用乘法、除法、取余操作，将两个数相除，如果它溢出了，返回MAX_INT～

分析：我用了减法和log函数。。就是e的(loga-logb)次方等于e的log(a/b) = a/b。。。。这应该不算投机取巧吧？。。。～

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(divisor == 0 || dividend == INT_MIN && divisor == -1) return INT_MAX;
        int sign = ((dividend >> 31) ^ (divisor >> 31)) == 0 ? 1 : -1;
        long a = abs((long)dividend);
        long b = abs((long)divisor);
        double c = exp(log(a) - log(b)) + 0.0000000001;
        return (int)(sign * c);
    }
};

class Solution {

public:

int divide(int dividend, int divisor) {

if(divisor == 0 || dividend == INT_MIN && divisor == -1) return INT_MAX;

int sign = ((dividend >> 31) ^ (divisor >> 31)) == 0 ? 1 : -1;

long a = abs((long)dividend);

long b = abs((long)divisor);

double c = exp(log(a) - log(b)) + 0.0000000001;

return (int)(sign * c);

}

};