没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
剑指 offer
3、数组中重复的数字
题目一:找出数组中重复的数字
法一:
import java.util.HashMap;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of
duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal
*duplication in C/C++
// 这里要特别注意~返回任意重复的一个,赋值 duplication[0]
// Return value: true if the input is valid, and there are some duplications in the
array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
boolean flag=false;
if(length==0||numbers==null){
duplication[0]=-1;
return flag;
}
for(Integer num: numbers){
if(map.containsKey(num)){
duplication[0]=num;
flag=true;
break;
}else{
map.put(num,0);
}
}
return flag;
}
}
法二:
import java.util.Arrays;
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of
duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal
*duplication in C/C++
// 这里要特别注意~返回任意重复的一个,赋值 duplication[0]
// Return value: true if the input is valid, and there are some duplications in the
array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
boolean flag=false;
if(numbers==null||length<0)
return flag;
Arrays.sort(numbers);
for(int i=0;i<length-1;i++){
if(numbers[i]==numbers[i+1]){
duplication[0]=numbers[i];
flag=true;
break;
}
}
return flag;
}
}
题目二:不修改数组找出重复的数字
public class NO3in2 {
/**
* 避免使用辅助空间
*/
public int getDuplicate(int[] arr) {
if (arr == null || arr.length <= 0) {
System.out.println("数组输入无效!");
return -1;
}
for (int a : arr) {
if (a < 1 || a > arr.length - 1) {
System.out.println("数字大小超出范围!");
return -1;
}
}
int low = 1;
int high = arr.length - 1; // high 即为题目的 n
int mid, count;
while (low <= high) {
mid = ((high - low) >> 2) + low;
count = countRange(arr, low, mid);
if (low == high) {
if (count > 1)
return low;
else
break; // 必有重复,应该不会出现这种情况吧?
}
if (count > mid - low + 1) {
high = mid;
} else {
low = mid + 1;
}
}
return -1;
}
private int countRange(int[] arr, int start, int end)
{
int count = 0;
for(int i = 0;i < arr.length;i++)
{
if(arr[i] >= start && arr[i] <= end)
++count;
}
return count;
}
public static void main(String[] args) {
NO3in2 test=new NO3in2();
int[] arr = {2,3,5,4,3,2,6,7};
int value = test.getDuplicate(arr);
System.out.println(value);
}
}
4、二维数组中的查找
public class Solution {
public boolean Find(int target, int [][] array) {
boolean flag=false;
int rows=array.length; //二维数组的行
int columns=array[0].length; //二维数组的列
if(array!=null && rows>0 && columns>0) //每一个条件都很重要
{
int row=0; //从数组右上角开始
int column=columns-1;
while(row<rows && column>=0) //设置的条件很重要
{
if(array[row][column]==target)
{
flag=true;
break;
}
else if(array[row][column]>target)
--column;
else
++row;
}
}
return flag;
}
}
5、替换空格
public class Solution { //关键还是要熟悉字符串中的类 String、StringBuffer
public String replaceSpace(StringBuffer str) {
int cnt=0; //计算空格数
for(int i=0;i<=str.length()-1;i++)
{
if(str.charAt(i)==' ')
{
cnt++;
}
}
int len=str.length()+2*cnt; //计算转换之后的长度
int i=str.length()-1; //转换之前的长度
int j=len-1; //转换之后的下标
str.setLength(len); //str 扩大之后的长度,防止下标越界
for(;i>=0&&i<len;--i) //不要 i<len 也行
{
if(str.charAt(i)!=' ')
{
str.setCharAt(j--,str.charAt(i));
}
else
{
str.setCharAt(j--,'0');
str.setCharAt(j--,'2');
str.setCharAt(j--,'%');
//--i;
}
}
return str.toString(); //将 StringBuffer 对象转化成 String 对象
}
}
6、从尾到头打印链表
/** //没有打印,返回一个 ArrayList 类型的集合
* public class ListNode { //关键还是熟悉 List 集合
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { //返回值是 ArrayList
类型
if(listNode==null){
ArrayList<Integer> list=new ArrayList<Integer>();
return list;
}
Stack<Integer> stack = new Stack<Integer>();
ListNode node=listNode;
while(node!=null){
stack.push(node.val);
node=node.next;
}
ArrayList<Integer> arr=new ArrayList<Integer>();
while(!stack.isEmpty()){
//System.out.println(stack.pop()+"");
arr.add(stack.pop());
}
return arr;
}
}
7、重建二叉树
剩余61页未读,继续阅读
资源评论
李大洲
- 粉丝: 15
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功