739 每日温度
根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
// 思路1 直接遍历统计
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
for(int i=0;i<T.length;i++){
int j = 0;
for(j=i+1;j<T.length&&T[j] <= T[i];j++);
if(j == T.length){
res[i] = 0;
}else{
res[i] = j - i;
}
}
return res;
}
647 回文子串
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
public int countSubstrings(String s) {
if(s == null || s.length() == 0){
return 0;
}
boolean[][] dp = new boolean[s.length()][s.length()];
int sum = 0;
for(int i=0;i<s.length();i++){
dp[i][i] = true;
}
sum += s.length();
// i 表示字符串的长度
for(int i=1;i<s.length();i++){
for(int j=0;j<s.length()-i;j++){
if(i == 1){
if(s.charAt(j) == s.charAt(j+1)){
dp[j][j+i] = true;
sum++;
}else{
dp[j][j+i] = false;
}
}else{
dp[j][j+i] = (s.charAt(j) == s.charAt(j+i)) && dp[j+1][j+i-1];
if(dp[j][j+i]){
sum++;
}
}
}
}
return sum;
}
621 任务调度器
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。
然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 ：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
采用模拟的方式实现，每次都是从最高的任务开始执行，然后进行递减，如果为0 ，递减够次数
public int leastInterval(char[] tasks, int n) {
// 算法的思想是每次都进行排序，且每一次都是从最大进行递减进行模拟
// 任务只有26中使用基数排序
int[] map = new int[26];
for(char c:tasks){
map[c-'A']++;
}
// 从小到大的排序
Arrays.sort(map);
int time = 0;
while(map[25]>0){
int i = 0;
while(i<=n){
if(map[25] <= 0){
break;
}
if(i<26 && map[25-i] > 0){
map[25-i]--;
}
time++;
i++;
}
Arrays.sort(map);
}
return time;
}
// 方法2 ，采用优先队列不进行排队，同时采用list保存每次修改的值，然后再添加进去，不能只维护一个list,在此上进行增删。
public int leastInterval(char[] tasks, int n) {
// 算法的思想是每次都进行排序，且每一次都是从最大进行递减进行模拟
// 任务只有26中使用基数排序
// 使用优先队列维持排序的状态
int[] map = new int[26];
for(char c:tasks){
map[c-'A']++;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(26,Collections.reverseOrder());
for(int x:map){
if(x > 0)
queue.offer(x);
}
int time = 0;
while(!queue.isEmpty()){
int i = 0;
LinkedList<Integer> list = new LinkedList<>();
while(i <= n){
if(!queue.isEmpty() && queue.peek() > 1){
int t = queue.poll();
list.add(t-1);
}else if(!queue.isEmpty()){
queue.poll();
}
time++;
if(queue.isEmpty() && list.size() == 0){
break;
}
i++;
}
for(int x:list){
queue.offer(x);
}
}
return time;
}
617 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
// 合并二叉树，采用先序遍历
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
if(t1 == null){
return t2;
}else if(t2 == null){
return t1;
}
t1.val = t1.val + t2.val;
t1.left = mergeTrees(t1.left,t2.left);
t1.right = mergeTrees(t1.right,t2.right);
return t1;
}
581 最短无序连续子数组
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
找到逆序中最小的数，逆序中最大的数，
然后从左遍历找打第一个大于最小数的值
从右向左遍历找打第一个小于最大数的值
public int findUnsortedSubarray(int[] nums) {
if(nums == null || nums.length < 2){
return 0;
}
// 最短无序子数组，从左到右，从右到左遍历寻找第一个无序节点
boolean flag = false;
int min = Integer.MAX_VALUE;int max = Integer.MIN_VALUE;
for(int i=1;i<nums.length;i++){
if(nums[i] < nums[i-1]) flag = true;
if(flag) min = Math.min(min,nums[i]);
}
flag = false;
for(int i=nums.length-2;i>=0;i--){
if(nums[i] > nums[i+1]) flag = true;
if(flag) max = Math.max(max,nums[i]);
}
int l,r;
for(l=0;l<nums.length;l++){
if(nums[l]>min){
break;
}
}
for(r=nums.length-1;r>=0;r--){
if(nums[r]<max){
break;
}
}
return r-l<0?0:r-l+1;
}
560 和为k的子数组
求连续子数组和，可以使用hashmap 存储连续求和的次数，然后每次进行校验。
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
public int subarraySum(int[] nums, int k) {
// 使用hashmap 统计和为k的数组个数
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int sum = 0;
int count = 0;
for(int i=0;i<nums.length;i++){
sum += nums[i];
if(map.containsKey(sum-k)){
count += map.get(sum-k);
}
map.put(sum,map.getOrDefault(sum,0)+1);
}
return count;
}
543 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
class NodeCount{
int val;
int mixVal;
int maxVal;
public NodeCount(int val,int mixVal,int maxVal){
this.val = val;
this.mixVal = mixVal;
this.maxVal = maxVal;
}
}
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
NodeCount res = diameterOfBinaryTreeCore(root);
return res.maxVal-1;
}
public NodeCount diameterOfBinaryTreeCore(TreeNode root){
if(root == null){
return new NodeCount(0,0,0);
}
NodeCount left = diameterOfBinaryTreeCore(root.left);
NodeCount right = diameterOfBinaryTreeCore(root.right);
int mixVal = left.val + right.val + 1;
int val = Math.max(left.val,right.val)+1;
int maxVal = Math.max(val,mixVal);
NodeCount node = new NodeCount(val,mixVal,Math.max(maxVal,Math.max(left.maxVal,right.maxVal)));
return node;
}
// 直接记录长度即可
// 这里只需要返回 单节点的长度，总长度采用外变量进行更新
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
if(root == null){
return 0;
}
depthTree(root);
return ans-1;
}
public int depthTree(TreeNode root){
if(root == null){
return 0;
}
int L = depthTree(root.left);
int R = depthTree(root.right);
ans = Math.max(ans,L+R+1);
return Math.max(L,R)+1;
}
538. 把二叉树转换为累加树
int curValue = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return root;
}
root.right = convertBST(root.right);
curValue += root.val;
root.val = curValue;
root.left = convertBST(root.left);
return root;
}
494. 目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
// 首先的思路是回溯深搜
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length == 0){
return 0;
}
dfs(nums,S,0);
return count;
}
public void dfs(int[] nums,int S, int cur){
if(cur == nums.length){
if(S == 0){
count ++;
}
return;
}else{
// 要么加
dfs(nums,S-nums[cur],cur+1);
// 要么减
dfs(nums,S+nums[cur],cur+1);
}
}
// 采用动态规划的思想，每次求前i项和为j的次数
int count = 0;
public int findTargetSumWays(int[] nums, int S) {
if(nums == null || nums.length == 0){
return 0;
}
// 分别表示前 i 项 和 为 j
int[][] dp = new int[nums.length][2001];
// 这里加1000 是怕出现负数
dp[0][nums[0] + 1000] = 1;
dp[0][-nums[0]+1000] += 1;
for(int i=1;i<nums.length;i++){
for(int j=-1000;j<=1000;j++){
// 说明存在前i-1项和
if(dp[i-1][j+1000] > 0){
dp[i][j-nums[i]+1000] += dp[i-1][j+1000];
dp[i][j+nums[i]+1000] += dp[i-1][j+1000];
}
}
}
return S > 1000 ? 0 : dp[nums.length - 1][S + 1000];
}
461. 汉明距离
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。
注意：
0 ≤ x, y < 231.
示例:
输入: x = 1, y = 4
输出: 2
思路：异或相同为0，不同为1
// 汉明距离，异或相同为0，不同为1
public int hammingDistance(int x, int y) {
int res = x ^ y;
int count = 0;
for(int i=0;i<32;i++){
if(((res>>i)&1) == 1){
count++;
}
}
return count;
}
448.找到所有数组中消失的数
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[4,3,2,7,8,2,3,1]
输出:
[5,6]
public List<Integer> findDisappearedNumbers(int[] nums) {
int[] copy = new int[nums.length+1];
for(int x:nums){
copy[x%(nums.length+1)] = 1;
}
List<Integer> res = new ArrayList<>();
for(int i=1;i<copy.length;i++){
if(copy[i] != 1){
res.add(i);
}
}
return res;
}
// 原数组取反标记，已经访问过
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<>();
// 思路任然采用原地标记的思路，将原数值，取反，来表示已经访问过，没变为负数说明没访问过
for(int i=0;i<nums.length;i++){
int val = Math.abs(nums[i])-1;
if(nums[val] > 0){
nums[val] = -nums[val];
}
}
for(int i=0;i<nums.length;i++){
if(nums[i] > 0){
res.add(i+1);
}
}
return res;
}
438. 找到字符串中的异位符
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
// 思路是采用字符数组统计的方式判断字符串是否相同
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int len = p.length();
for(int i=0;i<s.length()-len+1;i++){
String sub = s.substring(i,i+len);
if(check(sub,p)){
res.add(i);
}
}
return res;
}
// 如果只有字符的字符串可以使用hash来判断是否相同
public boolean check(String s, String t){
int[] z = new int[26];
for(char x:s.toCharArray()){
z[(x-'a')] ++;
}
for(char x:t.toCharArray()){
z[(x-'a')] --;
}
for(int x:z){
if(x != 0){
return false;
}
}
return true;
}
// 使用滑动窗口找寻字符异位词
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int len = p.length();
int[] needs = new int[26];
int[] windows = new int[26];
// 先统计p的字符数
for(char c:p.toCharArray()){
needs[c-'a']++;
}
int left = 0,right = 0,total = len;
while(right < s.length()){
char ch = s.charAt(right);
if(needs[ch-'a'] > 0){
windows[ch-'a']++;
if(windows[ch-'a']<=needs[ch-'a']){
total--;
}
}
while(total == 0){
if(right-left+1 == len){
res.add(left);
}
char c = s.charAt(left);
if(needs[c-'a'] > 0){
windows[c-'a'] --;
if(windows[c-'a'] < needs[c-'a']){
total++;
}
}
left++;
}
right++;
}
return res;
}
437. 路径总和3
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
// 先序遍历寻找路径和为sum的次数
int count = 0;
public int pathSum(TreeNode root, int sum) {
if(root == null){
return 0;
}
preOrder(root,sum);
pathSum(root.left,sum);
pathSum(root.right,sum);
return count;
}
public void preOrder(TreeNode root,int sum){
if(root == null){
return;
}
sum -= root.val;
if(sum == 0){
count++;
}
preOrder(root.left,sum);
preOrder(root.right,sum);
}
// 每一个节点进行统计返回
public int pathSum(TreeNode root, int sum) {
if (root == null){
return 0;
}
return paths(root,sum) + pathSum(root.left,sum) + pathSum(root.right,sum);
}
private int paths(TreeNode root,int sum) {
if (root == null){
return 0;
}
int res = 0;
if (root.val == sum){
res ++;
}
res += paths(root.left,sum - root.val);
res += paths(root.right,sum - root.val);
return res;
}
416 分割等和子集
// 实际上可以转化为，子集中是否存在是二分之一的子集
// 采用枚举的方法进行dfs搜索
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0){
return false;
}
int sum = 0;
for(int x:nums){
sum += x;
}
if(sum % 2 == 1){
return false;
}
// 使用背包问题的动态规划进行求解
boolean[][] dp = new boolean[nums.length][sum/2+1];
int target = sum/2;
if(nums[0] <= target){
dp[0][nums[0]] = true;
}
for(int i=1;i<nums.length;i++){
for(int j=0;j<=target;j++){
dp[i][j] = dp[i-1][j];
if(nums[i] == j){
dp[i][j] = true;
continue;
}
if(nums[i]<j){
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
}
return dp[nums.length-1][target];
}
public boolean canPartition(int[] nums) {
if(nums == null || nums.length == 0){
return false;
}
int sum = 0;
for(int x:nums){
sum += x;
}
if(sum % 2 == 1){
return false;
}
// 使用背包问题的动态规划进行求解
boolean[][] dp = new boolean[nums.length][sum/2+1];
int target = sum/2;
if(nums[0] <= target){
dp[0][nums[0]] = true;
}
for(int i=1;i<nums.length;i++){
for(int j=0;j<=target;j++){
dp[i][j] = dp[i-1][j];
if(nums[i]<=j){
dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
}
}
if(dp[i][target]){
return true;
}
}
return dp[nums.length-1][target];
}
45. 跳跃游戏2
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
思路是使用最大位置记录最大，当到达最大位置时更新遍历过程中的最大位置。
public int jump(int[] nums) {
int step = 0;
int maxPosition = nums[0];
int curMaxPosition = 0;
for(int i=1;i<nums.length;i++){
curMaxPosition = Math.max(curMaxPosition,i+nums[i]);
if(i == maxPosition || i == nums.length -1){
maxPosition = curMaxPosition;
step++;
}
}
return step;
}
406. 根据身高重建队列
假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
注意：
总人数少于1100人。
示例
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
public int[][] reconstructQueue(int[][] people) {
// 思路是先将所有人，按照从高到底，从前到后进行排序，这是因为最小的表明前2位置它一定是前2
// 先让个高进行插入
Arrays.sort(people,(o1,o2)->(o1[0] == o2[0])?o1[1] - o2[1]:o2[0]-o1[0]);
List<int[]> res = new ArrayList<>();
for(int[] i:people){
res.add(i[1],i);
}
// 将list 转换为 int[]数组使用toArray
return res.toArray(new int[res.size()][2]);
}
394. 字符串解码
这里字符串的存储必须使用StringBuilder 否则String 使用字符常量池会有65535限制。
字符串的解码， 使用字符栈 和 数值栈， 使用stringBuilder
在遇见 [ 时入栈， 在遇见 ] 只计算当前res重算的次数，不入栈
res = new StringBuilder(strStack.pop() + sb.toString());
其次不用考虑栈是否为空，括号一定是成对的。
public String decodeString(String s) {
// 使用数值栈 和 字符串栈来解析字符串
char[] ss = s.toCharArray();
Stack<Integer> numStack = new Stack<>();
Stack<String> strStack = new Stack<>();
int tmpNum = 0;
StringBuilder res = new StringBuilder();
for(char c : ss){
if(c>='0' && c<='9'){
tmpNum = tmpNum * 10 + (c - '0');
}else if(c == '['){
numStack.push(tmpNum);
strStack.push(res.toString());
res = new StringBuilder();
tmpNum = 0;
}else if(c == ']'){
int x = numStack.pop();
StringBuilder sb = new StringBuilder();
while(x-->0){
sb.append(res);
}
res = new StringBuilder(strStack.pop() + sb.toString());
}else {
res.append(c);
}
}
return res.toString();
}
347. 前k个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
// 使用堆排序构建前k个高频元素
public int[] topKFrequent(int[] nums, int k) {
// 统计前k个高频元素，可以采用hashmap 进行统计，然后放入优先队列
HashMap<Integer,Integer> map = new HashMap<>();
for(int x:nums){
map.put(x,map.getOrDefault(x,0)+1);
}
PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->(map.get(o1) - map.get(o2)));
for(int x:map.keySet()){
queue.offer(x);
if(queue.size()>k){
queue.poll();
}
}
int[] res = new int[k];
for(int i=k-1;i>=0;i--){
res[i] = queue.poll();
}
return res;
}
// 使用堆排序构建前k个高频元素
public int[] topKFrequent(int[] nums, int k) {
// 统计前k个高频元素，可以采用hashmap 进行统计，然后放入优先队列
HashMap<Integer,Integer> map = new HashMap<>();
for(int x:nums){
map.put(x,map.getOrDefault(x,0)+1);
}
// 使用桶排序获取前k大，将数字的次数作为插入的下标,使用数组链表数组结构解决hash冲突
ArrayList<Integer>[] list = new ArrayList[nums.length+1];
for(int x:map.keySet()){
int index = map.get(x);
if(list[index] == null){
list[index] = new ArrayList<>();
}
list[index].add(x);
}
List<Integer> res = new ArrayList<>();
for(int i = list.length - 1;i >= 0 && res.size() < k;i--){
if(list[i] == null) continue;
res.addAll(list[i]);
}
int[] result = new int[k];
for(int i=0;i<k;i++){
result[i] = res.get(i);
}
return result;
}
338. 比特币计数
// 统计数中1的.
public int[] countBits(int num) {
int[] ans = new int[num + 1];
for(int i=1;i<=num;i++){
ans[i] = ans[i&(i-1)] + 1;
}
return ans;
}
337. 打家劫舍3
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:
输入: [3,2,3,null,3,null,1]
3
/ \
2 3
\ \
3 1
public int rob(TreeNode root) {
return Solution(root).val;
}
public TreeNode Solution(TreeNode root){
if(root == null){
TreeNode newNode = new TreeNode(0);
return Solution(newNode);
}
if(root.left == null && root.right == null){
root.left = new TreeNode(0);
root.right = new TreeNode(0);
return root;
}
root.left = Solution(root.left);
root.right = Solution(root.right);
root.val = Math.max(root.left.val + root.right.val, root.val + root.left.left.val + root.left.right.val + root.right.left.val + root.right.right.val);
return root;
}
public int rob(TreeNode root) {
// 爷爷 + 孙子 和 爸爸 比大小
if(root == null){
return 0;
}
int[] res = robCore(root);
return Math.max(res[0],res[1]);
}
// 状态转换机，每一个节点都有偷或者不偷两种
public int[] robCore(TreeNode root){
if(root == null){
return new int[2];
}
int[] res = new int[2];
int[] left = robCore(root.left);
int[] right = robCore(root.right);
res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
res[1] = left[0] + right[0] + root.val;
return res;
}
322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
思路是动态规划，找找到amount钱的最少次数，就依次找出从1~amount的最少次数。
dp[i] = dp[i-coins[j]] + 1
public int coinChange(int[] coins, int amount) {
// 零钱兑换，就动态规划，找到兑换i的最少钱数
// dp[i] = min 遍历 dp[i-coins[j]] + 1
if(coins == null || coins.length == 0){
return -1;
}
int[] dp = new int[amount+1];
for(int i=1;i<=amount;i++){
// 这里最小的找钱次数是 amount + 1, 不要乱改
int min = amount+1;
for(int j=0;j<coins.length;j++){
if(coins[j]<=i)
min = Math.min(min,dp[i-coins[j]]+1);
}
dp[i] = min;
}
if (dp[amount] == amount+1){
return -1;
}
return dp[amount];
}
309.最佳买卖股票时机含冷冻期
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2){
return 0;
}
// 使用状态机进行计算
int[][] dp = new int[prices.length][3];
// 0 代表不持股 1 代表持股 2 代表 冷冻期
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for(int i=1;i < prices.length;i++){
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][2] - prices[i]);
dp[i][2] = dp[i-1][0];
}
return Math.max(dp[prices.length-1][0],Math.max(dp[prices.length-1][1],dp[prices.length-1][2]));
}
大数乘法
public String multiply(String num1, String num2){
int[] result = new int[num1.length() + num2.length()];
int[] n1 = new int[num1.length()];
int[] n2 = new int[num2.length()];
for(int i=0;i<num1.length();i++){
n1[i] = num1.charAt(i) - '0';
}
for(int j=0;j<num2.length();j++){
n2[j] = num2.charAt(j) - '0';
}
for(int i=0;i<num1.length();i++){
for(int j=0;j<num2.length();j++){
result[i+j] = n1[i] * n2[j];
}
}
// 进行进位
for(int i=result.length-1;i>0;i--){
result[i-1] += result[i] / 10;
result[i] = result[i] % 10;
}
// 转String
String res = "";
for(int i=0;i<result.length;i++){
res += result[i] + "";
}
return res;
}
287. 寻找重复的数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
public int findDuplicate(int[] nums) {
// 使用本地相反数进行标注
for(int x: nums){
int index = Math.abs(x);
if(nums[index] < 0){
return index;
}else{
nums[index] = -nums[index];
}
}
return -1;
}
283 移动0
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
public void moveZeroes(int[] nums) {
// 创建一个新的index作为防止下标
int index = 0;
for(int x : nums){
if(x != 0)
nums[index++] = x;
}
while(index < nums.length){
nums[index++] = 0;
}
}
279 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
public int numSquares(int n) {
int sqareLen = (int)(Math.sqrt(n));
int[] numSqare = new int[sqareLen];
for(int i=1;i<=sqareLen;i++){
numSqare[i-1] = i * i;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i=2;i<=n;i++){
int count = n+1;
for(int j=0;j < sqareLen && numSqare[j]<= i;j++){
count = Math.min(count,dp[i-numSqare[j]]+1);
}
dp[i] = count;
}
return dp[n];
}
240. 搜索二维矩阵
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
// 思路搜索从左下角开始
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return false;
}
int m = matrix.length;
int n = matrix[0].length;
int i = m-1,j = 0;
while(i >=0 && i < m && j >=0 && j < n){
if(matrix[i][j] == target){
return true;
}else if(matrix[i][j] < target){
j++;
}else{
i--;
}
}
return false;
}
239.滑动窗口的最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
public int[] maxSlidingWindow(int[] nums, int k) {
// 创建维持一个最大数值
int[] res = new int[nums.length-k+1];
for(int i=0;i<nums.length-k+1;i++){
int max = Integer.MIN_VALUE;
if(i > 0 && nums[i-1] != res[i-1] && nums[i+k-1] < res[i-1]){
res[i] = res[i-1];
}else{
for(int j=i;j<i+k;j++){
max = Math.max(max,nums[j]);
}
res[i] = max;
}
}
return res;
}
O(n) 的时间复杂度
public int[] maxSlidingWindow(int[] nums, int k) {
// 创建维持一个最大数值
// 维持left 最大数组 // 维持一个右最大数组
int n = nums.length;
if(n * k == 0){
return new int[0];
}
if(k == 1){
return nums;
}
int[] left = new int[n];
left[0] = nums[0];
int[] right = new int[n];
right[n-1] = nums[n-1];
for(int i = 1;i<n;i++){
if(i % k == 0){
left[i] = nums[i];
}else{
left[i] = Math.max(left[i-1],nums[i]);
}
int j = n - i - 1;
if((j+1)%k == 0){
right[j] = nums[j];
}else{
right[j] = Math.max(right[j+1],nums[j]);
}
}
int[] output = new int[n-k+1];
for (int i = 0; i < n - k + 1; i++)
output[i] = Math.max(left[i + k - 1], right[i]);
return output;
}
238.除自身以外数组的乘积
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
public int[] productExceptSelf(int[] nums) {
int[] tmp = new int[nums.length];
tmp[0] = 1;
for(int i=1;i<nums.length;i++){
tmp[i] = tmp[i-1] * nums[i-1];
}
int[] tmp2 = new int[nums.length];
tmp2[nums.length-1] = 1;
for(int i=nums.length-2;i>=0;i--){
tmp2[i] = tmp2[i+1] * nums[i+1];
}
for(int i=0;i<nums.length;i++){
tmp[i] = tmp[i] * tmp2[i];
}
return tmp;
}
234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<>();
ListNode p = head;
while(p != null){
stack.push(p.val);
p = p.next;
}
p = head;
while(!stack.empty()){
int val = stack.pop();
if(val != p.val){
return false;
}
p = p.next;
}
return true;
}
// 采用回溯法进行判断
ListNode first = null;
public boolean isPalindrome(ListNode head) {
first = head;
return isPalindromeCore(head);
}
public boolean isPalindromeCore(ListNode node){
if(node == null){
return true;
}
if(!isPalindromeCore(node.next)) return false;
if(first.val != node.val) return false;
first = first.next;
return true;
}
226. 翻转二叉树
public TreeNode invertTree(TreeNode root) {
if(root == null){
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
221. 最大正方形
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例:
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4
public int maximalSquare(char[][] matrix) {
int res = 0;
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return res;
}
int[][] dp = new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
if(matrix[i][0] == '1') res = 1;
dp[i][0] = matrix[i][0] - '0';
}
for(int i=0;i<matrix[0].length;i++){
if(matrix[0][i] == '1') res = 1;
dp[0][i] = matrix[0][i] - '0';
}
for(int i=1;i<matrix.length;i++){
for(int j=1;j<matrix[0].length;j++){
if(matrix[i][j] == '1'){
dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])) + 1;
res = Math.max(res,dp[i][j]);
}
}
}
return res * res;
}
215. 数组中第K大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int x:nums){
queue.offer(x);
if(queue.size() > k){
queue.poll();
}
}
return queue.poll();
}
208. 字典树
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
class Trie {
class TrieNode{
TrieNode[] links;
boolean isEnd;
final int R = 26;
public TrieNode(){
links = new TrieNode[R];
}
// 是否包含
public boolean containsKey(char ch){
return links[ch - 'a'] != null;
}
// put
public void put(char ch,TrieNode node){
links[ch-'a'] = node;
}
// get
public TrieNode get(char ch){
return links[ch - 'a'];
}
public void setEnd(){
isEnd = true;
}
public boolean isEnd(){
return isEnd;
}
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c: word.toCharArray()){
if(!node.containsKey(c)){
node.put(c,new TrieNode());
}
node = node.get(c);
}
node.setEnd();
}
private TrieNode searchPrifix(String word){
TrieNode node = root;
for(char c:word.toCharArray()){
if(node.containsKey(c)){
node = node.get(c);
}else{
return null;
}
}
return node;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = searchPrifix(word);
return node != null && node.isEnd();
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = searchPrifix(prefix);
return node != null;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
207. 课程表
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] coursesCount = new int[numCourses];
for(int[] item:prerequisites){
coursesCount[item[1]]++;
}
Stack<Integer> stack = new Stack<>();
for(int i=0;i<coursesCount.length;i++){
if(coursesCount[i] == 0)
stack.push(i);
}
while(!stack.empty()){
int x = stack.pop();
for(int[] item: prerequisites){
if(item[0] == x){
coursesCount[item[1]]--;
if(coursesCount[item[1]] == 0){
stack.push(item[1]);
}
}
}
}
for(int x:coursesCount){
if(x != 0){
return false;
}
}
return stack.empty();
}
206.翻转链表
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
ListNode pre = null;
ListNode p = head;
while(p != null){
ListNode next = p.next;
p.next = pre;
pre = p;
p = next;
}
return pre;
}
递归的翻转二茬链表
public ListNode reverseList(ListNode head) {
if(head.next == null){
return head;
}
ListNode node = reverseList(head.next);
head.next.next = head;
head.next = null;
return node;
}
236. 二叉树最近公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null){
return null;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left != null && right != null){
return root;
}else if(root == p || root == q){
return root;
}
return left == null ? right:left;
}
200. 岛屿的数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
// 标注即可
boolean[][] vis;
char[][] grid;
int m,n;
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0){
return 0;
}
this.grid = grid;
m = grid.length;
n = grid[0].length;
vis = new boolean[m][n];
int count = 0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j] == '1' && !vis[i][j]){
dfs(i,j);
count++;
}
}
}
return count;
}
public void dfs(int x,int y){
if(x < 0 || x >=m || y < 0 || y >= n || grid[x][y] != '1' ||vis[x][y]){
return;
}else{
vis[x][y] = true;
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
}
}
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
public int rob(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
if(nums.length <2){
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i=2;i<nums.length;i++){
dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
}
return dp[nums.length-1];
}
169.多数元素
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
// 多数元素，元素个数大于n/2 的可以，统计一个变量进行计数
public int majorityElement(int[] nums) {
int count = 1;
int element = nums[0];
for(int i=1;i<nums.length;i++){
if(nums[i] == element){
count++;
}else{
count--;
if(count == 0){
element = nums[i];
count = 1;
}
}
}
return element;
}
160. 找出链表的相交节点
思路使用交叉遍历的方法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA,q = headB;
while(p != q){
p = p == null ? headB:p.next;
q = q == null ? headA:q.next;
}
return p;
}
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
使用双栈实现最小栈
class MinStack {
// 使用双栈实现最小栈
Stack<Integer> stack;
Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if(minStack.empty()){
minStack.push(x);
}else{
int y = minStack.peek();
if(x < y){
minStack.push(x);
}else{
minStack.push(y);
}
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
curMax * x 和 x 比较大小，curMin * x 和 比最小
public int maxProduct(int[] nums) {
// 维护最大和最小值
int max = Integer.MIN_VALUE;
int curMax = 1;
int curMin = 1;
for(int x:nums){
if(x < 0){
int tmp = curMax;
curMax = curMin;
curMin = tmp;
}
curMax = Math.max(x,curMax * x);
curMin = Math.min(x,curMin*x);
max = Math.max(max,curMax);
}
return max;
}
139.单词拆分
使用回溯加记忆完成单词的拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
// 使用回溯算法进行尝试
public boolean wordBreak(String s, List<String> wordDict) {
return wordBreak(s,wordDict,0,new Boolean[s.length()]);
}
// 使用回溯算法进行尝试
public boolean wordBreak(String s, List<String> wordDict,int cur,Boolean[] memo) {
if(s.equals("") || s.length() == 0){
return true;
}else if(memo[cur] != null) {
return memo[cur];
}else {
for(int j=0;j < wordDict.size();j++){
String start = wordDict.get(j);
if(s.startsWith(start)){
boolean res = wordBreak(s.substring(start.length()), wordDict,cur + start.length()-1,memo);
if(res) {
return memo[cur] = true;
}
}
}
}
return memo[cur] = false;
}
// 使用动态规划进行单词的拆分
// 使用动态规划
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()+1];
dp[0] = true;
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
if(dp[j] && set.contains(s.substring(j,i))){
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
柱形图中最大矩形面积
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积.
// 最大的矩形面积是，当前的宽度乘以最小的高度
public int largestRectangleArea(int[] heights) {
int maxArea = 0;
int minHeight = Integer.MAX_VALUE;;
for(int i=0;i<heights.length;i++){
minHeight = Integer.MAX_VALUE;
for(int j=i;j<heights.length;j++){
minHeight = Math.min(minHeight,heights[j]);
maxArea = Math.max(maxArea,minHeight * (j-i+1));
}
}
return maxArea;
}
// 柱形图最大矩形面积，是最矮柱子尽可能两边延伸
// 最矮柱子左边最大面积
// 最矮柱子右边最大面积
// 采用分治的思想，找到最小的柱子
public int largestRectangleArea(int[] heights) {
return largestRectangleArea(heights,0,heights.length-1);
}
public int largestRectangleArea(int[] heights, int left, int right){
if(right < left){
return 0;
}
int minHeight = left;
for(int i=left + 1;i<=right;i++){
if(heights[i] < heights[minHeight]){
minHeight = i;
}
}
int area = heights[minHeight] * (right - left + 1);
int leftArea = largestRectangleArea(heights,left,minHeight-1);
int rightArea = largestRectangleArea(heights,minHeight+1,right);
return Math.max(area,Math.max(leftArea,rightArea));
}
79. 单词搜索
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
存在一个情况进入还需要退出的情况下必须进行回溯，否则可以直接dfs
boolean[][] vis;
public boolean exist(char[][] board, String word) {
if(board == null || board.length == 0 || board[0].length == 0){
return false;
}
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[i][j] == word.charAt(0)){
vis = new boolean[board.length][board[0].length];
vis[i][j] = true;
boolean flag = dfs(board,word.substring(1),i,j);
if(flag){
return true;
}
}
}
}
return false;
}
int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};
public boolean dfs(char[][] board,String word, int x, int y){
if(word == null || word.length() == 0){
return true;
}else{
for(int i=0;i<4;i++){
int xx = x + next[i][0];
int yy = y + next[i][1];
if(xx >= 0 && xx < board.length && yy >= 0 && yy < board[0].length && board[xx][yy] == word.charAt(0) && !vis[xx][yy]){
vis[xx][yy] = true;
boolean flag = dfs(board,word.substring(1),xx,yy);
if(flag) return true;
vis[xx][yy] = false;
}
}
}
return false;
}
网友评论