shanshanhi-CSDN博客

转载将数组分成两部分，使得这两部分的和的差最小

将一个数组分成两部分，不要求两部分所包含的元素个数相等，要求使得这两个部分的和的差值最小。比如对于数组{1,0,1,7,2,4}，可以分成{1,0,1,2,4}和{7}，使得这两部分的差值最小。思路：这个问题可以转化为求数组的一个子集，使得这个子集中的元素的和尽可能接近sum/2，其中sum为数组中所有元素的和。这样转换之后这个问题就很类似0-1背包问题了：在n件物品中找到m件

2017-03-28 17:35:32 26259 3

原创 494. Target Sum 和 416. Partition Equal Subset Sum

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.Find out

2017-03-10 11:00:26 393

转载 select、poll、epoll之间的区别总结[整理]

select，poll，epoll都是IO多路复用的机制。I/O多路复用就通过一种机制，可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。但select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用

2017-03-08 17:32:46 264

转载 5. Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.分析：采用中

2017-03-02 17:14:46 374

原创 15. 3Sum，16. 3Sum Closest，18. 4Sum（最后一个方法重要）重要

第一题、15. 3Sum Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not

2017-02-28 18:38:27 918

原创 26. Remove Duplicates from Sorted Array and 80. Remove Duplicates from Sorted Array II

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not allocate extra space for another array, you must do this in place with cons

2017-02-23 19:21:40 222

原创 75. Sort Colors--荷兰三色国旗问题

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.Here, we will use the integers 0, 1,

2017-02-23 18:55:48 503

原创 78. Subsets ,90. Subsets II(待研究)---位运算法（重要和Combination Sum一系列的题目类似）

