题目来源：力扣（LeetCode）https://leetcode-cn.com
本人水平较低，整理供个人学习回顾
35. 搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。
解题思路：本题这里使用的是折半查找(二分查找)算法，经分析若在原数组中存在要查找的值，直接使用返回目标的位置即可，若原数组没有要查找的值，返回high+1即为按顺序插入后的索引。
class Solution {
public int searchInsert(int[] nums, int target) {
int low = 0;
int high = nums.length-1;
int mid;
while(low <= high){
mid = (low+high)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
high = mid - 1;
else
low = mid + 1;
}
return high + 1;
}
}53. 最大子数组和
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
解题思路：可以用动态规划的方法来求解此题
class Solution {
public int maxSubArray(int[] nums) {
int preSum = 0;
int maxSum = nums[0];
for(int x : nums){
preSum = Math.max(preSum+x,x);
maxSum = Math.max(preSum,maxSum);
}
return maxSum;
}
}58. 最后一个单词的长度
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度,单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
解题思路：用空格将单词分成一个数组，取数组最后一个单词即可求出最后一个单词的长度。
class Solution {
public int lengthOfLastWord(String s) {
String[] word = s.split(" ");
return word[word.length-1].length();
}
}66. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。
解题思路：不用去纠结某一位是不是9，而应该去判断每一位加1之后是不是0：如果遇到了加一不是0的元素，就直接返回digits，如果遍历所有元素后digits数组中所有元素均为0，此时new一个digits数组，数组长度为原数组加一，且数组下标为0的元素赋值为1。
class Solution {
public int[] plusOne(int[] digits) {
int len = digits.length;
for(int i = len - 1;i >= 0;i--){
digits[i] = (digits[i] + 1) % 10;
if(digits[i] != 0){
return digits;
}
}
digits = new int[len+1];
digits[0] = 1;
return digits;
}
}67. 二进制求和
给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字
1和0。
解题思路：末尾对齐，逐列相加，逢二进一。 sum是上一位进位 carry、a串、b串的和对2的模。carry是用和除以2的值。注意如果最后carry的值是1，那么还要在builder中追加上1作为进位，且返回的字符串要经过翻转。
class Solution {
public String addBinary(String a, String b) {
int i = a.length()-1;
int j = b.length()-1;
int carry = 0; // 记录上一位运算后的进位，初始是0
StringBuilder builder = new StringBuilder();
// 从低位到高位遍历字符串，求出进位和对应的值添加到builder中
while(i >= 0 && j >= 0){
int sum = carry;
sum += a.charAt(i--) - '0';
sum += b.charAt(j--) - '0';
carry = sum / 2;
builder.append(sum % 2);
}
// 如果i>=0 说明a串没有遍历完，继续遍历
while(i >= 0){
int sum = a.charAt(i--) - '0' + carry;
carry = sum / 2;
builder.append(sum % 2);
}
// 如果j>=0 说明b串没有遍历完，继续遍历
while(j >= 0){
int sum = b.charAt(j--) - '0' + carry;
carry = sum / 2;
builder.append(sum % 2);
}
// 如果最后carry为1那么还要在builder中追加上进位1
if(carry == 1){
builder.append(carry);
}
// 最后要注意返回的是builder翻转后的字符串
return builder.reverse().toString();
}
}69. x 的平方根
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
解题思路：使用二分查找思路或者使用牛顿迭代法这种方法比上一种更快更高效。
// 二分查找
class Solution {
public int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long) mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
}// 牛顿迭代法
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
double C = x, x0 = x;
while (true) {
double xi = 0.5 * (x0 + C / x0);
if (Math.abs(x0 - xi) < 1e-7) {
break;
}
x0 = xi;
}
return (int) x0;
}
}83. 删除排序链表中的重复元素
给定一个已排序的链表的头
head， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表
解题思路：因为本题已经是一个升序的链表，所以直接用当前结点与下一结点做比较即可。若相同删除下一结点，若不同继续比较下一结点。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode cur = head;
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
88. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
解题思路：逆向双指针
观察可知，nums1 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进nums1 的最后面。
时间复杂度：O(m+n)。 指针移动单调递减，最多移动 m+n 次，因此时间复杂度为O(m+n)。
空间复杂度：O(1) 直接对数组nums1原地修改，不需要额外空间。
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m-1;
int p2 = n-1;
int index = m + n - 1;
int cur;
while (p1 >= 0 || p2 >= 0){
if(p1 == -1){
cur = nums2[p2--];
}else if(p2 == -1){
cur = nums1[p1--];
}else if(nums1[p1] < nums2[p2]){
cur = nums2[p2--];
}else{
cur = nums1[p1--];
}
nums1[index--] = cur;
}
}
}94. 二叉树的中序遍历
给定一个二叉树的根节点
root，返回它的 中序 遍历。
解题思路：按照递归的思路去写非常容易，这里只写出非递归算法。总体思路是沿着根的左子树依次入栈，直到没有左子树。出栈栈顶元素，访问出栈的元素，访问其右子树，回到while循环。继续这个过程。
/**
* 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> list = new ArrayList<Integer>();
Deque<TreeNode> stk = new LinkedList<TreeNode>();
while(root!=null||!stk.isEmpty()){
if(root!=null){
stk.push(root);
root = root.left;
}else{
root = stk.pop();
list.add(root.val);
root = root.right;
}
}
return list;
}
}100. 相同的树
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
解题思路：当两棵树的当前节点都为 null 时返回 true
当其中一个为 null 另一个不为 null 时返回 false
当两个都不为空但是值不相等时，返回 false
执行过程：当满足终止条件时进行返回，不满足时分别判断左子树和右子树是否相同，其中要注意代码中的短路效应
/**
* 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 boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
else if(p == null || q == null) return false;
else if(p.val != q.val) return false;
else return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
}101. 对称二叉树
给你一个二叉树的根节点
root， 检查它是否轴对称。
解题思路：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称可以实现这样一个递归函数，通过同步移动两个指针的方法来遍历这棵树，node1指针和 node2 指针一开始都指向这棵树的根，随后node1右移时，node2 左移，node1左移时，node2右移。每次检查当前 node1 和 node2节点的值是否相等，如果相等再判断左右子树是否对称。
/**
* 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 boolean isSymmetric(TreeNode root) {
return check(root,root);
}
public boolean check(TreeNode node1,TreeNode node2){
if(node1 == null && node2 == null) return true;
else if(node1 == null || node2 == null) return false;
else return (node1.val == node2.val) && check(node1.left,node2.right) && check(node1.right,node2.left);
}
}104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
解题思路：
如果我们知道了左子树和右子树的最大深度 l和 r，那么该二叉树的最大深度即为 max(l,r)+1。而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言，在计算当前二叉树的最大深度时，可以先递归计算出其左子树和右子树的最大深度，然后在 O(1)时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。
/**
* 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 int maxDepth(TreeNode root) {
if(root==null){
return 0;
}
int LeftHeight = maxDepth(root.left);
int RightHeight = maxDepth(root.right);
return Math.max(LeftHeight,RightHeight)+1;
}
}继续给出一种BFS算法
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int ans = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
ans++;
}
return ans;
}
}121. 买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
解题思路：暴力解法很简单，使用动态规划去解会更好
- 记录【今天之前买入的最小值】
- 计算【今天之前最小值买入，今天卖出的获利】，也即【今天卖出的最大获利】
- 比较【每天的最大获利】，取最大值即可
class Solution {
public int maxProfit(int[] prices) {
if(prices.length<=1)
return 0;
int min = prices[0];
int max = 0;
for(int i = 1;i < prices.length;i++){
max = Math.max(max,prices[i]-min);
min = Math.min(prices[i],min);
}
return max;
}
}136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
解题思路：
如何才能做到线性时间复杂度和常数空间复杂度呢？
使用位运算。对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。
任何数和 0做异或运算，结果仍然是原来的数，即a⊕0=a。 任何数和其自身做异或运算，结果是 0，即a⊕a=0。 异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。经过分析数组中所有元素异或运算后的元素即为只出现一次的数字
class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for(int num : nums){
single ^= num;
}
return single;
}
}125. 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。
解题思路：将s全转换为小写，新建一个StringBuilder，遍历s串只讲数字和字母加入到builder中，最后比较翻转后的builder串和原builder串是否相等即可。
class Solution {
public boolean isPalindrome(String s) {
if(s == null) return true;
s = s.toLowerCase();
int length = s.length();
StringBuilder sb = new StringBuilder(length);
for(char c : s.toCharArray()){
if((c >= '0'&& c <= '9')||(c >='a' && c<='z')){
sb.append(c);
}
}
return sb.toString().equals(sb.reverse().toString());
}
}
Comments NOTHING