- public class Solution {
- public boolean Find(int target, int [][] array) {
- if(array[0].length<=0)
- return false;
- for(int i = 0 ;i<array.length;i++)
- {
- for(int j = 0;j<array.length;j++)
- {
- if(array[i][j] == target)
- {
- return true;
- }
- }
- }
- return false;
- }
- }
但是这样的效率就很低下了, 还能进行优化, 参考一下大佬们是怎么进行优化的.
两种思路
一种是:
把每一行看成有序递增的数组,
利用二分查找,
通过遍历每一行得到答案,
时间复杂度是 nlogn
- public class Solution {
- public boolean Find(int [][] array,int target) {
- for(int i=0;i<array.length;i++){
- int low=0;
- int high=array[i].length-1;
- while(low<=high){
- int mid=(low+high)/2;
- if(target>array[i][mid])
- low=mid+1;
- else if(target<array[i][mid])
- high=mid-1;
- else
- return true;
- }
- }
- return false;
- }
- }
另外一种思路是:
利用二维数组由上到下, 由左到右递增的规律,
那么选取右上角或者左下角的元素 a[row][col] 与 target 进行比较,
当 target 小于元素 a[row][col] 时, 那么 target 必定在元素 a 所在行的左边,
即 col--;
当 target 大于元素 a[row][col] 时, 那么 target 必定在元素 a 所在列的下边,
即 row++;
- public class Solution {
- public boolean Find(int [][] array,int target) {
- 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;
- }
- }
其中还有点小坑 , 就是一定要确定好 数组遍历的起始位置.
题目二,
请实现一个函数, 将一个字符串中的每个空格替换成 " ". 例如, 当字符串为 We Are Happy. 则经过替换之后的字符串为 We Are Happy.
我的实现代码:
- public class Solution {
- public String replaceSpace(StringBuffer str) {
- return str.toString().replace(""," ");
- }
- }
总感觉自己实现的有点弱. 这个题应该不会这么简单, 膜拜一下大佬的代码去.
链接: https://www.nowcoder.com/questionTerminal/4060ac7e3e404ad1a894ef3e17650423
- /*
- 问题 1: 替换字符串, 是在原来的字符串上做替换, 还是新开辟一个字符串做替换!
- 问题 2: 在当前字符串替换, 怎么替换才更有效率 (不考虑 java 里现有的 replace 方法).
- 从前往后替换, 后面的字符要不断往后移动, 要多次移动, 所以效率低下
- 从后往前, 先计算需要多少空间, 然后从后往前移动, 则每个字符只为移动一次, 这样效率更高一点.
- */
- public class Solution {
- public String replaceSpace(StringBuffer str) {
- int spacenum = 0;//spacenum 为计算空格数
- for(int i=0;i<str.length();i++){
- if(str.charAt(i)==' ')
- spacenum++;
- }
- int indexold = str.length()-1; //indexold 为为替换前的 str 下标
- int newlength = str.length() + spacenum*2;// 计算空格转换成 之后的 str 长度
- int indexnew = newlength-1;//indexold 为为把空格替换为 后的 str 下标
- str.setLength(newlength);// 使 str 的长度扩大到转换成 之后的长度, 防止下标越界
- for(;indexold>=0 && indexold<newlength;--indexold){
- if(str.charAt(indexold) == ' '){ //
- str.setCharAt(indexnew--, '0');
- str.setCharAt(indexnew--, '2');
- str.setCharAt(indexnew--, '%');
- }else{
- str.setCharAt(indexnew--, str.charAt(indexold));
- }
- }
- return str.toString();
- }
- }
- /**
- * public class ListNode {
- * int val;
- * ListNode next = null;
- *
- * ListNode(int val) {
- * this.val = val;
- * }
- * }
- *
- */
- import java.util.ArrayList;
- public class Solution {
- ArrayList list = new ArrayList<Integer>();
- public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
- if(listNode!=null){
- this.printListFromTailToHead(listNode.next);
- list.add(listNode.val);
- }
- return list;
- }
- }
来源: http://www.bubuko.com/infodetail-3000176.html