feengzhk-CSDN博客

原创课后作业课本NP-complete证明题

8.3吝啬SAT问题是这样的:给定一组子句（每个自举都是其中文字的析取）和整数k，求一个最多k个变量为rue的满足赋值——如果该赋值存在。证明吝啬SAT是NP-完全问题。首先，易知STINGY SAT 的解是可在多项式时间内验证的，因此属于NP。另外，很容易可以将SAT 归约到STINGY SAT（将k 设为所有变量的总个数即可），于是可知STINGY SAT 为NP 完全问题。给定方

2017-07-11 22:04:22 333

原创 179. Largest Number

只需要保证 s1 + s2 > s2 + s1 class Solution {public: string largestNumber(vector& nums) { vector arr; for(auto i:nums) arr.push_back(to_string(i)); sort(arr.begi

2017-07-07 00:26:55 133

原创 189 Rotate Array

方法一：旋转数组，可以收尾相连看成一个循环数组初始化一个数组跟原数组一样数值，然后通过循环数组去赋值void RotateArray(int a[],int n,int k){ int *b = new int [n]; for(int i = 0;i < n;i++) b[i] = a[i]; for(int i = 0;i < n;i++)

2017-07-06 21:42:19 129

原创 198 House Robber

这里不能取数组相邻的俩个数，但是需要去个数组和的最大值方法一：建一个和原数组一样大小的DP数组，DP的每个值表示此时可以取到的最大和。int HouseRobber(int a[],int n){ int *dp = new int [n]; dp[0] = a[0]; dp[1] = max(a[1],a[0]); for(int i = 2; i

2017-07-06 21:11:15 140

原创 459. Repeated Substring Pattern

看了几天的kmp算法终于可以自己写出来了。class Solution {public: bool repeatedSubstringPattern(string s) { int n = s.size(); vector next(n,0); int j = 0; for(int i = 1;i < n;i++)

2017-06-06 20:51:24 293

原创 242. Valid Anagram

思路一：class Solution {public: bool isAnagram(string s, string t) { vector alphabet(26,0); for(int i = 0;i < s.size();i++) alphabet[s[i] - 'a']++; for(int j = 0

2017-05-31 14:00:13 171

原创 541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of th

2017-05-22 12:12:55 182

原创 85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.For example, given the following matrix:1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1

2017-05-14 23:47:05 162

原创 106. Construct Binary Tree from Inorder and Postorder Traversal

对于后序遍历来说，最后一个元素一定是根节点。然后在中序遍历中找的其未知，左边是左子树，右边是右子树。左子树在后序遍历中的最后一个节点又是根节点，从而递归下去。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode

2017-05-08 15:50:22 141

原创 104. Maximum Depth of Binary Tree

这个题目用递归的方法可以很容易理解和编写只是可能如果数据量很大的时候会导致栈的空间不够用用递归的方法的代码是：递归最重要的就是递归条件，不然会无限递归下去class Solution {public: int maxDepth(TreeNode* root) { return root == NULL ? 0 : max(maxDepth(root->lef

2017-04-30 16:42:32 153

转载 Nagle Algorithm

转: http://bbs.chinaunix.NET/thread-3767363-1-1.html在网络拥塞控制领域，我们知道有一个非常有名的算法叫做Nagle算法（Nagle algorithm），这是使用它的发明人John Nagle的名字来命名的，John Nagle在1984年首次用这个算法来尝试解决福特汽车公司的网络拥塞问题（RFC 896），该问题的具体描述是：如果我们的应

2017-04-28 16:28:15 504

转载水平触发和边缘触发

水平触发绪通知方式是水平触发，也就说如果内核通知应用层某一个文件描述符已经就绪，而如果应用层此后一直没有完整的处理该描述符（没有读取完相应的数据或者没有写入任何数据），那么内核会不断地通知应用层该文件描述符已经就绪。这就是所谓的水平触发：只要条件满足，那内核就会触发一个事件（只要文件描述符对应的数据没有被读取或者写入，那内核就不断地通知你）。边缘触发所谓边沿触发是相对水平触发而言的

2017-04-19 23:11:58 638

原创 46. Permutations

全排列问题比如给个数字 123 如何将他们进行全排列我们这里用到了递归的思考比如1跟2先调换 213 然后 1 跟 3 重新进行全排列,然后再调换回来swap(p[0],p[1]);permutations(p,1,2);swap(p[0],p[1]);然后1 跟 3 调换变成 321 然后 2跟1重新进行全排列swap(p[0],p[2]);

2017-04-18 11:54:49 601 1

原创 202. Happy Number

Write an algorithm to determine if a number is "happy".A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares

2017-04-16 22:54:04 175

原创 404. Sum of Left Leaves

3 / \ 9 20 / \ 15 7There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.class Solution {public: int sumOfLeftLeaves(TreeNode* root) {

2017-04-09 23:46:31 163

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; ot

2017-03-28 22:15:58 140

原创 283. Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.For example, given nums = [0, 1, 0, 3, 12], after calling you

2017-03-28 20:41:36 134

原创 169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.You may assume that the array is non-empty and the majority element

2017-03-26 22:50:07 155

原创 344. Reverse String

Write a function that takes a string as input and returns the string reversed.Example:Given s = "hello", return "olleh".class Solution {public: string reverseString(string s) { int

2017-03-19 22:46:03 202

原创 162. Find Peak Element

A peak element is an element that is greater than its neighbors.Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.The array may contain multiple peaks, in

2017-03-12 20:37:17 235

原创 9. Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.click to show spoilers.Some hints:Could negative integers be palindromes? (ie, -1)If you are thinking of convertin

2017-03-12 20:30:03 135

原创 461. Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.Given two integers x and y, calculate the Hamming distance.这个题目是要我们算两个正整数

2017-02-26 23:41:09 153

feengzhk的博客