1.多数元素
1.多数元素
解题思路：
运用hashMap来解决此题；
1.遍历数组，如果hashMap当中存在此下标元素，就直接将value++;
2.如果不存在此下标元素，就将此元素放入hashMap当中；
3.当首次放入hashMap的时候，也要取出对应的value值，看是否 大于 一般的数组长度；这种情况针对于，数组中只有一个元素时，所以，返回的也是这个元素；
4.当hashMap中已经存在此元素的情况，查出此元素对应的value值，然后判断是否大于 一半的数组长度，如果大于，记录元素，跳出循环，返回此元素。
class Solution {
public int majorityElement(int[] nums) {
int result=0;
HashMap<Integer,Integer> hashMap=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(!hashMap.containsKey(nums[i])){
hashMap.put(nums[i],1);
int ret=hashMap.get(nums[i]);
if(ret>(nums.length/2)){
result=nums[i];
break;
}
}else{
hashMap.put(nums[i],hashMap.get(nums[i])+1);
int ret=hashMap.get(nums[i]);
if(ret>(nums.length/2)){
result=nums[i];
break;
}
}
}
return result;
}
}
2.Excel表列序号
2.Excel表列序号
解题思路：
将字符串转为字符数组；
遍历字符数组；
如果只有一位，就直接算与 A的差+1；eg:C==>‘C’-‘A’+1=3;
如果有两位:eg:ZY: ‘Z’-‘A’+1===>26; 26*26+’Y’-‘A’+1=701;
class Solution {
public static int titleToNumber(String columnTitle) {
char[] arr=columnTitle.toCharArray();
int result=0;
for(int i=0;i<arr.length;i++){
result=result*26+arr[i]-'A'+1;
}
return result;
}
}
3.颠倒二进制位
3.颠倒二进制位
解题思路：
主要是依据 按位与 来解此题目；
拿n的末位与1按位与，结果放在result当中，从末位开始放，这样，等经过了32次循环后，result的头就是n的尾，n的头就是result的尾部。
public class Solution {
// you need treat n as an unsigned value
public static int reverseBits(int n) {
int result=0;
for(int i=0;i<32;i++){
//先将result左移一位，用来放 n 与 1 按位与的结果
//经过32次遍历之后，result的头就会变成n的结尾
result=result<<1;
if((n &1)==1){
result+=1;
}
//当n与1 按位与，其实是 n的末位与1按位与，所以，每经过一次循环，n就要右移一位
n=n>>1;
}
return result;
}
}
4.位1的个数
4.位1的个数
解题思路：
也是运用了 按位与的思想
与上一题思路类似。
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int result=0;
for(int i=0;i<32;i++){
if((n&1)==1){
result++;
}
n=n>>1;
}
return result;
}
}
5.快乐数
5.快乐数
解题思路：
这个题需要做两步：
1.首先需要 将n变为n的平方数；
2.其次，判断此时的n 是否为1；
如果n为1，就证明这个数字是快乐数字；
如果n不为1，就加入hashSet当中，如果hashSet当中已经存在这个n，就证明 进入了无限循环，此时，这个数字就不是快乐数。
import java.util.HashSet;
class Solution {
public static int add(int n){
int result=0;
while(n>0){
int ret=n%10;
result+=Math.pow(ret,2);
n=n/10;
}
return result;
}
public static boolean isHappy(int n) {
HashSet<Integer> hashSet=new HashSet<>();
while(n!=1){
n=add(n);
if(!hashSet.add(n)){
return false;
}
}
return true;
}
}
6.回文链表
6.回文链表
解题思路：
回文特点：正着读 的结果 等于 反着读 的结果；
遍历整个链表，将链表每个节点的值，放在stringBuilder字符串当中，然后再将 这个字符串 和反转之后的字符串 相比较，看是否相等。
class Solution {
public boolean isPalindrome(ListNode head) {
StringBuilder stringBuilder=new StringBuilder();
ListNode temp=head;
while(temp!=null){
stringBuilder.append(temp.val);
temp=temp.next;
}
if(stringBuilder.toString().equals(stringBuilder.reverse().toString())){
return true;
}
return false;
}
}
7.删除链表中的节点
7.删除链表中的节点
解题思路：
一般链表删除，都是需要知道当前节点，以及当前节点的上一个节点，要删除当前节点，需要做的是：让当前节点的上一个节点指向当前节点的下一个节点。
而此题目，没有告诉我们 链表的头节点，我们无法知道 当前待删除节点的上一个节点是什么。
所以，我们需要换种思路，
让待删除节点的下一个节点的只覆盖当前节点的值，此时，当前节点的值已经更新为下一个节点的值，此时，让当前节点指向下一个节点的下一个节点。
说的更简单一点就是：让下一个节点值覆盖当前节点，删除下一个节点。
class Solution {
public void deleteNode(ListNode node) {
//如果此时这个node是尾节点，此时就不能删除这个节点
if(node.next==null){
return;
}
node.val=node.next.val;
node.next=node.next.next;
}
}
8.有效的字母异位词
8.有效的字母异位词
解题思路：
利用hash表来完成此题
首先，将字符串s放入hashMap当中；
然后，遍历字符串t,如果hashMap当中存在t中的字符，便把hashMap对应的value减一，如果hashMap存在t中的字符，且对应的value值为1，就把这个字符从hashMap中移掉，如果hashMap当中不存在t中的字符，就直接返回false;
最后，判断hashMap是否为空，空，返回true;
如果不为空，返回false.
class Solution {
public static boolean isAnagram(String s, String t) {
char[] ss=s.toCharArray();
char[] tt=t.toCharArray();
HashMap<Character,Integer> hashMap=new HashMap<>();
for(int i=0;i<ss.length;i++){
if(!hashMap.containsKey(ss[i])){
hashMap.put(ss[i],1);
}else{
hashMap.put(ss[i],hashMap.get(ss[i])+1);
}
}
for(int j=0;j<tt.length;j++){
if(hashMap.containsKey(tt[j])&& hashMap.get(tt[j])==1){
hashMap.remove(tt[j]);
}else if(!hashMap.containsKey(tt[j])){
return false;
}else if(hashMap.containsKey(tt[j])){
hashMap.put(tt[j],hashMap.get(tt[j])-1);
}
}
if(hashMap.isEmpty()){
return true;
}
return false;
}
}
9.丢失的数字
9.丢失的数字
解题思路：
将数组进行排序；
循环遍历数组，数字的范围是[0,nums.length];
遍历数组，看下标是否等于相对应的数组元素；
如果退出了循环，还没有返回数字，就证明，这个丢失的长度是数组长度。
class Solution {
public int missingNumber(int[] nums) {
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
if(nums[i]!=i){
return i;
}
}
return nums.length;
}
}
10.移动零
10.移动零
解题思路：
这个题需要在原来的数组上操作；
主要的思路是：遍历数组，如果遇见了数组中的第一个0，记录下位置，继续遍历后面的，后面的如果出现了不为0的元素，就将这个不为0的元素和之前记录下第一个零交换位置，然后再更新第一个零的位置。
class Solution {
public static void moveZeroes(int[] nums) {
int first=-1;
for(int i=0;i<nums.length;i++){
if(nums[i]!=0){
if(first!=-1){
int temp=nums[first];
nums[first]=nums[i];
nums[i]=temp;
first++;
}
}else{
if(first==-1){
first=i;
}
}
}
}
}