剑指offer（三）

剑指offer刷题(一)——二维数组中的查找

题目

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

思路

首先选取数组中右上角的数字.如果该数字等于要查找的数字,查找过程结束.如果该数字大于要查找的数组,剔出这个数字所在的列;如果该数字小于要查找的数字,剔出这个数字所在的行.也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列,这样每一步都可以缩小查找的范围,直到找到要查找的数字,或者查找范围为空.

举例

如果在一个二维数组中找到数字7，则返回true，如果没有找到，则返回false。

C++

#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
    bool find(int target,vector<vector<int>> a){
        int rows= a.size();
        int cols=a[0].size();
        if(!a.empty()&&rows>0&&cols>0){
            int row=0;
            int col=cols-1;
            while(row<rows&&col>=0){
                if(a[row][col]==target){
                    return true;
                }
                else if(a[row][col]>target){
                    --col;
                }
                else{
                    ++row;
                }
            }
        }
        return false;
    }
};
int main(){
    int M=4;
    int N=4;
    int arr[4][4]={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
    vector<vector<int>> A(M);
    for(int i=0;i<M;i++)
        A[i].resize(N);
    for(int i=0;i<M;i++)
    {
        for(int j=0;j<N;j++){
            A[i][j]=arr[i][j];
        }
    }
    Solution s;
    bool b;
    b=s.find(6,A);
    cout<< boolalpha<<b;
    return 0;

}

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array) - 1
        cols= len(array[0]) - 1
        i = rows
        j = 0
        while j<=cols and i>=0:
            if target<array[i][j]:
                i -= 1
            elif target>array[i][j]:
                j += 1
            else:
                return True
        return False

从左下角开始找,如果target比该元素小则网上找,如果target比该元素大则往右找

剑指offer刷题(二)——替换空格

题目

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

思路

先统计空格数,然后确定变换后的长度.从原字符串的尾部开始,将原字符串的非空格字符复制到相应的位置,空格字符替换成指定字符.

C++

#include<iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;

class Solution{
public:
    char* replaceSpace(char*str,int length){
        int num=0;
        int i=0;
        while(str[i]!='\0')
        {
            if(str[i]==' ')
                num++;
            i++;
        }
        int final_length=length+2*num;
        int index=length-1;
        int index_new=final_length-1;
        while(index>=0&&index_new>=index){
            if(str[index]==' '){
                str[index_new]='0';
                str[index_new-1]='2';
                str[index_new-2]='%';
                index_new=index_new-2;
            }
            else{
                str[index_new]=str[index];
            }
            index_new--;
            index--;
        }



    }

};
int main(){
    char str[80];
    strcpy(str,"We are happy.");
    Solution s;
    s.replaceSpace(str,14);
    cout<<str;
return 0;
}

Python

class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        Ls=list(s)
        Out=''
        for ss in Ls:
            if(ss==' '):
                ss='%20'
            Out=Out+ss
        return Out

剑指offer刷题(三)——从尾到头打印链表

题目

输入一个链表，返回一个反序的链表。

思路

如果我们不希望修改原链表结构,返回一个反序列表,即”后进先出”,这类似于栈的顺序.我们就可以使用栈的结构来完成该任务.

C++

#include<iostream>
using namespace std;
#include<vector>
#include<stack>
struct ListNode{
    int val;
    struct ListNode *next;
    ListNode(int x):val(x),next(NULL){}

};

class Solution{
public:
    vector<int>printListFromTailToHead(ListNode*head){
        stack<int> nodes;
        vector<int> result;
        ListNode* node=head;
        while(node!=NULL){
            nodes.push(node->val);
            node=node->next;
        }
        while(!nodes.empty()){
            result.push_back(nodes.top());
            nodes.pop();
        }
        return result;



    }


};

int main(){
    int a[10]={1,2,3,4,5,6,7,8,9,10};
    ListNode *L;
    L=new ListNode(a[0]);
    ListNode *r;
    r=L;
    for(int i=1;i<10;i++){
        ListNode *p;
        p=new ListNode(a[i]);
        cout<<r->val<<" ";
        r->next=p;
        r=r->next;
    }
    Solution s;
    vector<int>v(10);
    v=s.printListFromTailToHead(L);
    for(int i=0;i<11;i++){
        cout<<v[i]<<endl;
    }
    return 0;
}

Python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def swap(self,pre,post):
        post.next=pre

    def printListFromTailToHead(self, listNode):
        # write code here
        if(listNode==None):
            return []

        head=listNode
        post=head.next
        head.next=None

        while(post!=None):
            postnext=post.next
            self.swap(head,post)
            head=post
            post=postnext
        L=[]
        while(head!=None):
            L.append(head.val)
            head=head.next
        return L

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def swap(self,pre,post):
        post.next=pre

    def printListFromTailToHead(self, listNode):
        # write code here
        if(listNode==None):
            return []

        head=listNode
        post=head.next
        head.next=None

        while(post!=None):
            postnext=post.next
            self.swap(head,post)
            head=post
            post=postnext
        L=[]
        while(head!=None):
            L.append(head.val)
            head=head.next
        return L