牛客网刷题总结-剑指offer(1)

说在前面:刷题真的是一件残酷的事情,就好比以前大学的时候只剩两天就考试了,刚刚看了一遍就开始先做题一样的感觉,面对无数的套路,幸运的时候还能庆幸自己能发现他们的套路。。 刷题的开始总是艰难的,希望有一天我能以上帝视角看清这些芸芸众生的时候,还能想起来当年我不止一次的一道题怼了一晚上照样白怼。

T1:二维数组的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

这里一般的思路肯定是,从行或者列开始找,根据递增的顺序,找到行或者列之后再判断列或者行,知道找到为止。最好的方法是,从左下角或者右上角开始找。原因是:这样的一行和一列的顺序是不一样的,这样我们找一行的时候没有就可以直接找下一行,充分利用递增的顺序,减少循环的次数。 其他的就是循环的写法了,关于数组,一定注意的是不要越界,这真的是我的痛啊,日常越界一百遍。^^_

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        bool found=false;
        if(array.size()==0 ||array[0].size()==0)
            return found;
        for(int i=array[0].size()-1;i>=0;--i){
            if(target>=array[0][i]){
                for(int j=0;j!=array.size();++j){
                    if(target==array[j][i])
                        found=true;
                }
            }
            else
                continue;
        }
        return found;
    }
};

T2:替换空格

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

替换的过程是,先找到这个空格,正常想法是,从前往后找,然后遇到就开始替换。但是注意到对于一般题目,最直观的解法总不是最好的,都是需要多从时间复杂度和空间复杂度想一想。就这个题目而言,直接从前往后替换,因为替换后的字符比原来多2个,所以每次替换我们都需要将后面的字符串向后移2个,这无疑会增加复杂度。一个很好的办法是:先统计空格的个数,计算出替换后的字符串长度,然后从后往前开始替换,这样就减少了移动的复杂度。
class Solution {
public:
    void replaceSpace(char *str,int length) {
        if(length<=0)
            return;
        int move_length=0;
        int original_length=0;
        for(int i=0;str[i]!='\0';++i){
            ++original_length;
            if(str[i]==' ')
                ++move_length;
        }
        int new_length=original_length+2*move_length;
        if(new_length>length)
            return;
        str[new_length]='\0';
        while(original_length>0){
            --original_length;
            if(str[original_length]==' '){
                str[--new_length]='0';
                str[--new_length]='2';
                str[--new_length]='%';
            }
            else
                str[--new_length]=str[original_length];
        }
    }
};

T3:从尾到头打印链表

输入一个链表,从尾到头打印链表每个节点的值。

链表我们一般都是从头到尾处理的,要从尾到头打印,这里想到一个数据结构:,后入先出的特点。从头到尾遍历链表,并把节点的值存入栈中,再从栈一一弹出即可。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        stack<int> stack;
        vector<int> result;
        while(head!=nullptr){
            stack.push(head->val);
            head=head->next;
        }
        while(stack.size()!=0){
            result.push_back(stack.top());
            stack.pop();
        }
        return result;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏窗户

有限域(3)——多项式环的商环构造有限域

  接着上两章内容,我们还是得继续寻找有限域的构造方法。上章证明矩阵环是个单环,自然是没戏了,但我们还可以考虑多项式环。

33420
来自专栏决胜机器学习

《编程之美》读书笔记(一)——中国象棋将帅有效位置

《编程之美》读书笔记(一) ——中国象棋将帅有效位置 (原创内容,转载请注明来源,谢谢) 一、问题 ? 如上述棋盘,假设将为点A,帅为点B。将只能在d10...

42360
来自专栏大数据学习笔记

Java程序设计(Java9版):第3章 流程控制

第3章 流程控制 学习要点 掌握三种流程控制 掌握简单的输入输出 了解三种循环设计方法 掌握数组、字符串和枚举类型 3.1 面向过程介绍...

38770
来自专栏ACM算法日常

独角兽与数列(置换群循环)- HDU 4985

群论是法国数学家伽罗瓦(Galois)的发明。伽罗瓦是一个极具传奇性的人物,年仅21岁就英年早逝于一场近乎自杀的决斗中。他用该理论,具体来说是伽罗瓦群,解决了五...

9130
来自专栏技术之路

算法时间复杂度

     算法复杂度分为时间复杂度和空间复杂度,一个好的算法应该具体执行时间短,所需空间少的特点。      随着计算机硬件和软件的提升,一个算法的执行时间是算...

18860
来自专栏take time, save time

你所能用到的数据结构(五)

七、骚年,这就是你的终极速度了吗? 在介绍了前面的几个排序算法之后,这一次我准备写写快速排序,快速排序之所以叫快速排序是因为它很快,它是已知实践中最快的排序算...

28250
来自专栏追不上乌龟的兔子

[多少懂点位运算】续·一行代码解决LeetCode268缺失数字

给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

17740
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继...

9610
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

35750
来自专栏落影的专栏

程序员进阶之算法练习(三十三)LeetCode专场

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址。 今天继续Lee...

12310

扫码关注云+社区

领取腾讯云代金券