当前位置 博文首页 > 令狐_JackieHao的博客:【剑指offer】编程习题集附上答案
class Solution
{
public void swap(int[] nums,int i,int j)
{
int temp=nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
public int findRepeatNumber(int[] nums)
{
int n=nums.length;
for(int num:nums)
if(num<0||num>=n)
return -1;
for(int i=0;i<n;i++)
{
while(nums[i]!=i&&nums[i]!=nums[nums[i]])
swap(nums,i,nums[i]);
if(nums[i]!=i&&nums[i]==nums[nums[i]])
return nums[i];
}
return -1;
}
}
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int i,j;
if((matrix==null||matrix.length==0)||(matrix.length==1&&matrix[0].length==0))
return false;
for (i=0;i<matrix.length;i++)
for (j=0;j<matrix[0].length;j++)
if(matrix[i][j]==target)
return true;
return false;
}
}
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if((matrix==null||matrix.length==0)||(matrix.length==1&&matrix[0].length==0))
return false;
int i=0,j=matrix[0].length-1;
while(i<=matrix.length-1&&j>=0){
if(target==matrix[i][j]) return true;
if(target>matrix[i][j]) i++;
else if(target<matrix[i][j]) j--;
}
return false;
}
}
class Solution {
public int[] spiralOrder(int[][] matrix) {
//判断边界
if(matrix.length==0)
return new int[0];//因为返回值是数组,所以实例化一个数组进行返回
//右下左上
int left=0,right=matrix[0].length-1,up=0,down=matrix.length-1;
int num=0;
int []res=new int[(right+1)*(down+1)];
while(true){
//右
for(int i=left;i<=right;i++)
res[num++]=matrix[up][i];
if(++up>down) break;///判断边界
//下
for(int i=up;i<=down;i++)
res[num++]=matrix[i][right];
if(--right<left) break;
//左
for(int i=right;i>=left;i--)
res[num++]=matrix[down][i];
if(--down<up) break;
//上
for(int i=down;i>=up;i--)
res[num++]=matrix[i][left];
if(++left>right) break;
}
return res;
}
}
class Solution {
public int search(int[] nums, int target) {
int res=0;
for(int i=0;i<nums.length;i++)
if(nums[i]==target)
res++;
return res;
}
}
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
int ans = 0;
while (left < right){
int mid = left + ((right - left)/2);
if (nums[mid] >= target){
right = mid;
} else {
left = mid + 1;
}
}
while (left < nums.length && nums[left++] == target){
ans++;
}
return ans;
}
}
class Solution {
public int missingNumber(int[] nums) {
int left = 0, right = nums.length;
while(left < right){
int mid = left + (right - left) / 2;
if (nums[mid] == mid) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}