题解
简单的动态规划吧算是 还是比较简单的题目 首先计算sum的值,如果和的值大于0那么这一段的和就对后面那个数有用,否则,就重新从下一个数开始,然后取最大值。
代码
class Solution {
public:int maxSubArray(vector<int>& nums) {int n = nums.size();int ans = nums[0],sum = 0;for(int i = 0; i < n; i++){if(sum > 0){sum = sum + nums[i];}else{sum = nums[i];}ans = max(ans , sum);}return ans;}
};
Rotate ImageTotal Accepted: 37958 Total Submissions: 118891 You are given an n x n 2D matrix representing an image.Rotate the image by 90 degrees (clockwise).Follow up:
Could you do this in-place? 先按145°对角线将图像对称翻转, 再将各行逆序翻转即可 class Solution {
public:void rotate(vector<vector<int> > &matrix) {int n = matrix.size();for (int y = 1; y < n; y++)for (int x = 0; x < y; x++)swap(mat...
Problem:Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.Summary:不使用+和-符号,计算两个整型数之和。Analysis:XOR相当于二进制数的无进位加法。进位位由两数&运算后左移一位确定。Example:用此方法计算5 + 3:1、无进位结果:101 ^ 011 = 110 进位:101 & 011 = 001 左移:001 << 1 = 0102、将进位与原结果相加:110 ^ 010 = 100 进位:110 & 010 = 010 左移:0...
https://leetcode.com/problems/house-robber/题目设计了一个抢劫犯的情景,其实就是求数组中不相邻数据进行组合得到的最大值举一个例子假设数据: 8 3 6 15 4 9 7 10那么首先可能选取 8 , 3每一个数字的选取都是根据他的前两个数字,前三个数字得到的最大值进行选择,等到6的时候考虑前面只能和8组合 8,3,14到数字15,那么就可以考虑在8,3中进行组合 8,3,14,23,4,9,7,10接下来的步骤:8,3,14,23,18,9,7,108,3,14,23,18,32,7,1...
Paint HouseThere are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of...
二叉搜索树的后续遍历序列输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。单挑递增栈辅助,逆向遍历数组// 单调递增栈辅助,逆向遍历数组。
var verifyPostorder = function (postorder) {
// 单调栈使用, 单调递增的单调栈
let stack = [];
// 表示上一个根节点的元素,这里可以把postorder的最后一个元素root看成无穷大节点...
问题描述:
给你一个字符串 s,找到 s 中最长的回文子串。
代码:
public class Solution {public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; }int maxLen = 1; int begin = 0; // dp[i][j] 表示 s[i..j] 是否是回文串 boolean[][] dp = new boolean[len][len]; // 初始化:所有长度为 1 的子串都是回文串 for (...
Given a list, rotate the list to the right by k places, where k is non-negative.For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL. 思路:先遍历一遍,得出链表长度,注意k可能大于len令k%=len,将尾节点next指针指向首节点,形成一个环 ,然后接着跑len-k步, 从这里断开,就是要求的结果。 1/**2 * Definition for singly-linked list.3 * struct ListNode {4 * int val;5 * ListNod...
请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点。传入函数的唯一参数为 要被删除的节点 。
现有一个链表 – head = [4,5,1,9],它可以表示为:
示例 1:
输入:head = [4,5,1,9], node = 5 输出:[4,1,9] 解释:给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9. 示例 2:
输入:head = [4,5,1,9], node = 1 输出:[4,5,9] 解释:给定你链表中值为 1 的第三个节点,那么在调用了...
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.基本思路:由于队列已经进行排序,每次取其中点,作为树的根。即可建得一棵平衡二叉树。/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* sortedA...
Problem Definition:Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. For example,"A man, a plan, a canal: Panama" is a palindrome."race a car" is not a palindrome.Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid pali...
题目地址
https://leetcode-cn.com/problems/video-stitching/
题目描述
将会获得一系列视频片段,这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠,也可能长度不一。视频片段 clips[i] 都用区间进行表示:开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑,例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。我们需要将这些片段进行再剪辑,并将剪辑后的内容拼接成...
题目链接:合并K个排序链表题意:合并k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。题解:这题的前身是合并两个排序链表。在剑指里有写。可以点击链接查看。。这个题,最好就是用小顶堆,O(nlog(K))。用c++的优先队列可以解决这个小顶堆。把每个节点丢进优先队列,然后以出队列的顺序作为新链表顺序代码: 1/**2 * Definition for singly-linked list.3 * struct ListNode {4 * int val;5 * ListNode *...
这个题也是括号的匹配,但是不是让你判断是否匹配,而是让找出所有匹配的情况,与以前的题目并不一样,难度也不是一个等级的。看到题目的测试用例,我的第一反应是循环,因为我对循环比较敏感吧,所以我用循环写了一下,但是我发现,n=2的时候很简单就写出了代码,但是n=3的时候就有点麻烦了,当n=4的时候--------我感觉大脑要炸了... 这说明了这个思路不行,必须换种思路去解题,所以我给自己一个n值-------- n=100 !好吧,我...
Partition ListGiven a linked list and a value x, partition it such that all
nodes less than x come before nodes greater than or equal
to x.You should preserve the original relative order of the nodes in each of the
two partitions.For
example,Given 1->4->3->2->5->2 and x =
3,return 1->2->2->4->3->5. 维护两个链表,一个记录比x小的(头newl, 尾left),一个记录不小于x的(头newr,尾right)。扫描一遍链...