福田网站建设-信科网络,韩国 网站设计,frontpage做网站,网站推广淘宝联盟怎么做新的一周#xff0c;新的专题。array的中等难度的题目快要结束了。能感觉到进步#xff0c;也依然能感觉到吃力。加油。
31 Next Permutation
思路#xff1a;读懂了题意#xff0c;知道是要求下一个排列数是什么。如果已经到最后一个了#xff0c;那就返回最小的那个。…新的一周新的专题。array的中等难度的题目快要结束了。能感觉到进步也依然能感觉到吃力。加油。
31 Next Permutation
思路读懂了题意知道是要求下一个排列数是什么。如果已经到最后一个了那就返回最小的那个。但是盯着那个 1,2,3;3,2,1看了两分钟毫无头绪。搜索到一篇好文章原来样例数据也很重要哦。把样例数据加长就能发现规律了。下面的内容和原文章基本一样。 例如输入6 5 4 8 7 5 1应该返回什么呢 首先肯定这个排列没有到最大不是返回最小的排列因为最起码8没在第一位。 第二从后面看起。5比1大如果调换5,1排列数更小不对。调换7,5也一样。继续看发现到4的位置可以换了。原来4后面的8 7 5 1 是一个递减序列。根据递减序列找到要替换的元素4。 第三4应该被5替换也就是递减序列中比4大的最小元素。替换之后是 6 5 5 8 7 4 1。 第四8 7 4 1 按照升序排列。 学习看完别人的答案我才知道我对6 5 4 8 7 5 1应该返回什么头脑中并没有清晰的概念。只是大概知道怎么做。样例数据延长有助于发现规律。 代码
79 Word Search
思路基本思路是回溯法。遍历board把每个char的位置放入map中。然后从word的第一个字符开始找。递归的退出条件是idxword.length。每一步查找的时候都只是查找固定位置相邻的位置上的元素。这里需要注意的是一个位置的元素被访问过以后就不能再访问了。我使用了双向队列解决这个问题。 学习直接修改board[i][j]*标记已经访问过的元素。速度更快。总结一下标记数组是否访问过可以开辟新的空间做标记可以修改原数组的值标记。修改原数组值可以修改为别的值或者添加负号。 代码
数字加和问题总结
两数字加和 三数字加和 四数字加和 四数组加和II 数字加和问题有几个细节1 返回的是数组下标还是数值2 数组是排序好的吗3 数组中有重复元素吗
782. Transform to Chessboard
题意特点1N∗NN∗NN*N的矩阵特点2相邻位置是指横轴和纵轴相邻的4个位置特点3:元素值0的4个邻居都是1元素值1的4个邻居都是0。 思路将例题的输入做了以下操作得到有效矩阵 如果矩阵中有相邻的两行或者相邻的两列相同就需要交换操作。 接下来思考如何判断矩阵中相邻两行相同。下标从0开始。第1行与第0行比较第2行与第1行比较。 还要思考如果找到相同的两行应该换到什么位置。例如第1行和第0行相同移动第1行第1行与第2行不同 第1行和与第2行换位置。再次比较新的第2行与第3行是否相同。当找不到替换位置的时候返回-1。
学习上面的总结并不彻底。参考网页 一个有效的矩阵的性质有 1 当第一行输入定了以后只有两种行数据0110和1001不会有形式。其中一种是另外一种的逆。对列也是一样的。由此观察到矩阵上左、上右、下左、下右四个位置的值可能是4个0也肯能是2个0和2个1或者4个1。 2 每一行(列)有一半值是1一半值是0。如果n2*k那么每行(列)有k个0k个1如果n2*k1那么每行(列)有k个0,k1个1或者k个1,k1个0。
152 Maximum Product Subarray
思路乘积最大的子数组立马联想到了和最大的子数组。都用动态规划。这里和与乘积有一个最大的区别是负数正数正数负数正数正数负数+正数而负数∗正数负数负数∗正数负数 负数*正数负数∗负数负数负数∗负数负数 负数*负数>负数。对于本题的状态转移方程就不只是和最大值之间的关系了。 dp[i]Math.max(Math.max(dp[i-1]*nums[i],dpMin[i-1]*nums[i]),nums[i]); dp[i-1]存储到i-1下标最大的乘积dpMin[i-1]存储到i-1下标最小的乘积。 这个题目与 Subarray Sum Equals K 是有区别的。 代码
