寻路人davey-CSDN博客

原创快排、堆排序

快排：快速排序主要运用了二分的思想，每次选择一个基准元素，比基准元素打的元素都放在基准元素前面，比基准元素小的元素都放在基准元素后面，这样不断递归细分，完成排序。C++代码实现：void QuickSort(int a[], int l, int r){ int temp = a[l]; int i = l, j = r; if(l<r){ while(i<j

2017-08-04 18:10:55 350

原创求二叉树深度、判断是否是平衡二叉树

求二叉树深度：递归的方法：从根节点按照先序顺序遍历二叉树，返回左子树和右子树中较大的深度，再加上1就是根节点的深度。C++代码实现：typedef struct TreeNode{ int data; struct TreeNode* leftchild; struct TreeNode* rightchild;}TreeNode, *Bitree;int TreeMaxDe

2017-08-04 13:55:53 591

原创数字在排序数组中出现的次数

题目：统计一个数字在排序数组中出现的次数。例如输入{1，2，3，3，3， 3，4，5}和数字3，那么输出应该是4，因为3出现了4次。思路：直接暴力求解时间复杂度为O(n) ,下面利用二分查找的思想，给出时间复杂度为O(logn) 的算法： 1. 利用二分查找的思想，找到第一个出现的K，时间复杂度为O(logn) ; 2. 利用二分查找的思想，找到最后一个出现的K，时间复杂度为O(logn)

2017-08-02 22:32:59 363

原创查找树中两个节点的最低公共祖先

求树中两个节点的最低公共祖先给定一棵树和两个节点，求解这两个节点在树中的最低公共祖先节点。（剑指Offer）思路：从根节点遍历树，直到要查找的节点，保存从根节点到要查找的节点的路径。遍历两次树，即保存了根节点到要查找的两个节点的两条路径，然后求出两条路径的最后一个交点即可。C++代码实现：#include <iostream>#include <vector>#include <list>u

2017-08-02 20:56:37 768

原创 LeetCode -- 650. 2 Keys Keyboard

题目：Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:Copy All: You can copy all the characters present on the notepad (partial copy

2017-08-02 11:49:22 1768

原创 C语言中atoi()函数实现--字符串转int型整数

C语言中有个atoi()函数，将字符串转成整数，返回int类型的数值。思路很简单，但是有很多边界和细节要处理，本文参考剑指offer上的实例，仅供参考。#include <iostream>#include <string>enum Status{kValid = 0, kInValid};int g_nStatus = kValid;long long str2intCore(const ch

2017-08-01 20:21:53 4290

原创 LeetCode -- 213. House Robber II

题目：After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a

2017-08-01 17:40:25 251

原创 LeetCode -- 198. House Robber

题目：You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent hou

2017-08-01 16:28:47 264

原创 LeetCode -- Range Sum Query - Immutable

题目：Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.Given nums = [-2, 0, 3, -5, 2, -1]sumRange(0, 2) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3No

2017-08-01 10:54:16 169

原创 LeetCode -- 118. Pascal's Triangle

题目：Given numRows, generate the first numRows of Pascal’s triangle. For example, given numRows = 5, Return[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]思路：本题主要考查vector 的基本操作，杨辉三角形的计算

2017-07-26 21:53:53 207

原创 LeetCode -- 88. Merge Sorted Array

题目：Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additio

2017-07-26 21:15:06 200

原创 LeetCode -- 66. Plus One

题目：Given a non-negative integer represented as a non-empty array of digits, plus one to the integer. You may assume the integer do not contain any leading zero, except the number 0 itself. The digits

2017-07-25 23:42:54 211

原创 LeetCode -- 122. Best Time to Buy and Sell Stock II

题目：Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy on

2017-05-26 09:26:24 230

原创 LeetCode -- 121. Best Time to Buy and Sell Stock

题目：Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),

2017-05-25 17:02:00 263

原创 LeetCode -- 120. Triangle

题目：Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.For example, given the following triangle[ [2], [3,4], [6,5,7]

2017-05-25 16:12:31 218

原创 LeetCode -- 96. Unique Binary Search Trees

题目：Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?For example, Given n = 3, there are a total of 5 unique BST’s. 1 3 3 2 1 \

2017-05-17 23:20:26 187

原创 LeetCode -- 70. Climbing Stairs

题目：You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?Note: Given n will be a positive

2017-05-17 11:15:14 203

原创 LeetCode -- 64. Minimum Path Sum

题目：Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.Note: You can only move either down or right at a

2017-05-17 11:00:03 202

原创 LeetCode -- 63. Unique Paths II

题目：Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid

2017-05-17 10:21:01 188

原创 LeetCode -- 62. Unique Paths

题目：A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the

2017-05-17 09:41:31 292

原创 LeetCode -- 53. Maximum Subarray

题目：Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array[-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has t

2017-05-16 23:37:53 199

原创 LeetCode -- 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.Example:Input: "babad"Output: "bab"Note: "aba" is also a valid answer.Example:Inp

2017-05-16 22:49:14 197

原创 Leetcode -- 491. 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:

2017-05-11 23:25:11 367

原创 Leetcode -- 38. Count and Say

题目：The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ...1 is read off as “one 1” or 11. 11 is read off as “two 1s” or 21. 21 is read off as “one 2

2017-05-10 23:54:02 221

原创凸包（Convex Hull）问题的三种解法: 暴力，Graham Scan，分治

凸包问题描述：平面上n个点的集合Q的convex hull是一个最小凸多边形P，Q的点或者在P上或者在P内。凸多边形P是具有如下性质多边形：连接P内任意两点的边都在P内暴力法：思想：从所有的点中找到y坐标最小的点P0，此点一定在凸包内，加入到凸包点集，然后遍历剩下点：每次选取两个点Pi，Pj，验证其他所有点是否在P0，Pi，Pj组成的三角形内。如果这个点不在所有组成的三角形内，则这个点是凸

2017-05-08 10:21:26 3995

原创阿里笔试 -- 小张和姑娘约会

题目：小张很多年过年都没有回家了，这次回家父母给他安排了很多个相亲的姑娘，有一个很长的名单，长度为N。父亲负责安排约会，每次随机的选择一个要相亲的对象，母亲负责记录哪些姑娘已经约会过了。直到和所有的姑娘都约会完一遍以后，这个浩大的相亲工程才会结束。这些天父母在吵架，他们之间不会有任何的言语沟通。所以父亲不知道哪些姑娘已经约会过了。因此下次约会的对象很可能是以前已经约会过的。如果小张要把所有的姑娘都约

2017-04-27 09:51:37 859

原创 Leetcode -- 36. Valid Sudoku

题目：Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. A partially filled sud

2017-04-24 21:42:21 205

原创最长公共子序列（Longest Common Sequence）

问题的定义：子序列 –X=(A, B, C, B, D, B) – Z=(B, C, D, B)是X的子序例 –W=(B, D, A)不是X的子序例公共子序列 – Z是序列X与Y的公共子序列如果Z是X的子序也是Y的子序列。最长公共子序列（LCS）问题输入：X = (x1,x2,…,xn)，Y = (y1,y2,…ym) 输出：Z = X与Y的最长公共子序列蛮力法： - 枚举X的

2017-04-22 16:22:32 1036

原创 Leetcode -- 35. Search Insert Position

题目：Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

2017-04-22 14:17:16 518

原创阿里巴巴测试题 -- 取石子问题

题目：有n个石子（n<＝100），A、B双方轮流选取，每次取走若干个石子，取走最后一个石子的一方获胜。要求：第一次不能全部取完；各方每次选取的石子数不能为0，也不能超过上次对方选择的石子数。问：如果A先取，那么第一次应该选几个才能保证获胜？如果第一次有多种策略，则输出石子数最多的一种

2017-04-22 09:16:58 1867

原创 Leetcode -- 34. Search for a Range

题目：Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.Your algorithm’s runtime complexity must be in the order of O(log n).If the target

2017-04-21 19:56:51 336

原创 Leetcode -- 33. Search in Rotated Sorted Array

题目：Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).You are given a target value to search. If found in the

2017-04-21 17:53:52 169

原创 Leetcode -- 31. Next Permutation

题目：Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.If such arrangement is not possible, it must rearrange it as the lowest possible o

2017-04-21 15:52:30 178

原创 Leetcode -- 29. Divide Two Integers

题目：Divide two integers without using multiplication, division and mod operator.If it is overflow, return MAX_INT.思路：不用乘法，除法和取模运算实现两个数的除法。注意考虑边界，如果divisor = -1, dividend = INT_MIN这时候会产生溢出，直接返回INT_MAX。

2017-04-21 09:46:21 177

原创 Leetcode -- 28. Implement strStr()

题目：Implement strStr().Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.思路：本题是让找到一个字符串是不是另一个字符串的子串，如果是就返回下标，如果不是返回-1。暴力比较，时间复杂度：O(mn)。C++代码如下：int

2017-04-21 08:52:01 229

原创 Leetcode -- 27. Remove Element

题目：Given an array and a value, remove all instances of that value in place and return the new length.Do not allocate extra space for another array, you must do this in place with constant memory.The or

2017-04-21 00:25:43 159

原创 Leetcode -- 26. Remove Duplicates from Sorted Array

题目：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 c

2017-04-21 00:03:20 180

原创 Leetcode -- 24. Swap Nodes in Pairs

题目：Given a linked list, swap every two adjacent nodes and return its head.For example,Given 1->2->3->4, you should return the list as 2->1->4->3.Your algorithm should use only constant space. You may n

2017-04-20 23:29:47 197

原创 Leetcode -- 22. Generate Parentheses

题目：Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is:[ "((()))", "(()())", "(())()", "()(())",

2017-04-18 09:33:53 182

原创 Leetcode -- 21. Merge Two Sorted Lists

题目：Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.思路：本题考查基础的链表操作。因为两个链表l1和l2已经有序，所以只需要按顺序比较即可，把较小的结点插入到新的

2017-04-16 23:46:51 218

哈工大计算机设计与实践 cpu设计

空空如也