陈中正的网络日志

LeetCode: Restore IP Address

题目

https://oj.leetcode.com/problems/restore-ip-addresses/

分析

这道题和八皇后类似,采用回溯法来解决,也就是 剪枝过的DFS。

代码

class Solution
{
public:
    vector<string> restoreIpAddresses(string s)
    {
        s_ = s;
        helper("", 1, 0);

        return res_;
    }

    void helper(string ip, int segment_num, int index)
    {
        if (segment_num == 4)
        {
            string ip_segment = s_.substr(index, s_.size() - index);
            if (!ip_segment.empty() && ip_segment.length() <= 3 
                    && isValid(ip_segment))
            {
                ip += ip_segment;
                res_.push_back(ip);
            }
        }
        else
        {
            for (int i = 1; i <= 3 && i <= s_.size() - index; i++)
            {
                string ip_segment = s_.substr(index, i);
                if (isValid(ip_segment))
                    helper(ip + ip_segment + '.', segment_num + 1, index + i);
            }
        }
    }

    bool isValid(string ip_segment)
    {
        if (ip_segment[0] == '0')
            return (ip_segment == "0");
        if (stoi(ip_segment) <= 255)
            return true;
        else
            return false;
    }

private:
    string s_;
    vector<string> res_;
};

Note

  1. 一开始做的采用一种非常麻烦的方法,每一层的solution记录每个点的位置,这样一来 isValid以及最后生成IP的时候就会特别的繁琐。

简单的方法是直接在每层递归中记录一个ip_segment,这样能够省好多的代码。

  1. stoi()的参数不能为“”,也不能超出int的表示范围,否则程序会崩溃。

因此在调用stoi()之前要先检查一下参数。

  1. 像stoi()这种函数如果崩溃了,可以采用  break + display 的方法在gdb 中找出崩溃的原因。

参考

http://blog.csdn.net/u011095253/article/details/9158449

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40989329

LeetCode: LRU Cache

题目

https://oj.leetcode.com/problems/lru-cache/

分析

这道题主要考察的是数据结构的设计能力。

首先考虑用hash_map来存储数据,这样get()可以达到O(1);不过hash_map没有淘汰LRU Cache的高效办法:一种方法是每个node存放一个最近使用的时间,每次set()时遍历时找出LRU node,这样set()是O(n)的时间复杂度,而且这样设计的话每次还要计算出哪个节点和现在的时间差值最大,实现起来特别麻烦。

之前面试的时候面试官提示可以用list实现:每次把最近用到的节点放到list最前面。但是当时觉得这种方法不太好,因为get()和set()的时间复杂度都是O(n),效率实在太低。

现在来看,应该是把hash_map和链表结合起来来用,使得get()和set()都能够达到O(1)的时间复杂度:每次用到的数据添加到list最前面,每次需要淘汰数据时,淘汰list的最后面的元素。同时用hash_map记录每个key在list中的位置,这样每次要根据key查询数据时,便到hash_map中查找数据。

代码

class LRUCache
{
public:
    LRUCache(int capacity)
    {
        capacity_ = capacity;
    }

    int get(int key)
    {
        if (cache_map_.find(key) == cache_map_.end())
            return -1;
        else
        {
            //delete old node and push a new node in front of list
            int temp = cache_map_[key]->second;
            cache_.erase(cache_map_[key]);
            cache_.push_front(pair<int, int>(key, temp));
            cache_map_[key] = cache_.begin();
            return temp;
        }
    }

    void set(int key, int value)
    {
        if (cache_map_.find(key) == cache_map_.end())
        {
            if (cache_.size() >= capacity_)
            {
                //delete the last node of list
                cache_map_.erase(cache_.back().first);
                cache_.pop_back();
            }
            //push new node in front of list
            cache_.push_front(pair<int, int>(key, value));
            cache_map_[key] = cache_.begin();
        }
        else
        {
            //delete old node and push a new node in front of  list
            cache_.erase(cache_map_[key]);
            cache_.push_front(pair<int, int>(key, value));
            cache_map_[key] = cache_.begin();
        }
    }

private:
    int capacity_;
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> cache_map_;
};

