leetCode 编程笔记

问：编写一个函数来查找字符串数组的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

示例输入：["flower", "flow", "flight"]

示例输出："fl"

示例输入：["dog", "racecar", "car"]

示例输出：""

解释：输入不存在公共前缀。

tips：所有的输入只包含小写字母 a-z 。

public class Solution { // 1. Method 1, start from the first one, compare prefix with next string, until end; // 2. Method 2, start from the first char, compare it with all string, and then the second char // I am using method 1 here public String longestCommonPrefix(String[] strs) { if (strs == null || strs.length == 0) { return ""; } String prefix = strs[0]; for(int i = 1; i < strs.length; i++) { int j = 0; while( j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) { j++; } if( j == 0) { return ""; } prefix = prefix.substring(0, j); } return prefix; } } 

有一个X x Y的网格，只能向右、向下移动，从(0, 0)走到(X - 1, Y - 1)，中间某些位置有障碍物，打印一条路径（优化）

答：解题思路。

计算过程：

1. 把底边和右边的每个格子标记为1
2. 其余格子从右下角往右上角依次遍历
3. 每个格子的值是其右边和下边格子值的和
4. 遍历到右上角后求得最终结果

例如上图的结果为10。

这种解法依据的思路，由于每个格子只能向右或向下走，那么它的走法就由其右边格子的走法和下边格子的走法之和。而最下边和最右边的每个格子都只有唯一的走法。由此就能推导出其余格子的走法。

tips：注意把握思想，把右下角右边和底部的边都设置为 1.之后向上推倒即可。最终结果是 10.

归并排序：

//将有序数组a[]和b[]合并到c[]中 void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } // 当其中一个列表的所有数据都比另一个列表的所有数据小的时候，例如 i = n，j = 0； while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; } 

tips：

解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

构建 Hash 表的时候（散列函数的设计）

f( key ) = key mod p ( p ≤ m ) mod ... 使用除留余数法的一个经验是，若散列表表长为m，通常p为小于或等于表

如何合理选取p值

使用除留余数法的一个经验是，若散列表表长为m，通常p为小于或等于表长（最好接近m)的最小质数或不包含小于20质因子的合数。

• 这句话怎么理解呢？要不这样吧，我再举个例子：某散列表的长度为100，散列函数H(k)=k%P,则P通常情况下最好选择哪个呢？A、91 B、93 C、97 D、99

• 实践证明，当P取小于哈希表长的最大质数时，产生的哈希函数较好。我选97，因为它是离长度值最近的最大质数。

可以盛最多水的容器

解法：我们可以循环遍历所有的两天边的乘积，取最大的值。

编程试题：求数列的和 使用语言：JAVA 参考正解代码如下： import java.util.*; class Main{ public static void main(String args[]){ int m; double sum,n; Scanner sc = new Scanner(System.in); while(sc.hasNext()){ n=sc.nextInt(); m=sc.nextInt(); sum=0; for(int i=0;i<m;i++){ sum=sum+n; n=Math.sqrt(n); } System.out.printf("%.2f",sum); System.out.println(); } } } 使用语言：C++ 参考正解代码如下： #include <math.h> #include <stdio.h> int main() { int n; double x, s; while (~scanf("%lf%d", &x, &n)) { for(s = 0.0; n--; x = sqrt(x)) s += x; printf("%.2lf\n", s); } return 0; } 使用语言：C# 参考正解代码如下： using System; namespace myApp { class Program { public static void Main() { string line; string[] p; int m, n; double nn; while (!string.IsNullOrEmpty(line = Console.ReadLine())) { p = line.Split(' '); n = int.Parse(p[0]); m = int.Parse(p[1]); double sum = 0; nn = n; for (int i = 0; i < m; i++) { sum = sum + nn; nn = Math.Sqrt(nn); } Console.WriteLine(string.Format("{0:f}", sum)); } } } } 使用语言：JavaScript 参考正解代码如下： var m; var sum,n; var sc while(sc = read_line()){ var arr = sc.split(' '); n=parseInt(arr[0]); m=parseInt(arr[1]); sum=0; for(var i=0;i<m;i++){ sum=sum+n; n=Math.sqrt(n); } print(sum.toFixed(2)); } 

注意上面的三个代码有几点注意：

一：JavaScript 的输入和输出为 sc = read——line() 输出：print(); 精确到后两位：sum.toFixed(2)

二：C / C++ 精确到两位小数为：printf("%.2lf\n", s);

三：Java编写程序的时候精确到小数点后两位的写法：System.out.printf("%.2f",sum);

水仙花的求解

编程试题：水仙花 使用语言：JAVA 参考正解代码如下： import java.util.Scanner; public class Main{ public static void main(String args[]){ Scanner reader=new Scanner(System.in); while(reader.hasNextInt()){ int m=reader.nextInt(); int n=reader.nextInt(); if(100<=m&&m<=n&&n<=999){ int j=0; for(int i=m;i<=n;i++) { int geWei,shiWei,baiWei; baiWei=i/100; shiWei=(i-baiWei*100)/10; geWei=i-baiWei*100-shiWei*10; if(i==geWei*geWei*geWei+shiWei*shiWei*shiWei+baiWei*baiWei*baiWei) {j=j+1; if(j>1){ System.out.print(" "+i); } else{ System.out.print(i); } } } if(j==0){ System.out.print("no"); } System.out.println(); } } } } 使用语言：C++ 参考正解代码如下： #include<stdio.h> int main(){ int m,n; while(scanf("%d%d",&m,&n)!=EOF){ int t=0; for(int i=m; i<=n; i++){ int a=i/100; int b=i%100/10; int c=i%10; if(i==a*a*a+b*b*b+c*c*c && t==0){ printf("%d ",i); t++; } else if(i==a*a*a+b*b*b+c*c*c && t==1){ printf("%d ",i); } } if(t!=0){ printf("\n"); } if(t==0){ printf("no\n"); } } return 0; } 使用语言：C# 参考正解代码如下： using System; namespace myApp { class Program { public static void Main() { string line; string[] p; int m, n; while ((line = Console.ReadLine()) != null) { p = line.Split(' '); n = int.Parse(p[1]); m = int.Parse(p[0]); var j=0; for(var i=m;i<=n;i++) { int geWei,shiWei,baiWei; baiWei = (i/100); shiWei = ((i-baiWei*100)/10); geWei = i-baiWei*100-shiWei*10; if(i==geWei*geWei*geWei+shiWei*shiWei*shiWei+baiWei*baiWei*baiWei) { j=j+1; if(j>1) { Console.Write(" "+i); } else { Console.Write(i); } } } if(j==0) { Console.Write("no"); } Console.Write("\r\n"); } } } } 使用语言：JavaScript 参考正解代码如下： var sc; while(sc = read_line()){ var arr = sc.split(' '); n=parseInt(arr[1]); m=parseInt(arr[0]); if(100<=m&&m<=n&&n<=999){ var out = []; var j=0; for(var i=m;i<=n;i++) { var geWei,shiWei,baiWei; baiWei=parseInt(i/100); shiWei=parseInt((i-baiWei*100)/10); geWei=i-baiWei*100-shiWei*10; if(i==geWei*geWei*geWei+shiWei*shiWei*shiWei+baiWei*baiWei*baiWei) { j=j+1; if(j>1){ out.push(" "+i); } else{ out.push(i); } } } if(j==0){ out.push("no"); } print(out.join('')); } }