二維數(shù)組中的查找

問題描述

在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

解題思路

縱向從下往上開始遍歷第一列，數(shù)值相等直接返回；小于n從上一行開始循環(huán)判斷，大于n判斷本行，相等則返回，沒有則繼續(xù)循環(huá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;}}}}} 復(fù)制代碼

替換空格

問題描述

請實(shí)現(xiàn)一個(gè)函數(shù)，將一個(gè)字符串中的每個(gè)空格替換成“%20”。例如，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。

解題思路

將字符串轉(zhuǎn)成char數(shù)組逐個(gè)遍歷，或直接遍歷字符串，使用StringBuilder構(gòu)建新字符串。

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();} 復(fù)制代碼

從尾到頭打印單鏈表

問題描述

將單鏈表元素從尾到前逆序打印

解題思路

創(chuàng)建Stack棧，從前向后遍歷單鏈表，完成后依次彈棧。

public void printWithStack(LinkNode node) {if (node == null) return;// 將鏈表節(jié)點(diǎn)依次壓棧Stack<LinkNode> stack = new Stack<>();stack.push(node);while (node.next != null) {stack.push(node.next);node = node.next;}// 將棧內(nèi)元素依次彈棧while (!stack.isEmpty()) {System.out.println(stack.pop().value);}} 復(fù)制代碼

兩個(gè)棧實(shí)現(xiàn)隊(duì)列

問題描述

用兩個(gè)棧來實(shí)現(xiàn)一個(gè)隊(duì)列，完成隊(duì)列的Push和Pop操作。 隊(duì)列中的元素為int類型。

解題思路

兩個(gè)棧 stack1 和 stack2:

push 動(dòng)作都在 stack1 中進(jìn)行，

pop 動(dòng)作在 stack2 中進(jìn)行。當(dāng) stack2 不為空時(shí)，直接 pop，

當(dāng) stack2 為空時(shí)，先把 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;}} 復(fù)制代碼

旋轉(zhuǎn)數(shù)組的最小值

問題描述

把一個(gè)數(shù)組最開始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。

輸入一個(gè)非減排序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。

例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。

NOTE：給出的所有元素都大于0，若數(shù)組大小為0，請返回0

解題思路

類似于二分查找，定義左右兩個(gè)指針left，right，計(jì)算中間指針位置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];} 復(fù)制代碼

斐波那契數(shù)列

問題描述

大家都知道斐波那契數(shù)列，現(xiàn)在要求輸入一個(gè)整數(shù)n，請你輸出斐波那契數(shù)列的第n項(xiàng)（從0開始，第0項(xiàng)為0）。 n<=39

類似青蛙跳臺(tái)階問題。

解題思路

公式: 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);} 復(fù)制代碼

• 動(dòng)態(tài)規(guī)劃

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;} 復(fù)制代碼

二進(jìn)制中1的個(gè)數(shù)

問題描述

輸入一個(gè)自然數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)。

解題思路

將自然數(shù)轉(zhuǎn)為二進(jìn)制數(shù)，遍歷新字符串。

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;} 復(fù)制代碼

調(diào)整數(shù)組奇偶數(shù)位置

問題描述

輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變。

解題思路

• 創(chuàng)建兩個(gè)集合分別放入奇數(shù)和偶數(shù)，再合至一起

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));} 復(fù)制代碼

• 類似于冒泡排序

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));} 復(fù)制代碼

數(shù)值的整數(shù)次方

問題描述

給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)n。求base的n次方。

解題思路

循環(huán)自乘，但需對特殊數(shù)值進(jìn)行處理。

public double square(double base, int n) {// 任何數(shù)的0次冪都是1if (n == 0) {return 1;}// 指數(shù)小于0，先求其相反數(shù)冪次，最后求倒if (n < 0) {// 底數(shù)為0時(shí)特別處理if (base == 0) {throw new RuntimeException("0沒有負(fù)數(shù)次冪");} 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;} 復(fù)制代碼

轉(zhuǎn)載于:https://juejin.im/post/5c8f3e6f6fb9a07100164d37

總結(jié)

以上是生活随笔為你收集整理的剑指offer java版（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。