一般般帅
上一篇:无
1~6题
2139 2018-11-11 2020-06-25
前言：牛客网剑指Offer编程题1~6题（如Java和Python答案冲突时，以Python二刷为准，出现这个问题的原因是牛客网判题不严谨，Leetcode相对严谨些）
一、二维数组中的查找
1、题目描述
考点数组，在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
// 下面是一个例子
10 20 30 40 50
20 30 40 50 60
30 40 50 60 70
40 50 60 70 80
50 60 70 80 90
2、我的代码
我的思路是这样的，以55为例
10 20 30 40 50
20 30 40 50 60
30 40 50 60 70
40 50 60 70 80
50 60 70 80 90
// 由于55大于10，大于30，大于50，且小于70，所以55必定出现在下面非0区域中，这就是我的思路
00 00 00 40 50
00 00 00 50 60
00 00 50 60 70
40 50 60 70 00
50 60 70 00 00
下面是代码实现
static class One {
static int[][] array = new int[][]{
{10, 20, 30, 40, 50},
{20, 30, 40, 50, 60},
{30, 40, 50, 60, 70},
{40, 50, 60, 70, 80},
{50, 60, 70, 80, 90}
};
/**
* 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
* 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
*/
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0 || array[0].length == 0) {
return false;
}
if (target < array[0][0]) {
return false;
}
return find(0, 0, target, array);
}
public boolean find(int i, int j, int target, int[][] array) {
// 比较当前值
if (array[i][j] == target) {
return true;
}
// 由于i = j，这里判断后续的操作是否越界
if (i + 1 == array.length) {
return false;
}
// 比较下一个对象，方向为左上到右下
if (array[i + 1][j + 1] == target) {
return true;
}
// 如果查找值大于下一个比较对象，则递归下一个
if (array[i + 1][j + 1] < target) {
return find(i + 1, j + 1, target, array);
}
// 如果小于，那就只能遍历右上角和左下角的那两块了
for (int x = i + 1; x < array.length; x++) {
for (int y = 0; y <= j; y++) {
if (array[x][y] == target) {
return true;
}
}
}
for (int x = 0; x <= i; x++) {
for (int y = j + 1; y < array.length; y++) {
if (array[x][y] == target) {
return true;
}
}
}
// 如果还没找到，那就真的不在了
return false;
}
public static void test() {
boolean result = new One().Find(5, One.array);
Assert.assertFalse(result);
result = new One().Find(10, One.array);
Assert.assertTrue(result);
result = new One().Find(55, One.array);
Assert.assertFalse(result);
result = new One().Find(80, One.array);
Assert.assertTrue(result);
result = new One().Find(90, One.array);
Assert.assertTrue(result);
result = new One().Find(100, One.array);
Assert.assertFalse(result);
result = new One().Find(102, One.niuke1);
Assert.assertTrue(result);
}
}
3、别人的代码
下面是别人的代码及思路。
public boolean Find1(int target, int [][] array) {
int len = array.length - 1;
int i = 0;
while((len >= 0) && (i < array[0].length)){
if(array[len][i] > target){
len--;
}else if(array[len][i] < target){
i++;
}else{
return true;
}
}
return false;
}
思路解析如下
// 他大概思路是这样的（从左下角或右上角开始均可）
10 20 30 40 50
20 30 40 50 60
30 40 50 60 70
40 50 60 70 80
50 60 70 80 90
// 寻找规律，以65为例，由于65 > 第一行最大数50，那么第一行去掉，同理去掉第二行
30 40 50 60 70
40 50 60 70 80
50 60 70 80 90
// 由于70 > 65，所以最后一列去掉，同理65 > 60，去掉第一行
40 50 60 70
50 60 70 80
// 由于65 < 70，去掉最后一列，同理60 < 65，去掉第一行
50 60 70
// 由于70 > 65，去掉最后一列，同理60 < 65,去掉第一行，没有找到目标数
4、python二刷
def Find(self, target, array):
if not array or not array[0]:
return False
_len_x = len(array)
_len_y = len((array[0]))
i = _len_x - 1
j = 0
while array[i][j] != target and i > 0 and j < _len_y - 1:
pos_value = array[i][j]
if pos_value < target:
j += 1
elif pos_value > target:
i -= 1
return i >= 0 and j < _len_y and array[i][j] == target
感觉自己的代码还是有点啰嗦，不如别人的代码好。
# 修改后的代码
def Find(self, target, array):
if not array or not array[0]:
return False
_len_x = len(array)
_len_y = len((array[0]))
i = _len_x - 1
j = 0
while i >= 0 and j <= _len_y - 1:
pos_value = array[i][j]
if pos_value < target:
j += 1
elif pos_value > target:
i -= 1
else:
return True
return False
二、替换空格
1、题目描述
考点字符串，请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy。则经过替换之后的字符串为We%20Are%20Happy。
2、我的代码
static class Two {
static String str = "We Are Haapy";
public String replaceSpace(StringBuffer str) {
if (str == null || str.length() == 0) {
return str == null ? null : str.toString();
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (Character.isWhitespace(str.charAt(i))) {
sb.append("%20");
continue;
}
sb.append(str.charAt(i));
}
return sb.toString();
}
private static void test() {
Two two = new Two();
Assert.assertEquals(str.replaceAll(" ", "%20"), two.replaceSpace(new StringBuffer(str)));
}
}
3、别人的代码
// 我的是新建一个字符串，这个是在原来的基础上修改，所以要问清楚面试官具体的要求
public String replaceSpace1(StringBuffer str) {
int spaceNum = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ')
spaceNum++;
}
int indexOld = str.length() - 1;
int newLength = str.length() + spaceNum * 2;
int endIndex = newLength - 1;
str.setLength(newLength);
for (; indexOld >= 0 && indexOld < newLength; --indexOld) {
if (str.charAt(indexOld) == ' ') {
str.setCharAt(endIndex--, '0');
str.setCharAt(endIndex--, '2');
str.setCharAt(endIndex--, '%');
} else {
str.setCharAt(endIndex--, str.charAt(indexOld));
}
}
return str.toString();
}
三、从尾到头打印链表
1、题目描述
考点链表，输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
2、我的代码
public ArrayList<Integer> printListFromTailToHead(ListNode node) {
ArrayList<Integer> list = new ArrayList<>();
if (node == null) {
return list;
}
while (node != null) {
list.add(node.val);
node = node.next;
}
int size = list.size();
int mid = size / 2 ;
for (int i = 0; i < mid; i++) {
int temp = list.get(i);
list.set(i, list.get(size - 1 - i));
list.set(size - 1 - i, temp);
}
return list;
}
3、别人的代码
由于要求还是有点出入的，别人的大概思路是这个样子。
// 使用一个栈
public ArrayList<Integer> printListFromTailToHead1(ListNode node) {
Deque<Integer> stack = new LinkedList<>();
while (node != null) {
stack.push(node.val);
node = node.next;
}
ArrayList<Integer> list = new ArrayList<>();
while (!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
四、重建二叉树
1、题目描述
考点二叉树，输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
2、我的代码
static class Four {
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
if (pre.length == 0) {
return null;
}
TreeNode root = new TreeNode(pre[0]);
int midIndex = index(pre[0], in);
root.left = reConstructBinaryTree(left(midIndex, pre[0], pre), left(midIndex, pre[0], in));
root.right = reConstructBinaryTree(right(midIndex, pre), right(midIndex, in));
return root;
}
private int[] left(int size, int exclude, int[] arr) {
int[] left = new int[size];
int j = 0;
for (int i = 0; i <= size; i++) {
if (arr[i] != exclude) {
left[j++] = arr[i];
}
}
return left;
}
private int[] right(int size, int[] arr) {
int[] right = new int[arr.length - size - 1];
int j = 0;
for (int i = size + 1; i < arr.length; i++) {
right[j++] = arr[i];
}
return right;
}
private int index(int value, int[] arr) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
private static void test() {
int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
TreeNode root = new Four().reConstructBinaryTree(pre, in);
pre(root);
}
private static void pre(TreeNode root) {
System.out.print(root.val + " ");
if (root.left != null) {
System.out.println("节点" + root.val + "的左节点是" + root.left.val);
pre(root.left);
}
if (root.right != null) {
System.out.println("节点" + root.val + "的右节点是" + root.right.val);
pre(root.right);
}
}
}
我觉得我是最棒的，不看别人的了。
3、python二刷
# 这个才是最棒的
def reConstructBinaryTree(self, pre, tin):
if not pre or not tin:
return None
return split(pre, tin)
def split(pre, tin):
if not pre:
return
root = TreeNode(pre[0])
left_pre, left_bin = split_left(pre, tin)
right_pre, right_bin = split_right(pre, tin)
root.left = split(left_pre, left_bin)
root.right = split(right_pre, right_bin)
return root
def split_left(pre, tin):
root = pre[0]
index = tin.index(root)
return pre[1:index + 1], tin[0:index]
def split_right(pre, tin):
root = pre[0]
index = tin.index(root)
return pre[index + 1:], tin[index + 1:]
五、用两个栈实现队列
1、题目描述
考点队列和栈，用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
2、我的代码
static class Five {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (!stack2.isEmpty()) {
return stack2.pop();
}
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
扩展题，用两个队列实现栈，代码如下
public class MyStack<E> {
private Queue<E> queue1;
private Queue<E> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(E e) {
if (queue2.size() != 0) {
queue2.offer(e);
} else {
queue1.offer(e);
}
}
public E pop() {
if (queue1.size() > 0) {
while (queue1.size() > 1) {
E e = queue1.poll();
queue2.offer(e);
}
return queue1.poll();
}
while (queue2.size() > 1) {
E e = queue2.poll();
queue1.offer(e);
}
return queue2.poll();
}
}
六、旋转数组的最小数字
1、题目描述
考点查找，把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
2、我的代码
static class Six {
public int minNumberInRotateArray(int[] array) {
if (array.length == 0) {
return 0;
}
if (array.length == 1) {
return array[0];
}
int i = 0;
// 判断方向
while (array[i] == array[i + 1] && i++ < array.length - 2) {
}
if (array[i] > array[i + 1]) {
return findMin(i + 1, true, array);
} else if (array[0] < array[array.length - 1]) {
return array[0];
} else {
return findMin(array.length - 1, false, array);
}
}
private int findMin(int i, boolean asc, int[] arr) {
if (asc) {
if (i == arr.length - 1) {
return arr[i];
}
if (arr[i] >= arr[i + 1]) {
return findMin(i + 1, true, arr);
} else {
return arr[i];
}
} else {
if (i == 2) {
return arr[i];
}
if (arr[i - 1] <= arr[i]) {
return findMin(i - 1, false, arr);
} else {
return arr[i];
}
}
}
private static void test() {
int min = new Six().minNumberInRotateArray(new int[]{3, 3, 4, 5, 1, 2});
Assert.assertEquals(min, 1);
}
}
一天6道题，完工。
总访问次数: 318次, 一般般帅 创建于 2018-11-11, 最后更新于 2020-06-25
欢迎关注微信公众号，第一时间掌握最新动态！