【100天算法入門 - 每日三題 - Day1】二叉樹的中序遍曆、兩數之和、整數反轉

哪 吒 2021-08-15 05:05:15 阅读数:474

本文一共[544]字,预计阅读时长:1分钟~
算法 每日 day1 day 二叉

1、LeetCode 94.二叉樹的中序遍曆

題目

給定一個二叉樹的根節點 root ,返回它的 中序 遍曆。

大神解法

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
inorder(root, res);
return res;
}
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
inorder(root.left, res);
res.add(root.val);
inorder(root.right, res);
}
}

2、LeetCode.1 兩數之和

題目

給定一個整數數組 nums 和一個整數目標值 target,請你在該數組中找出 和為目標值 target  的那 兩個 整數,並返回它們的數組下標。

你可以假設每種輸入只會對應一個答案。但是,數組中同一個元素在答案裏不能重複出現。

你可以按任意順序返回答案。

示例 1:

輸入:nums = [2,7,11,15], target = 9
輸出:[0,1]
解釋:因為 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例2:

輸入:nums = [3,2,4], target = 6
輸出:[1,2]

示例3:

輸入:nums = [3,3], target = 6
輸出:[0,1]

進階:你可以想出一個時間複雜度小於 O(n2) 的算法嗎?

小編菜解

/**
* 輸入:nums = [2,7,11,15], target = 9
* 輸出:[0,1]
* 解釋:因為 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
*/
public static int[] twoSum(int[] nums, int target) {
int[] ret = new int[2];
for(int i = 0;i<nums.length;i++){
for (int j = 0; j < nums.length - 1; j++) {
if((nums[i] + nums[j]) == target){
ret[0] = i;
ret[1] = j;
return ret;
}
}
}
return null;
}

大神解法

private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public static int[] twoSumByMap(int[] nums, int target) {
int[] indexs = new int[2];
for (int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])){
indexs[0] = i;
indexs[1] = map.get(nums[i]);
}
map.put(target - nums[i],i);
}
return indexs;
}

 3、LeetCode.7 整數反轉

題目

給你一個 32 比特的有符號整數 x ,返回將 x 中的數字部分反轉後的結果。

如果反轉後整數超過 32 比特的有符號整數的範圍 [−231,  231 − 1] ,就返回 0。

小編菜解

private static int reverse01(int param){
String fh = "";
String str = String.valueOf(param);
StringBuilder builder = null;
if(param < 0){
fh = "-";
builder = new StringBuilder(str.substring(1));
}else{
builder = new StringBuilder(str);
}
String value = builder.reverse().toString();
return Integer.parseInt(fh + Integer.parseInt(value););
}

提交失敗,存在 Exception in thread "main" java.lang.NumberFormatException: For input string: "9646324351"問題

 大神解法

private static int reverse02(int x){
int result = 0;
while(x != 0) {
int tmp = result; // 保存計算之前的結果
result = (result * 10) + (x % 10);
x /= 10;
// 將計算之後的結果 / 10,判斷是否與計算之前相同,如果不同,證明發生溢出,返回0
if (result / 10 != tmp) return 0;
}
return result;
}

往期精彩內容:

Java知識體系總結

【全棧最全Java框架總結】SSH、SSM、Springboot

超詳細的springBoot學習筆記

常見數據結構與算法整理總結

Java設計模式:23種設計模式全面解析

Java面試題總結(附答案)

10萬字208道Java經典面試題總結(附答案,建議收藏)

MySql知識體系總結

Linux知識體系總結

【Vue基礎知識總結 1】Vue入門

Redis知識體系總結

版权声明:本文为[哪 吒]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815050501533L.html