Note

在写代码的过程中,犯了很多2B的错误,导致花了很久才找出错误。

  1. 在更新list中的node时,忘记了同时更新map中的数据。

  2. 错误的把list.end()当做了list最后一个节点。 list.back()才是list最后一个节点。

参考

http://fisherlei.blogspot.com/2013/11/leetcode-lru-cache-solution.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40954059

LeetCode: Partition List

题目

https://oj.leetcode.com/problems/partition-list/

分析

新建两个链表,第一个链表存放小于x的数,另一个存放大于等于x的数

从前往后遍历给定链表的每一个元素,并根据大小添加到上面创建的两个链表中。

最后把两个链表连接起来。

代码

class Solution
{
public:
    ListNode *partition(ListNode *head, int x)
    {
        struct ListNode *less = new struct ListNode(0);
        struct ListNode *equal_or_greater = new struct ListNode(0);
        struct ListNode *ph, *pl, *pe;

        ph = head;
        pl = less;
        pe = equal_or_greater;
        //partition list into the two lists
        while (ph != NULL)
        {
            if (ph->val < x)
            {
                pl->next = ph;
                pl = pl->next;
                ph = ph->next;
            }
            else
            {
                pe->next = ph;
                pe = pe->next;
                ph = ph->next;
            }
        }

        //link the two lists
        pl->next = equal_or_greater->next;
        pe->next = NULL;

        //delete first node of the two lists
        struct ListNode *temp;
        temp = less;
        less = less->next;
        delete temp;
        delete equal_or_greater;

        return less;
    }
};

Note

一开始先删除头节点然后再连接两个链表,导致结果出问题了,原因在于删除头节点可能导致一个指针失效。

正确的做法应该是先连接链表再删除头节点。

参考

http://www.cnblogs.com/springfor/p/3862392.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40925997

LeetCode: Search a 2D Matrix

题目

https://oj.leetcode.com/problems/search-a-2d-matrix/

分析

用二分查找来解决这道题:

第一次二分查找在第一列中找到那个数所在的那一行,第二次二分查找在那一行中找出那个数。

时间复杂度是O(log(m)) + O(log(n))

一开始想不出第一次二分查找应该怎么写,即找出第一个比target小的那个数,

后来看了参考中的解法才明白,二分查找退出的那一时刻,如果arr[mid] != target,那么arr[l] 是第一个比target大的数,arr[r]是第一个比target小的数。

代码

class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int h = matrix.size();
        int w = matrix[0].size();


        int l = 0;
        int r = h - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (matrix[mid][0] < target)
                l = mid + 1;
            else if (matrix[mid][0] > target)
                r = mid - 1;
            else
                return true;
        }

        int row = r;
        if (row < 0)
            return false;

        l = 0;
        r = w - 1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (matrix[row][mid] < target)
                l = mid + 1;
            else if (matrix[row][mid] > target)
                r = mid - 1;
            else
                return true;
        }
        return false;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/24216235

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40920131

LeetCode: Edit Distance

题目

https://oj.leetcode.com/problems/edit-distance/

分析

一开始没有思路,看了一些大神的解法以后才明白如何用动态规划的思路来解决这道题。

  1. 数据结构

创建一个二维数组res[][],其中res[i][j]用来代表word1[0 : i-1]和word2[0 : j-1]的EditDistance。

  1. 递归关系

考虑word1[i] == word2[j]的情况, 直接匹配即可,res[i][j] = res[i-1][j-1];

