三天没有写题了，罪过！--Hash Table Start
（1）Island Perimeter
解题思路：
在矩阵上循环并记录岛(1)的个数;如果当前节点是岛，则检查其是否具有任何右邻居或下邻居，有的话邻居计数加1 ;岛的周长结果为islands * 4 - neighbors * 2.(乘2的原因是因为一条边属于两个邻居）。
代码如下：
public class Solution {
public int islandPerimeter(int[][] grid) {
int islands = 0;
int neighbours =0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
islands++;
if (i < grid.length - 1 && grid[i+1][j] == 1) neighbours++;
if (j < grid[0].length - 1 && grid[i][j+1] == 1) neighbours++;
}
}
}
return islands * 4 - neighbours * 2;
}
}
代码中if(j<grid[i].length&&。。。）要注意！！！
（2）Single Number
解题思路：
在java程序里面的异或用法： 相同输出0，不同输出1。
例如： System.out.println(1^1); 输出0 System.out.println(1^2)；输出3，因为最后2个低位都不一样，所以输出3 。
异域的概念是相同为0不同为1.如果两个数值异或后的值相同，异或前可能不同。 比如二进制：0010^0001=0011 而0000^0011=0011。 异或要慎用。
使用异或运算上述两个性质来解本题：自己与自己异或结果为0；异或满足交换律。
代码如下：
public class Solution {
public int singleNumber(int[] nums) {
if(nums == null || nums.length == 0) {
return -1;
}
int rst = 0;
for (int i = 0; i < nums.length; i++) {
rst ^= nums[i];
}
return rst;
}
}
（3）Find the Difference
最优解题思路：依旧是使用异或运算，除了字符串t中的多余字符外，其余字符都可以在异或运算中消除掉。
代码如下：
public class Solution {
public char findTheDifference(String s, String t) {
char rst = 0x00;
for (int i = 0; i < s.length(); i++) {
rst = (char)(rst ^ s.charAt(i));
}
for (int i = 0; i < t.length(); i++) {
rst = (char)(rst ^ t.charAt(i));
}
return rst;
}
}
注意字符串的长度s.length(),取某个字符s.charAt(i)的使用。
正常思路：用两个计数数组统计s和t的字母出现次数，不一样的那个就是答案。
代码如下：
public char findTheDifference(String s, String t) {
int count1[] = new int[26];
int count2[] = new int[26];
int i;
for (i = 0; i < s.length(); i++) {
count1[s.charAt(i)-'a']++;
}
for (i = 0; i < t.length(); i++) {
count2[t.charAt(i)-'a']++;
}
for (i = 0; i < 26; i++) {
if (count1[i] != count2[i])
return (char) ('a' + i);
}
return 0;
}
（4）Intersection of Two Arrays
解题思路一：
不能有重复数字，就想到使用数据类型Set。
逻辑原理： 数组一的数据存入hashset；遍历数组二如果set中存在该数据存入新的hashset中，同时从set中remove该元素，防止多个元素重复；遍历新hashset转变为array返回数据。
代码如下：
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);
}
Set<Integer> insertset = new HashSet<>();
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i])) {
insertset.add(nums2[i]);
set.remove(nums2[i]);//防止元素重复
}
}
//变为数组返回
int[] array = new int[insertset.size()];
int index = 0;
for (Integer num : insertset) {
array[index++] = num;
}
return array;
}
}
解题思路二：
1）对数组nums1进行排序；
2）对数组nums2进行排序；
3）遍历数组nums1和nums2中元素，并比较对应的元素，
- 若相等，则判断其值是否与结果中最后保存的元素（用mark记录）是否相等，相等则直接变化两个索引，否则将该值保存到结果中，并变化两个索引
- 不等，则变化较小元素对应的索引即可。
代码如下：
public int[] intersection(int[] nums1, int[] nums2){
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList result = new ArrayList();
int mark = 0;
for (int i = 0, j = 0; i < nums1.length && j < nums2.length; ){
if (nums1[i] == nums2[j]){
if (result.size() == 0 || nums1[i] != mark){
result.add(nums1[i]);
mark = nums1[i];
}
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else {
j++;
}
}
int[] res = new int[result.size()];
for (int i = 0; i < result.size(); i++){
res[i] = (int) result.get(i);//字符类型转换
}
return res;
}
最新文章
- ssh 公钥登陆的问题
- 2-2 Linux 根文件系统详解
- 微信小程序里碰到的坑和小知识
- 第九天 内容提供者 ContentResolver
- python递归次数和堆栈溢出问题
- JVM内存溢出及合理配置
- 嵌入式linux驱动开发之点亮led（驱动编程思想之初体验）
- codevs 5429 完全背包
- POJ 2376 Cleaning Shifts 贪心
- Jquery 中 $('obj').attr('checked',true)失效的几种解决方案
- web api简单验证实现办法
- Unity入门
- 《mysql必知必会》读书笔记--存储过程的使用
- JSP自定义标签必知必会
- java 基础03 继承
- HttpServletResponse实现文件下载
- python虚拟环境创建
- VMware虚拟机安装ghost win7系统方法
- Xamarin.Forms第三方XAML预览工具-LiveXAML简单体验
- 【C#】Config配置文件的读写，及无法写入/保存配置文件的问题