主页

选择排序(Selection Sort)

概念 选择排序是一种简单直观的排序算法,首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕. 顾名思意,就是直接从待排序数组里选择一个最小(或最大)的数字,每次都拿一个最小数字出来, 顺序放入新数组,直到全部拿完. 再简单点,对着一群数组说,你们谁最小出列,站到最后边,然后继续对剩余的无序数组说,你们谁最小出列,站到最后边,再继续刚才的操作,一直到最后一个,继续站到最后边,现在数组有序了. 优点 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行...

阅读更多

冒泡排序(Bubble Sort)

概念 冒泡排序是一种简单的排序算法.基本思想是迭代地对数列中的第一个元素到最后一个元素进行两两比较,当需要的时候交换这两个元素(位置).重复这个过程一直到所有元素都被排序到正确的位置上. 冒泡排序得名于较小的元素如同”气泡”一样逐渐漂浮到数列的顶端. 步骤 比较相邻的元素,如果第一个比第二个大1,就交换它们两个的位置. 对每一对相邻元素作进行同样的步骤,从开始第一对到结尾的最后一对这步做完后. 进行一轮的比较之后,最大的数会被不断交换到最后一位,这样最后一位数就是有序2的了. 针对所有的元素重复以上的步骤,直到所有的元素都被排好序. 举例 例 1 假定有一个数组[5, 7, 4, 10, 9],我们要把这个数组按从小到大排列 我们从第一个数开始,两个一组进...

阅读更多

希尔排序(Shell sort)

概念 将整个序列分割成若干小的子序列,再分别对子序列进行直接插入排序,使得原来序列成为基本有序。这样通过对较小的序列进行插入排序,然后对基本有序的数列进行插入排序,能够提高插入排序算法的效率。 希尔排序也是插入排序的一种,使用了分治的思想,让排序的时间复杂度较插入排序有大幅的提升,于是单独拿出来作为一章. 希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名. 步骤 先取一个正整数$d_1<n$,把所有序号相隔d1的数组元素放一组 组内进行直接插入排序 然后取$d_2<d_1$,重复上述分组和排序操作 直至$d_i=1$,即所有记录放进一个组中排序为止。 举例 例1 以n=10...

阅读更多

Algorithms(算法详解) 汉化项目

背景   在酷安闲逛时发现了这个应用.   Algorithms采用了动画演示的方式,向大家展示了算法的执行过程,通过精美的动画流程展示,帮助学习算法的人更加容易理解算法,加上我也正好在进行算法的学习,所以对这个应用的评价也相当高.   然而应用本身并没有提供中文版本,虽然在编程的学习中,我们都提倡直接使用英语进行学习,毕竟编程这个东西是外国人发明的,语法什么的都是为英语环境设计的,但是对于广大的初学者来说(包括我),直接面对英语环境,还是略显吃力,于是萌生了对其进行汉化的念头,既可以加深自己对算法的理解,也可以帮助到大家. 计划 Plan A 应用中有英文版的提供者,我认为作者应该是有针对国际化的设计,没有什么汉化可以比得上原生提供中文,于是我向开发者发送了邮件,希望向其提供...

阅读更多

80.Remove Duplicates from Sorted Array II(Medium)

Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice? 给定一个有序的整数数列,每个数最多只能出现两次,然后去除多余的数,把剩下的数排在原数组的前面,并返回新数列的长度   这虽然是个中等题,不过难度不大,唯一需要多考虑的就是在原数组前面排列新的数组 For example Given sorted array nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn...

阅读更多

500.Keyboard Row(Easy)

Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.   虽然还把键盘搬出来了,但是实际上只是搜索每一个String的字母是否在键盘的同一行出现,键盘的每一行只要用一个String代替就ok了,剩下的问题显然就简单了。 For example Input: [“Hello”, “Alaska”, “Dad”, “Peace”] Output: [“Alaska”, “Dad”] My Solution (Java) Version ...

阅读更多

374.Guess Number Higher or Lower(Easy)

We are playing the Guess Game. The game is as follows: I pick a number from 1 to n. You have to guess which number I picked. Every time you guess wrong, I’ll tell you whether the number is higher or lower. You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0): 我们来玩一个猜数游戏,游戏规则是这样的:我从1~n中选择一个数,你需要猜我选的数是哪一个,如果你猜错的...

阅读更多

121. Best Time to Buy and Sell Stock(Easy)

Say you have an array for which the i element is the price of a given stock on day i. 给定一个数组,其中第i个元素是第i天是这个股票的价格 If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),  design an algorithm to find the maximum profit. 如果你仅被允许交易一次(即买一支股票和卖一支股票),设计一个算法来找到最大的利润   这个题目有点绕,其实就是在一个数组中找到差值(利润...

阅读更多

283.Move Zeroes(Easy)

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 your function, nums should be [1, 3, 12, 0, 0]. 给定一个num数组,把数组中的0都移动到最后去 Note: 1.  You must do this in-place without making a copy of the array. ...

阅读更多

226.Invert Binary Tree(Easy)

Invert a binary tree. 反转二叉树   基本上二叉树的玩意儿用递归都能做 For example to My Solution (Java) Version 1  Time: 1ms:   简单地递归然后调换左右子树 /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ public class Solution {     public TreeNo...

阅读更多

9.Palindrome Number(Easy)

Determine whether an integer is a palindrome. Do this without extra space. 判断一个数是否为回文数,不要使用额外的空间   回文数就是顺序和倒叙写出来是同样的数的数,比如121,12321等 My Solution (Java) Version 1  Time: 195ms:   既然是顺序倒序都一样的话,那就构造倒序的数,如果和前面的数相等的话,那就是回文数咯,从前往后,最高位的变成新数的最低位,以此类推 public class Solution {     public boolean isPalindrome(int x) {         if(x<0)return false;     ...

阅读更多

264.Ugly Number II(Medium)

Write a program to find the n-th ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.  For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers. Note that 1 is typically treated as an ugly number.   题意就不翻译了,意思就是把丑数从小到大排列,输出制定位置的那个丑数是多少,按照上一题的那种朴素判断当然是行得通的,只要把1~n的数全...

阅读更多

263.Ugly Number(Easy)

Write a program to check whether a given number is an ugly number. Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.  For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7. Note that 1 is typically treated as an ugly number.   丑数就是分解因子之后只含有2,3,5的数就是丑数,题目是判断一个整数是不是丑数,简单到只有这一种解法,没有别的了 ...

阅读更多

217.Contains Duplicate(Easy)

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 distinct. 给定一个整数数组,如果数组里面有任意一个值至少出现两次及以上,则函数返回true,如果每个元素都不同则返回false My Solution (Java) Version 1  Time: 14ms:   第一次用到了set,好开心,然而并没有什么用,用list来...

阅读更多

28.Implement strStr()(Easy)

Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. 返回needle在haystack中第一次出现的位置的索引值,如果没有找到,就返回-1   就是寻常的字符串匹配搜索,应该因为是简单题,所以朴素的循环比较也能过,事实上应该要用KMP算法的 My Solution (Java) Version 1  Time: 7ms:   这就是一个典型的朴素的两重循环比较的算法,没有什么好说的 public class Solution {     public int strStr(Strin...

阅读更多