考虑word1[i] == word2[j]的情况,这种情况下分为以下多种情况来处理,然后取其中的最小值即可

      A. 用replace来处理,res[i][j] = res[i-1][j-1] + 1。这个应该很好理解,比如"abc1"和"abc2"两个字符串,res["abc1"]["abc2"] = res["abc"]["abc"] + 1。

      B. 用insert来处理,res[i][j] = res[i][j-1] + 1; 举个例子,还是"abc1"和"abc2"两个字符串,res["abc1"]["abc2"] = res["abc1"]["abc"] + 1;

      C. 用delete来处理,res[i][j] = res[i-1][j] + 1; 举个例子,还是"abc1"和"abc2"两个字符串,res["abc1"]["abc2"] = res["abc"]["abc2"] + 1; 

  1. 数据结构的初始化

因为在递归关系中用到了res[i-1][j-1],所以数据结构中的数据必然要先初始化才行,

res[i][0] = i; 代表 ""和"abc2"的EditDistance为4

res[0][i] = i; 代表 "abc1"和""的EditDistance为4

  1. 其他

在2. 递归关系中,还少考虑了一种情况,只不过为了理解起见一开始没有说,

当res[i] == res[j]时, res[i][j] 有时不能直接等于res[i-1][j-1],因为有可能用insert/delete处理的EditDistance比直接匹配的EditDistance更小,

所以res[i][j] = min(直接匹配,insert处理, delete处理), 即 res[i][j] = min(res[i-1][j-1], res[i-1][j] + 1, res[i][j-1] + 1);

代码

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> res(m + 1, vector<int>(n + 1));

        for (int i = 0; i <= m; i++)
            res[i][0] = i;
        for (int i = 0; i <= n; i++)
            res[0][i] = i;

        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                res[i][j] = min(res[i-1][j] + 1, res[i][j-1] + 1);
                if (word1[i-1] == word2[j-1])
                    res[i][j] = min(res[i][j], res[i-1][j-1]);
                else
                    res[i][j] = min(res[i-1][j-1] + 1, res[i][j]);
        }

        return res[m][n];
    }
};

参考

http://yucoding.blogspot.com/2013/09/leetcode-question-29-edit-distance.html

http://fisherlei.blogspot.com/2012/12/leetcode-edit-distance.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40894107

LeetCode: Minimum Path Sum

题目

https://oj.leetcode.com/problems/minimum-path-sum/

分析

动态规划题,

某一点的MinimumPathSum = min(左侧点的MinimumPathSum, 上侧点的MinimumPathSum) + 该点的数值

不过第一行和第一列的MinimumPathSum有些特殊,需要单独处理一下。

代码

class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> res(grid);

        //First row and first col 's Minimum Path Sum
        for (int i = 1; i < m; i++)
            res[i][0] += res[i-1][0];
        for (int i = 1; i < n; i++)
            res[0][i] += res[0][i-1];

        //Other points's Minimum Path Sum
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                res[i][j] += min(res[i-1][j], res[i][j-1]);

        return res[m-1][n-1];
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40868907

LeetCode: Unique Paths II

题目

https://oj.leetcode.com/problems/unique-paths-ii/

分析

这道题是Unique Paths的变形,只是稍微复杂了一点。

1.

在Unique Paths中, paths[i][j] = paths[i-1][j] + paths[i][j-1];

在Unique Paths II中,在这句之前要加一个判断语句来判断obstacleGrid[i][j]的值是否为1,如果是1则将paths[i][j]直接赋值为0

  1. 仅仅做完第一步还不行,原本第一行都为1,

现在如果第一行某个元素是obstacle,那么这一行该元素及其之后的元素路径数都为0,为什么呢?

因为要想如Unique Paths中所说路径长度达到最小,那么第一行obstacle之后的元素必然不能走。

第一列也是同样的道理。

