开篇
满打满算,还有半年的时间就要去找正式工作了,在念硕士的阶段,每天打的不是code,都是一堆命令的kinds of stuff,虽说Python也断断续续用了一年,但是连续写起来,还是要查查这查查拿,更不用说本科阶段入门CS 的C++。 可以用的OJ平台数不胜数,本科时候大家热衷的PTE,现在从国外火到国内的LeetCode(力扣),以及牛客网的在线编程。选定一个就好,此次选择剑指offer,题库共66道,难度适中,适用于让我快速系统的coding。每道题都会坚持使用C++以及Python来完成。虽然平时用的是Python3,平台在线编译只支持2.7,但是作为纯粹的编程练习来说,问题不大。
二维数组查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。(点我直接练习)
分析
题目意思非常明确,就是从二维向量中查找制定数字,题目的技巧就在于数字的递增规律。按行来查找,可以从右往左查,如果查到一行中某个位置的数值以及比目标值小,则可直接到下一行继续查找;从列的角度上来说,如果某一个位置的数值已经比目标还大,那么该列剩下的待查找数值一定也比目标值要大(因为是递增关系),所以该列剩余的值就不需要继续查,跳到下一行的时候,列指针不变,继续左移即可。
使用到的知识点
C++
二维向量的操作,长度,size
Python
Python 列表的操作方法
题解
C++(Clang++ 3.9) : 运行时间:10ms 占用内存:1400k
class Solution { public: bool Find(int target, vector<vector<int> > array) { int row = array.size(); if(row!=0){ int col = array[0].size()-1; int i = 0,j = col; while(i<row && j>=0){ if(array[i][j] == target) return true; else if(array[i][j] > target) j-=1; else i+=1; } } return false; } };
Python 2.7: 运行时间:337ms 占用内存:5740k
class Solution: def Find(self, target, array): row = len(array) if row != 0 : col = len(array[0])-1 row = 0 while row<len(array) and col>=0: if array[row][col] == target: return True elif array[row][col]>target: col -= 1 else : row += 1 return False
不得不说,用这两种语言同时做一道题,会非常难受和舒服。。。不用写’;’,不用声明变量真香,C++11 真是太麻烦了