二維數組中的查找
問題描述
在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
解題思路
縱向從下往上開始遍歷第一列，數值相等直接返回；小于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次冪都是1if (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;}
復制代碼