代码

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
    {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> paths(m, vector<int>(n, 1));

        int firstRowFirstObstacle = -1;
        int firstColFirstObstacle = -1;
        //get first obstacle position in first col and first row 
        for (int i = 0; i < m; i++)
            if (obstacleGrid[i][0] == 1)
            {
                firstColFirstObstacle = i;
                break;
            }
        for (int i = 0; i < n; i++)
            if (obstacleGrid[0][i] == 1)
            {
                firstRowFirstObstacle = i;
                break;
            }

        //assign 0 where firstObstacle and after that in first row and col
        if (firstColFirstObstacle != -1)
            for (int i = firstColFirstObstacle; i < m; i++)
                paths[i][0] = 0;
        if (firstRowFirstObstacle != -1)
            for (int i = firstRowFirstObstacle; i < n; i++)
                paths[0][i] = 0;

        //calculate paths
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (obstacleGrid[i][j] == 1)
                {
                    paths[i][j] = 0;
                    continue;
                }
                paths[i][j] = paths[i-1][j] + paths[i][j-1];
            }
        }

        return paths[m-1][n-1];
    }
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40865761

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40866417

LeetCode: Unique Paths

题目

https://oj.leetcode.com/problems/unique-paths/

分析

一开始没弄懂题意,存在一些问题:能不能走重复的路径?路径长度是否要求为最短的?

后来看了一些答案才明白,题目的隐含要求是,在走最短的路径的前提下,求不同路径数目。

这样一来题目就简单了,  某一点的不同路径数 = 左侧点的不同路径数 + 上侧点的不同路径数

可以用递归来求解,但这样效率底下,需要动态规划的方法来解决。

代码

class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        vector<vector<int>> paths(m, vector<int>(n, 1));

        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                paths[i][j] = paths[i-1][j] + paths[i][j-1];

        return paths[m-1][n-1];
    }
};

参考

http://blog.csdn.net/kenden23/article/details/17303497

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40865761

LeetCode: N-Queens II

题目

https://oj.leetcode.com/problems/n-queens-ii/

分析

N-Queens这道题解法一样,略作修改即可。

代码

class Solution
{
public:
    int totalNQueens(int n)
    {
        vector<int> solution(n);
        helper(solution, 0, n);

        return res;
    }
    void helper(vector<int> &solution, int row, int n)
    {
        if (row == n)
            res++;
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (isValid(solution, row, i))
                {
                    solution[row] = i;
                    helper(solution, row + 1, n);
                }
            }
        }
    }
    bool isValid(vector<int> &solution, int row, int col)
    {
        for (int i = 0; i < row; i ++)
            if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
                return false;
        return true;
    }

private:
    int res = 0;
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40686105

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40711959

LeetCode: N-Queens

题目

https://oj.leetcode.com/problems/n-queens/

分析

  1. 这道题采用的是回溯法,跟DFS非常类似,只不过是在DFS的递归前加一个判断。

  2. 关于如何表示结果。

可以采用一个N*N二维数组来存放结果,但是我们可以采用更好的办法:经过观察我们可以发现,每一行必然有一个皇后,因此我们可以用一个一维数组来表示结果,solution[0]=3 代表第0行的皇后放在第三列, solution[1]=5 代表第1行的皇后放在第5列,……以此类推。

  1. 关于如何判断一种结果是否合法。

题目要求任意两个皇后不能在同一行、同一列或者用一斜线上,在2中我们已经提过了用一维数组solution[n]来表示结果,任两个皇后肯定不在同一行,判断第i行和第j行的皇后是否同一列可以用 solution[i] == solution[j]来判断;如何判断第i行皇后和第j行皇后是否在同一斜线上呢?可以用 abs(i-j) == abs(solution[i] - solution[j]) 来判断。

代码

class Solution
{
public:
    vector<vector<string>> solveNQueens(int n)
    {
        vector<int> solution(n);
        helper(solution, 0, n);

        return res;
    }

    void helper(vector<int>& solution, int row, int n)
    {
        if (row == n)
        {
            vector<string> solution_2d(n, string(n, '.'));
            for (int i = 0; i < n; i++)
                solution_2d[i][solution[i]] = 'Q';

            res.push_back(solution_2d);
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                if (isValid(solution, row, i))
                {
                    solution[row] = i;
                    helper(solution, row + 1, n);
                }
            }
        }
    }

    bool isValid(vector<int>& solution, int row, int col)
    {
        for (int i = 0; i < row; i++)
            if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
                return false;
        return true;
    }

