1.二進(jìn)制中1的個數(shù)
輸入一個整數(shù)捌朴，輸出該數(shù)二進(jìn)制表示中1的個數(shù)洽损。其中負(fù)數(shù)用補(bǔ)碼表示庞溜。
思路：我的思路就是使用先使用Integer的toBinaryString方法將該數(shù)轉(zhuǎn)換成二進(jìn)制形式的字符串，然后統(tǒng)計(jì)1的個數(shù)。
public class Solution {
public int NumberOf1(int n) {
int count = 0;
String result = Integer.toBinaryString(n);
for(int i = 0; i < result.length(); i++) {
if(result.charAt(i) == '1') {
count++;
}
}
return count;
}
}
另一種更好的解法：位運(yùn)算符&流码，|又官，~等是針對二進(jìn)制的。所以我們可以使用&求解本題漫试。一個數(shù)如果不為0六敬，則它表示的二進(jìn)制必定帶有1，當(dāng)它減1的時候驾荣，其最低位的1必定會變成0外构，其后的0必定全部變成1，如1100播掷，減1审编，第三位變成了0，后面的兩個0 都變成1歧匈，就變成了1011垒酬，而1100 & 1011 = 1000，也就是說每次這個數(shù)和比它小1的數(shù)進(jìn)行&運(yùn)算件炉，都會消去一個1勘究，基于此，可以得到下面的解法斟冕。
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
}
2.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)的前面
輸入一個整數(shù)數(shù)組口糕，實(shí)現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分宫静，所有的偶數(shù)位于數(shù)組的后半部分走净，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對位置不變孤里。
思路：直接使用有個linkedList作為額外空間伏伯，然后把數(shù)組的奇數(shù)插入前半部分，偶數(shù)插入后半部分捌袜。
import java.util.LinkedList;
public class Solution {
public void reOrderArray(int [] array) {
LinkedList<Integer> t = new LinkedList<>();
int index = 0;
for(int i = 0; i < array.length; i++) {
// 如果是奇數(shù)说搅，則從list的第一個位置開始插，每次插入之后就記錄下該元素的下一個位置虏等，
// 當(dāng)?shù)诙€奇數(shù)來的時候弄唧，插入第一個奇數(shù)的后面
if(array[i] % 2 != 0) {
t.add(index, array[i]);
index = t.indexOf(array[i]) + 1;
} else {
// 偶數(shù)直接從list的最后面開始插入
t.add(t.size(), array[i]);
}
}
for(int i = 0; i < t.size(); i++) {
array[i] = t.get(i);
}
}
}
不使用額外的空間求解，使用類似于冒泡的思想霍衫，每次循環(huán)把一個偶數(shù)移動到數(shù)組的最后
public class Solution {
public void reOrderArray(int [] array) {
// 類似于冒泡的思想候引，每次把一個偶數(shù)移動到最末尾
for(int i = 0; i < array.length - 1; i++) {
for(int j = 0; j < array.length - i - 1; j++) {
if(array[j] % 2 == 0 && array[j + 1] % 2 != 0) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}
3.鏈表中倒數(shù)第k個節(jié)點(diǎn)
輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點(diǎn)敦跌。
思路1：首先遍歷一遍鏈表澄干，得到鏈表的長度len，則len - k就是倒數(shù)第k個節(jié)點(diǎn)
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
int len = 0;
ListNode t = head;
// 先求出鏈表的長度
while(t != null) {
len++;
t = t.next;
}
if(k > len) {
return null;
}
// 倒數(shù)第k個節(jié)點(diǎn)就是鏈表的長度減k位置處的節(jié)點(diǎn)
for(int i = 0; i <= len - k; i++) {
if(i == len - k) {
return head;
} else {
head = head.next;
}
}
return null;
}
}
思路2：使用兩個指針，第一個指針先移動k個位置麸俘，之后兩個指針一起移動辩稽，當(dāng)?shù)谝粋€指針移動到鏈表尾部的時候，第二個指針?biāo)赶虻脑鼐褪堑箶?shù)第k個元素
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode node1 = head;
ListNode node2 = head;
// 第一個指針先移動k個位置
while(k > 0) {
if(node1 != null) {
node1 = node1.next;
k--;
} else {
return null;
}
}
// 兩個指針一起移動从媚，當(dāng)?shù)谝粋€指針到底鏈表尾部的時候逞泄，第二個指針?biāo)赶虻脑鼐褪堑箶?shù)第k個元素
while(node1 != null) {
node1 = node1.next;
node2 = node2.next;
}
return node2;
}
}
4.反轉(zhuǎn)鏈表
輸入一個鏈表，反轉(zhuǎn)鏈表后拜效，輸出新鏈表的表頭喷众。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
// 如果是空鏈表，則返回null
if(head == null) {
return null;
}
// 用來存放反轉(zhuǎn)好的節(jié)點(diǎn)
ListNode pre = null;
// 用于存放當(dāng)前節(jié)點(diǎn)后面的節(jié)點(diǎn)
ListNode next = null;
while(head != null) {
// 保存當(dāng)前節(jié)點(diǎn)后面的節(jié)點(diǎn)拂檩，不然反轉(zhuǎn)后,后面的節(jié)點(diǎn)會丟失
next = head.next;
// 改變當(dāng)前節(jié)點(diǎn)鏈表的指向
head.next = pre;
// 把反轉(zhuǎn)部分賦值給pre
pre = head;
// 把當(dāng)前節(jié)點(diǎn)后面的節(jié)點(diǎn)賦值后head侮腹。進(jìn)行下一輪的遍歷
head = next;
}
return pre;
}
}
5.合并兩個排序的列表
輸入兩個單調(diào)遞增的鏈表嘲碧，輸出兩個鏈表合成后的鏈表稻励，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null) {
return list2;
}
if(list2 == null) {
return list1;
}
ListNode result = null;
ListNode r = null;
while(list1 != null && list2 != null) {
// 如果第二個鏈表的當(dāng)前值更小
if(list1.val >= list2.val) {
// 如果是第一次進(jìn)行賦值愈涩，則把更小的賦值給r望抽，并建立r和result的聯(lián)系
if(r == null) {
r = list2;
result = r;
} else {
r.next = list2;
r = r.next;
}
list2 = list2.next;
} else {
if(r == null) {
r = list1;
result = r;
} else {
r.next = list1;
r = r.next;
}
list1 = list1.next;
}
}
// 如果list1鏈表還有余下的節(jié)點(diǎn)，則直接進(jìn)行賦值
if(list1 == null) {
r.next = list2;
}
// 如果list2鏈表還有余下的節(jié)點(diǎn)履婉，則直接進(jìn)行賦值
if(list2 == null) {
r.next = list1;
}
return result;
}
}
6.樹的子結(jié)構(gòu)
輸入兩棵二叉樹A煤篙，B，判斷B是不是A的子結(jié)構(gòu)毁腿。（ps：我們約定空樹不是任意一個樹的子結(jié)構(gòu)）
思路：看到樹就有點(diǎn)懵逼辑奈，還有遞歸，看來要勤加練習(xí)樹這一塊已烤。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public static boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;
// 兩棵樹不為空則進(jìn)行遍歷鸠窗，否則直接返回false
if(root2 != null && root1 != null) {
// 如果當(dāng)前節(jié)點(diǎn)的值相等，則以當(dāng)前節(jié)點(diǎn)為起點(diǎn)胯究，繼續(xù)遍歷
if(root1.val == root2.val) {
result = doesRoot1HasRoot2(root1, root2);
}
// 如果找不到稍计，則以root1的左子樹為起點(diǎn)，繼續(xù)尋找root2
if(!result) {
result = HasSubtree(root1.left, root2);
}
// 如果還沒有找到裕循，則以root1的右子樹為起點(diǎn)臣嚣，繼續(xù)尋找root2
if(!result) {
result = HasSubtree(root1.right, root2);
}
}
return result;
}
public static boolean doesRoot1HasRoot2(TreeNode root1, TreeNode root2) {
// 如果root2先為空，則說明root2是root1的子樹剥哑，返回true
if(root2 == null) {
return true;
}
// 如果root1先為空硅则，則說明root2不是root1的子樹，返回false
if(root1 == null) {
return false;
}
// 如果當(dāng)前節(jié)點(diǎn)的值不相等株婴，返回false
if(root1.val != root2.val) {
return false;
}
return doesRoot1HasRoot2(root1.left, root2.left) && doesRoot1HasRoot2(root1.right, root2.right);
}
}
7.二叉樹的鏡像
操作給定的二叉樹怎虫，將其變換為源二叉樹的鏡像。
輸入描述
二叉樹的鏡像定義：源二叉樹
8
/
6 10
/ \ /
5 7 9 11
鏡像二叉樹
8
/
10 6
/ \ /
11 9 7 5
思路：直接用遞歸即可
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
Mirror(root.left);
Mirror(root.right);
}
}
8.順時針打印矩陣
輸入一個矩陣，按照從外向里以順時針的順序依次打印出每一個數(shù)字揪垄，例如穷吮，如果輸入如下4 X 4矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
思路：首先打印矩陣的第一行元素，然后把剩下的矩陣逆時針旋轉(zhuǎn)90度饥努，繼續(xù)打印矩陣的第一行元素捡鱼，直到矩陣為空。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
ArrayList<Integer> result = new ArrayList<>();
if(matrix == null) {
return result;
}
// 行的數(shù)量
int m = matrix.length;
int n = 0;
if(m > 0) {
// 列的數(shù)量
n = matrix[0].length;
}
for(int i = 0; i < n; i++) {
// 把當(dāng)前矩陣的第一行加入list
result.add(matrix[0][i]);
}
// 如果行的長度已經(jīng)等于1酷愧，則說明矩陣已經(jīng)遍歷完畢驾诈，直接輸出
if(m == 1) {
return result;
} else {
// 把當(dāng)前矩陣的第一行去掉
int[][] temp = new int[m - 1][n];
for(int i = 1; i < m; i++) {
for(int j = 0; j < n; j++) {
temp[i - 1][j] = matrix[i][j];
}
}
// 逆時針旋轉(zhuǎn)90當(dāng)前矩陣
result.addAll(printMatrix(rotateMatrix(temp, m - 1, n)));
}
return result;
}
// 將矩陣逆時針旋轉(zhuǎn)90度
public int[][] rotateMatrix(int[][] matrix, int m, int n) {
int[][] rmatrix = new int[n][m];
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
rmatrix[i][j] = matrix[j][n - i - 1];
}
}
return rmatrix;
}
}
9.包含min函數(shù)的棧
定義棧的數(shù)據(jù)結(jié)構(gòu)，請?jiān)谠擃愋椭袑?shí)現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復(fù)雜度應(yīng)為O（1））溶浴。
import java.util.Stack;
import java.util.Iterator;
public class Solution {
Stack<Integer> stack = new Stack<>();
public void push(int node) {
stack.push(node);
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek();
}
public int min() {
Iterator<Integer> iterator = stack.iterator();
int min = stack.peek();
while(iterator.hasNext()) {
int t = iterator.next();
if(min > t) {
min = t;
}
}
return min;
}
}
10.棧的壓入乍迄、彈出序列
輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序士败，請判斷第二個序列是否可能為該棧的彈出順序闯两。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序谅将，序列4,5,3,2,1是該壓棧序列對應(yīng)的一個彈出序列漾狼，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。（注意：這兩個序列的長度是相等的）
思路：首先遍歷壓入序列饥臂，遇到和彈出序列不一樣的元素逊躁，則放入一個list中，遍歷完壓入序列后隅熙，若彈出序列還沒遍歷完稽煤，則反向遍歷list，繼續(xù)和彈出序列比較囚戚，如果有任何一個不相等酵熙，則返回false。
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length != popA.length) {
return false;
}
ArrayList<Integer> result = new ArrayList<>();
int count = 0;
for(int i = 0; i < pushA.length; i++) {
if(pushA[i] == popA[count]) {
count++;
} else {
result.add(pushA[i]);
}
}
if(count != popA.length) {
for(int i = result.size() - 1; i >= 0; i--) {
if(result.get(i) != popA[count]) {
return false;
} else {
count++;
}
}
}
return true;
}
}