第一题、78. Subsets Given a set of distinct integers, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,3], a solution is: [ ...

2017-02-23 15:35:21 372

转载 152. Maximum Product Subarray Add to List --- 注意

Find the contiguous subarray within an array (containing at least one number) which has the largest product.For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest produ

2017-02-18 11:08:07 558

原创发现一个数组中重复的数字，448和287的总结 ---重要

区别一、448题目没有限制不能改变原来的数组，所以采用的是交换机制，不断的将错误位置上的数据不断的交换移动到本该属于其的位置上去，则重新遍历时，nums[i]!=i+1的数字即没有出现的数字，但287题目则限制了不能改变原来的数组，所以不能采用交换机制的方法，方法类似采用查找循环链表的环入口的方法，或者可以采用利用二分查找的思想；区别二、448题目中1-n之间重复的数字只出现了两次，但是在287

2017-02-17 13:39:34 889

原创 Combination Sum系列的三个题目39,40,216--重要（和78. Subsets ,90. Subsets II类似）

Combination Sum Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number ma

2017-02-17 13:08:30 404

原创 219. Contains Duplicate II---数组中两个重复的数字的下标最多相差k

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

2017-02-17 10:46:31 675

原创 217. Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is

2017-02-17 10:30:59 268

原创 1. Two Sum，167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.The function twoSum should return indices of the two numbers suc

2017-02-13 18:07:01 303

原创二叉树（二叉搜索树）上的两节点的公共祖先节点（235和236）

一、二叉搜索树上的两节点的公共祖先 235. Lowest Common Ancestor of a Binary Search Tree Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.According to the defini

2017-01-15 00:07:43 517

原创 AI Programmer--利用遗传算法实现AI Programmmer

本文是在读完AI Programmer：Autnomously Creating Software Programs Using Genetic Algorithms一文之后写的总结。一、文章的任务本文提出了一个可以自动完成编程任务的机器学习模型，即AI programmer。该模型使用遗传算法（Genetic Algorithm）进行优化搜索，模型可以在大部分普通机器上运行且仅需要最低限...

2018-11-22 11:06:27 2073

转载 increasing subsequences (递增子序列)

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .Example:Input: [4,...

2018-04-17 20:48:43 398

原创 knight-probability-in-chessboard(“马”在棋盘上的概率)

On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exactly K moves. The rows and columns are 0 indexed, so the top-left square is (0, 0), and the bottom-right s...

2018-04-17 19:15:49 1711

转载 Out of Boundary Paths 出界的路径

There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However...

2018-04-17 18:31:02 319

原创 Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of ...

2018-04-17 18:13:53 207

原创递归和非递归的辗转相除法

#include using namespace std;int gcd(int m,int n){ while(n!=0) { int rem = m % n; m = n; n = rem; } return m;} int gcd1(int num1, int num2){ if(num1<num2) return gcd1(num2,num1);

2017-12-05 09:04:03 1656

转载单链表排序----快排 & 归并排序

题目描述：　　给定一个乱序的单链表的头节点，对该链表中的节点进行排序　　要求时间复杂度为O(nlgn），空间复杂度为O(1)　　　　　　分析：　　由于题目要求时间复杂度我O(nlgn），因此选择排序和插入排序可以排除。　　在排序算法中，时间复杂度为O(nlgn）的主要有：归并排序、快速排序、堆排序。　　其中堆排序的空间复杂度为（n），也不符合要求，因此也可

2017-10-17 18:15:59 849

转载免费陷阱的问题--动态规划

免费馅饼Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 28835 Accepted Submission(s): 9848Problem Description都说天上不会掉馅饼，但有一天g

2017-03-28 15:30:42 702

原创 Python UnicodeDecodeError: 'gbk' codec can't decode byte 0xe9

在使用Python 3.5版本编码的过程中，直接open(filename,’r’),总是报错：Python UnicodeDecodeError: ‘gbk’ codec can’t decode byte 0xe9但是在用Python2.7版本的时候却什么错误都没有解决方案：在头文件中增加import codecs 然后将open(filename,’r’),改成：codecs.op

2017-03-25 20:42:14 4590

原创利用数组实现的堆排序

void HeapSort(int a[],int n){ int i; for(i = n/2; i > 0; i--){//构建初始堆 HeapAdjust(a,i,n); } for(i = n; i > 1; i--){//不断输出最大元素进行排序，输出后继续调整 swap(a,1,i); HeapAdjust(a,1,i-1); }}void HeapA

2017-03-22 13:38:10 1524 1

转载最大滑动窗口

参考：http://blog.csdn.net/ssjhust123/article/details/7967489http://codercareer.blogspot.com/2012/02/no-33-maximums-in-sliding-windows.htmlhttp://leetcode.com/2011/01/sliding-window-maximum.html

2017-03-22 12:03:21 352

转载什么是死锁及死锁的必要条件和解决方法【转】

进程死锁及解决办法操作系统 2009-09-24 16:48:58 阅读767 评论1 字号：大中小订阅一、要点提示（1）掌握死锁的概念和产生死锁的根本原因。（2）理解产生死锁的必要条件--以下四个条件同时具备：互斥条件、不可抢占条件、占有且申请条件、循环等待条件。（3）记住解决死锁的一般方法，掌握死锁的预防和死锁的避免二者的基本思想。（4）掌握

2017-03-17 20:57:50 559

转载进程与线程的通信方式

一、进程间的通信方式# 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。# 有名管道 (namedpipe) ：有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。# 信号量(semophore ) ：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机

2017-03-17 12:21:15 437

原创链表刷题总结-技巧以及注意事项

技巧：1.插入头节点的技巧，诸如：删除链表中重复节点的题，反转链表某个区间的题等，通过插入头节点，可以使得对头节点的操作同后面节点的操作一样；2.设置一快一慢指针，诸如：判断一个链表是否有环，有环环的入口点，链表的快速排序（通过求中间节点，然后merge，递归实现的快速排序）等

2017-03-13 20:04:31 1202

转载 NAT外网访问内网方法,内网端口映射外网ip

由于公网IP地址有限，不少ISP都采用多个内网用户通过代理和网关路由共用一个公网IP上INTERNET的方法，这样就限制了这些用户在自己计算机上架设个人网站，要实现在这些用户端架设网站，最关键的一点是，怎样把多用户的内网IP和一个他们唯一共享上网的IP进行映射！就象在局域网或网吧内一样，虽然你可以架设多台服务器和网站，但是对外网来说，你还是只有一个外部的IP地址，怎么样把外网的IP映射成相应的内网

2017-03-13 18:07:07 11266

转载 C++四种强制转换

C++的四种强制类型转换，所以C++不是类型安全的。分别为：static_cast , dynamic_cast , const_cast , reinterpret_cast为什么使用C风格的强制转换可以把想要的任何东西转换成合乎心意的类型。那为什么还需要一个新的C++类型的强制转换呢？新类型的强制转换可以提供更好的控制强制转换过程，允许控制各种不同种类的强制转换。C++中风格是stat

2017-03-13 17:59:47 335

转载 C++拷贝构造函数详解

一. 什么是拷贝构造函数首先对于普通类型的对象来说，它们之间的复制是很简单的，例如：[c-sharp] view plain copyint a = 100; int b = a; 而类对象与普通对象不同，类对象内部结构一般较为复杂，存在各种成员变量。下面看一个类对象拷贝的简单例子。[c-

2017-03-13 17:50:37 221

转载 C++实现顺序栈的基本功能

栈是限定仅在表头进行插入和删除操作的线性表，有着先进后出的特点（FILO）；现在我来动手实现栈的基本本功能练练手；定义栈的头文件如下：[cpp] view plain copy#ifndef CSTOCK_H_ #define CSTOCK_H_ const int STOCK_SIZE = 100;//定

2017-03-13 17:32:36 978

转载 C++运算符重载讲解与经典实例

C++中预定义的运算符的操作对象只能是基本数据类型，实际上，对于很多用户自定义类型，也需要有类似的运算操作。例如： class complex { public: complex(double r=0.0,double I=0.0){real=r;imag=I;} void display(); private: double real; dou

2017-03-13 17:25:28 302

转载 C++模板：函数模板和模板函数

1.函数模板的声明和模板函数的生成1.1函数模板的声明函数模板可以用来创建一个通用的函数，以支持多种不同的形参，避免重载函数的函数体重复设计。它的最大特点是把函数使用的数据类型作为参数。函数模板的声明形式为：template(参数表){ 函数体}其中，template是定义模板函数的关键字；template后面的

2017-03-13 17:18:30 364

转载 C++抽象类

一、纯虚函数定义. 纯虚函数是在基类中声明的虚函数，它在基类中没有定义，但要求任何派生类都要定义自己的实现方法。在基类中实现纯虚函数的方法是在函数原型后加“=0”二、引入原因：1、为了方便使用多态特性，我们常常需要在基类中定义虚拟函数。2、在很多情况下，基类本身生成对象是不合情理的。例如，动物作为一个基类可以派生出老虎、孔雀等子类，但动物本身生成对象明显不合常理。

2017-03-13 17:15:35 504

转载各种排序算法的总结和比较

1 快速排序（QuickSort）快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。（1）如果不多于1个数据，直接返回。（2）一般选择序列最左边的值作为支点数据。（3）将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。（4）对两边利用递归排序数列。快速排序比大部分排序算法

2017-03-13 13:14:34 992

转载归并排序的实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。[cpp] view plain copy

2017-03-13 13:02:12 271

转载 C++ 智能指针详解

C++ 智能指针详解一、简介由于 C++ 语言没有自动内存回收机制，程序员每次 new 出来的内存都要手动 delete。程序员忘记 delete，流程太复杂，最终导致没有 delete，异常导致程序过早退出，没有执行 delete 的情况并不罕见。用智能指针便可以有效缓解这类问题，本文主要讲解参见的智能指针的用法。包括：std::auto_ptr、boost::scoped_p

2017-03-13 10:26:19 190

转载变量定义和声明的区别（整理）

变量的声明有两种情况：1、一种是需要建立存储空间的。例如：int a 在声明的时候就已经建立了存储空间。2、另一种是不需要建立存储空间的。例如：extern int a 其中变量a是在别的文件中定义的。声明是向编译器介绍名字－－标识符。它告诉编译器“这个函数或变量在某处可找到，它的模样象什么”。而定义是说：“在这里建立变量”或“在这里建立函数”。它为名字分配存储空

2017-03-09 18:32:27 562

空空如也

空空如也