private:
    vector<vector<string>> res;
};

参考

http://www.cnblogs.com/TenosDoIt/p/3801621.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40686105

LeetCode: Multiply Strings

题目

https://oj.leetcode.com/problems/multiply-strings/

分析

大数乘法,不能直接相乘,因为会溢出。

首先两个乘数的各位之间两两相乘,得到多个同一列结果相加,

然后对结果进行进位。

如 25 × 25 = 625

                      2                5

     ×               2                5

————————————————————

                     10             25

          4         10

————————————————————

          4         20             25

————————————————————

          6           2              5

代码

class Solution
{
public:
    string multiply(string num1, string num2)
    {
        vector<int> temp_res(num1.size() + num2.size(), 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());

        for (int i = 0; i < num1.size(); i++)
            for (int j = 0; j < num2.size(); j++)
                temp_res[i + j] += (num1[i]-'0') * (num2[j]-'0');

        int carry = 0;
        for (int i = 0; i < temp_res.size(); i++)
        {
            int temp = temp_res[i] + carry;
            temp_res[i] = temp % 10;
            carry = temp / 10;
        }

        for (int i = temp_res.size() - 1; i >= 0; i--)
        {
            if (temp_res[i] != 0)
                break;
            temp_res.pop_back();
        } 
        reverse(temp_res.begin(), temp_res.end());
        string res;
        for (int i = 0; i < temp_res.size(); i++)
            res += temp_res[i] + '0';

        return res.size() != 0 ? res : string("0");
    }
};

参考

http://www.cnblogs.com/TenosDoIt/p/3735309.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40604889

LeetCode: Combination Sum II

题目

https://oj.leetcode.com/problems/combination-sum-ii/

分析

这道题是Combination Sum的变形,也是采用DFS的思路,但相比之下要注意两点:

  1. 因为不能重复,所以在进进行DFS递归时,要直接从当前位置的下一个位置开始进行“试探”。

  2. 若num中存在两个相同的元素,为了防止结果中重复出现,只有在第一个元素被选中的情况下,第二个元素才进行“试探”,否则不进行“试探”。

代码

class Solution
{
public:
    vector<vector<int>> combinationSum2(vector<int> &num, int target)
    {
        vector<int> solution;
        this->num = num;
        sort(this->num.begin(), this->num.end());

        DFS(solution, target, 0);

        return res;
    }

    void DFS(vector<int> &solution, int target, int start)
    {
        if (target == 0)
        {
            res.push_back(solution);
        }
        else
        {
            for (int i = start; i < num.size() && num[i] <= target; i++)
            {
                if (i > 0 && num[i] == num[i-1] && num[i-1] != solution.back())
                    continue;
                solution.push_back(num[i]);
                DFS(solution, target - num[i], i + 1);
                solution.pop_back();
            }
        }
    }

private:
    vector<int> num;
    vector<vector<int>> res;
};

参考

http://blog.csdn.net/timberwolf_2012/article/details/40479161

http://www.cnblogs.com/remlostime/archive/2012/10/29/2745125.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40509643

LeetCode: Combination Sum

题目

https://oj.leetcode.com/problems/combination-sum/

分析

DFS,之前总结过很多道同类型的题。

代码

class Solution
{
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        if (candidates.size() == 0)
            return res;
        this->candidates = candidates;
        sort(this->candidates.begin(), this->candidates.end());
        vector<int> solution;

        DFS(solution, 0, target);

        return res;
    }
    void DFS(vector<int> &solution, int start, int target)
    {
        if (target == 0)
            res.push_back(solution);
        else
        {
            for (int i = start; i < candidates.size() && candidates[i] <= target; i++)
            {
                solution.push_back(candidates[i]);
                DFS(solution, i, target-candidates[i]);
                solution.pop_back();
            }
        }
    }
