AlgorithmLearning

算法與數據結構練習

Java IT名企算法與數據結構題目最優解

1.棧和隊列

• 設計一個有getMin功能的棧
• 由兩個棧堆成的隊列
• 如何引用遞歸函數和棧操作逆序一個棧
• 貓狗隊列
• 用一個棧實現另一個棧的排序
• 求解漢諾塔問題,先修改一下游戲規則:線則限制不能從最左側直接移到最右側也不能從最右側直接移到最左側,而是必須經過中間.求當塔又N層時,最優移動過程和總步數
• 生成窗口最大值數組
• 構造數據的MaxTree
• 給定一個整形矩陣map,其中的值有0和1兩種,求其中全是1的所有矩陣區域中,最大的矩形區域為1的數量
• 最大值減去最少值小於或等於num的子數組數量

2.鍊錶問題

• 給定兩個有序鍊錶的頭指針head1 和head2 打印兩個鍊錶的公共部分
• 在單鍊錶和雙鍊錶中刪除倒數第k個節點
• 刪除鍊錶中間節點和a/b 處的節點
• 分別實現反轉單向鍊錶和反轉雙向鍊錶的函數
• 反轉部分單向鍊錶
• 環形單鍊錶的亞瑟夫問題
• 判斷一個鍊錶是否為回文結構
• 將單向鍊錶按某值劃分成左邊小中間相等右邊大得形式
• 複製含有隨機指針節點的鍊錶
• 兩個單鍊錶生成相加鍊錶
• 兩個鍊錶相交的一系列問題
• 將單鍊錶的每k個節點之間逆序
• 刪除無序單鍊錶中值重複出現的節點
• 在單鍊錶中刪除指定值得節點
• 將搜索二叉樹轉換成雙向鍊錶
• 單鍊錶的選擇排序
• 一種怪異的節點刪除方式
• 向有序的環形單鍊錶中插入新節點
• 合併兩個有序的單鍊錶
• 按照左右半區的方式重組單鍊錶

二叉樹問題

• 分別用遞歸和非遞歸方式實現二叉樹先序,中序和後序遍歷
• 打印二叉樹的邊界節點
• 如何較為直觀地打印二叉樹
• 二叉樹得序列化和反序列化
• 遍歷二叉樹的神級方法
• 在二叉樹中找到累加和為指定值的最長路徑長度
• 找到二叉樹中的最大搜索二叉子樹
• 找到二叉樹中符合搜索二叉樹條件的最大拓撲結構
• 二叉樹的按層打印與ZigZag打印
• 調整搜索二叉樹中兩個錯誤的節點
• 判斷t1樹是否包含t2樹全部的拓撲結構
• 判斷t1樹中是否有與t2樹拓撲結構完全相同的子樹
• 判斷二叉樹是否為平衡二叉樹
• 根據後序數組重建搜索二叉樹
• 判斷一棵二叉樹是否為搜索二叉樹和完全二叉樹
• 通過有序數組生成平衡搜索二叉樹
• 在二叉樹中找到一個節點的後繼節點
• 在二叉樹中找到兩個節點的最近公共祖先
• Tarjan算法與並查集解決二叉樹節點間最近公共祖先得批量查詢問題
• 二叉樹節點間最大距離問題
• 先序、中序、後序數組兩兩結合重構二叉樹
• 通過先序和中序數組生成後序數組
• 統計和生成所有不同的二叉樹
• 統計完全二叉樹的節點數
• 最大遞增子序列

遞歸和動態規劃

• 斐波那契系列問題的遞歸和動態規劃
• 矩陣的最小路徑和
• 換錢的最少貨幣數
• 換錢的方法數
• 漢諾塔問題
• 最長公共子序列問題
• 最長公共字串問題
• 最小編輯代價
• 字符串的交錯組成
• 龍與地下城遊戲問題
• 數字字符串轉換為字母組合的種數
• 表達式得到期望結果的組成種數
• 排成一條線的紙牌博弈問題
• 跳躍遊戲
• 數組中的最長連續序列
• N皇后問題

字符串問題

• 判斷兩個字符串是否護衛變形詞
• 字符串中數字子串的求和
• 去掉字符串中連續出現k個0的子串
• 判斷兩個字符串是否互為旋轉詞
• 將整數字符串轉成整數值
• 替換字符串中連續出現的指定字符串
• 字符串的統計字符串
• 判斷字符數組中是否所有的字符都只出現過一次
• 在有序但含有空的數組中查找字符串
• 字符串的調整與替換
• 翻轉字符串
• 數組中兩個字符串的最小距離
• 添加最少字符使字符串整體都是回文字符串
• 根據字符串的有效性和最長有效長度
• 公式字符串求值
• 0左邊必有1的二進製字符串數量
• 拼接所有字符串產生字典順序最小的大寫字符串
• 找到字符串的最長無重複字符子串
• 找到被指的新類型字符
• 最小包含子串的長度
• 回文最少分割數
• 字符串匹配問題
• 字典樹(前綴樹)的實現

位運算

• 不用額外變量交換兩個數
• 不用任何比較判斷找出兩個數中比較大的數
• 只用位運算不用算術運算實現整數的加減乘除運算
• 整數的二進製表達中又多少個1ccc
• 在其它數都出現偶數次的數組中找到出現奇數次的數
• 在其他數都出現k次的數組中找到只出現一次的數

數組和矩陣問題

• 轉圈打印矩陣
• 將正方形矩陣順時針轉動90°
• “之”字形打印矩陣
• 找到無序數組中最小的k個數
• 需要排序的最短子數組長度
• 在數組中找到出現次數大於N/K的數
• 在行列都排好序的矩陣中找數
• 最長的可整合子數組得長度
• 不重複打印排序數組種相加和為給定值的所有二元組和三元組
• 未排序正數數組中累加和為給定值的最長子數組長度
• 未排序數組中累加和為給定值的最長子數組系列問題
• 未排序數組中累加和小於或等於給定值的最長子數組長度
• 自然數數組排序
• 奇數小標都是奇數或者偶數下標都是偶數
• 子數組累加和最大
• 子矩陣的最大累加和問題
• 在數組中找到一個局部最小的位置
• 數組中子數組的最大累乘積
• 打印N個數組整體最大的Top K
• 邊界都是1的最大正方形大小
• 不包含本位置值得累乘數組
• 數組的partition調整
• 求最短通路值
• 數組中未出現的最小正整數
• 數組排序之後相鄰數的最大差值9

練習

• 替換空格(劍指offer)
• 二維數組中的查找(劍指offer)
• 反轉鍊錶(劍指offer)
• 刪除鍊錶的重複節點(劍指offer)
• 旋轉數組的最小數字(劍指offer)
• 數組中重複的數字(劍指offer)
• 表示數值得字符串(劍指offer)