剑指offer java版（一）
剑指offer java版（一）
二维数组中的查找
问题描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路
纵向从下往上开始遍历第一列，数值相等直接返回；小于n从上一行开始循环判断，大于n判断本行，相等则返回，没有则继续循环。
public void searchN(int n) {
if (nums.length == 0) return;
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i][0] == n) {
System.out.println("x=" + (nums.length - i + 1) + " y=" + 0);
return;
} else if (nums[i][0] < n) {
continue;
} else {
for (int j = 0; j < nums[i].length; j++) {
if (nums[i][j] == n) {
System.out.println("x=" + (nums.length - i + 1) + " y=" + j);
return;
}
}
}
}
}替换空格
问题描述
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路
将字符串转成char数组逐个遍历，或直接遍历字符串，使用StringBuilder构建新字符串。
public String replace(String str) {
StringBuilder builder = new StringBuilder();
char[] chars = str.toCharArray();
for (char c : chars) {
if (c == ' ') {
builder.append("%20");
} else {
builder.append(c);
}
}
return builder.toString();
}从尾到头打印单链表
问题描述
将单链表元素从尾到前逆序打印
解题思路
创建Stack栈，从前向后遍历单链表，完成后依次弹栈。
public void printWithStack(LinkNode node) {
if (node == null) return;
// 将链表节点依次压栈
Stack<LinkNode> stack = new Stack<>();
stack.push(node);
while (node.next != null) {
stack.push(node.next);
node = node.next;
}
// 将栈内元素依次弹栈
while (!stack.isEmpty()) {
System.out.println(stack.pop().value);
}
}两个栈实现队列
问题描述
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路
两个栈 stack1 和 stack2:
push 动作都在 stack1 中进行，
pop 动作在 stack2 中进行。当 stack2 不为空时，直接 pop，
当 stack2 为空时，先把 stack1 中的元素 pop 出来，push 到 stack2 中，再从 stack2 中 pop 元素。
class MyQueue {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(Integer integer) {
stack1.push(integer);
}
public Integer pop() {
if (stack1.isEmpty() && stack2.isEmpty()) {
throw new NullPointerException();
}
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
Integer i = stack2.pop();
while (!stack2.isEmpty()) {
stack1.push(stack2.pop());
}
return i;
}
}旋转数组的最小值
问题描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0
解题思路
类似于二分查找，定义左右两个指针left，right，计算中间指针位置mid
1、如果中间值>右边值，说明最小值在右半部分，left右移到mid+1
2、如果中间值=右边值，right左移一位，缩小距离
3、如果中间值<有右边值，说明最小值在左半部分，right更新为mid
public int search(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else if (nums[mid] == nums[right]) {
right = right - 1;
} else {
right = mid;
}
}
return nums[left];
}斐波那契数列
问题描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39
类似青蛙跳台阶问题。
解题思路
公式: f(n) = n, n <= 1 f(n) = f(n-1) + f(n-2), n > 1
- 递归
public int method1(int n) {
if (n == 0 || n == 1) return n;
return method1(n - 1) + method1(n - 2);
}- 动态规划
public int method2(int n) {
if (n == 0 || n == 1) return n;
int f1 = 0;
int f2 = 1;
for (int i = 2; i <= n; i++) {
f2 = f2 + f1;
f1 = f2 - f1;
}
return f2;
}二进制中1的个数
问题描述
输入一个自然数，输出该数二进制表示中1的个数。
解题思路
将自然数转为二进制数，遍历新字符串。
public int fun(int n) {
String binary = "";
while (n != 0) {
binary = n / 2 + binary;
n = n % 2;
}
char[] chars = binary.toCharArray();
if (chars == null || chars.length == 0) return 0;
int count = 0;
for (char c : chars) {
if (c == 1) count++;
}
return count;
}调整数组奇偶数位置
问题描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路
- 创建两个集合分别放入奇数和偶数，再合至一起
public void method1(int[] nums) {
if (nums == null || nums.length == 0) return;
ArrayList<Integer> ji = new ArrayList<>();
ArrayList<Integer> ou = new ArrayList<>();
for (int i : nums) {
if (i % 2 != 0) {
ji.add(i);
} else {
ou.add(i);
}
}
ji.addAll(ou);
for (int i = 0; i < ji.size(); i++) {
nums[i] = ji.get(i);
}
System.out.println(Arrays.toString(nums));
}- 类似于冒泡排序
public void method2(int[] nums) {
if (nums == null || nums.length == 0) return;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] % 2 == 0 && nums[j + 1] % 2 != 0) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(nums));
}数值的整数次方
问题描述
给定一个double类型的浮点数base和int类型的整数n。求base的n次方。
解题思路
循环自乘，但需对特殊数值进行处理。
public double square(double base, int n) {
// 任何数的0次幂都是1
if (n == 0) {
return 1;
}
// 指数小于0，先求其相反数幂次，最后求倒
if (n < 0) {
// 底数为0时特别处理
if (base == 0) {
throw new RuntimeException("0没有负数次幂");
} else {
double result1 = power(base, -n);
return 1 / result1;
}
}
return power(base, n);
}
/**
* 求幂
*
* @param base
* @param n
* @return
*/
public double power(double base, int n) {
if (n == 0) return 1;
double result = 1;
for (int i = 1; i <= n; i++) {
result = result * base;
}
return result;
}腾讯云开发者