private:
    vector<int> candidates;
    vector<vector<int>> res;
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40479161

LeetCode: Search for a Range

题目

https://oj.leetcode.com/problems/search-for-a-range/

分析

时间复杂度O(log n), 多半便是二分查找的题目。

题目要求找出一个范围,无非就是找到一个起始点和一个终止点,通过两次二分查找找到起始点和终止点即可。

起始点的特点是,等于target,而且它左侧没有target了或者它是数组第一个数。

终止点的特点是,等于target,而且它右侧没有target了或者它是数组最后一个数。

P.S. 标准二分查找代码可以查看这里

代码

class Solution
{
public:
    vector<int> searchRange(int A[], int n, int target)
    {
        vector<int> res;
        int l, r, m;

        l = 0;
        r = n - 1;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if ((A[m]==target) && (m==0 || A[m-1]!=target))
            {
                res.push_back(m);
                break;
            }
            else if (A[m] > target || A[m-1] == target)
                r = m - 1;
            else
                l = m + 1;
        }
        if (res.size() == 0)
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }

        l = 0;
        r = n - 1;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if ((A[m]==target) && (m==n-1 || A[m+1]!=target))
            {
                res.push_back(m);
                break;
            }
            else if (A[m] < target || A[m+1] == target)
                l = m + 1;
            else 
                r = m - 1;
        }
        return res;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40477301

LeetCode: Search in Rotated Sorted Array II

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/

分析

这道题是Search in Rotated Sorted Array的变形,因为有重复元素的存在,之前的方法就不不能直接用了,比如在{1, 3, 1, 1, 1}中寻找3, 结果就会出错。

出错的原因在于因为重复元素的存在,A[m]==A[l]时就不能确定在中点的哪一边是有序的,那就不能砍掉一半的查找范围了。

解决的办法是将左边界向右移动,直至A[m]!=A[l],这样一来在最坏情况下时间复杂度会变为O(n)。

源码

