算法题:二叉树相关
合并二叉树
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
1234567891011121314输入: Tree 1 Tree 2 1 2 / \ / \ 3 2 1 3 / \ \ 5 ...
算法题:位运算相关
只出现一次的数字题目描述
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例1:12输入: [2,2,1]输出: 1示例2:12输入: [4,1,2,1,2]输出: 4
思路由于时间复杂度与空间复杂度的限制,这道题目解决办法一定是很巧妙的。
答案是采用异或的方法。
Java的异或^是位运算的一种,含义是相同的位数置 0 ,相异的位数置 1 。数字本身(相同数字)的异或结果为 0 ,0 与任何数字的异或结果为其本身。
Hash Map中的hash码映射到数组位置就采用了异或的方法,(h=key.hashcode())^(h>>16);
例如:0000 0000 0000 1011 ^0000 0000 0000 11110000 0000 0000 0100
代码12345678910class Solution { public int singleNumber(int[] nums) { int r ...
快速排序 | 选择排序 | 冒泡排序
选择排序每次选择最小的元素放在第一个位置,再选第二小元素放到第二个位置… 以此类推,排序完成。
12345678910111213141516171819202122232425public class SelectSort { public static int[] sort(int[] nums){ if(nums==null || nums.length==0) return null; int len = nums.length; int[] A = new int[len]; System.arraycopy(nums, 0, A, 0, len); for(int i=0; i<len-1; i++){ int min = i; for(int j=i+1; j<len; j++){ if(A[min]>A[j]){ ...
Linux终端常用指令
常用指令集
指令
作用
pwd
打印当前工作目录
hostname
获取我的计算机的网络名称
mkdir
创建目录
cd
更改目录
ls
列出目录下的文件
rmdir
删除目录
pushd
push directory
popd
pop directory
cp
复制文件或目录
mv
移动/重命名文件或目录
less
按页查看文件
cat
输出整个文件
xargs
执行参数
find
查找文件
grep
查找文件里面的东西
man
阅读帮助手册
apropos
find what man page is appropriate
env
查看计算机环境
echo
输出一些参数
export
设置一个新的环境变量
exit
退出终端
sudo
危险! 拥有超级用户权限!
sudo rm –rf /*
赶紧跑路吧!
算法题--买卖股票的最佳时机
基础版
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例11234输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例2
12345输入: [1,2,3,4,5]输出: 4解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例3123输入: [7,6,4,3,1]输出: 0解释 ...
Minimum-Falling-Path-Sum
下降路径最小和题目细节
给定一个方形整数数组 A,我们想要得到通过 A 的下降路径的最小和。下降路径可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。
示例1123输入:[[1,2,3],[4,5,6],[7,8,9]]输出:12
解释:可能的下降路径有: 123[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9][2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9][3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]和最小的下降路径是 [1,4,7],所以答案是 12。
提示121 <= A.length == A[0].length <= 100-100 <= A[i][j] <= 100
思路典型的二维动态数组题目。创建一个二维的数组A[row][column]存储结果,每一个位置存储的是第一行到该位置最小的下降路径。
一般情况1A[i][j] +=min ...
Algorithm--Third Maximum Number
1. Third Maximum NumberTitle Detail
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
123Input: [3, 2, 1]Output: 1Explanation: The third maximum is 1.
Example 2:123Input: [1, 2]Output: 2Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
12Input: [2, 2, 3, 1]Output: 1
Explanation:Note that the third maximum here means ...
Java:List API
Java List常用类型
类型
特征
ArrayList
随机访问元素快;中间插入与删除元素较慢;操作不是线程安全的
LinkedList
中间插入与删除操作代价较低,提供优化的顺序访问;随机访问元素慢
ArrayListArrayList的UML类图如下所示:
ArrayList 继承了 AbstractList, 直接实现了 Cloneable, Serializable,RandomAccess 类型标志接口。
AbstractList 作为列表的抽象实现,将元素的增删改查都交给了具体的子类去实现,在元素的迭代遍历的操作上提供了默认实现。
RandomAccess 接口实现,表示 ArrayList 里的元素可以被高效效率的随机访问,以下标数字的方式获取元素。实现 RandomAccess 接口的列表上在遍历时可直接使用普通的 for 循环方式,并且执行效率上给迭代器方式更高。
Cloneable 接口的实现,表示了 ArrayList 支持调用 Object 的 clone 方法,实现 ArrayList 的拷贝。
Serializ ...
Algorithm:删除最外层的括号
删除最外层括号题目
有效括号字符串为空 (“”)、”(“ + A + “)” 或 A + B,其中 A 和 B 都是有效的括号字符串,+ 代表字符串的连接。例如,””,”()”,”(())()” 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 S 非空,且不存在将其拆分为 S = A+B 的方法,我们称其为原语(primitive),其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S,考虑将其进行原语化分解,使得:S = P_1 + P_2 + … + P_k,其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解,删除分解中每个原语字符串的最外层括号,返回 S 。
示例1
输入:”(()())(())”输出:”()()()”解释:输入字符串为 “(()())(())”,原语化分解得到 “(()())” + “(())”,删除每个部分中的最外层括号后得到 “()()” + “()” = “()()()”。
示例2
输入:”(()())(())(()(()))”输出:”()()()()(())”解释:输入字符串为 “(()())(()) ...
Algorithm--Minimum path sum
Dynamic ProgrammingMinimum Path SumTitle Detail
Given an integer array A, you partition the array into (contiguous) subarrays of length at most K. After partitioning, each subarray has their values changed to become the maximum value of that subarray.
Return the largest sum of the given array after partitioning.
Example 1:123Input: A = [1,15,7,9,2,5,10], K = 3Output: 84Explanation: A becomes [15,15,15,9,10,10,10]Note:121 <= K <= A.length <= 5000 <= A[i] <= 10^6
思路动态规划 问题。
用原来的 ...