739 每日温度
思路1: 暴力
针对每一个温度，找下一个比自己大的温度
class Solution {
public int[] dailyTemperatures(int[] T) {
for(int i=0;i<T.length;i++){
boolean flag=false;
for(int j=i+1;j<T.length;j++){
if(T[j]>T[I]){
T[i]=j-i;
flag=true;
break;
}
}
if(!flag){
T[i]=0;
}
}
return T;
}
}
思路2:
如何在思路1的基础上优化改进？怎样减少遍历次数呢？
我们可以分析，遍历一次数组中所有的值应该是少不了的，因为至少数组中每个值都需要计算一遍，所以时间复杂度肯定大于 O(n)。关键是要减少为每个数寻找值遍历次数。
如图所示，绿色部分区域会给多次遍历，如果我们能减少这部分区域的遍历次数，就能整体提高运算效率。
(在75找到76的过程中，已经遍历过71～72了)
如果我们先从右边计算，那么我们计算过的位置就不需要重复计算，如图所示：
关键在于“跳”的思想，可以往后跳跃
比如当前我们需要计算 75 位置，先向右遍历到 71(先看看自己右边的，所以j的初值是i+1 即j=i+1)，因为我们已经计算好了 71 位置对应的值为 2，那么我们就可以直接 跳 2 位 再进行比较，利用了已经有的结果，减少了遍历的次数。
该思路的代码也不好写，自己写了挺久，代码也不好
第二个for的结束循环条件自己写的很奇怪，应该是j < length，表明不能再跳了，到头了，虽然实际上并不可能越界，因为最后一个是0
别人写的
public int[] dailyTemperatures(int[] T) {
int length = T.length;
int[] result = new int[length];
//从右向左遍历
for (int i = length - 2; i >= 0; i--) {
// j+= result[j]是利用已经有的结果进行跳跃
for (int j = i + 1; j < length; j+= result[j]) {
if (T[j] > T[i]) {
result[i] = j - I;
break;//退出当前循环
} else if (result[j] == 0) { //遇到0表示后面不会有更大的值，那当然当前值就应该也为0
result[i] = 0;
break;//退出当前循环
}
}
}
return result;
}
思路3:栈
没实现没理解
//找出数组中大于当前元素的第一个元素，到当前元素的距离
//递减栈，当前元素与栈中元素比较，小则入栈，大则出栈并将二者之间的下标差值为出栈元素的结果值，并继续比较下一个栈顶元素
//如果栈为空，直接入栈(表示前面元素都找到了比自己大的值)
class Solution {
public int[] dailyTemperatures(int[] T) {
Stack<Integer> stack = new Stack<>();
int[] res = new int[T.length];
for(int i = 0; i < T.length; ++i){
while(!stack.isEmpty() && T[i] > T[stack.peek()]){
int temp = stack.pop();
res[temp] = i - temp;
}
stack.push(i);
}
return res;
}
}
维护递减栈，后入栈的元素总比栈顶元素小。
比对当前元素与栈顶元素的大小
若当前元素 < 栈顶元素：入栈
若当前元素 > 栈顶元素：弹出栈顶元素，记录两者下标差值即为所求天数
这里用栈记录的是 T 的下标。
class Solution(object):
def dailyTemperatures(self, T):
"""
:type T: List[int]
:rtype: List[int]
"""
stack = list()
t_length = len(T)
res_list = [0 for _ in range(t_length)]
for key, value in enumerate(T):
if stack:
while stack and T[stack[-1]] < value:
res_list[stack[-1]] = key - stack[-1]
stack.pop()
stack.append(key)
return res_list
这个的方法2
https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode-solution/
思路4:
时间紧急没看方法1
https://leetcode-cn.com/problems/daily-temperatures/solution/mei-ri-wen-du-by-leetcode-solution/
647 回文子串
思路1:运用之前做过的最长回文子串的思路完成
20% 30%
dp[i][j]表明s[i~j]是否回文
if s[i]==s[j]
dp[i][j]=dp[i+1][j-1]
else
dp[i][j]=0;
一个个判断过去，如果是，则计数加一
class Solution {
public int countSubstrings(String s) {
int len=s.length();
boolean[][] dp=new boolean[len][len];
int cnt=0;
for(int i=0;i<len;i++){
dp[i][i]=true;
cnt++;
if(i<len-1&&s.charAt(i)==s.charAt(i+1)){
dp[i][i+1]=true;
cnt++;
}
}
for(int l=3;l<=len;l++){
for(int i=0;i+l-1<len;i++){
if(s.charAt(i)==s.charAt(i+l-1)){
dp[i][i+l-1]=dp[i+1][i+l-2];
if(dp[i][i+l-1]==true) cnt++;
}
//if(s.charAt(i)==s.charAt(i+l-1) && dp[i+1][i+l-2]){
//dp[i][i+l-1]=true;
//cnt++;
//} 这样写也可以
else dp[i][i+l-1]=false;
}
}
return cnt;
}
}
动态规划其他人的写法：
没看明白
class Solution {
public int countSubstrings(String s) {
int res = 0;
int n = s.length();
// dp[i][j] 表示[i,j]的字符是否为回文子串
boolean[][] dp = new boolean[n][n];
// 注意，外层循环要倒着写，内层循环要正着写
// 因为要求dp[i][j] 需要知道dp[i+1][j-1]
for(int i=n-1; i>=0; i--){
for(int j=i; j<n; j++){
// (s.charAt(i)==s.charAt(j) 时，当元素个数为1,2,3个时，一定为回文子串
if(s.charAt(i)==s.charAt(j) && (j-i<=2 || dp[i+1][j-1])){
dp[i][j] = true;
res++;
}
}
}
return res;
}
}
dp降维优化
没看明白
class Solution {
public int countSubstrings(String s) {
// dp[i][j]：s[i : j] 是否为回文子串
// 转移方程：dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1]
// 计算顺序：i 从大到小，j 任意
// i 那维可以消掉，计算顺序：i 从大到小，j 从大到小
int res = 0;
boolean[] dp = new boolean[s.length()];
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = s.length() - 1; j >= i; j--) {
// aa a aaa 肯定是回文
dp[j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[j - 1]);
if (dp[j]) {
res++;
}
}
}
return res;
}
}
这里说了为什么要降 怎么想到降维
https://leetcode-cn.com/problems/palindromic-substrings/solution/shou-hua-tu-jie-dong-tai-gui-hua-si-lu-by-hyj8/
思路2:中心扩展法
没看明白
感觉和dp思路差不多
https://leetcode-cn.com/problems/palindromic-substrings/solution/liang-dao-hui-wen-zi-chuan-de-jie-fa-xiang-jie-zho/
该思路的评论区：
- left和center ，是如何看出存在2倍关系的？
- 想问一下动态规划中：
for (int j = 0; j < s.length(); j++) {
for (int i = 0; i <= j; i++)
这个循环是怎么想的，为什么先限定j 而不是
for（int i= 0； i < s.length(）, i++){
for(int j = i; j <s.length(), j++){
198 打家劫舍
思路1:超时
dfs遍历所有方案，找出最大的
class Solution {
public int rob(int[] nums) {
int max=0,cnt=0;
return dfs(nums,cnt,max,0);
}
int dfs(int[] nums,int cnt,int max,int index){
if(index>=nums.length){
if(cnt>max){
max=cnt;
}
return max;
}
return Math.max(dfs(nums,cnt+nums[index],max,index+2),
dfs(nums,cnt,max,index+1));
}
}
思路2:动态规划
！！动态规划的的四个解题步骤是：
- 定义子问题
- 写出子问题的递推关系
- 确定 DP 数组的计算顺序
- 空间优化（可选）
下面我们一步一步地进行讲解。
步骤一：定义子问题
稍微接触过一点动态规划的朋友都知道动态规划有一个“子问题”的定义。什么是子问题？子问题是和原问题相似，但规模较小的问题。例如这道小偷问题，原问题是“从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是“从 k 个房子中能偷到的最大金额”，用 f(k) 表示。
(重点：“从 k 个房子中能偷到的最大金额”，你不用管第k间房子偷不偷，f(k)的定义就是：“从 k 个房子中能偷到的最大金额”。第k间不一定偷)
可以看到，子问题是参数化的，我们定义的子问题中有参数 k。假设一共有 n 个房子的话，就一共有 n 个子问题。动态规划实际上就是通过求这一堆子问题的解，来求出原问题的解。这要求子问题需要具备两个性质：
- 原问题要能由子问题表示。
例如这道小偷问题中，k=n 时实际上就是原问题。否则，解了半天子问题还是解不出原问题，那子问题岂不是白解了。 - 一个子问题的解要能通过其他子问题的解求出。
例如这道小偷问题中，f(k) 可以由 f(k−1) 和 f(k−2) 求出，具体原理后面会解释。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题，那么这道题实际上没法用动态规划解。
小偷问题由于比较简单，定义子问题实际上是很直观的。一些比较难的动态规划题目可能需要一些定义子问题的技巧。
class Solution {
public int rob(int[] nums) {
int[] dp=new int[nums.length+1];//!!!!!
dp[0]=0;dp[1]=nums[0];
for(int i=2;i<=nums.length;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);
}
return dp[nums.length];
}
}
207 课程表
题意：你这个学期必须选修 numCourses 门课程，所以只要课程间形成了环，你就无法选修完所有的课程
思路：拓扑排序(广度优先遍历)
算法笔记415
关键点：邻接表、入度数组、队列、java容器的使用
代码艰难的按照思路写出来
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] inDegree=new int[numCourses];
List<List<Integer>> adjacency=new ArrayList<>();//邻接表
LinkedList<Integer> queue=new LinkedList<>();
//Queue<Integer> queue = new LinkedList<>();
for(int i=0;i<numCourses;i++){//重要
adjacency.add(new ArrayList<>());
}
for(int i=0;i<prerequisites.length;i++){
int pre=prerequisites[i][0],next=prerequisites[i][1];
inDegree[next]++;
adjacency.get(pre).add(next);//!!
}
for(int i=0;i<numCourses;i++){
if(inDegree[i]==0) queue.offer(i);
}
int cnt=0;
while(queue.size()>0){
//while(!queue.isEmpty()) {
int cur=queue.poll();cnt++;
//删除所有以它为出度的
//for(int j=0;j<adjacency.get(cur).size();j++){
for(int next:adjacency.get(cur)){
//int next=adjacency.get(cur).get(j);
//inDegree[next]--;
//if(inDegree[next]==0) queue.offer(next);
if(--inDegree[next]==0) queue.offer(next);//!
}
}
if(cnt==numCourses) return true;
else return false;
}
}
标准代码
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
int[] indegrees = new int[numCourses];
List<List<Integer>> adjacency = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++)
adjacency.add(new ArrayList<>());
// Get the indegree and adjacency of every course.
for(int[] cp : prerequisites) {
indegrees[cp[0]]++;
adjacency.get(cp[1]).add(cp[0]);
}
// Get all the courses with the indegree of 0.
for(int i = 0; i < numCourses; i++)
if(indegrees[i] == 0) queue.add(i);
// BFS TopSort.
while(!queue.isEmpty()) {
int pre = queue.poll();
numCourses--;
for(int cur : adjacency.get(pre))
if(--indegrees[cur] == 0) queue.add(cur);
}
return numCourses == 0;
}
}
思路2:深度优先遍历
没看 自己找题解或者评论区吧