class Solution
{
public:
    bool search(int A[], int n, int target)
    {
        int l = 0;
        int r = n - 1;
        int m;

        while (l <= r)
        {
            m = (l + r) >> 1;
            if (A[m] == target)
                return true;
            else
            {
                if (A[m] == A[l])
                    l++;
                else if (A[m] > A[l])
                {
                    if (target >= A[l] && target < A[m])
                        r = m - 1;
                    else
                        l = m + 1;
                }
                else
                {
                    if (target > A[m] && target <= A[r])
                        l = m + 1;
                    else
                        r = m - 1;
                }
            }
        }
        return false;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/20588511

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40156301

LeetCode: Search in Rotated Sorted Array

题目

https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

分析

还是运用二分的思想, 每次循环判断target在中点的左侧还是右侧,每次砍掉一半的查找范围, 直到得到最终结果。

在这个过程中用到的一个重要规律是: 

一个数字序列经过rotate之后, 以中间那个数字为边界, 一定一边是有序序列, 一边是 rotated有序序列(证明略)。

如何判断哪边是有序的呢? 如果中点大于左边界, 则左侧是有序序列, 否则右侧是有序序列。

分别用 l代表左边界, r代表右边界, m代表中间那个数,

如果A[m] == target, 则直接返回m即可。

如果A[m] >= A[l] ,说明左侧是有序序列

       如果target在左侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在右侧序列中, 则把 右边界r 设为 m-1

否则, 右侧是有序序列

       如果target在右侧有序序列范围内, 则把 左边界l 设为 m+1

       否则target在左侧有序序列范围内, 则把 右边界r 设为 m-1

 

P.S. 标准二分查找代码可以查看这里

代码

class Solution
{
public:
    int search(int A[], int n, int target)
    {
        if (n <= 0)
            return -1;
        int l = 0;
        int r = n - 1;
        int m;

        while (l <= r)
        {
            m = (l + r) / 2;
            if (A[m] == target)
                return m;
            else if (A[l] < A[m])
            {
                if (A[l] <= target && target <= A[m-1])
                    r = m - 1;
                else
                    l = m + 1;
            }
            else
            {
                if (A[m+1] <= target && target <= A[r])
                    l = m + 1;
                else
                    r = m - 1;
            }
        }
        return -1;
    }
};

参考

http://blog.csdn.net/linhuanmars/article/details/20525681

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39860279

LeetCode: Divide Two Integers

题目

https://oj.leetcode.com/problems/divide-two-integers/

分析

  1. 题目要求实现除法运算且不能用乘除和取余运算, 一开始想用的递减计数的方式, 显然这种方法效率太低了, 从而导致超时。

不能用乘除和取余如何快速的逼近结果呢? 答案是采用移位运算, 以指数的形式增长, 快速逼近最终的结果。

举例来说明, 137 / 7 = 19如何用移位运算来快速得到最终结果呢?

           135 - 7 × 2 ^ 4 = 23    > 7

           23   - 7 * 2 ^ 1  = 9      > 7

           9     - 7 * 2 ^ 0  = 2      <  7    停止运算

最终结果    24 + 21 + 20 = 19

  1.  为了防止溢出, 将int型参数隐式转换为long long型参数。

代码

class Solution
{
public:
    int divide(long long dividend, long long divisor)
    {
        int res = 0;
        int sign = (dividend>0 && divisor>0) || (dividend<0 && divisor<0);
        dividend = dividend > 0 ? dividend : -dividend;
        divisor = divisor > 0 ? divisor : -divisor;

        while (dividend >= divisor)
        {
            long long res_temp = 1;
            while (res_temp * divisor <= dividend)
                res_temp <<= 1;
            res_temp >>= 1;
            res += res_temp;
            dividend -= res_temp * divisor;
        }
        return sign ? res : -res;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39558059

LeetCode: Remove Duplicates from Sorted Array

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/

分析

从前向后遍历, 如果该元素不和前面元素重复, 就该元素排到前面。

代码

class Solution
{
public:
    int removeDuplicates(int A[], int n)
    {
        if (n < 1) 
            return n;
        int count = 1;
        for (int i = 1; i < n; i++)
            if (A[i] != A[i-1])
                A[count++] = A[i];
        return count;
    }
};

参考

http://blog.csdn.net/xudli/article/details/8423225

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39544993

LeetCode: Remove Duplicates from Sorted List II

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

分析

  1. 双指针来实现, 左侧的指针指向上一个有效结点, 右侧的指针进行试探, 直到找出有效结点后和左侧的指针连接起来。

  2. 由于链表第一个结点可能被删除掉, 所以左侧指针初始化为头结点的前一个指针。

代码

class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        if (head == NULL)
            return head;

        ListNode *pre_head = new ListNode(0);
        pre_head->next = head;

        ListNode *pl, *pr;
        pl = pre_head;
        pr = head;
        while (pr != NULL)
        {
            if (pr->next != NULL && pr->val == pr->next->val)
            {
                pl = pl->next;
                pr = pr->next;
            }
            else
            {
                while (pr->next != NULL && pr->val == pr->next->val)
                {
                    ListNode *temp = pr;
                    pr = pr->next;
                    delete temp;
                }
                pr = pr->next;
            }
        }

        ListNode *temp = pre_head;
        pre_head = pre_head->next;
        delete temp;
        return pre_head;
    }
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-remove-duplicates-from-sorted.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39544599

LeetCode: Remove Duplicates from Sorted List

题目

https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/

分析

从前向后遍历即可

代码

class Solution
{
public:
    ListNode *deleteDuplicates(ListNode *head)
    {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *p = head;
        while (p != NULL && p->next != NULL)
        {
            if (p->val == p->next->val)
            {
                ListNode *temp = p->next;
                p->next = p->next->next;
                delete temp;
            }
            else
                p = p->next;
        }
        return head;
    }
};

参考

http://www.programcreek.com/2013/01/leetcode-remove-duplicates-from-sorted-list/

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39456291