剑指 offer

前言

本文内容是《剑指 Offer》的问题求解整理，使其文档化，主要包括问题的代码编写（主流语言）和思路分析。
文章结构按照10小题为一章节来划分，每一小题的编程语言的实现一般按照【低级语言》脚本语言》高级语言】的格式来展示。
引用别人的一句话“我们不生产代码，我们是代码的搬运工”。
文章内容仅供参考。

1~10

二维数组的查找

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

   <?php

function Find($target, $array)
{
    foreach($array as $key=>$val){
        if(in_array($target,$val)){
            return "true";
        }
    }
    return "false";
}
while(fscanf(STDIN,"%d,%s",$a,$b) == 2){
    $target = $a;
    eval('$array='.$b.';');
    try{
        echo Find($target,$array)."n";
    }catch(Exception $e){
        die;
    }
}

   public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;
        int cols = array[0].length;
        int i=rows-1,j=0;
        while(i>=0 && j<cols){
            if(target<array[i][j])
                i--;
            else if(target>array[i][j])
                j++;
            else
                return true;
        }
        return false;
    }
}

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

   class Solution
{
    public bool Find(int target, int[][] array)
    {
        int row=0;
        int col=array[0].Length-1;
        while(row<=array.Length-1&&col>=0){
            if(target==array[row][col])
                return true;
            else if(target>array[row][col])
                row++;
            else
                col--;
        }
        return false;

    }
}

解题思路
矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，因此从左下角开始查找，当要查找数字比左下角数字大时。右移要查找数字比左下角数字小时，上移。

替换空格
- 题目描述
  请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
```
   <?php
// 直接使用函数
function replaceSpace($str)
{
    return str_replace(' ','%20',$str);
}
// 不允许直接调用内置函数
<?php
function replaceSpace($str)
{
    $res = '';
    $strLength = strlen($str);
    for($i=0;$i<$len;$i++){
        if($str[$i]==' '){
                $res .='%20';
        }else{
                $res .=$str[$i];
        }
    }
    return $res;
}
```
- 解题思路
  - 问题1：替换字符串，是在原来的字符串上做替换，还是新开辟一个字符串做替换！
  - 问题2：在当前字符串替换，怎么替换才更有效率（不考虑内置的replace方法）。
    - 从前往后替换，后面的字符要不断往后移动，要多次移动，所以效率低下
    - 从后往前，先计算需要多少空间，然后从后往前移动，则每个字符只为移动一次，这样效率更高一点。

从尾到头打印链表

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

     <?php

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function printListFromTailToHead($head)
{
    $arrayList = [];
    while($head !== null){
        $arrayList[]=$head->val;
        $head=$head->next;
    }
    return array_reverse($arrayList);
}

解题思路
有三种思路，
- 第一就是利用栈先入后出的特性完成；
- 第二就是存下来然后进行数组翻转；
- 第三是利用递归。

重建二叉树
- 题目描述
  输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
- 解题思路
题目描述
解题思路
题目描述
解题思路
题目描述
解题思路
题目描述
解题思路
题目描述
解题思路

11~20

题目描述
解题思路

21~30

题目描述
解题思路

前言

1~10

11~20

21~30

近期文章

近期评论

标签

热门

文章归档

分类目录

功能